【C++】AVL树

🚀write in front🚀
📜所属专栏： C++学习
🛰️博客主页：睿睿的博客主页
🛰️代码仓库：🎉VS2022_C语言仓库
🎡您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！
关注我，关注我，关注我，你们将会看到更多的优质内容！！

前言：

  在前面我们学习了二叉搜索树，一个查询效率非常高的一个数据结构，但是如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下，效率就变成了log(n)（直接变成链表了）。所以，为了解决这种方法，大佬们创造出了AVL树和红黑树！
  今天我们就来讲解并浅浅的手撕一下AVL树。

一.AVL树的概念

  两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决效率低的方法：

  当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
  简单的说，就是每插入一个结点，就检查一下该结点的左右子树高度差，如果超过1，那就进行调整（也就是旋转，后面会说到）。

所以AVL树的性质如下：

• 空树root=nullptr
• 非空树：
• 它的左右子树都是AVL树
• 左右子树高度之差的绝对值不超过1

二.AVL树结点的定义：

  其实，AVL树就是比我们之前学的二叉搜索树多一个平衡因子和一个父节点：

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;

	pair<K, V> _kv;
	int _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
16
17
18

  而父节点是为了解决旋转操作而做的准备。平衡因子_bf，用来表示节点的平衡状态。通常，平衡因子是右子树的高度减去左子树的高度。AVL树要求每个节点的平衡因子在[-1, 1]范围内，以保持树的平衡。

三.插入结点操作：

  AVL树的插入操作分为三个步骤，认真看相信你一定能学会：

1.先根据key的大小将结点插入其应该在的位置

  这里的操作和二叉搜索树一样，就不用多说了：

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
	//空结点直接插入
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
//找到位置
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
//插入结点
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		cur->_parent = parent;
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

2.更新平衡因子

我们对平衡因子的定义是：

右子树的高度-左子树的高度

所以要搞清楚每一个结点的平衡因子，在插入的时候就一定要算好。

• 如果我们插入的结点在父亲结点的右边，那父亲节的的平衡因子是不是就相当于+1了
• 同样的如果我们插入的结点在父亲的左边，那就相当于父亲的平衡因子-1了。

if (cur == parent->_left)
			{
				parent->_bf--;
			}
else // if (cur == parent->_right)
			{
				parent->_bf++;
			}
1
2
3
4
5
6
7
8

3.根据平衡因子不同的情况进行不同的操作：

情况1：父节点的平衡因子等于0

  更新以后parent平衡因子等于0，说明parent所在子树的高度不变(每次只插入一个结点，高度就要么增加1不平衡，要不就不变），不会影响祖先结点的平衡因子，就不用继续沿着root的路径往上走

情况2：父节点的平衡因子变成1或-1：

  更新以后parent的平衡因子等于1或-1，说明parent的高度变了，也就说明parent所在的子树高度变高了，此时就一定会影响到祖先结点的平衡因子。此时我们就要继续重复第二步骤：更新父亲的父亲的平衡因子，此时只要让cur=parent即可。

//当parent为空的时候就停止更新结点
while (parent)
	{
	//不断更新结点：
		if (cur == parent->_left)
		{
			parent->_bf--;
		}
		else 
		{
				parent->_bf++;
		}
		//情况1：停止更新
		if (parent->_bf == 0)
		{
		// 更新结束
			break;
		}
		//情况2：继续向上更新
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			// 继续往上更新
			cur = parent;
			parent = parent->_parent;
		}
		//情况3：旋转
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			// 子树不平衡了，需要旋转
			
		}
		}

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

情况3：父节点的平衡因子变成2或-2：

  更新以后parent为2或-2，说明parent的子树高度变化，并且已经不平衡了，此时就要对于parent进行旋转。

那么什么是旋转呢？

我们以这个图为例子：

此时搜索树的高度已经不平衡了，我们就要对其进行旋转，旋转以后会变成这个样子：

