AVL树——自平衡的二叉搜索树_自平衡树

AVL树

1. AVL树的概念

• 命名由来
  AVL树，由Georgy Adelson-Velsky 和 Evgenii Landis 发明，命名也是取自他们两人的名字AVL。
• AVL树是什么？
  AVL树其实是一棵：自平衡的二叉搜索树，也叫高度平衡树。
  它是数据结构中最早出现的一棵自平衡的二叉搜索树。

下面我们通过探究AVL树的特点来了解它。

2. AVL树的特点

我们将AVL树的名字拆开，很容易就知道它到底是一棵什么样的树：自平衡的、二叉树、搜索树，所以它的特点有：

1. 搜索树：任意一棵子树，它的左子树的所有节点都比根节点小，且右子树的所有节点都比根节点大；在搜索树中，我们有K型搜索树和K/V型搜索树，AVL树同样有这两种。
2. 自平衡的：任意一棵子树，左子树和右子树的高度差不超过1，一旦超过1，就会自行进行树旋转操作，使得这棵AVL树的左右子树高度差不超过1。
3. 二叉树：AVL树的数据结构中有三个指针，分别指向左孩子、右孩子、父节点；此外，部分AVL树的实现中，存在一个整形变量平衡因子，用以辅助实现自平衡功能（关于平衡因子，后文会进行解释）。
4. 时间复杂度：查找、遍历、插入、删除都为O(log₂N)。

在AVL树众多特点中，我们最最需要关注的是：AVL树是如何实现自平衡的？下面，我们就来揭开AVL树自平衡的神秘面纱。

3. AVL树的自平衡

AVL树如何实现自平衡呢？
实现自平衡，涉及到两个概念，一个是平衡因子，另一个是旋转，平衡因子用来记录AVL树是否平衡，旋转则是让不平衡的AVL树变得平衡。

3.1 平衡因子

• $平衡因子（balancefactor，简称bf）=右子树的高度-左子树的高度$
  当然，反过来也是可以的，甚至不使用平衡因子也是可以的，我们为了理解方便，以下所有例子都是平衡因子=右子树的高度-左子树的高度。

• 对于一棵AVL树，任何一个节点的平衡因子的可能取值为{-2,-1,0,1,2}。

• 当插入一个新的节点，它的祖先节点的平衡因子可能会受到影响，因此我们需要一路向上更新祖先节点的平衡因子。

• 以下是插入了一个新的节点后，更新平衡因子的思路：

  1）如果当前节点是它的父节点parent的左孩子，说明新节点插入到了parent的左子树，左子树的高度加了一，父节点的平衡因子减一；
  2）如果当前节点是它的父节点parent的右孩子，说明新节点插入到了parent的右子树，右子树的高度加了一，父节点的平衡因子加一；
  3）若当前$bf=0$，表示左右子树一样高，处于平衡状态，说明再往上的祖先节点们都没有受到影响，更新结束。（说明：因为AVL树每次只能插入一个节点，若更新完平衡因子后，节点X的bf变成了0，说明节点X原来的bf不是-1就是1，也就是说原本节点X的左右子树高度相差1，在插入新节点后bf变成了0，也就是给左右子树中矮的那棵子树增高了1层，就使得节点X的左右子树一样高了。对于X节点和X的祖先来说，插入了一个新节点，并没有让自己左右子树的高度差变得更大，所以也就没有必要再往上更新平衡因子了。）
  4）若当前$bf=\pm 1$，表示左右子树的高度差为1（虽然不是绝对的平衡，但是满足AVL树的要求），不必进行旋转操作，需要继续向上更新平衡因子（把当前节点cur的parent作为当前节点，parent的parent作为新的parent）；
  5）更新完平衡因子后，若当前$bf=\pm 2$，表示左右子树的高度差为2，此时处于不平衡状态，需要进行旋转操作，使其平衡，旋转后更新结束。
  6）更新到根节点时，更新结束。

• 值得注意的是，曾经我把平衡因子的计算方法记错了，以为$当前的bf=右孩子的bf-左孩子的bf$，导致代码出现严重的问题。其实真正的计算方法是：
  $平衡因子=右子树的高度-左子树的高度$

3.2 旋转

当一棵AVL树的某个节点的平衡因子变成了2或-2，就需要进行旋转操作，将左右子树的高度重新变回{-1, 0, 1}之间。

