数据结构与算法_AVL平衡二叉树_四种旋转，插入和删除

1 AVL平衡二叉树的概念

平衡二叉树在BST树基础上加了平衡操作。
BST树特点 ：在BST树的基础上，引入了节点“平衡”的概念，任意一个节点的左右子树高度差不超过 1 ，为了维持节点的平衡，引入了四种旋转操作，如下：
1.左孩子左子树太高，做右旋转操作
2.右孩子的右子树太高，做左旋转操作
3.左孩子的右子树太高，做左-右旋转操作（也叫左平衡操作）
4.右孩子的左子树太高，做右-左旋转操作（也叫右平衡操作）

AVL树：记忆的时候，与BST树的插入删除联系起来。
下面分别记录AVL的四种失衡操作，并举例说明。

2 AVL的四种旋转操作

2.1 右旋转

右旋转调整。如下图所示，40左子树高度为2，右子树高度为0 ，这种情况称为左失衡，需要进行右旋转。

2.2 左旋转

左旋转调整。当节点的右子树高度大于节点的左孩子高度时候，如下图情况，需要做左旋转调整。
调整方法：先记录当前节点的右孩子。然后，当前节点的右孩子指向当前节点孩子的左孩子；然后孩子节点的左孩子指向当前节点。

2.3 左右旋转

左右旋转，也叫左平衡调整。这种情况需要调整两次，先进行一次左旋转，再进行一次右旋转。如下图所示。

2.4 右左旋转

右左旋转，也称为有平衡操作。这种情况也需要调整两次，即先进行一次右旋转，再进行一次左旋转。

3 AVL的插入，旋转调整举例

4. BST树 和 AVL树插入1-10后，对比

BST树插入1-10后，BST树变成了一个链表；AVL树则是一颗平衡二叉树。

5. AVL四种旋转操作，插入，删除代码实现

#include 
#include 
using namespace std;

// 定义AVL节点类型 
template <typename T>
class AVLTree
{
public:
	AVLTree() : root_(nullptr) { }

	// 插入操作
	void insert(const T &val)
	{
		root_ = insert(root_, val);
	}

	// 删除操作
	void remove(const T & val)
	{
		root_ = remove(root_, val);
	}


private:
	// 定义AVL树节点类型 
	struct Node
	{
		Node(T data = T())
			:data_(data)
			, left_(nullptr)
			, right_(nullptr)
			, height_(1)
		{}
		T data_;
		Node *left_;
		Node *right_;
		int height_;
	};
	Node *root_;

	//
	int max(int a, int b)
	{
		return a > b ? a : b;
	}


	/*
	*	功能：返回node高度
	*/
	int height(Node *node)
	{
		return node == nullptr ? 0 : node->height_;
	}

	/* 
	*	功能：node节点进行右旋转，并返回旋转后的根节点
	*
	*	参数：
	*		 node : 当前节点
	*	
	*   返回值： 
	*		 返回旋转后的根节点
	*/
	Node *rightRotate(Node *node)
	{
		Node *child = node->left_;
		node->left_ = child->right_;
		child->right_ = node;

		// 旋转后根节点和child节点发生了变化，所以要更新高度值。
		node->height_ = max(height(node->left_), height(node->right_)) + 1;
		node->height_ = max(height(child->left_), height(child->right_)) + 1;

		// 返回旋转后的根节点
		return child;
	}

	/*  功能：左旋转，并返回旋转后的根节点
	*
	*	参数：
	*		 node : 根节点
	*
	*   返回值：
	*		 返回旋转后的根节点
	*/
	Node *leftRotate(Node *node)
	{
		Node *child = node->right_;
		node->right_ = child->left_;
		child->left_ = node;

		// 更新旋转后的高度值
		node->height_ = max(height(node->left_), height(node->right_)) + 1;
		child->height_ = max(height(child->left_), height(child->right_)) + 1;

		// 返回旋转后的根节点
		return child;
	}

	/*
	*	功能：左右旋转，并把根节点返回
	*
	*	参数：
	*		  node : 以参数node为旋转轴	
	*/		
	Node * leftBalance(Node *node)
	{
		node->left_ = leftRotate(node->left_);  // 先对根节点左孩子进行左旋转
		return rightRotate(node);				// 再对，根节点右孩子进行右旋转。
	}

	/*
	*	功能：右左旋转，并把根节点返回
	*
	*	参数：
	*		  node : 以参数node为旋转轴
	*/
	Node * rightBalance(Node *node)
	{
		node->right_ = rightRotate(node->right_);  // 以左孩子为根进行左旋
		return leftRotate(node);
	}