其实细心的大家会发现，旋转之后其实就相当于让parent高的那一侧少了一层结点，让parent低的那层多了一层结点。其实本质就是本来左右差为2，让多的那一边把多的一个拿给少的，此时也就正好平衡了。

那么，旋转到底是怎么操作的呢？

这里我们要先记着旋转的前提：

1. 保持二叉搜索树
2. 变成平衡树并且降低这个子树的高度

在这里呢，旋转有很多种情况，最终分为下面的四种：

左单旋：新节点插入较高右子树的右侧—右右

左单旋的核心操作是这样的：

parent->right=cur->left;
cur->left=parent;
1
2

我们先举一个简单的例子：

这个树在通过左单旋之后会变成这样：

其实这里的本质就是：cur是在parent的右边，一定是比parent大的，所以说我们的parent可以放在cur的左边，这是没有问题的，而cur的左边那个结点怎么处理呢？cur左边的那个结点也是比parent大的，但是又要比cur小，所以我们将其放在parent的右边就可以了。这个时候也是满足二叉搜索树的性质，而且让树也平衡了。

当然这里还有特殊情况要判断一下，就是如果cur左边为空，要多判断一下。

具体旋转途径如下：

那么我们何时左单旋呢？显而易见，cur的值为1，parent为2的时候就是左单旋了：

void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;

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

		cur->_left = parent;

		Node* ppnode = parent->_parent;
		//这里要将其与上面的树连接起来，而parent的位置会改变，所以我们要提前记录下parent的parent结点。
		parent->_parent = cur;


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

			}

			cur->_parent = ppnode;
		}

		parent->_bf = cur->_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
28
29
30
31
32
33
34
35
36
37
38
39
40

当然，这里还有一个很重要的就是旋转完以后，cur和parent的平衡因子都变成了0！！原因我刚刚也分析过了。

右单旋：新节点插入较高左子树的左侧—左左：

这里和上面的右单旋其实是类似的，我们直接来看看过程图就可以了：

