【C++】AVL树

个人主页：🍝在肯德基吃麻辣烫
我的gitee：C++仓库
个人专栏：C++专栏

---

前言

本文章将会模拟实现一棵AVL树。

---

以下是本篇文章正文内容

一、什么是AVL树？

AVL树也是一个二叉搜索树，只不过是在二叉搜索树的基础上，增加了一个条件：

任意一棵子树的左右高度差的绝对值不大于1。

---

设计AVL树的原因

在二叉平衡搜索树中，在正常情况下，对该树的任意节点进行查找，最多查找OlogN次，但如果在极端情况下，该树退化成了单只树，则会极大降低搜索效率，变成O(n)，所以为了避免让二叉搜索树出现极端情况，设计出一棵具有平衡性质的二叉搜索树：AVL树

---

二、AVL树的性质

• 1）它的左右子树都是AVL树
• 2）左右子树高度之差（平衡因子）的绝对值不超过1（-1/0/1）

平衡因子：右子树高度 - 左子树的高度（注意是右 - 左）

由此可知，一棵AVL树是高度平衡的，它的高度可保持在logN，所以搜索效率可以保持在logN

---

三、二叉树节点的定义

template<class K, class V>
class AVLTreeNode
{
public:
	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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 1）需要有一个平衡因子存在，即_bf
• 2）_data值可以是一个键值对，也可以是其他类型，这里我选择了pair。
• 3）在后面的其他操作中，会频繁用到一个节点的父亲，所以直接在节点中添加一个_parent成员。

---

四、AVL树的插入

插入大致分为几个步骤：

如果根节点为空，则直接插入到根节点的位置

1）先找到插入位置，因为这是一棵搜索树，如果该节点的值比根小，则往左走，如果比根大，往右边走。

2）找到待插入位置后，插入该节点，然后调整平衡因子。

如果插入的是左边，则parent的平衡因子–，如果插入的是右边，则parent的平衡因子++。

如果parent的平衡因子是1或-1，说明父亲的子树有一边高了，则需要继续向上调整。(最坏情况就是调整平衡因子到根的位置)

如果parent的parent的平衡因子大于1或者小于-1了，则不满足AVL树的特性，需要进行旋转。

旋转

1）右单旋

新插入的节点在根节点的左侧，导致根节点的平衡因子变成-2。
则需要将根节点进行右旋。
规则如下：

• 1）cur的right给parent的left
• 2）parent变成了cur的right
  调整后，cur变成了新的根，parent变成cur的right
  此时需要注意一些细节：

如果在旋转前，parent不是根，也就是如果parent还是某一个节点的孩子，则在旋转后cur变成新的根，需要替代parent的位置，变成那个节点的孩子。

如果旋转前parent就是根，则直接让旋转后的cur的parent为空即可。

调整后cur和parent的平衡因子变成0。

2）左单旋

新插入的节点在根节点的右侧，导致根节点的平衡因子变成2。
则需要将根节点进行左旋。
规则如下：

• 1）cur的left给parent的right
• 2）parent变成了cur的left
  调整后，cur变成了新的根，parent变成curr的left
  此时需要注意一些细节：

如果在旋转前，parent不是根，也就是如果parent还是某一个节点的孩子，则在旋转后cur变成新的根，需要替代parent的位置，变成那个节点的孩子。

如果旋转前parent就是根，则直接让旋转后的cur的parent为空即可。

调整后cur和parent的平衡因子变成0。

3）左右双旋

插入新节点后，如果cur的平衡因子为1，parent的平衡因子为-2
说明整颗树的结构大概是这样的：

这就说明，此时这棵树不再是AVL树，所以我们需要对其进行旋转。

旋转操作如下：

• 1）让cur的右指向curright的左，然后cur成为curright的左。此时curright的父亲就变成了原来的cur的父亲，cur的父亲变成了curright

以上操作是左旋的操作过程

• 2）让parent的左指向curright的右，然后parent变成了curright的右，此时parent的父亲变成了curright。

以上操作是右旋的操作过程

这里还需要注意一些细节：
如果在旋转前，parent不是根，也就是如果parent还是某一个节点的孩子，则在旋转后curright变成新的根，需要替代parent的位置，变成那个节点的孩子。

平衡因子的处理：

• • 1）如果旋转之前，curright的平衡因子是0，则说明，curright这个节点，一定是新插入的节点。

（因为如果不是新插入的节点，在插入该节点前，这棵树就不是AVL树了）。

在进行左右双旋后，cur，curright，parent三个节点的平衡因子都是0。

• • 2）如果旋转之前，curright这个节点的平衡因子是-1，该情况就是上图画出的情况，说明新插入节点在curright的左子树，在左右双旋后，cur和curright的平衡因子变成0，parent的平衡因子是1
• • 3）如果旋转之前，curright这个节点的平衡因子是1，说明新插入节点在curright的右子树，在左右双旋后，parent和curright的平衡因子变成0，cur的平衡因子是-1

4）右左双旋

插入新节点后，如果cur的平衡因子为-1，parent的平衡因子为2
说明整颗树的结构大概是这样的：

这就说明，此时这棵树不再是AVL树，所以我们需要对其进行右左旋转。

旋转操作如下：

• 1）让cur的左指向curleft的右，然后cur成为curleft的右。此时culeft的父亲就变成了原来的cur的父亲，cur的父亲变成了curleft

以上操作是右旋的操作过程

• 2）让parent的右指向curleft的左，然后parent变成了curleft的左，此时parent的父亲变成了curleft。

以上操作是左旋的操作过程

这里还需要注意一些细节：
如果在旋转前，parent不是根，也就是如果parent还是某一个节点的孩子，则在旋转后currleft变成新的根，需要替代parent的位置，变成那个节点的孩子。

平衡因子的处理：

• • 1）如果旋转之前，curleft的平衡因子是0，则说明，curleft这个节点，一定是新插入的节点。

（因为如果不是新插入的节点，在插入该节点前，这棵树就不是AVL树了）。

在进行左右双旋后，cur，curleft，parent三个节点的平衡因子都是0。

• • 2）如果旋转之前，curleft这个节点的平衡因子是1，该情况就是上图画出的情况，说明新插入节点在curleft的右子树，在右左双旋后，cur和curleft的平衡因子变成0，parent的平衡因子是-1
• • 3）如果旋转之前，curleft这个节点的平衡因子是-1，说明新插入节点在curleft的左子树，在右左双旋后，parent和curleft的平衡因子变成0，cur的平衡因子是1

以上就是旋转的四种情况。

AVL树插入完整代码

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;
		}
		Node* cur = _root;
		Node* cur_parent = _root;
		//1.找到待插入位置
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				cur_parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				cur_parent = cur;
				cur = cur->_left;
			}
			else
				return false;
		}

		//2.先判断待插入节点是在parent的左边还是右边
		cur = new Node(kv);
		if (cur_parent->_kv.first > kv.first)
		{
			cur_parent->_left = cur;
		}
		else
		{
			cur_parent->_right = cur;
		}
		cur->_parent = cur_parent;


		//下面为调整二叉树的平衡
		
		//1.更新平衡因子
		//
		while (cur_parent)
		{
			//左子树--
			if (cur_parent->_left == cur)
			{
				cur_parent->_bf--;
			}
			//右子树++
			else
			{
				cur_parent->_bf++;
			}

			//平衡因子=0，不再影响祖先
			if (cur_parent->_bf == 0)
			{
				break;
			}
			
			//不平衡了，影响祖先，要向上也调整
			else if (cur_parent->_bf == 1 || cur_parent->_bf == -1)
			{
				cur = cur_parent;
				cur_parent = cur_parent->_parent;
			}

			//此时该树出问题了，需要旋转进行平衡

			else if (cur_parent->_bf == 2 || cur_parent->_bf == -2)
			{
					//右边高，向左旋转
				if (cur_parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(cur_parent);
				}

				//左边高，向右旋转
				else if (cur_parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(cur_parent);
				}

				//折线型，右边高，右左双旋
				else if (cur_parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(cur_parent);
				}

				//折线形，左边高，左右双旋
				else if (cur_parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(cur_parent);
				}
					
				//旋转完成后一定平衡了，则break
				break;

			}

			else
			{
				assert(false);
			}

		}
		cout << kv.first << endl;
		return true;
	}

	//左单旋
	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		Node* ppNode = parent->_parent;

		parent->_right = curleft;
		if (curleft)
			curleft->_parent = parent;

		cur->_left = parent;
		parent->_parent = cur;

		if (!ppNode)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (ppNode->_right == parent)
			{
				ppNode->_right = cur;
			}
			else
			{
				ppNode->_left = cur;
			}

			cur->_parent = ppNode;
		}

		cur->_bf = parent->_bf = 0;

	}

	//右单旋
	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		Node* ppNode = parent->_parent;

		parent->_left = curright;
		//如果cur的右子树是空
		if(curright)
			curright->_parent = parent;

		cur->_right = parent;
		parent->_parent = cur;

		if (!ppNode)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			cur->_parent = ppNode;
			//要知道根的左边是cur还是右边是cur
			if (ppNode->_left == parent)
			{
				ppNode->_left = cur;
			}
			else
			{
				ppNode->_right = cur;
			}
		}

		cur->_bf = parent->_bf = 0;
	}

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

		//该节点为新插入的节点
		if (bf == 0)
		{
			curright->_bf = 0;
			cur->_bf = 0;
			parent->_bf = 0;
		}

		//新插入节点在curright的右边，右边高了
		//     p
		//   c
		//     cr

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

		//新插入节点在curright的左边，左边高了
		else if (bf == -1)
		{
			curright->_bf = 0;
			cur->_bf = 0;
			parent->_bf = 1;
		}

	}

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

		RotateR(parent->_right);
		RotateL(parent);

		//该节点为新插入的节点
		if (bf == 0)
		{
			curleft->_bf = 0;
			cur->_bf = 0;
			parent->_bf = 0;
		}
		//新插入节点在curleft的右边，右边高了
		//     p
		//		  c
		//     cl
		else if (bf == 1)
		{
			curleft->_bf = 0;
			cur->_bf = 0;
			parent->_bf = -1;
		}
		//新插入节点在curleft的左边，左边高了
		else if (bf == -1)
		{
			curleft->_bf = 0;
			cur->_bf = 1;
			parent->_bf = 0;
		}
	}

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

