平衡搜索树-AVL树 图文详解 (万字长文)

目录

• AVL树
  
  
  
  • AVL树的概念
    
    
    
    • AVL树节点的定义：
      
    • AVL树的插入
      
      
      
      • 基本情况分析
        
      • 平衡因子对应的操作
        
      • 旋转操作
        
        
        
        • 分析需要旋转的情况
          
          
          
          • 结论
            
          
          
        • 4种旋转操方法与特性
          
        • 6种双旋平衡因子特性
          
        
        
      • 代码实现
        
        
        
        • 四种旋转实现
          
        • 插入操作实现
          
        • 树高度与是否平衡树判断实现
          
        • 其他实现
          
        
        
      • 插入验证
        
      • BenchMark
        
        
        
        • 环境
          
        • 测试工具和方法
          
        • 测试结果：
          
        
        
      
      
    
    
  
  

AVL树

AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而淘汰平均搜索长度。
一棵AVL树大概是空树，大概是具有以下性质的二叉搜索树：

• 它的左右子树都是AVL树
  
• 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
  
  
  
  (默认平衡因子=右子树高度-左子树高度)
  

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在$O(log_2 n)$，搜索时间复杂度O($log_2 n$)。

AVL树是由BST二叉搜索树改进而来,基本概念参考BST篇,本篇文章不再具体描述.
AVL树节点的定义：

1. template<class K, class V>
2. struct AVLTreeNode
3. {
4.                 //三叉链: left right parent
5.      AVLTreeNode* _left;   // 该节点的左孩子
6.      AVLTreeNode* _right;  // 该节点的右孩子
7.      AVLTreeNode* _parent; // 该节点的双亲
8.      std::pair<K,V> _kv;         // 键值对
9.      int _bf;              // 该节点的平衡因子 balance factor
11.                 AVLTreeNode(const std::pair<K, V>& kv)
12.                         :_left(nullptr)
13.                         , _right(nullptr)
14.                         , _parent(nullptr)
15.                         , _kv(kv)
16.                         , _bf(0)
17.                 {}
18. };

复制代码

AVL树的插入

基本情况分析

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

• 按照二叉搜索树的方式插入新节点
  
• 调整节点的平衡因子
  a. 更新父结点平衡因子
  b. 根据父结点的平衡因子进行相应的操作
  

对于平衡因子
插入新结点后,起首可能会影响父结点的平衡因子,迭代往上,可能还会影响部分或全部(到根节点)祖先结点的平衡因子.
具体地说,即插入新结点后,需要根据父结点平衡因子的情况,决定是否继续往上对祖结点进行更新平衡因子,最多到达根结点.
平衡因子对应的操作

父结点平衡因子如何决定是否继续往上更新? 取决于更新后parent->_bf的值

• 若parent->_bf == 1 || parent->_bf == -1 ,阐明插入前的父结点一定是左右子树高度相等,即_bf为0.新增结点后父结点所在子树高度一定发生变化,爷爷结点所在子树也可能发生变化,因此需要进行迭代更新祖先平衡因子.
  

  不可能是2或-2变成1或-1,因为这是AVL树的插入,至少先保证是AVL树才能插入
  

  
  
  
• 若parent->_bf == 2 || parent->_bf == -2 ,阐明插入前的父结点所在子树一边高一边低,之后新结点恰好插入到了高的一边,导致不平衡,需要做旋转操作,调整平衡.
  
• parent->_bf == 0,插入后父结点的平衡因子平衡,阐明原先父结点的左右子树是一边高一边低,然后插入刚好插到了低的一边,使其平衡.插入结束.
  

旋转操作

分析需要旋转的情况

起首，要针对AVL子树，找出/抽象出可能发生旋转的情况。
一棵可能发生旋转的树至少高度差为1，即两个结点以上。（前提）

1.                                                 （可能会发生旋转的子树至少两个结点以上）

复制代码

​
其中a,b,c是三棵AVL子树

• 当子树高度h==0时,即a、b、c都为空树
  
• 当子树高度h==1时,a、b、c都是叶子结点
  
• 当子树高度h==2时,a、b、c分别有三种情况
  
  
  
  此时这个AVL子树有3*3*3=27种情况：a为x/y/z，b为x/y/z，c为x/y/z。
  
• 云云往下，还有更多的情况，但全部形状都可以用图中模型来取代。
  

