【C++模拟实现】手撕AVL树

【C++模拟实现】手撕AVL树

作者：爱写代码的刚子

时间：2023.9.10

前言：本篇博客将会介绍AVL树的模拟实现(模拟AVL树的插入)，以及如何去验证是否为AVL树

AVL树的介绍（百度百科）

AVL树本质上还是一棵二叉搜索树，它的特点是：

1. 本身首先是一棵二叉搜索树。

2. 带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。

AVL树insert函数的实现代码

template<class K,class V>
class AVLTreeNode
{
public:
    AVLTreeNode(const pair<K,V>& kv)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_kv(kv)
    ,_bf(0)
    {}
    
    AVLTreeNode* _left;
    AVLTreeNode* _right;
    AVLTreeNode* _parent;//需要设立父节点指针
    pair<K,V> _kv;

    int _bf;
};

template<class K,class V>
class AVLTree
{
    typedef AVLTreeNode<K,V> Node;
public:
    AVLTree()
    :_root(nullptr)
    {}

    
    bool insert(const pair<K,V>& kv)
    {
        if(_root==nullptr)
        {
            _root=new Node(kv);
            return true;
        }
        else
        {
            Node* cur=_root;
            Node* parent=nullptr;//设计parent指针是必要的
            while(cur)
            {
                if(cur->_kv.first>kv.first)
                {
                    parent=cur;
                    cur=cur->_left;
                }
                else if(cur->_kv.first<kv.first)
                {
                    parent=cur;
                    cur=cur->_right;
                }
                else{
                    return false;
                }
            }
            cur=new Node(kv);
          
          //判断新加入的节点是父节点的左子树还是右子树
            if(parent->_kv.first>kv.first)
            {
                parent->_left=cur;
            }
            else{
                parent->_right=cur;
            }
            cur->_parent=parent;
            
            while(parent)
            {
              //及时调整父节点的平衡因子
                if(parent->_left==cur)
                {
                    --parent->_bf;
                }
                else{
                    ++parent->_bf;
                }

                if(parent->_bf==0)//当父节点的平衡因子为0时停止调整
                {
                    break;
                }
                else if(parent->_bf==-1||parent->_bf==1)
                {
                    cur=parent;
                    parent=parent->_parent;
                }
                else if(parent->_bf==2||parent->_bf==-2)//处理异常情况
                {
                    //出现问题的情况
                    if(parent->_bf==-2&&cur->_bf==-1)
                    {
                        _RotateR(parent);//右单旋
                    }
                    else if(parent->_bf==2&&cur->_bf==1)
                    {
                        _RotateL(parent);//左单旋
                    }
                    else if(parent->_bf==-2&&cur->_bf==1)
                    {   
                        _RotateLR(parent);//左右双旋

                    }
                    else if(parent->_bf==2&&cur->_bf==-1)
                    {
                        _RotateRL(parent);//右左双旋
                    }
                    else
                    {
                        assert(false);
                    }


                    break;

                }
                else{
                    assert(false);
                }
                
            }
        }
        return true;
    } 
    

    void _RotateR(Node* parent)//右单旋的实现
    {
        Node*cur=parent->_left;
        Node*curRight=cur->_right;
        Node*ppnode=parent->_parent;
        
        
        cur->_right=parent;
        parent->_left=curRight;

        if(curRight)//curRight可能是nullptr
        {
            curRight->_parent=parent;
        }
        parent->_parent=cur;
        
        //处理ppnode
        if(parent==_root)//parent为头节点时需要单独处理
        {
            _root=cur;
            cur->_parent=nullptr;

        }
        else
        {
            if(ppnode->_left==parent)
            {
                ppnode->_left=cur;
            }
            else{
                ppnode->_right=cur;
            }
            cur->_parent=ppnode;
        }
        parent->_bf=cur->_bf=0;

    }
    void _RotateL(Node* parent)
    {
        Node* cur=parent->_right;
        Node* curLeft=cur->_left;
        Node* ppnode=parent->_parent;

        cur->_left=parent;
        parent->_right=curLeft;

        if(curLeft)
        {
            curLeft->_parent=cur;
        }
        parent->_parent=cur;

        if(parent==_root)
        {
            _root=cur;
            cur->_parent=nullptr;
        }
        else
        {
            if(ppnode->_left==parent)
            {
                ppnode->_left=cur;
            }
            else{
                ppnode->_right=cur;
            }
            cur->_parent=ppnode;
        }
        parent->_bf=cur->_bf=0;
    }
    void _RotateLR(Node* parent)
    {
        Node* cur=parent->_left;
        Node* curRight=cur->_right;
        int bf=curRight->_bf;

        _RotateL(cur);
        _RotateR(parent);

        //最好再处理一下平衡因子，减少耦合度
        if(bf==0)//单链情况下
        {
            parent->_bf=0;
            cur->_bf=0;
            curRight->_bf=0;
        }
        else if(bf==-1)
        {
            parent->_bf=1;
            curRight->_bf=0;
            cur->_bf=0;
        }
        else if(bf==1)
        {
            parent->_bf=-1;
            curRight->_bf=0;
            cur->_bf=0;
        }
        else{
            assert(false);
        }
    }
    void _RotateRL(Node* parent)
    {
        Node* cur=parent->_right;
        Node* curLeft=cur->_left;
        int bf=curLeft->_bf;

        _RotateR(cur);
        _RotateL(parent);

        if(bf==0)
        {
            parent->_bf=0;
            curLeft->_bf=0;
            cur->_bf=0;
        }
        else if(bf==1)
        {
            parent->_bf=0;
            curLeft->_bf=-1;
            cur->_bf=0;
        }
        else if(bf==-1)
        {
            parent->_bf=0;
            curLeft->_bf=1;
            cur->_bf=0;
        }
        else{
            assert(false);
        }
        
    }
  private:
    


    Node* _root;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269

验证是否为AVL树

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;
    }
    

    bool _Isbalance()
    {
        return _Isbalance(_root);
    }
    bool _Isbalance(Node* root)
    {
        if(root==nullptr)
        {
            return true;
        }

        int right=_Height(root->_right);
        int left=_Height(root->_left);

        if(root->_bf!=right-left)
        {
            cout<<"平衡因子异常"<<root->_bf<<" "<<right<<" "<<left<<endl;
            return false;
        }

        return abs(right-left)<2&&_Isbalance(root->_left)&&_Isbalance(root->_right);


    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

• 根据AVL树的特性引入两个成员函数_Height函数用于计算二叉树的高度

• 以下为验证结果：
  

AVL树模拟实现的要点

易忘点

一定要时刻注意_parent指针的修改！尤其旋转函数中需要判断旋转后的二叉树的根节点是否还有父亲节点，如果有，需要在旋转前先保存，之后再链接上。

AVL树的旋转思路

1. 新增在左，parent平衡因子减减
2. 新增在右，parent平衡因子加加
3. 更新后parent平衡因子 == 0，说明parent所在的子树的高度不变，不会再影响祖先，不用再继续沿着到eot的路径往上更新
4. 更新后parent平衡因子 == 1 0r -1，说明parent所在的子树的高度变化，会再影响祖先，需要继续沿着到root的路径往上更新更新后
5. 更新后parent平衡因子 == 2 or -2，说明parent所在的子树的高度变化且不平衡，对parent所在子树进行旋转，让他平衡
6. 更到根节点，插入结束

---

由于AVL树画图较为麻烦，作者先不画了，可以看看其他大佬的博客，一些需要注意的地方已经写在代码注释里了，AVL树的删除之后有机会可以模拟实现一下。
AVL树的调试较为麻烦，模拟实现可以提高自己的调试能力。