旋转分为两种，一种是单旋转，另一种是双旋转。

下面，我们以插入操作来讲解旋转！

3.2.1. 单旋转（Single Rotation）

单旋又分为左单旋和右单旋，它们分别适用于不同的场景：

1）左单旋

右边“重”一点，需要把整个图像向左旋转。
核心步骤：
parent->right = curleft;
cur->left = parent;

下面我们针对h取不同的值图解分析：

1. h = 0
   h=0时，有且仅有1种场景！

   

   注意：这里新节点只能插入到cur的右边！如果插入到cur的左边，那么就需要右左双旋了！

2. h = 1
   新节点有2种插入位置，因此h=1时，有2种可能场景！

   

   注意：这里新节点可以插入到“70”的左或右，新节点“80”节点与“70”可以看做一个整体，新节点在哪个位置不影响左单旋！

3. h = 2
   a子树有3种，b子树有3种，c子树有1种；新节点插入的位置有4种，因此h=2时，共有36种可能场景！

   

   为什么a子树和b子树可以是x、y、z当中任意一种，但是c子树只可能是z呢？
   原因：a子树和b子树是什么类型，对于parent而言没有任何影响，不会让parent的平衡因子变得更大，因此都可以；
   但是c子树不同，对于左单旋而言，新节点必然插入到c子树当中（为什么说必然，如果插入到a子树，AVL树依旧平衡，用不着旋转，如果插入到b子树，就是双旋了，我们后面再讲），因此：
   1）假设c子树是x型的
   

   新节点有三种插入的位置，左边两个位置插入后会诱发双旋（双旋请看后面），右边一个位置插入后AVL树依旧平衡。

   2）假设c子树是y型的

新节点也有三种插入的位置，新节点插入在左边后AVL树依旧平衡。
插入在右边两个位置时，c子树本身就不平衡了，
当插入在最右的位置，c子树内部进行左单旋，使AVL树平衡，这属于"h=0"，而不属于"h=2"；
当插入在右起第二个位置，c子树内部进行右左双旋，AVL树平衡，这不属于左单旋。

3）只有c子树是z型的，parent节点的平衡因子才会变成2，才会需要进行左单旋。
1
2
3
4
5
6

4. h取更大的值
   会有越来越多可能出现的场景。

所以需要用到左单旋的场景有无数种！

2）右单旋

同样地，右单旋与左单旋一样，仅仅是位置变化罢了。

左边“重”一点，需要把整个图像向右旋转。
核心步骤：
parent->left = curright;
cur->right = parent;

右单旋这里就不再根据不同的h值画图分析了，它与左单旋大同小异。
h=0时仅仅有1种场景；
h=1时有2种场景；
h=2时有36种场景；
h越来越大，可能的场景越来越多…
总体来说右单旋也有无数种可能场景！

3.2.2 双旋转（Double Rotation）

所谓双旋，其实就是旋转两次，一次左单旋，一次右单旋。
双旋转也分为两种：右左双旋和左右双旋。

1）右左双旋

先右单旋，后左单旋。
所有符合下图所示的AVL树结构，都会导致右左双旋！

新节点既可能插入到b子树中，也可能插入到c子树中，这两种情况都会导致右左单旋！

1. h = 0
   h=0时，有且仅有这一种场景！

   

2. h = 1
   新节点有两个可能插入的位置，因此h=1引发右左双旋有2种可能场景！

   

3. h = 2

   a子树和d子树各有3种，b子树和c子树可能分别有2种，因此符合h=2的右左双旋共有36种可能场景！

   

4. h为更大的值，会有更多可能引发右左双旋的场景！

因此，双旋与单旋一样，都有无数种可能的场景！

其实双旋也就是两次单旋罢了，唯一需要注意的点在于：双旋后的parent/cur/curleft的平衡因子不是简单地变成0，而是根据不同情况有不同结果（因为旋转不会改变a/b/c/d子树的内部，他们的平衡因子不会改变，只有parent/cur/curleft的平衡因子会随着旋转而变化！）：

1. h=0时，curleft就是新节点，它的平衡因子为0，双旋后三者平衡因子都为0
2. h!=0时，curleft的平衡因子是1还是-1，取决于新节点插入到curleft的左子树还是右子树。
   插入到右子树时，（旋转前）curleft平衡因子是1，旋转后curleft平衡因子是1，其余为0；
   插入到左子树时，（旋转前）curleft平衡因子是-1，旋转后cur平衡因子是1，其余为0

