数据结构:AVL树详解(平衡二叉树)_avl树全称是什么

AVL 树详解

AVL树的概念

平衡二叉树 又名 平衡二叉搜索（排序）树，简称 AVL树（Balanced Binary Tree） （BBT）。

AVL树名字的由来：
两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
为了纪念他们，将 平衡二叉树 称为 AVL树。

AVL树本质上是二叉搜搜树，但是它又具有以下特点：

• 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，
• 左右两个子树也都是一棵平衡二叉树。

平衡因子

这里介绍一个概念：平衡因子，平衡因子在AVL树中是一个极其重要的概念。

平衡因子（Balance Factor，简写为bf）
一个节点的平衡因子大小计算方式： 结点的平衡因子 = 左子树的高度 - 右子树的高度 。

在 AVL树中，所有节点的平衡因子都必须满足： -1<=bf<=1，即当前节点的左右两个子树的高度差的绝对值不超过1。

两张图理解平衡因子：

由AVL树的定义可知，上图符合AVL（平衡二叉树的定义），所有节点的平衡因子的绝对值都不大于2.

再来看一张图：

由AVL树的定义可知，上图不符合AVL树的定义，因为节点值为1的点平衡因子不符合要求，所以上图不是AVL树。

AVL树的作用：
对于一般的二叉搜索树，其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度同时也由此而决定。但在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度。因此，AVL树严格操纵树两端的平衡性，使其在对数据进行操纵时的效率最大化。

AVL树基本操作

构建AVL树

构建AVL树的基本节点
AVL树的基本节点需要包含其左孩子的指针、右孩子指针、双亲指针、记录平衡因子的bf变量以及节点中存储的数据类型。
值得一提的是，AVL树中的基本节点中的数据都是以键值对的形式进行存储的。

AVL树基本节点的定义：

template<class K,class V>
class AVLTreeNode
{
public:
	AVLTreeNode<K, V>* left;
	AVLTreeNode<K, V>* right;
	AVLTreeNode<K, V>* parent;
	pair<K, V> kv;
	short bf;

