一个简单的AVL树的实现

上一篇文章实现了一个最简单的二叉搜索树,里面理由两个成员函数:插入和中序遍历。我觉得,插入应该算是BSTreet中最核心的一个函数了。

二叉搜索树虽然是一颗排序树,但当数据的插入顺序基本逆序时,BSTreet就退化为一个很近似链表的结构。而链表中查找的时间复杂度为O(n),显然这失去了二叉搜索树O(lgN)的优势。

因此我们可以对BSTree进行改进,使之成为一个平衡的二叉搜索树,即AVL树。 <!--more-->

AVL树的特点是:

  • 左子树和右子树的高度之差不超过1;
  • 左子树和右子树都是AVL树;

当我们插入一个数,使得AVL树不满足以上条件时,需要对其进行旋转。具体可见如下代码:

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
#pragma once
#include&lt;iostream&gt;
using namespace std;
namespace NonRecursion
{
template&lt;typename K,typename V&gt;
struct AVLTreeNode{
K _key;
V _value;
AVLTreeNode&lt;K,V&gt;* _parent;
AVLTreeNode&lt;K,V&gt;* _left;
AVLTreeNode&lt;K,V&gt;* _right;
int _bf;
AVLTreeNode(const K&amp; key,const V&amp; value)
:_key(key),_value(value),_parent(NULL),_left(NULL),_right(NULL),_bf(0)
{}
};
template&lt;typename K,typename V&gt;
class AVLTree{
typedef AVLTreeNode&lt;K,V&gt; Node;
public:
AVLTree()
:_root(NULL)
{}
~AVLTree()
{
_erase(_root);
}
bool Insert(const K&amp; key,const V&amp; value)
{
//1.空树
//2.查找位置
//3.插入节点
//4.更新平衡因子,调整树
//5.如果进行了旋转调整,则将parent进行重新连接
if(_root==NULL)
{
_root=new Node(key,value);
return true;
}
Node* parent=NULL;
Node* cur=_root;
//插入节点
while(cur!=NULL)
{
if(cur-&gt;_key&lt;key)
{
parent=cur;
cur=cur-&gt;_right;
}
else if(cur-&gt;_key&gt;key)
{
parent=cur;
cur=cur-&gt;_left;
}
else
return false;
}
cur=new Node(key,value);
if(parent-&gt;_key&lt;key)
parent-&gt;_right=cur;
else
parent-&gt;_left=cur;
cur-&gt;_parent=parent;
//调节平衡因子
while(parent!=NULL)
{
if(cur==parent-&gt;_left)
parent-&gt;_bf--;
else
parent-&gt;_bf++;
/* parent-&gt;_bf==0:break;
* parent-&gt;_bf==1/-1:continue go up;
* parent-&gt;_bf==2/-2:rotate;
*/
if(parent-&gt;_bf==0)
break;
else if(parent-&gt;_bf==1 || parent-&gt;_bf==-1)
{
cur=parent;
parent=parent-&gt;_parent;
}
else //parent-&gt;_bf==2/-2
{
if(parent-&gt;_bf==2)
{
if(cur-&gt;_bf==1)
_RotateL(parent);
else
_RotateRL(parent);
}
else
{
if(cur-&gt;_bf==-1)
_RotateR(parent);
else
_RotateLR(parent);
}
break;
}
}
return true;
}
Node* Find(const K&amp; key)
{
Node* cur=_root;
while(cur!=NULL)
{
if(cur-&gt;_key==key)
return cur;
else if(cur-&gt;key&gt;key)
cur=cur-&gt;_left;
else
cur=cur-&gt;_right;
}
return NULL;
}
void InOrder()
{
_InOrder(_root);
cout&lt;&lt;endl;
}
bool IsBalance()
{
int depth=0;
return _IsBalance(_root,depth);
}
bool Remove(const K&amp; key);
//////////////////////////////////////////////////////////////////////////////////
protected:
bool _IsBalance(Node* root,int&amp; depth)
{
if(root==NULL)
{
depth=0;
return true;
}
int left,right;
if(_IsBalance(root-&gt;_left,left) &amp;&amp; _IsBalance(root-&gt;_right,right))
{
depth=left&gt;right?left+1:right+1;
if(root-&gt;_bf==right-left)
return true;
else
return false;
}
return false;
}
void _InOrder(Node* root)
{
if(root==NULL)
return;
_InOrder(root-&gt;_left);
cout&lt;&lt;root-&gt;_key&lt;&lt;" ";
_InOrder(root-&gt;_right);
}
void _RotateL(Node* root)
{
if(root==NULL)
return;
Node* parent=root;
Node* subR=parent-&gt;_right;
Node* subRL=subR-&gt;_left;
parent-&gt;_right=subRL;
if(subRL!=NULL)
subRL-&gt;_parent=parent;
Node* ppNode=parent-&gt;_parent;
subR-&gt;_left=parent;
parent-&gt;_parent=subR;
if(ppNode!=NULL)
{
if(ppNode-&gt;_left==parent)
ppNode-&gt;_left=subR;
else
ppNode-&gt;_right=subR;
}
else
{
_root=subR;
}
subR-&gt;_parent=ppNode;
parent-&gt;_bf = subR-&gt;_bf = 0;
//parent-&gt;_bf--;
//subR-&gt;_bf--;
}
void _RotateR(Node* root)
{
if(root==NULL)
return;
Node* parent=root;
Node* subL=parent-&gt;_left;
Node* subLR=subL-&gt;_right;
parent-&gt;_left=subLR;
if(subLR!=NULL)
subLR-&gt;_parent=parent;
Node* ppNode=parent-&gt;_parent;
subL-&gt;_right=parent;
parent-&gt;_parent=subL;
if(ppNode!=NULL)
{
if(ppNode-&gt;_left==parent)
ppNode-&gt;_left=subL;
else
ppNode-&gt;_right=subL;
}
else
{
_root=subL;
}
subL-&gt;_parent=ppNode;
parent-&gt;_bf = subL-&gt;_bf = 0;
//parent-&gt;_bf++;
//subL-&gt;_bf++;
}
void _RotateRL(Node* root)
{
if(root==NULL)
return;
Node* parent=root;
Node* subR=parent-&gt;_right;
Node* subRL=NULL;
if(subR!=NULL)
subRL=subR-&gt;_left;
_RotateR(subR);
_RotateL(parent);
}
void _RotateLR(Node* root)
{
if(root==NULL)
return;
Node* parent=root;
Node* subL=parent-&gt;_left;
_RotateL(subL);
_RotateR(parent);
}
void _erase(Node* root)
{
if(root==NULL)
return;
_erase(root-&gt;_left);
_erase(root-&gt;_right);
delete root;
}
private:
Node* _root;
};
}

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往