	/*
	*	功能：node中插入节点，并返回新插入节点
	*
	*/
	Node * insert(Node *node, const T & val)
	{
		if (node == nullptr)
		{
			return new Node(val);
		}

		if (node->data_ > val)   // 向当前节点的左子树中插入新节点，所以要判断，当前节点的左子树是否太高
		{
			node->left_ = insert(node->left_, val);  // 新插入的节点都在叶子节点上，所以下面回溯时，调整树的平衡状态。

			// 在回溯时候，判断节点是否失衡，如果node的左子树太高导致Node失衡了，
			// 当前在向左子树中插入节点，新节点在左子树的叶子中，只可能导致左子树失衡，不存在右子树失衡的情况，所以直接用左子树高度 减去 右子树高度。
			if (height(node->left_) - height(node->right_) > 1)  // 如果当前节点的左子树比右子树高
			{		 // 分两种情况来判断，一个是左孩子的左子树节点失衡，一个树右孩右子树节点失衡。
				if (height(node->left_->left_) >= height(node->left_->right_))
				{
					node = rightRotate(node);   // 用旋转后的根节点 代替根节点
				}
				else
				{
					node = leftBalance(node);
				}
			}
		}
		else if (node->data_ < val)
		{
			node->right_ = insert(node->right_, val);

			// 在递归回溯时候，判断节点是否失衡，Node的右子树太高，node 失衡了
			if (height(node->right_) - height(node->left_) > 1)
			{
				if (height(node->right_->right_) >= height(node->right_->left_))  // 1-10，插入节点9时会出现这种情况
				{
					node = leftRotate(node);
				}
				else
				{
					node = rightBalance(node);
				}

			}
		}
		else // 如果新插入节点与当前节点相等，不插入，不用再递归，直接回溯
		{
			;
		}
		
		// 更新节点高度。因为递归中增加了新节点，所以回溯时候，更新节点的高度。
		node->height_ = max(height(node->left_), height(node->right_)) + 1;

		return node; // rrturn后，直接回溯，不再向下递归
	}

	/*
	*	功能：删除val节点
	*
	*	参数：
	*		  node: 当前处理的根节点
	*		  val : 待删除的值
	*/
	Node * remove(Node *node,const T & val)
	{
		if (node == nullptr)
		{
			return nullptr;
		}

		if (node->data_ > val)    // 如果当前节点大于val，则从当前节点左孩子中查找
		{
			node->left_ = remove(node->left_, val);
			
			// 删除左子树的节点之后，可能造成右子树太高
			if (height(node->right_) - height(node->left_) > 1)
			{
				// 右子树太高，分两种情况，第一：
				if (height(node->right_->right_) >= height(node->right_->left_))
				{
					// 右孩子的右子树太高
					node = leftRotate(node);
				}
				else
				{
					node = rightBalance(node);
				}
			}

		}
		else if (node->data_ < val)
		{
			node->right_ = remove(node->right_, val);

			// 删除右节点后，可能造成左子树太高
			if (height(node->left_) - height(node->right_) > 1)
			{
				// 如果左孩子的左子树失衡
				if (height(node->left_->left_) >= height(node->left_->right_))
				{
					node = rightRotate(node);
				}
				else
				{
					node = leftBalance(node);
				}
			}

		}
		else  // 删除节点，先删除两个孩子的节点，再删除一个孩子的节点
		{
			 // 找到后，先处理两个孩子的节点，然后再删除一个孩子的节点。
			if (node->left_ != nullptr && node->right_ != nullptr)
			{
				// 为了避免删除前驱和后继节点造成节点失衡，she高删除谁
				if (height(node->left_) >= height(node->right_))
				{
					// 删除	前驱
					Node *pre = node->left_;
					while (pre->right_ != nullptr)
					{
						pre = pre->right_;
					}
					node->data_ = pre->data_;						// 覆盖值
					node->left_ = remove(node->left_, pre->data_);  // 删除前驱节点
				}
				else
				{
					// 删除后继节点
					Node *post = node->right_;
					while (post->right_ != nullptr)
					{
						post = post->left_;
					}
					node->data_ = post->data_;
					node->right_ = remove(node->right_, post->data_);  // 删除后继节点
				}
			}
			else  // 最多有一个孩子节点
			{
				if (node->left_ != nullptr)
				{
					Node *left = node->left_;
					delete node;
					return left;
				}
				else if (node->right_ != nullptr)
				{
					Node *right = node->right_;
					delete node;
					return right;
				}
				else
				{
					return nullptr;
				}
			}

		}

		// 更新节点高度
		node->height_ = max(height(node->left_), height(node->right_)) + 1;
		return node;
	}
};


int main()
{
	AVLTree<int> avl;
	for (int i = 1; i < 11; i++)
	{
		avl.insert(i);
	}

	avl.remove(6);
	system("pause");
	return 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
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
294
295
296
297
298
299
300
301
302
303
304
305
306