验证一棵树为AVL树

• 1）验证这棵树的中序遍历是有序的。
• 2）验证每一棵树的左右子树高度差不大于1

int Height(Node* root)
{
	if (root == nullptr)
		return 0;

	int left = Height(root->_left);
	int right = Height(root->_right);
	return left > right ? left + 1 : right + 1;
}

bool IsBalanceTree()
{
	cout << "IsBalanceTree():";
	return _IsBalanceTree(_root);
}

//通过高度判断是否为AVL树
//1.通过高度计算出真实的平衡因子，再与AVL树本身的平衡因子进行比较

bool _IsBalanceTree(Node* root)
{
	if (root == nullptr)
		return true;

	int lefth = Height(root->_left);
	int righth = Height(root->_right);
	int bf = righth - lefth;

	if (bf != root->_bf || bf > 1 || bf < -1)
	{
		return false;
	}

	return _IsBalanceTree(root->_left) && _IsBalanceTree(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

AVL树的性能分析

由于AVL树的绝对平衡（每棵树高度差不大于1），每次在插入数据时，难免会遇到多次旋转，最坏情况需要旋转到根部。虽然旋转时间复杂度O(1)，但如果旋转次数过多，也会造成效率下降。在本文中没有提到AVL树的删除，删除操作更加复杂，我没有研究过hh，不过同样每删除一个数据，都必须保证整棵树是AVL树，这又需要大量旋转来维持它的平衡。

所以在面对大量数据，并且不再有新数据的插入时，可以使用AVL树进行查找，效率为O(logN).

总结

本文主要讲述了AVL树的插入过程及其效率分析。