数据结构 平衡二叉树

开始学习AVL树了，目前简单了解了其相关概念

平衡因子：

基本旋转方式：

1.左单旋

记失衡节点为x

x右孩子为y

x->right = y->left

y->left = x

2.右单旋

记失衡节点为x

x左孩子为y

x->left = y->right

y->right = x

最小失衡子树：在新插入的节点向上查找，以第一个平衡因子的绝对值超过一的节点为根节点的子树

插入：

1.进行BST插入

2.算插入节点的所有祖先节点的平衡因子

节点x高度x->h = max(x->left->h,x->right->h) + 1

节点平衡因子:x->left->h - x->right->h(左右子树高度差的绝对值)

3.插入导致失衡情况，进行旋转（优先调整最小失衡子树）

判断失衡：

1.先找出x->left和x->right中高度较高的

2.再去高度子树里面去看根节点的哪边的子树高

4.调用对应调整函数

假设最小失衡子树根节点为A

1.LL

在A节点左孩子的左子树插入节点破坏平衡

调整策略：对A进行一次右旋

2.LR

在A节点左孩子的右子树插入节点破坏平衡

调整策略：（1）以A->left为中心进行左旋，转换成为了LL

(2)按照LL情况进行操作

3.RR

在A节点右孩子的右子树插入节点破坏平衡

调整策略：对A进行一次左旋

4.RL

在A节点右孩子的左子树插入节点破坏平衡

调整策略：（1）以A->right为中心进行右旋，转换为RR

(2)按照RR情况进行操作

删除操作

1.执行二叉排序树删除

2.判断是否失衡

在x节点的一边子树中删除了一个节点，就等价于在其另一边子树插入了一个节点导致的失衡--->删除的失衡类型及调整方式和插入的一模一样

左删除 相当于 右边插入：RR RL

右删除 相当于 左边插入：LL LR

终于完成了AVL树了，接下来就学习一下哈夫曼树（似乎是另一条路线的样子）和时间复杂度了

日常：麻了，四级好像要寄了，算了一下，似乎430~440的样子（作文翻译全按及格算的），希望能过 下周二考工程师职业素养期末，坐大牢，本来说周末复习的，装一个远行星号装了一上午，下午还有文明经典，属实难绷

代码实现如下

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
using namespace std;

template<class T>
class AVL_Node
{
public:
    T data;
    AVL_Node<T>* left = nullptr;
    AVL_Node<T>* right = nullptr;
    int h = 1;//记录节点高度
};
template<class T>
class AVL_Tree
{
public:
    AVL_Tree()
    {
        root = new AVL_Node<T>;
        if (root == nullptr)
        {
            cout << "开辟失败" << endl;
        }
        else
        {
            root->left = nullptr;
            root->right = nullptr;
        }
    }
    AVL_Tree(T k)
    {
        root = new AVL_Node<T>;
        if (root == nullptr)
        {
            cout << "开辟失败" << endl;
        }
        else
        {
            root->left = nullptr;
            root->right = nullptr;
            root->data = k;
        }
    }
    AVL_Node<T>* AVL_Insert(AVL_Node<T>* ro, T k)
    {
        if (ro == nullptr)
        {
            AVL_Node<T>* s = new AVL_Node<T>;
            s->data = k;
            return s;
        }
        else if (k < ro->data)
        {
            ro->left = AVL_Insert(ro->left, k);
            //高度可能变化,判断是否失衡
            if (Get_h(ro->left) - Get_h(ro->right) > 1)
            {
                AVL_Node<T>* l = ro->left;//用于判断失衡类型
                //也可以通过子树高度判断
                //if (Get_h(l->left) > Get_h(l->right))
                if (k < l->data)
                {
                    //LL
                    ro = LL_rotation(ro);
                }
                else
                {
                    //LR
                    ro = LR_rotation(ro);
                }
            }
            //返回变化后子树根节点并且改变高度(因为都要进行，所以可以一起挪到函数末尾)		
        }
        else
        {
            ro->right = AVL_Insert(ro->right, k);
            //高度可能变化,判断是否失衡
            if (Get_h(ro->right) - Get_h(ro->left) > 1)
            {
                AVL_Node<T>* r = ro->right;//用于判断失衡类型
                //也可以通过子树高度判断
                //if(Get_h(r->right) > Get_h(r->left))
                if (k > r->data)
                {
                    //RR
                    ro = RR_rotation(ro);
                }
                else
                {
                    //RL
                    ro = RL_rotation(ro);
                }
            }
            //返回变化后子树根节点并且改变高度(因为都要进行，所以可以一起挪到函数末尾)
        }
        ro->h = max(Get_h(ro->left), Get_h(ro->right)) + 1;
        return ro;
    }
    int Get_h(AVL_Node<T>* x)
    {
        if (x == nullptr)
        {
            return 0;
        }
        else
        {
            return x->h;
        }
    }
    AVL_Node<T>* LL_rotation(AVL_Node<T>* ro)
    {
        AVL_Node<T>* y = ro->left;
        ro->left = y->right;
        y->right = ro;
        //高度可能改变
        ro->h = max(Get_h(ro->left), Get_h(ro->right)) + 1;
        y->h = max(Get_h(y->left), Get_h(y->right)) + 1;
        return y;
    }
    AVL_Node<T>* LR_rotation(AVL_Node<T>* ro)
    {
        ro->left = RR_rotation(ro->left);
        ro = LL_rotation(ro);
        return ro;
    }
    AVL_Node<T>* RR_rotation(AVL_Node<T>* ro)
    {
        AVL_Node<T>* y = ro->right;
        ro->right = y->left;
        y->left = ro;
        //高度可能改变
        ro->h = max(Get_h(ro->left), Get_h(ro->right)) + 1;
        y->h = max(Get_h(y->left), Get_h(y->right)) + 1;
        return y;
    }
    AVL_Node<T>* RL_rotation(AVL_Node<T>* ro)
    {
        ro->right =LL_rotation(ro->right);
        ro = RR_rotation(ro);
        return ro;
    }
    void mid_order(AVL_Node<T>* ro)
    {
        if (ro == nullptr)
        {
            return;
        }
        if (ro->left != nullptr)
        {
            mid_order(ro->left);
        }
        cout << ro->data << ' ' << ro->h << endl;
        if (ro->right != nullptr)
        {
            mid_order(ro->right);
        }
    }