以h==2为例，只有当b或c为z情况时，插入到b或c子树会影响到根结点（30），并使其发生旋转。
其他情况都无法使其发生旋转。因此，当前可以总结出2种需要旋转的情况：

• c为z时，插到c中（左左）
  
• b为z时，插到b中（左右）
  

左左：较高的子树是左孩子（60）所在子树，插到左孩子（60）的左子树上（c）引发根（30）旋转的情况叫“左左”。
顺口：插在较高左子树的左孩子上。

同理，水平镜像翻转的AVL子树也同理

• c为z时，插到c中（右右）
  
• b为z时，插到b中（右左）
  

结论

合并起来总共4种需要旋转的情况，验证其他高度也同样云云。

其中插入b子树使30结点发生旋转的情况：a为x/y/z，b为z，c为x/y/z，总共3*3=9种
其中插入c子树使30结点发生旋转的情况：a为x/y/z，b为x/y/z，c为z，总共3*3=9种
特例的数量非常多，无法穷举。

4种旋转操方法与特性

• 新节点插入较高左子树的左侧---左左：右单旋
  
  
  
  • 特性
    父：-2
    子：-1
    
  
  
  最左边高，旧根的左孩子变成新根，旧根成为新根的右孩子，同时领养新根的旧右孩子。
  

  儿子上位 -- 儿子当根
  右单旋（主角是儿子）：老爹在我的右上方，让老爹以我为轴，旋转到我的右下方
  

  
  
• 新节点插入较高右子树的右侧---右右：左单旋
  
  
  
  • 特性
    父：2
    子：1
    
  
  
  最右边高，旧根的右孩子变成新根，旧根成为新根的左孩子，同时领养新根的旧左孩子。
  
  
• 新节点插入较高左子树的右侧---左右：先左单旋再右单旋
  
  
  
  • 特性
    父：-2
    子：1
    
  
  
  
  
  
  • 旧根的左儿子的右孩子（简称右孙子）高：让右孙子成为旧根的左孩子，旧左孩子变成孙子的左孩子，同时领养孙子的左孩子。 -- 对右孙子做左旋操作
    
  • 右孙子成为旧根的新左儿子，再对新作儿子做右旋操作即可。
    

  孙子上位 --- 孙子当根
  感性描述：先左单旋再右单旋（孙子是主角）：我在孙子左边，我的老爹在孙子右边，然后让孙子的爹（我）左旋下来，孙子成为我的爹，我的旧爹成为孙子的爹；末了再让孙子的新爹右旋下来。
  描述2： 两次旋转分别用途： 1. 转化成标准单旋； 2.标准单旋
  

  
  
• 新节点插入较高右子树的左侧---右左：先右单旋再左单旋
  
  
  
  • 特性
    父：2
    子：-1
    
  
  
  
  

总共4种旋转的情况：

• 右旋（左左）
  
• 左旋（右右)
  
• 先左旋再右旋（左右）
  
• 先右旋再左旋（右左）
  

简要图：

6种双旋平衡因子特性

容易发现单旋平衡因子都是0（高度差为0），而双旋平衡因子较为复杂，观察规律总结出一共6种情况。

• 左右左（h>0)
  
  
  
  • 旧（特性）
    孙：-1
    
  • 新
    父：1
    子：0
    孙：0
    
  
  
  
  
• 左右右(h>0)
  
  
  
  • 旧（特性）
    孙：1
    
  • 新
    父：0
    子：-1
    孙：0
    
  
  
  
  

• 右左右（h>0）
  
  
  
  • 旧（特性）
    孙：1
    
  • 新
    父：-1
    子：0
    孙：0
    
  
  
  
  
• 右左左（h>0）
  
  
  
  • 旧（特性）
    孙：-1
    
  • 新
    父：0
    子：1
    孙：0
    
  
  
  
  
• 左右，特例（h==0)
  
  
  
  • 旧（特性）
    孙：0
    
  • 新
    父：0
    子：0
    孙：0
    
  
  
  
  
• 右左（h==0)，与5相同
  
  
  
  • 旧（特性）
    孙：0
    
  • 新
    父：0
    子：0
    孙：0
    
  
  

代码实现

四种旋转实现

