本文最后更新于：1 年前
AVLTree旋转树 - 应对面试中的数据结构问题
AVL树是根据它的发明者G. M. Adelson-Velskii和E. M. Landis命名的。它是一种特殊的二叉搜索树。AVL树要求: 任一节点的左子树深度和右子树深度相差不超过1
(空树的深度为0。注意，有的教材中，采用了不同的深度定义方法，所以空树的深度为-1)
下面是AVL树:
我们可以发现，左边高，它的高度差就是 -1，右边高，高度差就是1。两边一样高，那么高度差就是 0 。所以我们可以用平衡因子，来确定它的一个高度差。这样可以更好的控制它的高度。
AVL树的节点创建
为了更好的控制，我们决定使用三叉链。也就是新增一个parent节点指向自己的父亲，根节点的父亲为空指针。而我们还要一个平衡因子变量，来记录它子树的高度差。left和right指针指向左右两个孩子。这里我们采取key,value模型，所以用pair结构体，作为节点的值。
节点结构体代码：
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
|
struct AVLNode {
int val;
int height;
AVLNode* left;
AVLNode* right;
AVLNode(int v) : val(v), height(1), left(nullptr), right(nullptr) {}
};
template<class K,class V>
struct AVLNode
{
AVLNode<K, V>* _left;
AVLNode<K, V>* _right;
AVLNode<K, V>* _parent;
int _bf;
pair<K, V> _kv;
AVLNode(const pair<K,V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
,_kv(kv){}
};
|
AVL类创建
只需要一个成员变量 root 来指向整颗树的根即可。构造函数就把root初始化为空。
1
2
3
4
5
6
7
8
9
| template <class K, class V>
class AVLTree
{
typedef AVLNode<K, V> Node;
public:
AVLTree() :_root(nullptr){}
private:
Node* _root;
};
|
AVL树的插入
AVL树的插入，我们要先找到可以插入的位置，然后插入。插入之后我们树的高度可能会发生变化，因此我们需要向上去更新平衡因子。所以我们插入后分多种情况，那就是插入后平衡因子为 0, 1/-1 ，2/-2的情况
插入后平衡因子为0的情况：
插入后平衡因子为0，那么说明在插入之前，这颗树的平衡因子是 -1 或者1，所以在插入之后这棵树的平衡因子变成了0，那么就意味着这棵树已经平衡了，这种情况就不需要做什么事情了。
插入后平衡因子为1/-1的情况：
如果插入和平衡因子为1或者-1，说明在插入之前这棵树的平衡因子是0。也就是说插入之前这颗树是平衡的，而插入之后，引发了高度变化。所以可能会造成不平衡的情况，这种情况我们需要一种往上更新平衡因子。在更新的过程可能会遇到平衡因子变成 2 或者 -2的情况，这时候就需要发生旋转。
插入后平衡因子为2/-2的情况：
在插入的过程中，平衡因子可能会出现为2/-2的情况。当平衡因子为1/-1的时候，会一直往上更新，而在更新的过程中就会发生平衡因子为 2/-2的情况，这种情况我们就需要发生旋转。
假设我们插入一个10，那么10插入的位置应该在 8的右边。
那么此时 8 的左右子树高度发生了变化，因为插入了一个新节点。如果新增节点在右边，则 平衡因子自减，如果新增节点在右边，则平衡因子自增。所以新增后，平衡因子的变化是。
也就是，7所在的节点的子树不平衡了，因为它的平衡因子 > 1了。所以此时我们要发生旋转。而旋转有四种情况。
第一种情况，右边一边高
就如上图的情况，7所在节点的右子树右边一边高，所以这时候我们需要左旋转。那么我们假设7节点为parent。7的右节点8为subR，8的左节点为subRL，而7的父节点为grandparent
左单旋的步骤:
1.让parent的右节点连接subRL
2.subRL的父节点连接parent，如果为空则不连接
3.subR的左节点连接parent
4.parent的父节点连接subR
5.grandparent与subR连接
旋转流程图
最后，我们会发现parent和subR的平衡因子都变了0。也就意味着这颗子树达到了平衡。
左旋转代码：
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
|
void RotateL(Node* parent)
{
Node* grandparent = parent->_parent;
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
if (grandparent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parent == grandparent->_left)
grandparent->_left = subR;
else
grandparent->_right = subR;
subR->_parent = grandparent;
}
parent->_bf = subR->_bf = 0;
}
|
第二种情况：左边一边高
左边一边高和右边一边高的思路完全一样。只不过方向反过来。。下面这棵树就是左边一边高，所以我们用右单旋进行调整。
右单旋的步骤:
1.让parent的左节点连接subLR
2.subLR的父节点连接parent，如果为空则不连接
3.subL的右节点连接parent
4.parent的父节点连接subL
5.grandparent与subL连接
右单旋旋转动图:
右单旋代码：
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
|
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* grandpraent = parent->_parent;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
parent->_parent = subL;
if (grandpraent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (grandpraent->_left == parent)
grandpraent->_left = subL;
else
grandpraent->_right = subL;
subL->_parent = grandpraent;
}
subL->_bf = parent->_bf = 0;
}
|
第三种情况：新节点插入较高左子树的右侧—左右
一边高是直线，曲线就是整棵树是左边高，但是它的孩子却在和它相反的一边。这就意味着这棵树是曲线的，所以单纯的左右旋转无法使它达到平衡。而旋转完后，我们还需要控制平衡因子，控制平衡因子又有三种情况。
情况1.当subL右节点的平衡因子为0时(也就是新增)
把subL左旋转后
随后这颗树就变成了左边一边高，我们再把parent右旋转。
这种情况下，新增节点，subL，parent的平衡因子都变成了0。
情况2.subL的右节点平衡因子为-1时
和之前一样，先把subL左旋转
再把parent右旋转
旋转后
subL的平衡因子为0
subLR的平衡因子为0
parent的平衡因子为1
情况3.subL的右节点平衡因子为1时
老规矩，把subL进行左单旋
再把parent右单旋
旋转后
subL的平衡因子为-1
subLR的平衡因子为0
parent的平衡因子为0
左右双旋代码:
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
| void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int lrbf = subLR->_bf;
RotateL(subL);
RotateR(parent);
if (lrbf == 0)
{
parent->_bf = subL->_bf = subLR->_bf = 0;
}
else if (lrbf == -1)
{
subL->_bf = subLR->_bf = 0;
parent->_bf = 1;
}
else if (lrbf == 1)
{
subL->_bf = -1;
subLR->_bf = parent->_bf = 0;
}
else
assert(false);
}
|
第四种情况：新节点插入较高右子树的左侧—右左
这种情况和第三种情况相反，但也另外分了三种情况。
情况1.subRL就是新增节点
先右旋转subR
再左旋转parent
旋转完后，subRL和subR还有parent的平衡因子都为0。
情况2.当在subRL的平衡因子为-1时
先右单旋subR
再左单旋parent
最后的平衡因子分别为:
subRL 0
parent 0
subR 1
情况3.当在subRL的平衡因子为1时
老规矩，先右旋 subR
然后左旋转parent
最后的平衡因子分别是：
parent -1
subRL 0
subR 0
右左双旋代码:
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
|
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int rlbf = subRL->_bf;
RotateR(subR);
RotateL(parent);
if (rlbf == 0)
{
subR->_bf = subRL->_bf = parent->_bf = 0;
}
else if (rlbf == -1)
{
subRL->_bf = parent->_bf = 0;
subR->_bf = 1;
}
else if (rlbf == 1)
{
parent->_bf = -1;
subR->_bf = subRL->_bf = 0;
}
else
assert(false);
}
|
检查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
| bool IsBalance()
{
return _IsBalance(_root);
}
bool _IsBalance(Node* root)
{
if (root == nullptr)
return true;
int LeftHeight = _Height(root->_left);
int RightHeight = _Height(root->_right);
if (root->_bf != RightHeight - LeftHeight)
{
cout << root->_kv._first <<"现在是平衡因子是:" << root->_bf << endl;
cout << root->_kv._first <<"平衡因子应该是:" << RightHeight - LeftHeight << endl;
}
return abs(LeftHeight - RightHeight) < 2;
}
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;
}
|
查找值
直接查找即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
bool Find(const K& k)
{
if (_root == nullptr)
return false;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > k)
cur = cur->_left;
else if (cur->_kv.first < k)
cur = cur->_right;
else
return true;
}
return false;
}
|
全部代码：
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
|
template<class K, class V>
struct AVLNode
{
AVLNode<K, V>* _left;
AVLNode<K, V>* _right;
AVLNode<K, V>* _parent;
int _bf;
pair<K, V> _kv;
AVLNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
, _kv(kv) {}
};
template <class K, class V>
class AVLTree
{
typedef AVLNode<K, V> Node;
public:
AVLTree() :_root(nullptr){}
bool insert(const pair<K,V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
parent = cur;
if (cur->_kv.first > kv.first)
cur = cur->_left;
else if (cur->_kv.first < kv.first)
cur = cur->_right;
else
return false;
}
cur = new Node(kv);
cur->_parent = parent;
if (cur->_kv.first > parent->_kv.first)
parent->_right = cur;
else
parent->_left = cur;
while (parent)
{
if (cur == parent->_right)
parent->_bf++;
else
parent->_bf--;
if (parent->_bf == 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)
RotateL(parent);
else if (parent->_bf == -2 && cur->_bf == -1)
RotateR(parent);
else if (parent->_bf == -2 && cur->_bf == 1)
RotateLR(parent);
else if (parent->_bf == 2 && cur->_bf == -1)
RotateRL (parent);
break;
}
else
assert(false);
}
}
void RotateL(Node* parent)
{
Node* grandparent = parent->_parent;
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
if (grandparent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parent == grandparent->_left)
grandparent->_left = subR;
else
grandparent->_right = subR;
subR->_parent = grandparent;
}
parent->_bf = subR->_bf = 0;
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* grandpraent = parent->_parent;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
parent->_parent = subL;
if (grandpraent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (grandpraent->_left == parent)
grandpraent->_left = subL;
else
grandpraent->_right = subL;
subL->_parent = grandpraent;
}
subL->_bf = parent->_bf = 0;
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int lrbf = subLR->_bf;
RotateL(subL);
RotateR(parent);
if (lrbf == 0)
{
parent->_bf = subL->_bf = subLR->_bf = 0;
}
else if (lrbf == -1)
{
subL->_bf = subLR->_bf = 0;
parent->_bf = 1;
}
else if (lrbf == 1)
{
subL->_bf = -1;
subLR->_bf = parent->_bf = 0;
}
else
assert(false);
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int rlbf = subRL->_bf;
RotateR(subR);
RotateL(parent);
if (rlbf == 0)
{
subR->_bf = subRL->_bf = parent->_bf = 0;
}
else if (rlbf == -1)
{
subRL->_bf = parent->_bf = 0;
subR->_bf = 1;
}
else if (rlbf == 1)
{
parent->_bf = -1;
subR->_bf = subRL->_bf = 0;
}
else
assert(false);
}
bool Find(const K& k)
{
if (_root == nullptr)
return false;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > k)
cur = cur->_left;
else if (cur->_kv.first < k)
cur = cur->_right;
else
return true;
}
return false;
}
bool IsBalance()
{
return _IsBalance(_root);
}
bool _IsBalance(Node* root)
{
if (root == nullptr)
return true;
int LeftHeight = _Height(root->_left);
int RightHeight = _Height(root->_right);
if (root->_bf != RightHeight - LeftHeight)
{
cout << root->_kv.first << "现在是平衡因子是:" << root->_bf << endl;
cout << root->_kv.first << "平衡因子应该是:" << RightHeight - LeftHeight << endl;
}
return abs(LeftHeight - RightHeight) < 2;
}
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;
}
private:
Node* _root;
};
|