int cl_bf = curleft->_bf;

// 旋转不会改变a/b/c/d子树的内部，他们的平衡因子不会改变，
// 只有parent/cur/curleft的平衡因子会随着旋转而变化！
if (cl_bf == 0)
{
    cur->_bf = 0;
    parent->_bf = 0;
    curleft->_bf = 0;
}
else if (cl_bf == 1)
{
    cur->_bf = 0;
    parent->_bf = 0;
    curleft->_bf = -1;
}
else if (cl_bf == -1)
{
    cur->_bf = 1;
    parent->_bf = 0;
    curleft->_bf = 0;
}
else
{
    throw"cl_bf is wrong!";
}
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

2）左右双旋

先进行左单旋，再进行右单旋。
所有符合下图所示结构的AVL树，都会引发左右双旋！

和右左双旋一样，b子树和c子树都有可能插入新节点！

当h=0时，有且仅有1种场景；
当h=1时，有2种可能场景；
当h=2时，有36种可能场景；
当h更大，有更多种可能的场景！

因此，左右双旋也有无数种可能场景！

需要注意的是：双旋后的parent/cur/curright的平衡因子不是简单地变成0，而是根据不同情况有不同结果：

1. h=0时，curright就是新节点，它的平衡因子为0，双旋后三者平衡因子都为0
2. h!=0时，curright的平衡因子是1还是-1，取决于新节点插入到curleft的左子树还是右子树。
   插入到右子树时，（旋转前）curright平衡因子是1，旋转后cur平衡因子是-1，其余为0；
   插入到左子树时，（旋转前）curright平衡因子是-1，旋转后parent平衡因子是1，其余为0

int cr_bf = curright->bf;
if (cr_bf == 0)
{
    parent->_bf = 0;
    cur->_bf = 0;
    curright->_bf = 0;
}
else if (cr_bf == 1)
{
    parent->_bf = 0;
    cur->_bf = -1;
    curright->_bf = 0;
}
else if (cr_bf == -1)
{
    parent->_bf = 1;
    cur->_bf = 0;
    curright->_bf = 0;
}
else
{
    thorw "cr_bf is wrong!";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

AVL树的删除操作，比插入操作更加复杂，它不仅仅要满足搜索树的条件（这本身就够复杂了），还要满足“平衡”，删除导致的平衡因子的判断更为复杂！能力有限，本文不对删除操作进行讲解。

4. AVL树源码（插入操作）

下面附上AVL树插入操作的源代码：

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

// K模型和KV模型都可以，这不是AVL树的重点。
template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode(const pair<K, V>& kv)
		: _kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{ }

	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf; // 平衡因子
};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;

