AVL树

简介

模拟实现

平衡因子更新原则：

更新停止条件

旋转

代码

小知识

简介

AVL树是最先发明的自平衡二叉查找树，为空树或具备以下性质的二叉搜索树：1.左右子树都为AVL树。 2.左右子树高度差的绝对值不超过1。

模拟实现

使用平衡因子来模拟实现

平衡因子更新原则：

1.平衡因子 = 右子树高度 - 左子树高度

2.只有子树高度变化才会影响当前结点平衡因子

3.插入结点在parent右子树，parent结点平衡因子++，在parent左子树，parent结点平衡因子 --

4.parent所在子树高度是否变化决定了是否继续向上更新

更新停止条件

1.更新后parent的平衡因子等于0,更新中parent的平衡因子变化为-1->0或者1->0,说明更新前parent子树一边高一边低,新增的结点插入在低的那边,插入后parent所在的子树高度不变,不会影响parent的父亲结点的平衡因子,更新结束。

2.更新后parent的平衡因子等于1或-1,更新前更新中parent的平衡因子变化为0->1或者0->-1,说明更新前parent子树两边一样高,新增的插入结点后,parent所在的子树一边高一低,parent所在的子树符合平衡要求,但是高度增加了1,会影响parent的父亲结点的平衡因子,所以要继续向上更新。

3.更新后parent的平衡因子等于2或-2,更新前更新中parent的平衡因子变化为1->2或者-1->-2说明更新前parent子树一边高一边低,新增的插入结点在高的那边,parent所在的子树高的那边更高了,破坏了平衡,parent所在的子树不符合平衡要求,需要旋转处理,旋转的目标有两个: (1)、把parent子树旋转平衡。(2)、降低parent子树的高度,恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新,插入结束。

4.不断更新,更新到根,跟的平衡因子是1或-1也停止了。

旋转

（1）左单旋

此时需要旋转，将root移动到root_r的左边，root_rl成为root的右子树，root_r成为新的根结点或成为root父结点的子结点。

（2）右单旋

这时需要旋转，和左单旋相似

（3）左右双旋

如果插入结点在root_lr 的左右结点，需要左右双旋，先root_l左旋，再root右旋。

（4）右左双旋

如果插入结点在root_rl 的左右结点，需要右左双旋，先对root_r进行右旋，在对root进行左旋。

代码

namespace my_AVLtree
{
   template<class K,class V>
   struct AVLTree_node
   {
       pair<K, V> _kv;
       AVLTree_node<K,V>* _left = nullptr;
       AVLTree_node<K,V>* _right = nullptr;
       AVLTree_node<K,V>* _parent = nullptr;
       int _bf = 0; //平衡因子

       AVLTree_node(const pair<K,V>& kv)
           :_kv(kv)
       {}
   };

//直接是key/value版本

   template<class K,class V>
   class AVLTree
   {
       typedef AVLTree_node<K, V> node;
       node* _root = nullptr;

       void _inorder(node* root)
       {
           if (!root)
               return;

           _inorder(root->_left);
           cout << root->_kv.first << ':' << root->_kv.second << endl;
           _inorder(root->_right);
       }

       node* Copy(node* root)
       {
           if (!root)
               return nullptr;

           node* newroot = new node(root->_kv.first, root->_kv.second);
           newroot->_left = Copy(root->_left);
           newroot->_right = Copy(root->_right);

           return newroot;
       }

       void Destory(node* root)
       {
           if (!root)
               return;

           Destory(root->_left);
           Destory(root->_right);
           delete root;
       }

       void rotateL(node* root) //左单旋
       {
           node* child = root->_right;
           node* childchild = child->_left;
           node* rootparent = root->_parent;

           root->_right = childchild;
           if (childchild) childchild->_parent = root;

           child->_parent = rootparent;
           if (root == _root) _root = child;
           else
           {
               if (rootparent->_left == root) rootparent->_left = child;
               else if (rootparent->_right == root) rootparent->_right = child;
               else assert(false);
           }
           root->_parent = child;
           child->_left = root;

    //更新平衡因子

           child->_bf = 0;
           root->_bf = 0;
       }

       void rotateR(node* root) 右单旋
       {
           node* child = root->_left;
           node* childchild = child->_right;
           node* rootparent = root->_parent;

           root->_left = childchild;
           if (childchild) childchild->_parent = root;

           child->_parent = rootparent;
           if (root == _root) _root = child;
           else
           {
               if (rootparent->_left == root) rootparent->_left = child;
               else if (rootparent->_right == root) rootparent->_right = child;
               else assert(false);
           }
           root->_parent = child;
           child->_right = root;

//更新平衡因子

           child->_bf = 0;
           root->_bf = 0;
       }

int _Height(node* root) //求高度
        {
            if (root == nullptr)
                return 0;
            int leftHeight = _Height(root->_left);
            int rightHeight = _Height(root->_right);
            return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
        }

