核心

1.判断不平衡的类型

平衡因子：α=左树高-右树高
调整依据：α 大于1 或小于-1 时说明树需要调整
LL 左树长上加长，右旋树根，记忆孤儿，先断后连
RR 右树高上又涨，左旋树根
LR 先左旋【左孩子】转化为LL
RL 先右旋【右孩子】转化为RR

2.删除：采用拿最小值代替根节点的方法

AVLTree.h

#pragma once

#include<algorithm>
#include<cstdint>//给出不同宽度的整型数的宏定义
#include<functional>//重载了()的各种定义
#include<optional>//方便多个值返回，且能判断是否有返回值
#include<queue>


//namespace 允许像类，对象，函数聚集在一个名字下
namespace ds {
    template<typename T>
    class AVLTree;//先声明后实现
    template<typename T>
    class AVLTreeNode {
    public:
        friend class AVLTree<T>;//这里是为什么呢？

    public:
        AVLTreeNode() = default;
        //explicit 关键字的作用就是防止 单个参数的类构造函数 的 隐式自动转换
        explicit AVLTreeNode(const T& key) : key_(key) {}
        //在函数声明后加上”=delete;”，就可将该函数禁用，防止某些隐式类型转换
        AVLTreeNode(const AVLTreeNode&) = delete;
        AVLTreeNode(AVLTreeNode&&) = delete;//不可以传递右值
        ~AVLTreeNode() = default;

        AVLTreeNode& operator=(const AVLTreeNode&) = delete;
        AVLTreeNode& operator=(AVLTreeNode&&) = delete;

        T key_;
    private:
        AVLTreeNode* left_{ nullptr };
        AVLTreeNode* right_{ nullptr };
        int height_{ 1 }; //每个节点里记忆当前的高度
    };


    template<typename T>
    class AVLTree {
    public:
        using callback_t = std::function<void(T&)>;//将函数作为对象包装，之后可以作为参数

    public:
        AVLTree() = default;
        AVLTree(std::initializer_list<T> keys);
        AVLTree(const AVLTree&) = delete;
        AVLTree(const AVLTree&&) = delete;
        ~AVLTree();

        AVLTree& operator=(const AVLTree&) = delete;
        AVLTree& operator=(AVLTree&&) = delete;
        void pre_order_traversal(callback_t callback);
        void in_order_traversal(callback_t callback);
        void post_order_traversal(callback_t callback);
        void level_order_traversal(callback_t callback);
        void insert(const T& key);

        template<typename U>
        void remove(const U& key);
        template<typename U>
        auto search(const U& key);
        auto minimum();
        auto maximum();
        auto height();
        auto size();
        void clear();

    private:
        //封装函数为参数的优点:callback是自定义的访问格式
        void pre_order_traversal_helper(AVLTreeNode<T>* root, callback_t callback);
        void in_order_traversal_helper(AVLTreeNode<T>* root, callback_t callback);
        void post_order_traversal_helper(AVLTreeNode<T>* root, callback_t callback);
        void breadth_first_traversal_helper(AVLTreeNode<T>* root, callback_t callback);

        //返回左树高减去右树的高
        auto balance(const AVLTreeNode<T>* root);

        //简单递归即可
        AVLTreeNode<T>* rotate_left(AVLTreeNode<T>* root);
        AVLTreeNode<T>* rotate_right(AVLTreeNode<T>* root);
        AVLTreeNode<T>* insert_helper(AVLTreeNode<T>* root, const T& key);

        //为什么这里又单独搞了一个U
        template<typename U>
        AVLTreeNode<T>* remove_helper(AVLTreeNode<T>* root, const U& key);
        template<typename U>
        AVLTreeNode<T>* search_helper(AVLTreeNode<T>* root, const U& key);

        AVLTreeNode<T>* minimum_helper(AVLTreeNode<T>* root);
        AVLTreeNode<T>* maximum_helper(AVLTreeNode<T>* root);
        auto height_helper(const AVLTreeNode<T>* root);
        auto size_helper(const AVLTreeNode<T>* root);
        void clear_helper(AVLTreeNode<T>* root);

        //实际成员变量
        AVLTreeNode<T>* root_{ nullptr };

    };

    template<typename T>
    AVLTree<T>::AVLTree(std::initializer_list<T> keys) {
        for (auto key : keys) {
            insert(key);
        }
    }

    template<typename T>
    AVLTree<T>::~AVLTree() { clear(); }

    template<typename T>
    void AVLTree<T>::pre_order_traversal(AVLTree::callback_t callback) {
        pre_order_traversal_helper(root_, callback);
    }

    template<typename T>
    void AVLTree<T>::in_order_traversal(AVLTree::callback_t callback) {
        in_order_traversal_helper(root_, callback);
    }

