AVL树

た入场券 2022-06-15 09:08 183阅读 0赞

AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

AVL树是建立在二叉搜索树的基础之上的，因为二叉树搜索树有缺陷

![这里写图片描述][SouthEast]  
当我们的二叉搜索树是如上图的样子，那么它是顺序查找，在它的最坏情况下 时间复杂度是O( N),在这种情况下如果我们数据特别多，那么效率太低。而这种问题是因为它的左右子树的高度差极度不平衡造成的。  
为了解决这种问题因此引入了AVL树，AVL树自身也是满足搜索二叉树的性质的，只不过它在左右子树高度差不平衡的时候会进行调整

AVL树的性质  
1. 左子树和右子树的高度之差的绝对值不超过1 2. 树中的每个左子树和右子树都是AVL树 3. 每个节点都有一个平衡因子(balance factor–bf),任一节点的平衡因子是-1,0,1。(每个节点的平衡因子等于右子树的高度减去左子 树的高度 )  
而AVL树的插入和删除它的时间复杂度都是O(logN)

AVL树的插入操作  
由于AVL树的插入需要插入节点的父亲的信息，因此AVL树要维护的是一个个具有三叉链结构的节点，而之前普通的搜索二叉树维护的只是一个二叉链结构的 节点  
因此AVL树较为普通的搜索二叉树较难  
1、父节点的|bf|==2进行旋转  
2、父节点的|bf|==1高度增加，向上更新平衡因子  
3、父节点的|bf|==0，停止更新平衡因子

对于旋转又分为4种情况:  
1、左单旋  
2、右单旋  
3、左右双旋  
4、右左双旋

1、左单旋：  
![这里写图片描述][SouthEast 1]

左单旋的代码就可以根据上图写出来

void RotateL( Node*&parent)
        {
            Node*SubR = parent->_right;
            Node*SubRL = SubR->_left;
            parent->_right = SubRL;
            if (SubRL)
            {
                SubRL->_parent = parent;
            }
            SubR->_left = parent;
            Node*ppNode = parent->_parent;
            parent->_parent = SubR;
            if (ppNode == NULL)
            {
                _root = SubR;
                _root->_parent = NULL;
            }
            else//考虑这个parent节点可能不是根节点
            {
    
                if (parent == ppNode->_left)
                {
                    ppNode->_left = SubR;
    
                }
                else
                {
                    ppNode->_right = SubR;
    
                }
                SubR->_parent = ppNode; 
            }
            parent->_bf = SubR->_bf = 0;
        }

2、右单旋：  
![这里写图片描述][SouthEast 2]  
右单旋的代码就可以根据上图写出来

void RotateR(Node*&parent)
        {
            Node*SubL = parent->_left;
            Node*SubLR = SubL->_right;
            parent->_left = SubLR;
            if (SubLR)
            {
                SubLR->_parent = parent;
            }
            SubL->_right = parent;
            Node*ppNode = parent->_parent;//不确定parent这个节点是不是根节点，要做判断，因此不能随意链接
            parent->_parent = SubL;
            if (ppNode == NULL)
            {
                _root = SubL;
                _root->_parent = NULL;
            }
            else
            {
                if (parent == ppNode->_left)
                {
                    ppNode->_left = SubL;
                }
                else
                {
                    ppNode->_right = SubL;
                }
                SubL->_parent = ppNode;
            }
            SubL->_bf = parent->_bf = 0;
        }

3、左右双旋  
![这里写图片描述][SouthEast 3]

![这里写图片描述][SouthEast 4]

代码如下：

void RotateLR(Node*parent)
        {
           RotateL(parent->left);
            RotateR(parent);
        }

这个代码是有问题的没有考虑特殊情况  
因此修改代码  
![这里写图片描述][SouthEast 5]  
![这里写图片描述][SouthEast 6]

void RotateLR(Node*parent)
        {
            Node*SubL = parent->_left;
            Node*SubLR = SubL->_right;
            int Prebf = SubLR->_bf;
            RotateL(SubL);
            RotateR(parent);
            if (Prebf == -1)
            {
                SubL->_bf = 0;
                parent->_bf = 1;
            }
            else if (Prebf == 1)
            {
                SubL->_bf = -1;
                parent->_bf = 0;
            }
            else
            {
                parent->_bf = SubL->_bf = 0;
            }
            SubLR->_bf = 0;
        }

4、右左双旋  
同左右双旋原理一样  
代码如下

void RotateRL(Node*parent)
        {
            RotateR(parent->_right);
            RotateL(parent);
        }