public:
	bool Insert(const pair<K, V>& kv)
	{
		// 1. 树为空
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		// 2. 树不为空，找到需要填放的位置
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		// 3. 判断应该插入到左还是右
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		// 4. 控制平衡
		// 更新平衡因子
		while (parent) // 只有_root的parent是nullptr，当更新到_root就结束
		{
			// 看看当前的cur是parent的左还是右，左说明左子树改变了，右说明右子树改变了。
			if (cur == parent->_left) // 如果插入到左子树，parent的平衡因子减一
			{
				parent->_bf--;
			}
			else // 如果插入到右子树，parent的平衡因子加一
			{
				parent->_bf++;
			}

			if (parent->_bf == 0) // 如果parent的平衡因子为0，就结束更新了
			{
				break;
			}
			else if (parent->_bf == -1 || parent->_bf == 1) // 需要继续更新
			{
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == -2 || parent->_bf == 2) // 不平衡了，需要旋转
			{
				// 需要旋转
				// 1. 左单旋
				if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				// 2. 右单旋
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				// 3. 右左双旋
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				// 4. 左右双旋
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}

				// 旋转结束就停止更新了
				break;
			}
			else // 如果出现bug，平衡因子不为-2/-1/0/1/2其中一个，抛出异常
			{
				assert(false);
			}
		}

		return true;
	}


	// 左旋右旋核心操作就两三步，麻烦是因为三叉链，不仅要改left和
	// right，还要改各个parent。此外，还要考虑parent是根的情况和curleft是空的情况
	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;


		// step1.1 curleft变成parent的右
		parent->_right = curleft;
		// step1.2 parent变成curleft的parent，如果curleft为空，那就不用进行这一步操作了
		if (curleft)
		{	
			curleft->_parent = parent;
		}
				
		// step2.1 parent变成cur的左
		cur->_left = parent;
		// step2.2 cur变成parent的parent，在此之前先保存一份parent->parent
		Node* pparent = parent->_parent;
		parent->_parent = cur;

		// step3.1 如果parent是根节点，那么cur变成新的根，cur的parent就是nullptr
		if (pparent == nullptr)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		// step3.2 如果parent不是根，那么将cur与pparent进行双向的链接
		else
		{
			if (pparent->_left == parent)
			{
				pparent->_left = cur;
			}
			else
			{
				pparent->_right = cur;
			}
			cur->_parent = pparent;
		}

		// step4 最后更新一下平衡因子
		parent->_bf = cur->_bf = 0;
	}

	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;


		// step1.1 curright变成parent的左
		parent->_left = curright;
		// strp1.2 curright可能为空，为空就什么都不做
		// 若curright不为空，parent变成curright的parent
		if (curright) 
		{
			curright->_parent = parent;
		}

		// step2.1 parent变成cur的右
		cur->_right = parent;
		// step2.2 cur变成parent的parent，在此之前，先保存一份parent->_parent
		Node* pparent = parent->_parent;
		parent->_parent = cur;


		// step3.1 如果parent是根节点，那么cur变成新的根，cur的parent就是nullptr
		if (pparent == nullptr)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		// step3.2 如果parent不是根节点，那么将pparent与cur进行双向的链接
		else
		{
			if (parent == pparent->_left)
			{
				pparent->_left = cur;
			}
			else
			{
				pparent->_right = cur;
			}
			cur->_parent = pparent;
		}

		// step4 最后更新一下平衡因子
		parent->_bf = cur->_bf = 0;
	}

	void RotateRL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		int cl_bf = curleft->_bf;

		// 对于旋转部分，直接复用即可！
		RotateR(cur);
		RotateL(parent);

		// 还要更新平衡因子！单旋是把parent和cur的bf都置0，但是双旋不同，结合图来看！
		// 旋转不会改变a/b/c/d子树的内部，他们的平衡因子不会改变，
		// 只有parent/cur/curleft的平衡因子会随着旋转而变化！
		if (cl_bf == 0)
		{
			cur->_bf = 0;
			parent->_bf = 0;
			curleft->_bf = 0;
		}
		else if (cl_bf == 1)
		{
			cur->_bf = 0;
			parent->_bf = -1;
			curleft->_bf = 0;
		}
		else if (cl_bf == -1)
		{
			cur->_bf = 1;
			parent->_bf = 0;
			curleft->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void RotateLR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		int cr_bf = curright->_bf;

		// 对于旋转部分，直接复用即可！
		RotateL(cur);
		RotateR(parent);

		// 还要更新平衡因子！单旋是把parent和cur的bf都置0，但是双旋不同，结合图来看！
		// 旋转不会改变a/b/c/d子树的内部，他们的平衡因子不会改变，
		// 只有parent/cur/curright的平衡因子会随着旋转而变化！

		if (cr_bf == 0)
		{
			parent->_bf = 0;
			cur->_bf = 0;
			curright->_bf = 0;
		}
		else if (cr_bf == 1)
		{
			parent->_bf = 0;
			cur->_bf = -1;
			curright->_bf = 0;
		}
		else if (cr_bf == -1)
		{
			parent->_bf = 1;
			cur->_bf = 0;
			curright->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}



	// 下面的三个函数并不是AVL树的接口，是用来辅助调试的！
	bool isBalance()
	{
		return isBalance(_root);
	}

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

	// 通过计算高度差来判断AVL树是否平衡
	bool isBalance(Node* root)
	{
		if (root == nullptr)
			return true;

		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);

		int sub = rightHeight - leftHeight;

		if (sub != root->_bf)
		{
			cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << "    ";
			return false;
		}

		return abs(sub) < 2
			&& isBalance(root->_left)
			&& isBalance(root->_right);
	}

private:
	Node* _root = nullptr;
};
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
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343