    template<typename T>
    void AVLTree<T>::post_order_traversal(AVLTree::callback_t callback) {
        post_order_traversal_helper(root_, callback);
    }

    template<typename T>
    void AVLTree<T>::level_order_traversal(AVLTree::callback_t callback) {
        breadth_first_traversal_helper(root_, callback);
    }

    template<typename T>
    void AVLTree<T>::insert(const T& key) { root_ = insert_helper(root_, key); }

    template<typename T>
    template<typename U>
    void AVLTree<T>::remove(const U& key) {
        root_ = remove_helper(root_, key);
    }


    template<typename T>
    template<typename U>
    auto AVLTree<T>::search(const U& key) {
        auto res = search_helper(root_, key);
        //std::optional对象只是包含对象的内部内存加上一个布尔标志，方便判断是否有值
        return res ? std::optional<std::reference_wrapper<T>>{res->key_}
        //reference_wrapper 将引用包装成一个对象，即引用的包装器
        : std::nullopt;
    }

    template<typename T>
    auto AVLTree<T>::minimum() {
        auto min = minimum_helper(root_);
        return min ? std::optional<std::reference_wrapper<T>>{min->key_}
        : std::nullopt;
    }

    template<typename T>
    auto AVLTree<T>::maximum() {
        auto max = maximum_helper(root_);
        return max ? std::optional<std::reference_wrapper<T>>{max->key_}
        : std::nullopt;
    }

    template<typename T>
    auto AVLTree<T>::height() { return height_helper(root_); }

    template<typename T>
    auto AVLTree<T>::size() { return size_helper(root_); }

    template<typename T>
    void AVLTree<T>::clear() {
        clear_helper(root_);
        root_ = nullptr;
    }


    template<typename T>
    void AVLTree<T>::pre_order_traversal_helper(AVLTreeNode<T>* root, AVLTree::callback_t callback) {
        if (!root) return;
        callback(root->key_);
        pre_order_traversal_helper(root->left_, callback);
        pre_order_traversal_helper(root->right_, callback);
    }

    template<typename T>
    void AVLTree<T>::in_order_traversal_helper(AVLTreeNode<T>* root, AVLTree::callback_t callback) {
        if (!root) return;
        in_order_traversal_helper(root->left_, callback);
        callback(root->key_);
        in_order_traversal_helper(root->right_, callback);
    }

    template<typename T>
    void AVLTree<T>::post_order_traversal_helper(AVLTreeNode<T>* root, AVLTree::callback_t callback) {
        if (!root) return;
        post_order_traversal_helper(root->left_, callback);
        post_order_traversal_helper(root->right_, callback);
        callback(root->key_);
    }

    template<typename T>
    void AVLTree<T>::breadth_first_traversal_helper(AVLTreeNode<T>* root, AVLTree::callback_t callback) {
        if (!root) return;
        std::queue<AVLTreeNode<T>*> queue;
        queue.push(root);
        while (!queue.empty()) {
            AVLTreeNode<T>* current{ queue.front() };//大括号是一个初始化操作
            callback(current->key_);
            queue.pop();
            if (current->left_) queue.push(current->left_);
            if (current->right_) queue.push(current->right_);
        }
    }

    template<typename T>
    auto AVLTree<T>::balance(const AVLTreeNode<T>* root) {
        if (!root) return 0;
        return height_helper(root->left_) - height_helper(root->right_);
    }

    template<typename T>
    AVLTreeNode<T>* AVLTree<T>::rotate_left(AVLTreeNode<T>* root) {
        AVLTreeNode<T>* pivot{ root->right_ };//旋转中心
        AVLTreeNode<T>* orphan{ pivot->left_ };//孤儿:被挤断的元素

        pivot->left_ = root;//旋下
        root->right_ = orphan;//接上

        //更新变动节点的高度
        root->height_ = std::max(height_helper(root->left_), height_helper(root->right_)) + 1;
        pivot->height_ = std::max(height_helper(pivot->left_), height_helper(pivot->right_)) + 1;

        return pivot;
    }


    template<typename T>
    AVLTreeNode<T>* AVLTree<T>::rotate_right(AVLTreeNode<T>* root) {
        AVLTreeNode<T>* pivot{ root->left_ };
        AVLTreeNode<T>* orphan{ pivot->right_ };

        pivot->right_ = root;
        root->left_ = orphan;

        root->height_ = std::max(height_helper(root->left_), height_helper(root->right_)) + 1;
        pivot->height_ = std::max(height_helper(pivot->left_), height_helper(pivot->right_)) + 1;

        return pivot;
    }