但是这个代码是有问题的没有考虑特殊情况  
当然这幅图我们也只是考虑了新增节点之后10的平衡因子为1，同左右双旋一样还要考虑10为0或者1的情况(这样考虑是因为10的父亲的祖父的平衡因子会随着10的变化而变化  
因此修改代码

![这里写图片描述][SouthEast 7]  
![这里写图片描述][SouthEast 8]

void RotateRL(Node*parent)
        {
            Node*SubR = parent->_right;
            Node*SubRL = SubR->_left;
            int Prebf = SubRL->_bf;
            RotateR(SubR);
            RotateL(parent);
            if (Prebf == -1)
            {
                SubR->_bf = 1;
                parent->_bf = 0;
            }
            else if (Prebf == 1)
            {
                SubR->_bf = 0;
                parent->_bf = -1;
            }
            else
            {
                parent->_bf = SubR->_bf = 0;
            }
            SubRL->_bf = 0;
        }

完整代码：

#include<iostream>
    #include<stdlib.h>
    using namespace std;
    template<class K,class V>
    struct AVLTreeNode
    {
        AVLTreeNode(const K &key,const V&value=0)
        :_left(NULL)
        , _right(NULL)
        , _parent(NULL)
        , _key(key)
        , _value(value)
        , _bf(0)
        {
    
        }
        AVLTreeNode<K,V>*_left;
        AVLTreeNode<K, V>*_right;
        AVLTreeNode<K, V>*_parent;
        K _key;
        V _value;
        int _bf;
    };
    template<class K,class V>
    class AVLTree
    {
        typedef AVLTreeNode<K, V> Node;
    public:
        AVLTree()
            :_root(NULL)
        {
    
        }
        bool Insert(const K &key,const V&value)
        {
            if (_root == NULL)
            {
                _root = new Node(key, value);
                return true;
            }
            else
            {
                Node*cur = _root;
                Node*parent = NULL;
                while (cur)
                {
                    if (cur->_key > key)//和BS一样
                    {
                        parent = cur;
                        cur = cur->_left;
                    }
                    else if (cur->_key < key)
                    {
                        parent = cur;
                        cur = cur->_right;
                    }
                    else
                    {
                        return false;
                    }
                }
                cur = new Node(key, value);
                if (key > parent->_key)
                {
                    parent->_right = cur;
                    cur->_parent = parent;
                }
                else
                {
                    parent->_left = cur;
                    cur->_parent = parent;
                }
                //节点插入完成
                //在插入节点之后进行平衡因子的调节，分情况进行处理
                while (parent)//一直到调整到根节点为空为止
                {
                    if (cur == parent->_left)
                    {
                        parent->_bf--;
                    }
                    else if (cur == parent->_right)
                    {
                        parent->_bf++;
    
                    }
                    if (parent->_bf ==2||parent->_bf==-2)//进行旋转，旋转又分为4种
                    {
                        if (parent->_bf == -2)
                        {
                            if (parent->_left->_bf == 1)
                            {
                                RotateLR(parent);
                                return true;
                            }
                            else if (parent->_left->_bf == -1)
                            {
                                RotateR(parent);
                                return true;
                            }
                        }
                        else
                        {
                            if (parent->_right->_bf == 1)
                            {
                                RotateL(parent);
                                return true;
                            }
                            else if (parent->_right->_bf == -1)
                            {
                                RotateRL(parent);
                                return true;
                            }
                        }
                    }
                    else if (parent->_bf == 1 || parent->_bf == -1)//继续向上调整
                    {
                        cur = parent;
                        parent = parent->_parent;
                    }
                    else
                    {
                        break;//停止更新
                    }
                }
            }
            return true;
        }
        void RotateL( Node*&parent)
        {
            Node*SubR = parent->_right;
            Node*SubRL = SubR->_left;
            parent->_right = SubRL;
            if (SubRL)
            {
                SubRL->_parent = parent;
            }
            SubR->_left = parent;
            Node*ppNode = parent->_parent;
            parent->_parent = SubR;
            if (ppNode == NULL)
            {
                _root = SubR;
                _root->_parent = NULL;
            }
            else//考虑这个parent节点可能不是根节点
            {
    
                if (parent == ppNode->_left)
                {
                    ppNode->_left = SubR;
    
                }
                else
                {
                    ppNode->_right = SubR;
    
                }
                SubR->_parent = ppNode; 
            }
            parent->_bf = SubR->_bf = 0;
        }
    
        void RotateR(Node*&parent)
        {
            Node*SubL = parent->_left;
            Node*SubLR = SubL->_right;
            parent->_left = SubLR;
            if (SubLR)
            {
                SubLR->_parent = parent;
            }
            SubL->_right = parent;
            Node*ppNode = parent->_parent;//不确定parent这个节点是不是根节点，要做判断，因此不能随意链接
            parent->_parent = SubL;
            if (ppNode == NULL)
            {
                _root = SubL;
                _root->_parent = NULL;
            }
            else
            {
                if (parent == ppNode->_left)
                {
                    ppNode->_left = SubL;
                }
                else
                {
                    ppNode->_right = SubL;
                }
                SubL->_parent = ppNode;
            }
            SubL->_bf = parent->_bf = 0;
        }
        void RotateLR(Node*parent)
        {
            Node*SubL = parent->_left;
            Node*SubLR = SubL->_right;
            int Prebf = SubLR->_bf;
            RotateL(SubL);
            RotateR(parent);
            if (Prebf == -1)
            {
                SubL->_bf = 0;
                parent->_bf = 1;
            }
            else if (Prebf == 1)
            {
                SubL->_bf = -1;
                parent->_bf = 0;
            }
            else
            {
                parent->_bf = SubL->_bf = 0;
            }
            SubLR->_bf = 0;
        }
        void RotateRL(Node*parent)
        {
            Node*SubR = parent->_right;
            Node*SubRL = SubR->_left;
            int Prebf = SubRL->_bf;
            RotateR(SubR);
            RotateL(parent);
            if (Prebf == -1)
            {
                SubR->_bf = 1;
                parent->_bf = 0;
            }
            else if (Prebf == 1)
            {
                SubR->_bf = 0;
                parent->_bf = -1;
            }
            else
            {
                parent->_bf = SubR->_bf = 0;
            }
            SubRL->_bf = 0;
        }
        bool IsBalance()
        {
            int depth = 0;
            return  _IsBalance(_root);//判断是否为AVL树
        }
        void InOrder()//中序遍历并不能检测是否是AVL树
        {
            _InOrder(_root);
        }
        int Hight(Node*root)
        {
            if (root == NULL)
            {
                return 0;
            }
            int leftHight = Hight(root->_left);
            int rightHight = Hight(root->_right);
            return leftHight > rightHight ? (leftHight + 1) : (rightHight + 1);
        }
        bool _IsBalance(Node*root)//时间复杂度为n^2
        {
            if (root == NULL)
            {
                return true;
            }
            int leftHight = Hight(root->_left);
            int rightHight = Hight(root->_right);
            int sub = rightHight - leftHight;
            if (abs(sub)>1||(sub) != root->_bf)
            {
                cout<<"异常为"<<root->_key<<" "<<root->_bf << endl;
                return false;
            }
            return abs(rightHight - leftHight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
        }
    
            bool _IsBalancePost(Node*root, int &depth)//采用时间复杂度为O(N)的算法
        {
            if (root == NULL)
            {
                depth = 0;
                return true;
            }
            int LeftDepth;
            int RightDepth;
            if (!_IsBalancePost(root->_left, LeftDepth))
            {
                return false;
            }
            if (!_IsBalancePost(root->_right, RightDepth))
            {
                return false;
            }
            int diff = RightDepth - LeftDepth;
            if (diff > 1 || diff<-1||diff!=root->_bf)
            {
                cout << "平衡因子异常:";
                cout << root->_key<<" ,"<<root->_bf << endl;
                return false;
            }
            depth = RightDepth - LeftDepth>0 ? RightDepth+1 : LeftDepth +1;
            return true;
        }
    protected:
        void _InOrder(Node*root)
        {
            if (root == NULL)
            {
                return;
            }
            _InOrder(root->_left);
            cout << root->_key << " ";
            _InOrder(root->_right);
        }
        Node*_root;
    };
    void FunTest1()
    {
        //4, 2, 6, 1, 3, 5, 15, 7, 16, 14
        //{16, 3, 7, 11, 9, 26, 18, 14, 15}
        AVLTree<int, int>av;
        int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; for (int i = 0; i<(sizeof(arr) / sizeof(arr[0]));i++) { av.Insert(arr[i],i); cout << av.IsBalance() << endl; } cout << "IsBalance is "; av.InOrder(); } void FunTest2() { AVLTree<int, int>av; int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; for (int i = 0; i<(sizeof(arr) / sizeof(arr[0])); i++) { av.Insert(arr[i],i); cout<<av.IsBalance()<<endl; } cout << "IsBalance is "; av.InOrder(); } int main() { FunTest1(); system("pause"); return 0; }

[SouthEast]: /images/20220615/aa599abb4f2049a0bd9c493894287ae2.png
[SouthEast 1]: /images/20220615/b36e1a1824a24381b4279a9a8918d6be.png
[SouthEast 2]: /images/20220615/384774c9b1a74f49b3029c27b24ed8d2.png
[SouthEast 3]: /images/20220615/768c3a0b739645eb8df9bf101988d63e.png
[SouthEast 4]: /images/20220615/727ab1af3fd540d1ada1363d2cd11ea4.png
[SouthEast 5]: /images/20220615/5eaffa617ab642ac8c6ad0dba6969a01.png
[SouthEast 6]: /images/20220615/9e95d8de58444fb0b030bd44420ea13e.png
[SouthEast 7]: /images/20220615/5fffda689c6b4e67af4c45396b1917b1.png
[SouthEast 8]: /images/20220615/16be86a00a4247a3a613e4e9b18c368f.png