       void rotateLR(node* root) //-2 1
       {
           node* orootp = root->_parent;
           rotateL(root);
           rotateR(orootp);
           //更新平衡因子

           root-> _bf = _Height(root->_right) - _Height(root->_left);
           orootp-> _bf = _Height(orootp->_right) - _Height(orootp->_left);
       }

       void rotateRL(node* root) // 2 -1
       {
           node* orootp = root->_parent;
           rotateR(root);
           rotateL(orootp);
           //更新平衡因子

           root-> _bf = _Height(root->_right) - _Height(root->_left);
           orootp-> _bf = _Height(orootp->_right) - _Height(orootp->_left);
       }

       bool _IsBalanceTree(node* root) //用来检测
       {
           // 空树也是AVL树
           if (nullptr == root)
               return true;
           // 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差
           int leftHeight = _Height(root->_left);
           int rightHeight = _Height(root->_right);
           int diff = rightHeight - leftHeight;
           // 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者
               // pRoot平衡因⼦的绝对值超过1，则⼀定不是AVL树
           if (abs(diff) >= 2)
           {
               cout << root->_kv.first << "⾼度差异常" << endl;
               assert(false);
               return false;
           }
           if (root->_bf != diff)
           {
               cout << root->_kv.first << "平衡因⼦异常" << endl;
               assert(false);
               return false;
           }
           // pRoot的左和右如果都是AVL树，则该树⼀定是AVL树
           return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
       }

       size_t _size(node* root)
       {
           if (!root) return 0;
           return _size(root->_left) + _size(root->_right) + 1;
       }

   public:

       AVLTree() = default;//告诉编译器使用默认生成的构造函数

       AVLTree(const AVLTree<K, V>& tmp)
       {
           _root = Copy(tmp._root);
       }

       AVLTree<K,V>& operator=(AVLTree<K, V> tmp)
       {
           swap(_root, tmp._root);
           return *this
       }

       ~AVLTree()
       {
           Destory(_root);
           _root = nullptr;
       }

       bool insert(const pair<K,V>& kv)
       {
           node* tmp = _root;
           if (!_root)
               tmp = _root = new node(kv);
           else
           {
               node* prev = _root;
               node* cur = _root;
               while (cur)
               {
                   if (cur->_kv.first < kv.first)
                   {
                       cur = cur->_right;
                       if (cur)
                           prev = prev->_right;
                   }
                   else if (cur->_kv.first > kv.first)
                   {
                       cur = cur->_left;
                       if (cur)
                           prev = prev->_left;
                   }
                   else
                       return false;
               }
               if (prev->_kv.first > kv.first)
               {
                   --prev->_bf; //更新平衡因子
                   tmp = prev->_left = new node(kv);
                   tmp->_parent = prev;
               }
               else
               {
           ++prev->_bf;//更新平衡因子
                   tmp = prev->_right = new node(kv);
                   tmp->_parent = prev;
               }
           }



           node* parent = tmp->_parent;
           while (parent)
           {
               if (!parent->_bf) break;
               else if (parent->_bf == 1 || parent->_bf == -1)
               {
                   if (parent == _root) break;
                   tmp = parent;
                   parent = parent->_parent;
                   if (parent->_left == tmp) --parent->_bf;
                   else if (parent->_right == tmp) ++parent->_bf;
                   else assert(false);
               }
               else if (parent->_bf == 2 && tmp->_bf == 1)
               {
                   rotateL(parent);
                   break;
               }
               else if (parent->_bf == -2 && tmp->_bf == -1)
               {
                   rotateR(parent);
                   break;
               }
               else if (parent->_bf == 2 && tmp->_bf == -1)
               {
                   rotateRL(tmp);
                   break;
               }
               else if (parent->_bf == -2 && tmp->_bf == 1)
               {
                   rotateLR(tmp);
                   break;
               }
               else
                   assert(false);
           }
           return true;
       }

       node* search(const K& first)
       {
           node* cur = _root;
           while (cur)
           {
               if (cur->_kv.first < first)
                   cur = cur->_right;
               else if (cur->_kv.first > first)
                   cur = cur->_left;
               else
                   return cur;
           }
           return nullptr;
       }

       void inorder()
       {
           _inorder(_root);
           cout << endl;
       }

       bool IsBalanceTree()
       {
           return _IsBalanceTree(_root);
       }

       int Height()
       {
           return _Height(_root);
       }

       size_t Size()
       {
           return _size(_root);
       }

   };

}