    template<typename T>
    AVLTreeNode<T>* AVLTree<T>::insert_helper(AVLTreeNode<T>* root, const T& key) {

        //1.插入，没有就直接创建，不存重复值，左小右大
        if (!root) return new AVLTreeNode(key);


        if (key < root->key_)
            root->left_ = insert_helper(root->left_, key);
        else if (root->key_ < key)
            root->right_ = insert_helper(root->right_, key);

        root->height_ = std::max(height_helper(root->left_), height_helper(root->right_)) + 1;


        //检查调整，使平衡
        if (balance(root) > 1) {//新值在左树
            if (key < root->left_->key_) {
                //LL
                return rotate_right(root);
            }
            if (root->left_->key_ < key) {
                //LR
                root->left_ = rotate_left(root->left_);
                return rotate_right(root);
            }
        }
        else if (balance(root) < -1) {//在右树
            if (root->right_->key_ < key) {
                //RR（左旋）
                return rotate_left(root);
            }
            if (key < root->right_->key_) {
                //RL--> RR 先右旋后左旋
                root->right_ = rotate_right(root->right_);
                return rotate_left(root);
            }
        }

        return root;
    }

    template<typename T>
    template<typename U>
    AVLTreeNode<T>* AVLTree<T>::remove_helper(AVLTreeNode<T>* root, const U& key) {

        if (!root) return nullptr;
        if (key < root->key_)
            root->left_ = remove_helper(root->left_, key);
        else if (root->key_ < key)
            root->right_ = remove_helper(root->right_, key);
        else {//正好是当前的根值
            if (!root->left_ && !root->right_) {
                delete root;
                root = nullptr;
            }
            else if (!root->left_) {
                //保存要清空的值
                AVLTreeNode<T>* tmp{ root };
                root = root->right_;
                delete tmp;
            }
            else if (!root->right_) {

                AVLTreeNode<T>* tmp{ root };
                root = root->left_;
                delete tmp;
            }
            else {//左右孩子都存在，取右子树中的最小值当根，再删除原位置
                AVLTreeNode<T>* min{ minimum_helper(root->right_) };
                root->key_ = min->key_;
                root->right_ = remove_helper(root->right_, min->key_);
                //AVLTreeNode<T> *max{Maximum(root->left_)};
                //root->key_ = max->key_;
                //root->left_ = remove(root->left_, max->key_);
            }
        }


        // 调整平衡
        if (!root) return nullptr;

        root->height_ = std::max(height_helper(root->left_), height_helper(root->right_)) + 1;

        if (balance(root) > 1) {//左树高了
            if (balance(root->left_) >= 0) {//左树的左孩子更高LL
                return rotate_right(root);
            }
            //右孩子更高 LR
            root->left_ = rotate_left(root->left_);
            return rotate_right(root);
        }
        if (balance(root) < -1) {
            if (balance(root->right_) <= 0) {
                return rotate_left(root);
            }
            root->right_ = rotate_right(root->right_);
            return rotate_left(root);
        }

        return root;
    }

    template<typename T>
    template<typename U>
    AVLTreeNode<T>* AVLTree<T>::search_helper(AVLTreeNode<T>* root, const U& key) {
        while (root) {
            if (root->key_ < key) {
                root = root->right_;
            }
            else if (key < root->key_) {
                root = root->left_;
            }
            else {
                return root;
            }
        }
        return nullptr;
    }

    template<typename T>
    AVLTreeNode<T>* AVLTree<T>::minimum_helper(AVLTreeNode<T>* root) {
        if (!root) return nullptr;
        while (root->left_) root = root->left_;
        return root;
    }

    template<typename T>
    AVLTreeNode<T>* AVLTree<T>::maximum_helper(AVLTreeNode<T>* root) {
        if (!root) return nullptr;
        while (root->right_) root = root->right_;
        return root;
    }


    template<typename T>
    auto AVLTree<T>::height_helper(const AVLTreeNode<T>* root) {
        if (!root) return 0;
        return root->height_;
    }


    //递归求个数
    template<typename T>
    auto AVLTree<T>::size_helper(const AVLTreeNode<T>* root) {
        if (!root) return 0;
        return size_helper(root->left_) + size_helper(root->right_) + 1;
    }


    // 先序删除
    template<typename T>
    void AVLTree<T>::clear_helper(AVLTreeNode<T>* root) {
        if (!root) return;
        if (root->left_) clear_helper(root->left_);
        if (root->right_) clear_helper(root->right_);
        delete root;
    }
};

用法:直接调用接口即可

#include"AVLTree.h"
#include<iostream>

using namespace std;
using namespace ds;

void show(int &t) {
    cout << t << " ";
}
int main() {
    AVLTree<int> tmp({ 12,24,25,11,110 });

    tmp.pre_order_traversal(show);

    cout << endl;
    if (auto res = tmp.search(12)) { 
        cout << res->get() << endl;
    }
    return 0;
}