/*
上图在插入前，AVL树是平衡的，新节点插入到30的左子树(注意：此处不是左孩子)中，30左
子树增加
了一层，导致以60为根的二叉树不平衡，要让60平衡，只能将60左子树的高度减少一层，右子
树增加一层，
即将左子树往上提，这样60转下来，因为60比30大，只能将其放在30的右子树，而如果30有
右子树，右子树根的值一定大于30，小于60，只能将其放在60的左子树，旋转完成后，更新节点
的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：
1. 30节点的右孩子可能存在，也可能不存在
2. 60可能是根节点，也可能是子树
如果是根节点，旋转完成后，要更新根节点
如果是子树，可能是某个节点的左子树，也可能是右子树
同学们再此处可举一些详细的例子进行画图，考虑各种情况，加深旋转的理解
*/
void _RotateR(PNode pParent)
{
// pSubL: pParent的左孩子
// pSubLR: pParent左孩子的右孩子，注意：该
PNode pSubL = pParent->_pLeft;
PNode pSubLR = pSubL->_pRight;
// 旋转完成之后，30的右孩子作为双亲的左孩子
pParent->_pLeft = pSubLR;
// 如果30的左孩子的右孩子存在，更新亲双亲
if(pSubLR)
pSubLR->_pParent = pParent;
// 60 作为 30的右孩子
pSubL->_pRight = pParent;
// 因为60可能是棵子树，因此在更新其双亲前必须先保存60的双亲
PNode pPParent = pParent->_pParent;
// 更新60的双亲
pParent->_pParent = pSubL;
// 更新30的双亲
pSubL->_pParent = pPParent;
// 如果60是根节点，根新指向根节点的指针
if(NULL == pPParent)
{
_pRoot = pSubL;
pSubL->_pParent = NULL;
}
else
{
// 如果60是子树，可能是其双亲的左子树，也可能是右子树
if(pPParent->_pLeft == pParent)
pPParent->_pLeft = pSubL;
else
pPParent->_pRight = pSubL;
}
// 根据调整后的结构更新部分节点的平衡因子
pParent->_bf = pSubL->_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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

先左单旋再右单旋：节点插入较高左子树的右侧—左右：

对于以下情况，单纯的左单旋或者右单旋是无法解决的：

这个时候就要对其先进行右单旋，此时就变成了左单旋的模式，在对其进行左单旋就ok了，我们先以一个简单的例子为例子：

此时我们先把90那个结点右单旋，就变成了parent=2，cur=1的模式，就可以左单旋了。

下面我们来看看过程图：

其实这里的本质就是：

所以旋转后平衡因子的更新和旋转前cur的平衡因子有关
cur为0：

cur为-1：

cur为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)
		{
			cur->_bf = 0;
			curleft->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 1)
		{
			cur->_bf = 0;
			curleft->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)
		{
			cur->_bf = 1;
			curleft->_bf = 0;
			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
27
28
29
30
31
32

先右单旋再左单旋：新节点插入较高右子树的左侧—右左：

  这里和上面的情况也是类似的，jrm可以自己画图分析啦~
过程图如下：

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

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

		if (bf == 0)
		{
			cur->_bf = 0;
			curleft->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 1)
		{
			cur->_bf = 0;
			curleft->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)
		{
			cur->_bf = 1;
			curleft->_bf = 0;
			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
27
28
29
30
31
32

总结：
假如以Parent为根的子树不平衡，Parent的平衡因子为2或者-2，分以下情况考虑

1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR
   当pSubR的平衡因子为1时，执行左单旋
   当pSubR的平衡因子为-1时，执行右左双旋
2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL
   当pSubL的平衡因子为-1是，执行右单旋
   当pSubL的平衡因子为1时，执行左右双旋

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

insert的完整代码：

 bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		cur->_parent = parent;

		// ... 控制平衡
		// 更新平衡因子
		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else // if (cur == parent->_right)
			{
				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)
				{
					RotateRL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}

				break;
			}
			else
			{
				assert(false);
			}
		}


		return true;
	}

	void RotateL(Node* parent)
	{
		++_rotateCount;

		Node* cur = parent->_right;
		Node* curleft = cur->_left;

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

		cur->_left = parent;

		Node* ppnode = parent->_parent;

		parent->_parent = cur;


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

			}

			cur->_parent = ppnode;
		}

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


	void RotateR(Node* parent)
	{
		++_rotateCount;

		Node* cur = parent->_left;
		Node* curright = cur->_right;

		parent->_left = curright;
		if (curright)
			curright->_parent = parent;

		Node* ppnode = parent->_parent;
		cur->_right = parent;
		parent->_parent = cur;

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

			cur->_parent = ppnode;
		}

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

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

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

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

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

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

		if (bf == 0)
		{
			parent->_bf = 0;
			cur->_bf = 0;
			curright->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			cur->_bf = 0;
			curright->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			cur->_bf = -1;
			curright->_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
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

四.AVL树的删除(了解)

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不错与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。至于具体的实现，有时间在更新吧！

五.AVL树的验证:

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

1.二叉搜索树的验证：

中序遍历即可，若有序，就说明为二叉搜索树

2.验证其为平衡树：

a.每个节点子树高度差的绝对值不超过1

b.节点的平衡因子是否计算正确

int Height()
	{
		return Height(_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;
	}

	bool IsBalance()
	{
		return IsBalance(_root);
	}

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

		int leftHight = Height(root->_left);
		int rightHight = Height(root->_right);

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

		return abs(rightHight - leftHight) < 2
			&& IsBalance(root->_left)
			&& IsBalance(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
36
37
38
39
40

总的来说，要写这个验证就是为了检验我们代码里面的bug，说实话这段代码挺长的，如果代码出现问题我们一个一个调试去看会非常的难受，这也是一种调试技巧吧！

总结

这就是AVL树的实现，个人感觉难度还是上了很多的。以后我也要多多复习这一部分。

  更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

专栏订阅：
每日一题
C语言学习
算法
智力题
初阶数据结构
Linux学习
C++学习
更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！