【C++进阶】：AVL树(平衡因子)

一.概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

二.插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子

1.搜索二叉树

2.平衡因子

一颗树如何插入会影响节点的平衡因子呢？（平衡因子是右节点减去左节点）

如果我们插在6的左边，那么6的平衡因子减一，同理7的左子树高度加一，那么7的平衡因子减一，再继续向上5的右子树的最高高度并没有发生改变，所以5的平衡因子不发生改变。

同理，插在6的右边，6的平衡因子加一，7的平衡因子减一。

如果插在9的右边，那么8的平衡因子就会变为2，说明此树不平衡。

总结：
1.新镇在左，parent平衡因子减减。
2.新增在右，parent平衡因子加加。
3.如果更新后的parent平衡因子为0，说明parent所在的树的高度不变，不会再影响祖先，不用再继续更新了。
4如果更新后parent的平衡因子为1或者-1，那么就需要继续向上更新。
5.如果更新后，parent平衡因子为2或-2，说明该树不平衡，对parent所在的子树进行旋转。

三.旋转

1.更新平衡因子

由上面分析可以知道更新结束的条件是平衡因子为0或者更新到根节点。

首先在每个节点里加入平衡因子

接着在插入的同时更新平衡因子

2.旋转

旋转要保持的要求：
1.旋转后也是搜索二叉树。
2.变成平衡树并且降低树的高度。

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

1.左单旋

通过观察我们可以发现，我们其实只需要移动蓝色的节点就可以实现左旋。我们将这三个节点分别记录，然后修改它们的内部属性即可。

2.右单旋

3.先右旋再左旋

这里的旋转并不难，直接复用就可以.

困难的部分是如何调控平衡因子，插入的位置不同，平衡因子也不同分三种情况讨论。

4.先左旋再右旋

同理，左右旋与上文一样，需要分三种情况来讨论。

四.完整代码

测试

#include"KVL.h"
#include

int main()
{
	AVLTree<int,int> t;
	srand(time(0));
	vector<int>a;
	for (int i = 0; i < 100; i++)
		a.push_back(rand());
	for (auto x : a)
		t.Insert(make_pair(x,x));
	t.Print();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

树

#include
#include
using namespace std;

template<class K,class V>
struct KVLTreeNode
{
	pair<K, V>_kv;
	KVLTreeNode<K, V>* _left;
	KVLTreeNode<K, V>* _right;
	KVLTreeNode<K, V>* _parent;
	int _bf;//平衡因子
	KVLTreeNode(const pair<K,V>&kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{}
};

template<class K,class V>
class AVLTree
{
public:
	typedef KVLTreeNode<K,V> Node;
	
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* cur = _root;
		Node* parent = _root;
		while (cur)
		{
			if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
				return false;
		}
		cur = new Node(kv);
		if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = 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)
				{
					RotateLR(parent);
				}
				//先右单选再左单旋
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}
	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		Node* ppnode = parent->_parent;//记录父节点的父节点

		//父节点的右孩子变成curleft
		parent->_right = curleft;
		if(curleft)//细节注意curleft为空时不能操作
			curleft->_parent = parent;
		//父节点变为cur的左孩子
		cur->_left = 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)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		Node* pphead = parent->_parent;

		//父节点到cur右边
		cur->_right=parent;
		parent->_parent = cur;
		//父节点的左孩子变成curright
		parent->_left = curright;
		if (curright)
			curright->_parent = parent;
		//cur的父节点变为原来父节点的父节点
		if (pphead)//如果不是根节点
		{
			if (pphead->_left == parent)
				pphead->_left = cur;
			else
				pphead->_right = cur;
			cur->_parent = pphead;
		}
		else
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		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)
		{
			parent->_bf = cur->_bf = 0;
		}
		//第二种情况
		else if (bf == 1)
		{
			parent->_bf = -1, cur->_bf = 0, curleft->_bf = 0;
		}
		//第三种情况
		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 = cur->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = curright->_bf = 0, cur->_bf = -1;
		}
		else if (bf == -1)
		{
			parent->_bf = 1, cur->_bf = curright->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void Print()
	{
		Print(_root);
	}
	void Print(Node* root)
	{
		if (root == nullptr) return;

		Print(root->_left);
		cout << root->_kv.second << ' ';
		Print(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