1. //1. 右右
2.     void RotateL(Node* parent) {
3.         //. 记录爷爷(父亲的父亲)
4.         //. 我是父的右儿子(我是主角)
5.         //. 记录下我的左子树(托管)
6.         //  旋转(爷、父、子关系重新调整）
7.         //      成为爷爷的右儿子 (如果没有爷爷,则跳过;且说明父是根,更新我成为根)
8.         //      把我的左子树托管给父成为他的右孩子
9.         //      旧父成为我的左儿子,旧父的父更新成我
10.         //. 更新平衡因子
11.               
12.         //. 记录爷爷(父亲的父亲)
13.         //. 我是父的右儿子
14.         //. 记录下我的左子树
15.         Node* pparent = parent->_parent;
16.         Node* cur = parent->_right;
17.         Node* leftchild = cur->_left;
19.         //旋转
20.         //. 成为爷爷的右儿子 (如果没有爷爷,则跳过;且说明父是根,更新我成为根)
21.         if (pparent) {              //有爷爷
22.             if(parent == pparent->_left)
23.                 pparent->_left = cur;
24.             else {
25.                 pparent->_right = cur;
26.             }
27.             cur->_parent = pparent; //三叉链维护
28.         }
29.         else {                      //没有爷爷,父亲是根
30.             cur->_parent = nullptr;
31.             _root = cur;
32.         }
33.         //. 父子地位交换
34.         parent->_right = leftchild;
35.         if (leftchild) {            //三叉链维护
36.             leftchild->_parent = parent;
37.         }
38.         cur->_left = parent;
39.         parent->_parent = cur;
40.         //旋转 【end】
42.         //更新平衡因子
43.         cur->_bf = 0;
44.         parent->_bf = 0;
45.     }
48. //2. 左左
49.     void RotateR(Node* parent) {
50.         //. 记录爷爷
51.         //. 我是父的左儿子
52.         //. 记录下我的右子树
53.         Node* pparent = parent->_parent;
54.         Node* cur = parent->_left;
55.         Node* rightChild = cur->_right;
57.         //旋转
58.         //. 成为爷爷的左儿子 (如果没有爷爷,则跳过;且说明父是根,更新我成为根)
59.         if (pparent) {              //有爷爷
60.             if (parent == pparent->_left)
61.                 pparent->_left = cur;
62.             else {
63.                 pparent->_right = cur;
64.             }
65.             cur->_parent = pparent; //三叉链维护
66.         }
67.         else {                      //没有爷爷,父亲是根
68.             cur->_parent = nullptr;
69.             _root = cur;
70.         }
71.         //. 父子地位交换
72.         parent->_left = rightChild;
73.         if (rightChild) {            //三叉链维护
74.             rightChild->_parent = parent;
75.         }
76.         cur->_right = parent;
77.         parent->_parent = cur;
78.         //旋转 【end】
80.         //更新平衡因子
81.         cur->_bf = 0;
82.         parent->_bf = 0;
84.     }
85. //3. 左右
86.     void RotateLR(Node* parent) {
87.         //我是儿子,但是主角是孙子
88.         //记录下孙子
89.         //记录下孙子的平衡因子(特征)
90.         //对孙子进行左单旋,再右旋
91.         //更新平衡因子
92.         Node* cur = parent->_left;
93.         Node* grandson = cur->_right;
94.         int bf = grandson->_bf;
96.         RotateL(cur);
97.         RotateR(grandson->_parent);
99.         //三种情况
100.         if (bf == 0) {
101.             parent->_bf = 0;
102.             cur->_bf = 0;
103.             grandson->_bf = 0;
104.         }
105.         else if (bf == 1) {
106.             parent->_bf = 0;
107.             cur->_bf = -1;
108.             grandson->_bf = 0;
109.         }
110.         else if (bf == -1) {
111.             parent->_bf = 1;
112.             cur->_bf = 0;
113.             grandson->_bf = 0;
114.         }
115.         else {
116.             assert(false); //错误检查
117.         }
118.     }
120. //4. 右左
121.     void RotateRL(Node* parent) {
122.         //我是儿子(父的右孩子),但是主角是孙子
123.         //记录下孙子(我的左孩子)
124.         //记录下孙子的平衡因子(特征)
125.         //对孙子进行右单旋,再左单旋
126.         //更新平衡因子
127.         Node* cur = parent->_right;
128.         Node* grandson = cur->_left;
129.         int bf = grandson->_bf;
131.         RotateR(cur); //将孙子的爹,就是我,进行右单旋
132.         RotateL(grandson->_parent); //将儿子的新爹进行左单旋
134.         //三种情况
135.         if (bf == 0) {
136.             parent->_bf = 0;
137.             cur->_bf = 0;
138.             grandson->_bf = 0;
139.         }
140.         else if (bf == 1) {
141.             parent->_bf = -1;
142.             cur->_bf = 0;
143.             grandson->_bf = 0;
144.         }
145.         else if (bf == -1) {
146.             parent->_bf = 0;
147.             cur->_bf = 1;
148.             grandson->_bf = 0;
149.         }
150.         else {
151.             assert(false);
152.         }
153.     }

