数据结构---AVL树

AVL树的概念

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

一颗AVL树或者是空树，或者是具有以下性质的二叉搜索树。

• 它的左右子树都是AVL树
• 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

如果一颗二叉搜索树是高度平衡的，他就是AVL树。如果他有n个皆点，其高度可保持在 O(log2n),搜索时间复杂度O(log2n)。

AVL树节点的定义

template 
class AVLNode
{
public:
	AVLNode* _letf;
	AVLNode* _right;
	AVLNode* _parent;

	pair _kv;

	int _bf;

	AVLNode(const pair& 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
19
20
21

AVL树的插入

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

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

如果这个节点新增在左，parent平衡因子减1；如果新增在右，parent平衡因子加1。如果更新后parent平衡因子为0，说明parent所在的子树的高度不变，不会影响祖先，不用再继续沿着到root的路径往上更新。更新后parent的平衡因子为0或者-1，说明parent所在的子树的高度变化，会影响祖先，需要沿着到root的路径往上更新。更新后parent平衡因子为2或者-2，说明parent所在子树的高度变化且不平衡，要对parent所在的子树进行旋转，让它平衡。

如何通过旋转，让这个树平衡呢？

右边高，就往左边旋转。

左边高，就往右边旋转。

旋转的时候要注意，保持他是搜索树，变成平衡树且降低这个子树的高度。

左单旋，右边高，强行往左边旋。

右单旋与左单旋道理一样。

---

如果出现了上图中的树，靠左单旋或者右单旋就不能到平衡的目的了。这种情况要靠双旋来解决。

就图中的树而言：先以7为旋转点，进行右单旋(此时6会变成7的右儿子，此时树的情况就是一条斜线)，在以5为旋转点，进行左单旋。就可以平衡了。

但这个时候需要对平衡因子做出调整，因为左右旋转之后会把平衡因子更新为0，所以到强行更改一下旋转部分的平衡因子。

	bool insert(const pair& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		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->_parent)
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				// 再更新的过程中，父节点的平衡因子=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);
				}// 1.左单旋
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}// 2.右单旋
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}// 3.右左单旋
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}// 4.左右单旋
				break;
			}
			else
			{
				// 防止代码出bug，遇到平衡因子为>2的情况。
				assert(false);
			}

		}

		return true;

	}
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

源代码

#pragma once

template 
class AVLNode
{
public:
	AVLNode* _left;
	AVLNode* _right;
	AVLNode* _parent;

	pair _kv;

	int _bf;

	AVLNode(const pair& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		,_bf(0)
	{}

};


template 
class AVLTree
{
public:
	typedef AVLNode Node;

	bool insert(const pair& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		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->_parent)
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				// 再更新的过程中，父节点的平衡因子=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);
				}// 1.左单旋
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}// 2.右单旋
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}// 3.右左单旋
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}// 4.左右单旋
				break;
			}
			else
			{
				// 防止代码出bug，遇到平衡因子为>2的情况。
				assert(false);
			}

		}

		return true;

	}

	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;
		}
		else
		{
			assert(false);
		}

	}


	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 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是一颗局部子树，ppnode用来记录局部子树的父节点
		parent->_parent = cur;

		if (parent == _root) // 如果parent是根节点
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else // 如果parent是一颗局部的子树
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}
			cur->_parent = ppnode;
		}


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

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

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


		cur->_right = 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 = 0;
		cur->_bf = 0;
	}

	void InOrder()
	{
		_InOrder(_root);
	}

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

		_InOrder(root->_left);
		cout << root->_kv.first << endl;
		_InOrder(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