    //找以ro为根节点的树中最靠右节点
    AVL_Node<T>* Find_p(AVL_Node<T>* ro)
    {
        AVL_Node<T>* p = ro;
        while (p->right != nullptr)
        {
            p = p->right;
        }
        return p;
    }
    AVL_Node<T>* Del(AVL_Node<T>* ro,T k)
    {
        if (ro == nullptr)
        {
            return nullptr;
        }
        if (k < ro->data)
        {
            ro->left = Del(ro->left, k);
            //判断失衡 RR RL
            if (Get_h(ro->right) - Get_h(ro->left) > 1)
            {
                AVL_Node<T>* r = ro->right;
                if (Get_h(r->right) >= Get_h(r->left))
                {
                    ro = RR_rotation(ro);
                }
                else
                {
                    ro = RL_rotation(ro);
                }
            }
        }
        else if (k > ro->data)
        {
            ro->right = Del(ro->right, k);
            //判断失衡 LL LR
            if (Get_h(ro->left) - Get_h(ro->right) > 1)
            {
                AVL_Node<T>* l = ro->left;
                if (Get_h(l->left) >= Get_h(l->right))
                {
                    ro = LL_rotation(ro);
                }
                else
                {
                    ro = LR_rotation(ro);
                }
            }
        }
        else
        {
            if (ro->left != nullptr && ro->right != nullptr)
            {
                AVL_Node<T>* p = Find_p(ro->left);
                ro->data = p->data;
                ro->left = Del(ro->left, p->data);
                //判断失衡
                if (Get_h(ro->right) - Get_h(ro->left) > 1)
                {
                    AVL_Node<T>* r = ro->right;
                    if (Get_h(r->right) >= Get_h(r->left))
                    {
                        ro = RR_rotation(ro);
                    }
                    else
                    {
                        ro = RL_rotation(ro);
                    }
                }
            }
            else
            {
                AVL_Node<T>* ch = nullptr;
                if (ro->left != nullptr)
                {
                    ch = ro->left;
                }
                else
                {
                    ch = ro->right;
                }
                delete ro;
                ro = nullptr;
                return ch;
            }
        }
        ro->h = max(Get_h(ro->left), Get_h(ro->right)) + 1;
        return ro;
    }
    //查找
    void Find(T k)
    {
        AVL_Node<T>* p = root;
        while (p != nullptr && p->data != k)
        {
            if (k < p->data)
            {
                p = p->left;
            }
            else
            {
                p = p->right;
            }
        }
        if (p == nullptr)
        {
            cout << "不存在" << endl;
        }
        else
        {
            cout << "存在" << endl;
        }
    }
public:
    AVL_Node<T>* root;
};
int main()
{
    AVL_Tree<int> tree(1);
    for (int i = 1; i < 8; ++i)
    {
        tree.root = tree.AVL_Insert(tree.root,i + 1);
    }
    tree.mid_order(tree.root);
    tree.Del(tree.root, 4);
    cout << endl;
    tree.mid_order(tree.root);
    tree.Find(6);
    return 0;
}