复制代码

插入操作实现

1.     bool Insert(const std::pair<K,V> kv) {
2.         //第一个结点做根
3.         if (_root == nullptr) {
4.             _root = new Node(kv);
5.             _size++;
6.             return true;
7.         }
9.         //搜索
10.         Node* parent = _root;
11.         Node* cur = _root;
12.         while (cur) {
13.             //大于往右走
14.             if (kv.first > cur->_kv.first) {
15.                 parent = cur;
16.                 cur = cur->_right;
17.             }
18.             //小于往左走
19.             else if (kv.first < cur->_kv.first) {
20.                 parent = cur;
21.                 cur = cur->_left;
22.             }
23.             //找到了,存在相同的key
24.             else {
25.                 return false;
26.             }
27.         } //循环搜索...
29.         //不存在,可以插入
30.         cur = new Node(kv);                         //new后,cur值发生改变,之后都不能使用地址进行比较
31.         if (cur->_kv.first < parent->_kv.first) {
32.             parent->_left = cur;
33.         }
34.         else {
35.             parent->_right = cur;
36.         }
37.         cur->_parent = parent; //三叉链链上父结点
38.         _size++;
40.         //调整平衡因子 : 最多到根,根的parent为nullptr
41.         while (parent) {
43.             //更新平衡因子
44.             if (cur->_kv.first < parent->_kv.first) {
45.                 parent->_bf--;
46.             }
47.             else {
48.                 parent->_bf++;
49.             }
51.             //看是否需要调整
52.             if (parent->_bf == 1 || parent->_bf == -1) {
53.                 cur = parent;
54.                 parent = parent->_parent;
55.             }
56.             else if(parent->_bf == 0){
57.                 break;
58.             }
59.             else if(parent->_bf == 2 || parent->_bf == -2){
60.                 if (parent->_bf == -2 && cur->_bf == -1) {      //左左
61.                     RotateR(parent);
62.                 }
63.                 else if (parent->_bf == 2 && cur->_bf == 1) {   //右右
64.                     RotateL(parent);
65.                 }
66.                 else if (parent->_bf == -2 && cur->_bf == 1) {  //左右
67.                     RotateLR(parent);
68.                 }
69.                 else if(parent->_bf == 2 && cur->_bf == -1){    //右左
70.                     RotateRL(parent);
71.                 }
72.                 else {                                          //错误检查
73.                     assert(false);
74.                 }
75.                 break;
76.             }
77.             else {
78.                 assert(false);
79.             }
80.         }
82.         return true;
83.     }

复制代码

树高度与是否平衡树判断实现

1.     size_t Hight() {
2.         return _Hight(_root);
3.     }
5.     bool IsBalance() {
6.         return _IsBalance(_root);
7.     }
8.    
9.     size_t _Hight(Node* root) {
10.         if (root == 0) return 0;                //空
11.         size_t leftH = _Hight(root->_left);
12.         size_t rightH = _Hight(root->_right);
13.         return std::max(leftH, rightH) + 1;     //+1:自己高度为1
14.     }
16.     bool _IsBalance(Node* root) {
17.         if (root == nullptr) return true;
18.         int leftH = _Hight(root->_left);
19.         int rightH = _Hight(root->_right);
20.         int bf = rightH-leftH;
21.         return  bf == root->_bf         //平衡因子
22.             && (bf > -2 && bf < 2)      //高度差
23.             && _IsBalance(root->_left)  
24.             && _IsBalance(root->_right);
25.     }

复制代码

其他实现

[code]#include#include#includetemplatestruct AVLTreeNode {        //三叉链    AVLTreeNode* _left;    AVLTreeNode* _right;    AVLTreeNode* _parent;    int _bf; //balance factor    std::pair _kv;    AVLTreeNode(const std::pair& kv)        :_left(nullptr),        _right(nullptr),        _parent(nullptr),        _bf(0),        _kv(kv)    {}};templateclass AVLTree {public:    using Node = AVLTreeNode;    AVLTree()    :_root(nullptr)    ,_size(0)    {}public:    void InOrder() {        _InOrder(_root);        std::cout