	AVLTreeNode(const pair<K, V>& _kv)
		:left(nullptr), right(nullptr), parent(nullptr), kv(_kv), bf(0)
	{
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注意：AVL树与二叉搜索树不同的是，AVL树的节点还多了一个指向双亲的指针 parent，用于在插入时调节平衡因子等地方使用使用
AVL树类的定义：

template <class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
	AVLTreeNode<K, V>* root;
public:
	AVLTree():root(nullptr){}
1
2
3
4
5
6
7

AVL插入操作

为了保持AVL树的平衡，插入操作可能需要进行旋转。这里分为4中情况调整，本文将逐一分析

左单旋

parent 的右子树的右子树增加节点(如下图)，需要进行左单旋。
如图：在 c 处增加一个节点，那么此时 parent 节点处的平衡因子为 2 ，需要进行调整，将 subR 节点的左孩子作为 parent 节点的右孩子，在将 parent 作为subR的左孩子。即完成了一次左单旋。

注意：这里的 h >= 0 ，也就是说 a、b、c 三处的子树高度可以是0(子树为空)到无穷；

旋转完后需要在修改相应节点的平衡因子。

代码如下：

void RotateL(Node* parent)  //左旋
	{
		Node* subR = parent->right, * subRL = subR->left;
		parent->right = subRL;
		if(subRL)  //可能不存在，需要判断
		subRL->parent = parent;

		subR->left = parent;

		if (root == parent)
		{
			subR->parent = nullptr;
			root = subR;
		}
		else
		{
			Node* P_parent = parent->parent;
			if (P_parent->left == parent)
				P_parent->left = subR;
			else
				P_parent->right = subR;
			subR->parent = P_parent;
		}
		parent->parent = subR;
		//修改相应的平衡因子
		parent->bf = subR->bf = 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

右单旋

parent 的左子树左子树增加节点(如下图)，需要进行右单旋。
如图：在 a 处增加一个节点，那么此时 parent 节点处的平衡因子为 -2 ，需要进行调整，将 subL节点的右孩子作为 parent 节点的左孩子，再将 parent 作为subL的右孩子。即完成了一次右单旋。

注意：这里的 h >= 0 ，也就是说 a、b、c 三处的子树高度可以是0(子树为空)到无穷；

旋转完后需要在修改相应节点的平衡因子。

代码如下：

void RotateL(Node* parent)  //左旋
	{
		Node* subR = parent->right, * subRL = subR->left;
		parent->right = subRL;
		if(subRL)  //可能不存在，需要判断
		subRL->parent = parent;

		subR->left = parent;

		if (root == parent)
		{
			subR->parent = nullptr;
			root = subR;
		}
		else
		{
			Node* P_parent = parent->parent;
			if (P_parent->left == parent)
				P_parent->left = subR;
			else
				P_parent->right = subR;
			subR->parent = P_parent;
		}
		parent->parent = subR;
		//修改相应的平衡因子
		parent->bf = subR->bf = 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

先右旋再左旋

subRL 的右子树增加节点(如下图)，需要进行右单旋。
如图：在 c 处增加一个节点，那么此时 parent 节点处的平衡因子为 2 ，需要进行调整，将 subRL节点的右孩子作为 subR 节点的左孩子，subR作为subRL的右孩子，parent的右孩子修改为subRL,这样对于subR节点就完成了一次右旋，再将 subRL的左孩子作为parent的右孩子，parent作为subRL的左孩子，即完成了一次右左单旋。
注意：这里的 h >= 0 ，也就是说 a、b、c 三处的子树高度可以是0(子树为空)到无穷；

具体图示如下图：

根据最后调整后的树，修改parent，subR，subRL的平衡因子。
当一开始插入的位置是b时，上述旋转操作不变，只有在最后修改平衡因子时有所不同，所以在进行两次旋转前，需要先记录subRL的平衡因子，根据其subRL平衡因子再修改调整后的树的平衡因子。

代码如下：

void RotateRL(Node* parent)
	{
		Node* subR = parent->right, * subRL = subR->left;
		short _bf = subRL->bf;
		RotateR(parent->right);
		RotateL(parent);
		if (_bf == 0)  
		{   //subRL 自己就是新增节点,此时parent节点下的子树只有parent，subR，subRL这三个节点
			subR->bf = parent->bf = subRL->bf = 0;
		}
		else if (_bf == 1)  //subRL右子树新增节点
		{
			subR->bf = subRL->bf = 0;
			parent->bf = -1;
		}
		else if (_bf == -1)
		{
			subR->bf = 1;
			subRL->bf = parent->bf = 0;
		}
		else
		{
			assert(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

先左旋再右旋

subLR 的右子树增加节点(如下图)，需要进行左单旋。
如图：在 c 处增加一个节点，那么此时 parent 节点处的平衡因子为 -2 ，需要进行调整，将 subLR节点的左孩子作为 subL 节点的右孩子，subL作为subLR的左孩子，parent的左孩子修改为subLR,这样对于subLR节点就完成了一次右旋，再将 subLR的右孩子作为parent的左孩子，parent作为subLR的右孩子，即完成了一次左右单旋。
注意：这里的 h >= 0 ，也就是说 a、b、c 三处的子树高度可以是0(子树为空)到无穷；

具体图示如下图：

根据最后调整后的树，修改parent，subR，subRL的平衡因子。
当一开始插入的位置是b时，上述旋转操作不变，只有在最后修改平衡因子时有所不同，所以在进行两次旋转前，需要先记录subLR的平衡因子，根据其subLR平衡因子再修改调整后的树的平衡因子。

总结

假如以 parent 为根的子树不平衡，即 parent 的平衡因子为2或者-2，分以下情况考虑

• parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR
  • 当subR的平衡因子为1时，执行左单旋
  • 当subR的平衡因子为-1时，执行右左双旋
• parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为subL
  • 当subL的平衡因子为-1是，执行右单旋
  • 当subL的平衡因子为1时，执行左右双旋

旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新。

AVL树的性能

  AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这
样可以保证查询时高效的时间复杂度，即$lo{g}_2(N)$。但是如果要对AVL树做一些结构修改的操
作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，
有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数
据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

代码总览：

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

template<class K,class V>
class AVLTreeNode
{
public:
	AVLTreeNode<K, V>* left;
	AVLTreeNode<K, V>* right;
	AVLTreeNode<K, V>* parent;
	pair<K, V> kv;
	short bf;

	AVLTreeNode(const pair<K, V>& _kv)
		:left(nullptr), right(nullptr), parent(nullptr), kv(_kv), bf(0)
	{
	}
};

template <class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
	AVLTreeNode<K, V>* root;
public:
	AVLTree():root(nullptr){}
	~AVLTree() { Destory(root); }
	bool Insert(const pair<K, V>& _kv)
	{
		if (!root)
		{
			root = new Node(_kv);
			return true;
		}
		Node* cur = root, * parent = root;
		while (cur)
		{
			parent = cur;
			if (cur->kv.first < _kv.first)
				cur = cur->right;
			else if (cur->kv.first > _kv.first)
				cur = cur->left;
			else
				return 0;
		}

		//找到待插入位置
		cur = new Node(_kv);
		cur->parent = parent;
		if (parent->kv.first < _kv.first)
			parent->right = cur;
		else
			parent->left = cur;
	
		while (parent)
		{
			//修改平衡因子,循环向上遍历修改
			if (parent->left == cur)
				parent->bf--;
			else
				parent->bf++;

			if (parent->bf == 0)
				break;
			else if (abs(parent->bf) == 1)
			{
				cur = parent;
				parent = parent->parent;
			}
			else if (parent->bf == 2)
			{
				if (cur->bf == 1)
					RotateL(parent);
				else if (cur->bf == -1)
					RotateRL(parent);
				break;
			}
			else if (parent->bf == -2)
			{
				if (cur->bf == 1)
					RotateLR(parent);
				else if (cur->bf == -1)
					RotateR(parent);
				break;
			}
			else
			{
				assert(false);
			}
		}
		return 1;
	}

	void RotateL(Node* parent)  //左旋
	{
		Node* subR = parent->right, * subRL = subR->left;
		parent->right = subRL;
		if(subRL)  //可能不存在，需要判断
		subRL->parent = parent;

		subR->left = parent;

		if (root == parent)
		{
			subR->parent = nullptr;
			root = subR;
		}
		else
		{
			Node* P_parent = parent->parent;
			if (P_parent->left == parent)
				P_parent->left = subR;
			else
				P_parent->right = subR;
			subR->parent = P_parent;
		}
		parent->parent = subR;
		parent->bf = subR->bf = 0;
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->left, * subLR = subL->right;
		parent->left = subLR;
		if (subLR)  //可能不存在，需要判断
			subLR->parent = parent;

		subL->right = parent;

		if (root == parent)
		{
			subL->parent = nullptr;
			root = subL;
		}
		else
		{
			Node* P_parent = parent->parent;
			if (P_parent->left == parent)
				P_parent->left = subL;
			else
				P_parent->right = subL;
			subL->parent = P_parent;
		}
		parent->parent = subL;
		parent->bf = subL->bf = 0;
	}

	void RotateRL(Node* parent)
	{
		Node* subR = parent->right, * subRL = subR->left;
		short _bf = subRL->bf;
		RotateR(parent->right);
		RotateL(parent);
		if (_bf == 0)  
		{   //subRL 自己就是新增节点,此时parent节点下的子树只有parent，subR，subRL这三个节点
			subR->bf = parent->bf = subRL->bf = 0;
		}
		else if (_bf == 1)  //subRL右子树新增节点
		{
			subR->bf = subRL->bf = 0;
			parent->bf = -1;
		}
		else if (_bf == -1)
		{
			subR->bf = 1;
			subRL->bf = parent->bf = 0;
		}
		else
		{
			assert(false);
		}

	}

	void RotateLR(Node* parent)
	{
		Node* subL = parent->left, * subLR = subL->right;
		short _bf = subLR->bf;
		RotateL(parent->left);
		RotateR(parent);
		if (_bf == 0)
		{   //subRL 自己就是新增节点,此时parent节点下的子树只有parent，subR，subRL这三个节点
			subL->bf = parent->bf = subLR->bf = 0;
		}
		else if (_bf == 1)  //subRL右子树新增节点
		{
			subL->bf = -1;
			subLR->bf = parent->bf = 0;
		}
		else if (_bf == -1)
		{
			subL->bf = subLR->bf = 0;
			parent->bf = 1;
		}
		else
		{
			assert(false);
		}
	}

	
	void _InOrder(Node* root)
	{
		if (!root)
			return;
		_InOrder(root->left);
		cout << root->kv.first << "  " << root->kv.second << endl;
		_InOrder(root->right);
	}

	void Inorder()
	{
		_InOrder(root);
	}

	int _Height(Node* root)
	{
		if (!root) return 0;
		int left = _Height(root->left);
		int right = _Height(root->right);

		return (left > right ? left : right) + 1;
	}
	
	const string str = "平衡因子异常";

	bool _Is_Balance(Node* root)
	{
		if (!root) return 1;
		int left_height = _Height(root->left);
		int right_height = _Height(root->right);
		/*try
		{*/
			if (right_height - left_height != root->bf)
			{
				cerr << str << endl;
			}
		/*}*/
		/*catch (string e)
		{
			cerr << str << endl;
			assert(false);
		}*/
		return abs(right_height - left_height) < 2 && _Is_Balance(root->left) && _Is_Balance(root->right);
	}

	void Is_Balance()
	{
		_Is_Balance(root);
	}

	void Destory(Node* root)
	{
		if (!root) return;
		Destory(root->left);
		Destory(root->right);
		delete root;
	}

	

};

int main()
{
	const int N = 100000,NN=1000000;
	srand(time(0));
	int a;
	AVLTree<int, int> AVL;
	for (int i = 0; i < N; i++)
	{
		a = rand()%NN;
		AVL.Insert(make_pair(a,a));
	}
		
	AVL.Inorder();
	AVL.Is_Balance();


}
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