盐析白兔

这个屌丝很懒，什么也没留下！

热门标签

数据结构之进阶二叉树（二叉搜索树和AVL树、红黑树的实现）超详细解析，附实操图和搜索二叉树的实现过程图

作者：盐析白兔 | 2024-04-11 23:14:51

踩

绪论
“生命有如铁砧，愈被敲打，愈能发出火花。——伽利略”；本章主要是数据结构二叉树的进阶知识，若之前没学过二叉树建议看看这篇文章一篇掌握二叉树，本章的知识从浅到深的对搜索二叉树的使用进行了介绍和对其底层逻辑的实现进行了讲解，希望能对你有所帮助。话不多说安全带系好，发车啦（建议电脑观看）。

1.二叉搜索树

1.1二叉搜索树的概念:

二叉搜索树又称二叉排序树/二叉查找树**，它或者是一棵空树。二叉搜索树还有二叉树的性质不同的是其性质有：
1. 大于子树根节点的值存在根节点的右子树
2. 小于子树根节点的值存在根节点的左子树
3. 左右子树都是二叉搜索树
换种说法：若它的左子树不为空，则左子树上所有节点的值都小于根节点的值、若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。

1.2二叉树搜索树一些常用功能（基本功能）

1.2.1 插入数据

有了前面的二叉搜索树的性质后，能很好的想到其插入的实现，只不过其中会有一些小的细节需要注意！
主要是判断当前子树根节点的值和传进来的值进行比较，然后当走到为空时，表示就是为要插入的位置
注意细节：

当根节点为空时，修改根节点即可。
我们需要记录父节点然后链接父子节点。

具体见下面代码：

bool Insert(const K& key, const V& val)
{
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}

	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (cur->_key == key)
		{
			return false;//不插入相同的值
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			parent = cur;
			cur = cur->_right;
		}
	}
	//当循环结束表示已经到了所要插入节点的位置！
	cur = new Node(key);
	if (parent->_key > key)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	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

1.2.2 删除数据

对于删除数据来说有几个不同的情况：

当删除节点没有左右节点时，我们直接将其节点删除即可

当删除节点只有左节点/右节点时
将这个左节点/右节点链接到删除节点的父节点
当删除节点用同时有两个节点
使用替换删除法（找到删除节点左子树的最右节点（最大节点）/删除节点右子树的最左节点（最小节点）后替换到删除的节点后删除，不过删除的时候要注意链接（2）！）

注意：假如交换的节点有子树那么需要注意将其链接到交换节点的父节点

此处可以把1和2情况并到一起写，即当有左为空/右为空时不管右/左为不为空都连接到其父节点
具体代码实现：

bool Erase(const K& key)
{
	Node* parent = nullptr, * child = nullptr;//删除节点的父亲
	Node* cur = _root;//所要删除的节点
	while (cur)
	{
		if (cur->_key == key) //找到删除节点
		{
			//可以把左右为空和 左或右不为空写在一起
			
			if (cur->_left == nullptr)//当其左边为空时
			{
				if (cur == _root)
				{
					_root = cur->_right;
				}
				else
				{
					//即当有左为空时不管删除节点的右为不为空都直接连接到其父节点

					if (parent->_left == cur)//判断在父节点的左边还是右边
					{
						parent->_left = cur->_right;
					}
					else// if (parent->_right = cur)
					{
						parent->_right = cur->_right;
					}
				}
				delete cur;
			}
			else if (cur->_right == nullptr)//当其右边为空时
			{
				if (cur == _root)
				{
					_root = cur->_left;
				}
				else
				{
					if (parent->_left == cur)
					{
						parent->_left = cur;
					}
					else// if (parent->_right = cur)
					{
						parent->_right = cur;
					}
				}
				delete cur;
			}
			else//当左右同时不为空时
			{
				//找到删除节点左子树的最大值/右子树的最小值、与删除节点交换
				//找到左子树的最右节点
				Node* tmp = cur->_left;//最右节点
				Node* p = cur;//最右节点的父节点
				while (tmp->_right)
				{
					p = tmp;
					tmp = tmp->_right;
				}

				//父节点链接 最右节点的左节点
				if (p->_right == tmp) {
					p->_right = tmp->_left;
				}
				else {
					p->_left = tmp->_left;
				}

				swap(tmp->_key, cur->_key);
				//交换后删除即可
				delete tmp;
			}
			return true;
		}
		else if (cur->_key > key)//找不到继续循环
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			parent = cur;
			cur = cur->_right;
		}
	}
	return 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
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

1.2.3查找数据

直接利用二叉搜索树的性质即可很好的写出查找
通过大的在右小的在左的性质，就能最多树的层数次就能找到
若找不到则就会找到空的位置处

Node* Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_key == key)
		{
			return cur;//找到返回该节点
		}
		else if (cur->_key > key)
		{
			cur = cur->_left;
		}
		else
		{
			cur = cur->_right;
		}
	}
	return nullptr;//找不到则返回nullptr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.3二叉树搜索树基本功能用递归式实现

从代码直接分析，若有啥问题可以评论提出喔！

1.3.1插入

bool _InsertR(Node*& root, const K& key)//递归式插入 Recursion
{
	if (root == nullptr)
	{
	//此处为引用也就是别名，当修改root就其实就是修改到了树（就不用链接了）
		root = new Node(key);
		return true;
	}
	if (root->_key == key)//若相等则表示已经插入过了那么返回错误
	{
		return false;
	}
	else if (root->_key > key)//当root值大于key时往左走
	{
		return _InsertR(root->_left, key);
	}
	else//当root值小于key时往右走
	{
		return _InsertR(root->_right, key);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1.3.2删除

bool _EraseR(Node*& root, const K& key)
{
	//同样当左右无节点时直接删除
	//当只有左或者只有右时，链接其右或左到祖先即可
	//当同时有左右子树时交换删除
	if (root == nullptr) {//为空表示不存在返回空
		return false;
	}
	if (root->_key > key)//当root值大于key时往左走
	{
		return _EraseR(root->_left, key);
	}
	else if (root->_key < key)//当root值小于key时往右走
	{
		return _EraseR(root->_right, key);
	}
	else//找到后
	{
		if (root->_left == nullptr)
		{
			Node* tmp = root;
			root = root->_right;//因为root是引用，所以当修改root后会影响到整棵树
			delete tmp;//再将原本的root给释放了
			
			return true;
		}
		else if (root->_right == nullptr)
		{
			Node* tmp = root;
			root = root->_left;//因为root是引用，所以当修改root后会影响到整棵树
			delete tmp;//再将原本的root给释放了
			
			return true;
		}
		else
		{
			Node* tmp = root->_left;//找到左子树的最大值（最右值）
			while (tmp->_right)
			{
				tmp = tmp->_right;
			}

			swap(tmp->_key, root->_key);//交换

			return _EraseR(root->_left, key);//通过递归删除把key删除，里面就包含了链接
		}
	}
}
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

1.3.3查找

此处如果你已经理解了上面的那么这里就非常简单了就不过诉了

Node* _FindR(Node* root, const K& key)
{
	if (root == nullptr)
	{
		return nullptr;
	}

	if (root->_key < key)
	{
		return _FindR(root->_right, key);
	}
	else if (root->_key > key)
	{
		return _FindR(root->_left, key);
	}
	else
	{
		return root;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.4二叉搜索树的源码

如果是要学习的话，建议一定要将整体的结构框架理清楚了，下面是二叉搜索树的整体代码，包括了构造函数、析构函数、以及一些还没交代的函数。

template<class K>
struct BSTreeNode
{
	BSTreeNode(const K& key)
		:_key(key)
		, _left(nullptr)
		, _right(nullptr)
	{}

	K _key;
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
};

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree() = default;


	~BSTree()
	{
		_Destory(_root);
	}

	//BSTree(const BSTree<K>& t)
	//{
	//	_Copy(t._root);
	//}

	BSTree(const BSTree<K>& t)
	{
		_root = _Copy(t._root);
	}

	BSTree<K>& operator=(BSTree<K> t)
	{
		//_Destory(_root);
		//_Copy(t._root);

		swap(_root, t._root);//现代写法
		return *this;
	}


	void InOrder()
	{
		_InOrder(_root);
	}

	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_key == key)
			{
				return false;//不插入相同的值
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				parent = cur;
				cur = cur->_right;
			}
		}
		//当循环结束表示已经到了所要插入节点的位置！
		cur = new Node(key);
		if (parent->_key > key)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		return true;
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key == key)
			{
				return cur;//不插入相同的值
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				cur = cur->_right;
			}
		}
		return nullptr;
	}

	//替换法 删除
	//找到删除节点的左子树的最大值(最左子树的右节点)/右子树的最小值(右子树的最左节点)后与删除的位置进行交换
	bool Erase(const K& key)
	{
		Node* parent = nullptr, * child = nullptr;//删除节点的父亲
		Node* cur = _root;//所要删除的节点
		while (cur)
		{
			if (cur->_key == key)
			{
				//if (cur->_left == nullptr &&
				//	cur->_right == nullptr)
				//{
				//	delete cur;
				//}
				//else if (del->_left && del->_right)
				//{
				//	//MaxNode(del->_left);//左子树的最大值
				//	Node* min = MinNode(del->_right); //右子树的最小值
				//	swap(del, min);
				//	delete del;
				//}
				//可以把左右为空和 左或右不为空写在一起

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

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

				}
				else
				{
					//找到删除节点左子树的最大值/右子树的最小值、与删除节点交换
					//交换后删除即可
					Node* tmp = cur->_left;
					Node* p = cur;
					while (tmp->_right)
					{
						p = tmp;
						tmp = tmp->_right;
					}

					if (p->_right == tmp) {
						p->_right = tmp->_left;
					}
					else {
						p->_left = tmp->_left;
					}

					swap(tmp->_key, cur->_key);
					delete tmp;
				}
				return true;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				parent = cur;
				cur = cur->_right;
			}
		}
		return false;
	}



	bool InsertR(const K& key)//递归式插入 Recursion
	{
		return _InsertR(_root, key);
	}

	Node* FindR(const K& key)
	{
		return _FindR(_root, key);
	}

	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}



private:


	void _Destory(Node* root)
	{
		if (root == nullptr) return;
		_Destory(root->_left);
		_Destory(root->_right);
		delete root;
	}

	//void _Copy(Node* root)
	//{
	//	if (root == nullptr) return;
	//	_InsertR(_root, root->_key);
	//	_Copy(root->_left);
	//	_Copy(root->_right);
	//}

	Node* _Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* newRoot = new Node(root->_key);
		newRoot->_left = _Copy(root->_left);
		newRoot->_right = _Copy(root->_right);

		return newRoot;
	}

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

		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

	//判断root->_key 与 key
	bool _InsertR(Node*& root, const K& key)//递归式插入 Recursion
	{
		if (root == nullptr)
		{
			root = new Node(key);//此处为引用也就是别名，当修改root就其实就是修改到了树
			return true;
		}
		if (root->_key == key)
		{
			return false;
		}
		else if (root->_key > key)
		{
			return _InsertR(root->_left, key);
		}
		else
		{
			return _InsertR(root->_right, key);
		}
	}

	Node* _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
		{
			return nullptr;
		}

		if (root->_key < key)
		{
			return _FindR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _FindR(root->_left, key);
		}
		else
		{
			return root;
		}
	}

	bool _EraseR(Node*& root, const K& key)
	{
		//同样当左右无节点时直接删除
		//当只有左或者只有右时，链接其右或左到祖先即可
		//当同时有左右子树时交换删除
		if (root == nullptr) {
			return false;
		}
		if (root->_key > key)
		{
			return _EraseR(root->_left, key);
		}
		else if (root->_key < key)
		{
			return _EraseR(root->_right, key);
		}
		else
		{
			if (root->_left == nullptr)
			{
				Node* tmp = root;
				root = root->_right;//因为root是引用，所以当修改root后会影响到整棵树
					delete tmp;//再将原本的root给释放了
				return true;
			}
			else if (root->_right == nullptr)
			{
				Node* tmp = root;
				root = root->_left;//因为root是引用，所以当修改root后会影响到整棵树
				delete tmp;//再将原本的root给释放了
				return true;
			}
			else
			{
				Node* tmp = root->_left;//找到左子树的最大值（最右值）
				while (tmp->_right)
				{
					tmp = tmp->_right;
				}

				swap(tmp->_key, root->_key);//交换

				return _EraseR(root->_left, key);//通过递归删除把key删除，里面就包含了链接
			}
		}
	}
	Node* _root;
};
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
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365

1.5二叉搜索树的应用

k模型，K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。如:给一个单词word，判断该单词是否拼写正确。
KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：英汉词典就是英文与中文对应关系<English，meaning>、或者统计个数对应的就是元素和个数的关系<ele,count>。

在上面我们写的是就是k模型，下面我们将其修改为kv模型(对于k模型来说大概的都不需要修改只有一部分需要简单修改)
具体代码为：

template<class K, class V>
struct BSTreeNode
{
	BSTreeNode(const K& key, const V& val)
		:_key(key)
		, _val(val)
		, _left(nullptr)
		, _right(nullptr)
	{}

	K _key;
	V _val;
	BSTreeNode<K, V>* _left;
	BSTreeNode<K, V>* _right;
};

template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K, V> Node;
public:
	BSTree()
		:_root(nullptr)
	{}

	void InOrder()
	{
		_InOrder(_root);
	}

	bool Insert(const K& key, const V& val)
	{
		//1. 当根节点为空时，修改根节点即可。
		if (_root == nullptr)
		{
			_root = new Node(key, val);
			return true;
		}


		//2. 我们需要记录父节点然后链接父子节点。
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_key == key)
			{
				return false;//不插入相同的值
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				parent = cur;
				cur = cur->_right;
			}
		}
		//当循环结束表示已经到了所要插入节点的位置！
		cur = new Node(key, val);
		if (parent->_key > key)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		return true;
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key == key)
			{
				return cur;//不插入相同的值
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				cur = cur->_right;
			}
		}
		return nullptr;
	}

	//替换法 删除
	//找到删除节点的左子树的最大值(最左子树的右节点)/右子树的最小值(右子树的最左节点)后与删除的位置进行交换
	bool Erase(const K& key)
	{
		Node* parent = nullptr, * child = nullptr;//删除节点的父亲
		Node* cur = _root;//所要删除的节点
		while (cur)
		{
			if (cur->_key == key) //找到删除节点
			{
				if (cur->_left == nullptr)//当其左边为空时
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						//即当有左为空时不管删除节点的右为不为空都直接连接到其父节点

						if (parent->_left == cur)//判断在父节点的左边还是右边
						{
							parent->_left = cur->_right;
						}
						else// if (parent->_right = cur)
						{
							parent->_right = cur->_right;
						}
					}
					delete cur;
				}
				else if (cur->_right == nullptr)//当其右边为空时
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur;
						}
						else// if (parent->_right = cur)
						{
							parent->_right = cur;
						}
					}
					delete cur;
				}
				else//当左右同时不为空时
				{
					//找到删除节点左子树的最大值/右子树的最小值、与删除节点交换
					//找到左子树的最右节点
					Node* tmp = cur->_left;//最右节点
					Node* p = cur;//最右节点的父节点
					while (tmp->_right)
					{
						p = tmp;
						tmp = tmp->_right;
					}

					//父节点链接 最右节点的左节点
					if (p->_right == tmp) {
						p->_right = tmp->_left;
					}
					else {
						p->_left = tmp->_left;
					}

					swap(tmp->_key, cur->_key);
					//交换后删除即可
					delete tmp;
				}
				return true;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				parent = cur;
				cur = cur->_right;
			}
		}
		return false;
	}

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

		_InOrder(root->_left);
		cout << root->_key << '-' << root->_val << " ";
		_InOrder(root->_right);
	}

	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

英汉词典实现：

int main()
{
	kv::BSTree<string, string> dict;
	//插入单词
	dict.Insert("sort", "种类");
	dict.Insert("left", "左边");
	dict.Insert("right", "右边");
	dict.Insert("insert", "插入");
	dict.Insert("key", "钥匙");

	string str;
	while (cin>>str)//输入所要查找的单词
	{
		kv::BSTreeNode<string, string>* ret = dict.Find(str);
		if (ret)
		{
			cout << ret->_val << endl;
		}
		else
		{
			cout << "不存在" << endl;
		}
	}
	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

在这里插入图片描述

计数实现：

int main()
{
	string arr[] = { "苹果", "苹果","梨子", "香蕉", "苹果", "桃子", "哈密瓜", "梨子", "苹果", "西瓜", "哈密瓜", "苹果", "桃子" };
	kv::BSTree<string, int> countTree;
	for (auto& e : arr)
	{
		kv::BSTreeNode<string, int>* ret = countTree.Find(e);
		if (ret == nullptr)
		{
			countTree.Insert(e, 1);
		}
		else
		{
			ret->_val++;
		}
	}
	countTree.InOrder();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在这里插入图片描述

2.键值对、关联式容器、序列式容器

在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器。因为其底层为线性序列的数据结构，里面存储的是元素本身。
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高，如：map、set、unordered_map、unordered_set。
键值对用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。
键值对可以用一个新的变量 pair<K,V> 表示
其结构可以看成：

template <class T1, class T2>
struct pair
{
	T1 first;
	T2 second;
	
	pair(): first(T1()), second(T2())
	{}

	pair(const T1& a, const T2& b): first(a), second(b)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12

有了上面这个类，我们可以定义一个变量为 pair<int,int> _kv
这样就能调用其内部的元素：_kv.first代表第一个元素K、_kv.second表示第二个元素
或者为pair<int,int>* _kv,_kv->first同样代表第一个元素、_kv->second表示第二个元素

3.AVL树

3.1AVL树的概念

当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

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

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在
$O(log_2 n)$ ，搜索时间复杂度O( $log_2 n$ )。

3.2AVL树的构造

AVL树是一个三叉树，他的节点有三个指针分别指向左孩子、右孩子、父节点，还有一个值（这个值是kv模型的）和一个平衡因子。

具体如下：

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode(const pair<K,V>& kv)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _bf(0)
	{}

	AVLTreeNode<K,V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;

	int _bf;   // 节点的平衡因子 balance factor
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.3AVL树的基本功能

3.3.1平衡因子

在某个根上其左右子树的高度差（左子树的高度- 右子树的高度）

例子：直接通过下面的图来理解：
在这里插入图片描述

上图中在原图上的左子树的子叶增加元素（可增加该左子树的左边或者右边）
一开始可以看到所有的根的平衡因子都为0因为左右子树的高度一样。

当在最左边加上一个节点后，其平衡被打破为-1（根的左子树增加一个(所以根的右子树-左子树 = -1)，对于该左子树来说也是其左子树增加所以同样的平衡变成 -1）
当在左子树的最右加上一个节点后，对于根来说仍然是左子树有变高（所以还是-1），而对于该左子树来说那就是其右子树增加了（那么右子树-左子树=1）

在上面插入新节点的例子中仍然满足平衡二叉树的平衡条件（左右孩子的高度差不超过1），如果出现平衡因子出现问题的话那就需要去旋转！（具体请继续往下看）

3.3.2插入（以及插入中的左旋、右旋、左右双旋、右左双旋的问题）

AVL树的插入本质上还是搜索二叉树的插入，但因为加入了平衡因子的所就可能出现一下问题：当插入一个节点后其平衡因子只可能变成 1，0，-1，-2，2
那么这几个平衡因子产生的情况又能分为几种情况：
附：下面的例子中的长方框表示着子树，而小框就表示新增的节点

当平衡因子变成了0 ：那么表示新增节点后使平衡，那么其实是不用做什么的，因为该子树的层数并没有增加，仅仅只需把该子树的平衡因子改成0即可。
当平衡因子变成了1/-1：那么表示该子树的层数发生了改变，那么连锁的也会导致上方的祖先的平衡因子发生改变。
如何向上调整：改变cur和parent的关系即可（cur = parent，parent = parent->parent）
当平衡因子变成-2/2：此时表示在原本高的一方又加了一个节点，那么此时因为平衡因子的错误，那么需要去旋转来解决这个问题。
旋转又分为多种情况：
附：在下面多以cur和parent的关系为一棵子树来看。
1.右旋：当在左子树的左边新增元素（左左），此时因为原本为-1的p再在左边加元素后就变成了-2，此时就需要对cur进行右旋，方法为：将把cur的右子树链接成parent，再把parent的左子树换成cur的右子树（此时就断开了链接）（具体如下图）
旋转后cur = p = 0
代码：

void RotateR(Node* parent)
{
	Node* SubL = parent->_left;//此处就为 cur
	Node* SubLR = SubL->_right;

	//parent的左换成cur的右
	parent->_left = SubLR;
	//把cur的右孩子换成parent
	SubL->_right = parent;
	
	//注意还要修改其父指针
	Node* Ppnode = parent->_parent;

	parent->_parent = SubL;
	if (SubLR)//cur的右边可能为空
		SubLR->_parent = parent;

	if (_root == parent)//如果parent为根节点，则需要把subR改变成根节点并且其父亲为nullptr
	{
		_root = SubL;
		SubL->_parent = nullptr;
	}
	else
	{
		//同时还要考虑父亲 是祖先的左或右
		if (Ppnode->_left == parent)
		{
			Ppnode->_left = SubL;
		}
		else
		{
			Ppnode->_right = SubL;
		}
		SubL->_parent = Ppnode;
	}


	SubL->_bf = 0;
	parent->_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

2.左旋：当在右子树的右边新增节点（右右），同样的就是 p就将变成2，此时要用对cur左旋，方法为：将cur的左子树断开链接为p，再把p的右子树断开链接成cur的左子树在这里插入图片描述
旋转后cur = p = 0
代码：

void RotateL(Node* parent)
{
	Node* SubR = parent->_right;//此处就为 cur
	Node* SubRL = SubR->_left;

	//parent的右换成cur的左
	parent->_right = SubRL;
	//把cur的左孩子换成parent
	SubR->_left = parent;

	Node* Ppnode = parent->_parent;

	//注意 还要修改其父指针

	parent->_parent = SubR;
	if (SubRL)//右边可能为空
		SubRL->_parent = parent;
		
	if (_root == parent)//如果parent为根节点，则需要把subR改变成根节点并且其父亲为nullptr
	{
		_root = SubR;
		SubR->_parent = nullptr;
	}
	else
	{
		//同时还要考虑父亲 是祖先的左或右
		if (Ppnode->_left == parent)
		{
			Ppnode->_left = SubR;
		}
		else
		{
			Ppnode->_right = SubR;
		}
		SubR->_parent = Ppnode;
	}
	SubR->_bf = 0;
	parent->_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

3.左右双旋：此处我们先定义p（parent）、subL（parent的左子树）、subLR（subL的右子树），当在左子树的右边新增节点（左右），此时我们先对 subL和subLR 组成的子树进行左旋后，再对p和subLR组成的子树进行右旋。其中有两种可能，当插入到subLR的左边/subLR的右边时他们对平衡因子的影响是不一样的我们需要分开讨论，具体见下图：在这里插入图片描述
旋转后当在subLR的左边插入的话 subLR = subL = 0， p = 1，若在subLR的右边插入的话则subLR = p = 0 ， subL = -1
代码：

void RotateLR(Node* parent)
{
	Node* subL = parent->_left;//此处就为 cur

	Node* subLR = subL->_right;
	int bf = subLR->_bf; 
	//先对cur 进行左旋 再对 parent进行右旋

	RotateL(subL);
	RotateR(parent);

	if (bf == 0)//自己为新增
	{
		parent->_bf = subL->_bf = subLR->_bf = 0;
	}
	else if (bf == -1)
	{
		// subRL的左子树新增
		parent->_bf = 1;

		subLR->_bf = 0;
		subL->_bf = 0;
	}
	else if (bf == 1)
	{
		// subRL的右子树新增
		parent->_bf = 0;
		subLR->_bf = 0;
		
		subL->_bf = -1;
	}
	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
33
34
35
36

4.右左双旋：此处我们先定义p（parent）、subR（parent的右子树）、subRL（subR的左子树），当在右子树的左边新增节点（右左），此时我们先对 subR和subRL 组成的子树进行右旋后，再对p和subRL组成的子树进行左旋。其中有两种可能，当插入到subRL的左边/subRL的右边时他们只是对平衡因子的影响是不一样的我们需要分开讨论，具体见下图：在这里插入图片描述
旋转后当在subLR的左边插入的话 subRL = p = 0， subR = 1，若在subLR的右边插入的话则subRL = subR = 0， p = 1
代码：

void RotateRL(Node* parent)
{
	Node* subR = parent->_right;//此处就为 cur
	Node* subRL = subR->_left;
	int bf = subRL->_bf;
	//先对cur 进行左旋 再对 parent进行右旋

	RotateR(subR);
	RotateL(parent);


	if (bf == 0)//自己为新增
	{
		parent->_bf = subR->_bf = subRL->_bf = 0;
	}
	else if (bf == -1)
	{
		// subRL的左子树新增
		subR->_bf = 1;

		subRL->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == 1)
	{
		// subRL的右子树新增
		subR->_bf = 0;
		subRL->_bf = 0;

		parent->_bf = -1;
	}
	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
33
34
35
36

对于插入函数代码：

bool Insert(const pair<K,V>& kv)
{
	//平衡二叉树 ： 左子树的值都小于根的值 、 右子树的值都大于根的值
	Node* cur = _root;
	Node* parent = nullptr;

	if (!_root) {
		_root = new Node(kv);
		return true;
	}
	//1.找到所要插入的位置
	while (cur)
	{
		if (cur->_kv.first > kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_kv.first < kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else//若已经存在则返回插入失败
		{
			return false;
		}
	}
	
	//2. 确立位置后 ， new出新节点在cur处，然后在建立 链接关系
	//关系：
	// cur 没有左右为null
	// 主要是改变其_parent 和 父亲的left/right, 而要去判断cur 在 _parent的左还是右  通过比较kv.first 和 父亲的kv.first的值
	//此处parent 为其 父亲
	cur = new Node(kv);
	if (parent->_kv.first > kv.first)
	{
		parent->_left = cur;
		//注意此处也要改变 cur 的 _parent
		cur->_parent = parent;
	}
	else
	{
		parent->_right = cur;
		cur->_parent = parent;
	}

	while (parent)
	{

		//建立链接后，因为有了新插入的节点 故需要 先修改平衡因子
		//某个根节点的平衡因子为 ： 右孩子的_bf（平衡因子） - 左孩子的_bf

		//插入后 父亲可能的情况为：
		//-2: 左边高插到了左
		//-1: 平衡到 插左边 
		//0 : 1 / -1 -> 插到左或右 // 
		//1 : 平衡插右边
		//2 : 右 右
		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)//当父亲的平衡因子为1，表示该子树的层数有了增加，但任然是满足AVL树的条件
		{											   //因为子树层数的增加，则对应的会影响到祖先，故需要向上修改祖先的平衡因子
			cur = parent;
			parent = parent->_parent;
		}

		else if(parent->_bf == 2 || parent->_bf == -2)//当父亲的bf 为 2/-2 时则已经影响到了AVL树的平衡，故需要去通过旋转来保证AVL树
		{
			if (parent->_bf == -2 && cur->_bf == -1)//左左
			{
				//进行对父节点的右旋
				RotateR(parent);
			}
			if (parent->_bf == -2 && cur->_bf == 1)//左右
			{
				//先右旋再左旋
				RotateLR(parent);

			}
			if (parent->_bf == 2 && cur->_bf == 1)//右右
			{
				//左旋
				RotateL(parent);

			}
			if (parent->_bf == 2 && cur->_bf == -1)//右左
			{
				//先左旋再右旋
				RotateRL(parent);
			}
			//注意此处当旋转完后就直接break跳出循环了，因为其在内部已经将平衡因子调整好了，不用再考虑祖先平衡因子问题
			// 1、旋转让这颗子树平衡了
			// 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新
			break;
		}
		else 
		{
			assert(0);
		}
	}
	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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

3.4AVL树的源码

在其中还包括了一些扩展功能

求树的高度（_Height）。
判断而AVL的每个节点是否满足平衡条件（IsBalance），这个函数是用来测试该AVL树是否满足条件的，实现原理为：遍历整个二叉树，并且在过程中判断其左右子树的差是否满足平衡条件。

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode(const pair<K,V>& kv)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _bf(0)
	{}

	AVLTreeNode<K,V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;

	int _bf;   // 节点的平衡因子 balance factor
};

// AVL: 二叉搜索树 + 平衡因子的限制
template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K,V> Node;//通过模板将node确定类型
public:
	AVLTree()
		:_root(nullptr)
	{}

	// 在AVL树中插入值为data的节点
	bool Insert(const pair<K,V>& kv)
	{
		//平衡二叉树 ： 左子树的值都小于根的值 、 右子树的值都大于根的值
		Node* cur = _root;
		Node* parent = nullptr;

		if (!_root) {
			_root = new Node(kv);
			return true;
		}
		//1.找到所要插入的位置
		while (cur)
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else//若已经存在则返回插入失败
			{
				return false;
			}
		}
		
		//2. 确立位置后 ， new出新节点在cur处，然后在建立 链接关系
		//关系：
		// cur 没有左右为null
		// 主要是改变其_parent 和 父亲的left/right, 而要去判断cur 在 _parent的左还是右  通过比较kv.first 和 父亲的kv.first的值
		//此处parent 为其 父亲
		cur = new Node(kv);
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
			//注意此处也要改变 cur 的 _parent
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}

		while (parent)
		{
			//建立链接后，因为有了新插入的节点 故需要 先修改平衡因子
			//某个根节点的平衡因子为 ： 右孩子的_bf（平衡因子） - 左孩子的_bf

			//插入后 父亲可能的情况为：
			//-2: 左边高插到了左
			//-1: 平衡到 插左边 
			//0 : 1 / -1 -> 插到左或右 // 
			//1 : 平衡插右边
			//2 : 右 右
			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)//当父亲的平衡因子为1，表示该子树的层数有了增加，但任然是满足AVL树的条件
			{											   //因为子树层数的增加，则对应的会影响到祖先，故需要向上修改祖先的平衡因子
				cur = parent;
				parent = parent->_parent;
			}

			else if(parent->_bf == 2 || parent->_bf == -2)//当父亲的bf 为 2/-2 时则已经影响到了AVL树的平衡，故需要去通过旋转来保证AVL树
			{
				if (parent->_bf == -2 && cur->_bf == -1)//左左
				{
					//进行对父节点的右旋
					RotateR(parent);
				}
				if (parent->_bf == -2 && cur->_bf == 1)//左右
				{
					//先右旋再左旋
					RotateLR(parent);

				}
				if (parent->_bf == 2 && cur->_bf == 1)//右右
				{
					//左旋
					RotateL(parent);

				}
				if (parent->_bf == 2 && cur->_bf == -1)//右左
				{
					//先左旋再右旋
					RotateRL(parent);
				}
				//注意此处当旋转完后就直接break跳出循环了，因为其在内部已经将平衡因子调整好了，不用再考虑祖先平衡因子问题
				// 1、旋转让这颗子树平衡了
				// 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新
				break;
			}
			else 
			{
				assert(0);
			}
		}
		return true;
	}

	// AVL树的验证
	bool IsBalance()
	{
		return _IsBalance(_root);
	}

private:
	// 根据AVL树的概念验证pRoot是否为有效的AVL树
	bool _IsBalance(Node* root)
	{
		//主要是平衡因子的判断
		//此处不同用bf ， 此处应该用height来确定bf是否正确

		if (!root) return true;
		
		int leftbf = _Height(root->_left);
		int rightbf = _Height(root->_right);

		if (rightbf - leftbf != root->_bf) {
			cout << "平衡因子出问题" << endl;
		}

		if (abs(rightbf - leftbf) > 1)
			return false;
		
		return _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}

	size_t _Height(Node* root)
	{
		if (!root) return 0;
		int LeftchildTreeHeight = _Height(root->_left);
		int RightchildTreeHeight = _Height(root->_right);
		return LeftchildTreeHeight > RightchildTreeHeight ? LeftchildTreeHeight + 1 : RightchildTreeHeight + 1;
	}
	// 右单旋
	// 把cur的右孩子换成parent，parent的左换成cur的右
	void RotateR(Node* parent)
	{
		Node* SubL = parent->_left;//此处就为 cur
		Node* SubLR = SubL->_right;

		//parent的左换成cur的右
		parent->_left = SubLR;
		//把cur的右孩子换成parent
		SubL->_right = parent;
		
		//注意还要修改其父指针
		Node* Ppnode = parent->_parent;

		parent->_parent = SubL;
		if (SubLR)//cur的右边可能为空
			SubLR->_parent = parent;

		if (_root == parent)//如果parent为根节点，则需要把subR改变成根节点并且其父亲为nullptr
		{
			_root = SubL;
			SubL->_parent = nullptr;
		}
		else
		{
			//同时还要考虑父亲 是祖先的左或右
			if (Ppnode->_left == parent)
			{
				Ppnode->_left = SubL;
			}
			else
			{
				Ppnode->_right = SubL;
			}
			SubL->_parent = Ppnode;
		}


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

	// 左单旋
	// 同理
	void RotateL(Node* parent)
	{
		Node* SubR = parent->_right;//此处就为 cur
		Node* SubRL = SubR->_left;

		//parent的右换成cur的左
		parent->_right = SubRL;
		//把cur的左孩子换成parent
		SubR->_left = parent;


		Node* Ppnode = parent->_parent;

		//注意 还要修改其父指针

		parent->_parent = SubR;
		if (SubRL)//右边可能为空
			SubRL->_parent = parent;

		if (_root == parent)//如果parent为根节点，则需要把subR改变成根节点并且其父亲为nullptr
		{
			_root = SubR;
			SubR->_parent = nullptr;
		}
		else
		{
			//同时还要考虑父亲 是祖先的左或右
			if (Ppnode->_left == parent)
			{
				Ppnode->_left = SubR;
			}
			else
			{
				Ppnode->_right = SubR;
			}
			SubR->_parent = Ppnode;
		}

		SubR->_bf = 0;
		parent->_bf = 0;
	}
	// 右左双旋
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;//此处就为 cur
		Node* subRL = subR->_left;
		int bf = subRL->_bf;
		//先对cur 进行左旋 再对 parent进行右旋

		RotateR(subR);
		RotateL(parent);


		if (bf == 0)//自己为新增
		{
			parent->_bf = subR->_bf = subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			// subRL的左子树新增
			subR->_bf = 1;

			subRL->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 1)
		{
			// subRL的右子树新增
			subR->_bf = 0;
			subRL->_bf = 0;

			parent->_bf = -1;
		}
		else
		{
			assert(false);
		}
	}
	
	// 对于在 左子树的 右边加元素的情况 ， 用左右双旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;//此处就为 cur

		Node* subLR = subL->_right;
		int bf = subLR->_bf; 
		//先对cur 进行左旋 再对 parent进行右旋

		RotateL(subL);
		RotateR(parent);
		
		if (bf == 0)//自己为新增
		{
			parent->_bf = subL->_bf = subLR->_bf = 0;
		}
		else if (bf == -1)
		{
			// subRL的左子树新增
			parent->_bf = 1;

			subLR->_bf = 0;
			subL->_bf = 0;
		}
		else if (bf == 1)
		{
			// subRL的右子树新增
			parent->_bf = 0;
			subLR->_bf = 0;
			
			subL->_bf = -1;
		}
		else
		{
			assert(false);
		}
	}
private:
	Node* _root;
};
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
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351

4.红黑树

4.1红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

4.2红黑树的性质

红黑树有的性质：

每个节点不是黑色就是红色
树的根节点必须是黑色
如果根节点为红色那么其左右子树必须为黑色节点（不能出现连续的红色节点）
每条路径的黑色节点个数是一样的

注意：其中路径要包括到null节点处的路径
在这里插入图片描述
红黑树确保没有一条路径会比其他路径长出俩倍：
最短路径：是一条全黑节点的路径
最长路径：是在有相同个黑色节点的前提下穿插着红色节点
具体如下图：

4.3红黑树结构的定义

结构是由三叉链（包括了左右父链接）、pair<K,V>值，颜色组成。

enum Color
{
	BLACK,
	RED
};

template<class K , class V>
struct RBTreeNode {
	RBTreeNode<K,V>* _left = nullptr;
	RBTreeNode<K,V>* _right = nullptr;
	RBTreeNode<K,V>* _parent = nullptr;
	pair<K, V> _kv;
	Color _col = RED;//默认生成的节点颜色是红色

	RBTreeNode(const pair<K,V>& kv)
		:_kv(kv)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4.3红黑树结构的基本功能

4.3.1插入数据

插入数据（此处的红黑树是在cur、parent、grandfather、uncle中来看）后面在这个颗树中主要分为三种情况：
在g的左边插入（其中默认插入的节点是红色节点、旋转和AVL树是一样的）时：

当p为红，g、u为黑时插入节点cur。此时把p、u改成黑色将g改成红色，再向上调整把（cur = g ， p = g->p）

当p为红，g为黑、u存在且为黑时插入新节点。

当在左边插入时，就先对局部左边进行变色（情况一），变色后向上调整c、p、g、u，再进行右旋（在向上调整后的树上）后再变色（将p变成黑、g变成黑）。

当在右边插入时，同样先变色（情况一），后向上调整，再进行先左旋和右旋后再进行变色（将g变成红色、c变成黑色）。

3. 当g为黑，p、c也为红、u为空时
此时先左旋+变色（p变成黑色、g变成红色）
在g的右边插入时：是一样的就不过诉了

下面通过代码来看：

// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
// 注意：为了简单起见，本次实现红黑树不存储重复性元素
bool Insert(const pair<K,V>& kv)
{
	//此处和AVL平衡二叉树的性质一样找到所要插入节点的位置 大的在右 、 小的在左
	Node* parent = nullptr;
	Node* cur = _root;
	
	if (cur == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return true;
	}

	//找到插入的位置！
	while (cur)//当为null时表示此处就是要插入的位置！
	{
		if (cur->_kv.first > kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_kv.first < kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else 
		{
			return false;
		}
	}

	//找到位置后，插入
	cur = new Node(kv);//建立新节点
	//建立链接
	if (parent->_kv.first > kv.first)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	cur->_parent = parent;


	//插入时要判断插入后是否会导致不平衡！对于红黑树来说主要问题有
		//1. 不能出现连续的红节点
		//2. 最长路径不超过最短路径的两倍
	//判断是否需要变色/旋转
	// 
	//1.当父亲节点为黑色时，当新增了一个红色节点时就结束插入了
	// 
	//2.当父为红时：
	//	情况一(仅变色即可)：当parent为红 grandfather为黑 uncle存在且为黑 插入一个新节点
	// 
	//
	while (parent && parent->_col == RED)
	{
		Node* g = parent->_parent;//grandfather
		if (g->_left == parent)
		{
			Node* u = g->_right;//uncle
			
			if (u && u->_col == RED)//u存在且为红
			{
				//变色即可
				u->_col = parent->_col = BLACK;
				g->_col = RED;
				
				//向上调整
				cur = g;
				parent = g->_parent;
				//当g 的 父亲为黑时或者为null时停止调整
			}
			else //u不存在或者为黑
			{
				if (cur == parent->_left)//此处u不存在和当插入节点在左边时的情况一样直接右旋加变色即可
				{
					//旋转加变色
					RotateR(g);
					parent->_col = BLACK;
					g->_col = RED;
				}
				else
				{
					//旋转加变色
					RotateL(parent);
					RotateR(g);

					cur->_col = BLACK;
					g->_col = RED;
				}
			}
		}
		else
		{
			Node* u = g->_left;//uncle
			if (u && u->_col == RED)//u存在且为红
			{
				//变色即可
				u->_col = parent->_col = BLACK;
				g->_col = RED;

				//向上调整
				cur = g;
				parent = g->_parent;

				//当g 的 父亲为黑时或者为null时停止调整
			}
			else //u不存在或者为黑
			{
				if (cur == parent->_right)//此处u不存在和当插入节点在左边时的情况一样直接右旋加变色即可
				{
					RotateL(g);
					parent->_col = BLACK;
					g->_col = RED;
				}
				else
				{
					RotateR(parent);
					RotateL(g);

					cur->_col = BLACK;
					g->_col = RED;
				}
			}
		}
	}
	_root->_col = BLACK;
	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
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

4.3.判断红黑树的正确性

判断红黑树的正确性，主要还是在于其性质是否满足
主要判断下：

根节点是否为黑
是否出现连续的红色节点
最长路径有没有超过最短路径的两倍
每条路径的黑色节点是否一样

有了这些目标后设计代码（通过注释来解释！）：

bool IsValidRBTRee()
{
	if (_root == nullptr) return true;//此时无节点为真
	if (_root->_col == RED) return false;//根节点只能为黑，若为红返回假

	Node* cur = _root;
	int blackCount = 0;//记录一条路径的黑色节点个数！
	while (cur)
	{
		if (cur->_col == BLACK)
		{
			blackCount++;
		}
		cur = cur->_left;
	}

	return _IsValidRBTRee(_root,blackCount,0);
}

bool _IsValidRBTRee(Node* root, size_t blackCount, size_t pathBlack)
{
	if (root == nullptr)
	{
		if (blackCount != pathBlack)//当为null时表示该路径已经结束，那么判断改路径的黑色节点（pathblack） 和其他路径的黑色节点（blacCount）是否相同
		{
			return false;
		}
		return true;
	}

	if (root->_col == RED)
	{
		if (root->_left && root->_right && (root->_left->_col == RED || root->_right->_col == RED))
		{
			cout << "有连续的红色节点" << endl;
			return false;
		}
	}

	if (root->_col == BLACK)
	{
		pathBlack++;//某条路径的黑节点个数
	}

	//前序遍历
	return _IsValidRBTRee(root->_left, blackCount, pathBlack) &&
		_IsValidRBTRee(root->_right, blackCount, pathBlack);
}
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

4.4红黑树的源码

#pragma once
#include<iostream>
using namespace std;
// 请模拟实现红黑树的插入--注意：为了后序封装map和set，本文在实现时给红黑树多增加了一个头结点

enum Color
{
	BLACK,
	RED
};

template<class K , class V>
struct RBTreeNode {

	RBTreeNode<K,V>* _left = nullptr;
	RBTreeNode<K,V>* _right = nullptr;
	RBTreeNode<K,V>* _parent = nullptr;
	pair<K, V> _kv;
	Color _col = RED;//默认生成的节点颜色是红色

	RBTreeNode(const pair<K,V>& kv)
		:_kv(kv)
	{}
};

template<class K,class V>
class RBTree
{
	typedef typename RBTreeNode<K,V> Node;
public:

	// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
	// 注意：为了简单起见，本次实现红黑树不存储重复性元素
	bool Insert(const pair<K,V>& kv)
	{
		//此处和AVL平衡二叉树的性质一样找到所要插入节点的位置 大的在右 、 小的在左
		Node* parent = nullptr;
		Node* cur = _root;
		
		if (cur == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}

		//找到插入的位置！
		while (cur)//当为null时表示此处就是要插入的位置！
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else 
			{
				return false;
			}
		}

		//找到位置后，插入
		cur = new Node(kv);//建立新节点
		//建立链接
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;


		//插入时要判断插入后是否会导致不平衡！对于红黑树来说主要问题有
			//1. 不能出现连续的红节点
			//2. 最长路径不超过最短路径的两倍
		//判断是否需要变色/旋转
		// 
		//1.当父亲节点为黑色时，当新增了一个红色节点时就结束插入了
		// 
		//2.当父为红时：
		//	情况一(仅变色即可)：当parent为红 grandfather为黑 uncle存在且为黑 插入一个新节点
		// 
		//
		while (parent && parent->_col == RED)
		{
			Node* g = parent->_parent;//grandfather
			if (g->_left == parent)
			{
				Node* u = g->_right;//uncle
				
				if (u && u->_col == RED)//u存在且为红
				{
					//变色即可
					u->_col = parent->_col = BLACK;
					g->_col = RED;
					
					//向上调整
					cur = g;
					parent = g->_parent;
					//当g 的 父亲为黑时或者为null时停止调整
				}
				else //u不存在或者为黑
				{
					if (cur == parent->_left)//此处u不存在和当插入节点在左边时的情况一样直接右旋加变色即可
					{
						//旋转加变色
						RotateR(g);
						parent->_col = BLACK;
						g->_col = RED;
					}
					else
					{
						//旋转加变色
						RotateL(parent);
						RotateR(g);

						cur->_col = BLACK;
						g->_col = RED;
					}
				}
			}
			else
			{
				Node* u = g->_left;//uncle
				if (u && u->_col == RED)//u存在且为红
				{
					//变色即可
					u->_col = parent->_col = BLACK;
					g->_col = RED;

					//向上调整
					cur = g;
					parent = g->_parent;

					//当g 的 父亲为黑时或者为null时停止调整
				}
				else //u不存在或者为黑
				{
					if (cur == parent->_right)//此处u不存在和当插入节点在左边时的情况一样直接右旋加变色即可
					{
						RotateL(g);
						parent->_col = BLACK;
						g->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(g);

						cur->_col = BLACK;
						g->_col = RED;
					}
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}

	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}

//
//	// 获取红黑树最左侧节点
	Node* LeftMost()
	{
		Node* cur = _root;
		while (cur)
		{
			if(cur->_left == nullptr)
			{
				return cur;
 			}
			cur = cur->_left;
		}
		return nullptr;
	}
//
//	// 获取红黑树最右侧节点
	Node* RightMost()
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_right == nullptr)
			{
				return cur;
			}
			cur = cur->_right;
		}
		return nullptr;
	}
//
//	// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
	//	1.每条路径中的黑色节点个数是否一样
	//	2.最长路径不超过最短路径的两倍
	//	3.不能出现连续的红色节点
	//	4.根节点为黑色
	//
	bool IsValidRBTRee()
	{
		if (_root == nullptr) return true;//此时无节点为真

		if (_root->_col == RED) return false;//根节点只能为黑，若为红返回假

		Node* cur = _root;
		int blackCount = 0;//记录一条路径的黑色节点个数！
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				blackCount++;
			}
			cur = cur->_left;
		}

		return _IsValidRBTRee(_root,blackCount,0);
	}

	int Height()
	{
		if (_root == nullptr) return 0;
		return _Height(_root);
	}


	int Size()
	{
		if (_root == nullptr) return 0;

		return _Size(_root);
	}
	
	//检测红黑树中是否存在值为data的节点，存在返回该节点的地址，否则返回nullptr
	Node* Find(const K val)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first == val)
			{
				return cur;
			}
			else if (cur->_kv.first > val)
			{
				cur = cur->_left;
			}
			else {
				cur = cur->_right;
			}
		}
		return nullptr;
	}

private:


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

		return _Size(root->_left) +
			_Size(root->_right) + 1;
	}
	
	int _Height(Node* root)
	{
		if (root == nullptr)return 0;

		int lefthight = _Height(root->_left);

		int righthight = _Height(root->_right);

		return lefthight > righthight ? lefthight + 1 : righthight + 1;
	}
	void _Inorder(Node* root)
	{
		if (root == nullptr)return;

		_Inorder(root->_left);
		cout << root->_kv.first << " " ;
		_Inorder(root->_right);
	}

	bool _IsValidRBTRee(Node* root, size_t blackCount, size_t pathBlack)
	{
		if (root == nullptr)
		{
			if (blackCount != pathBlack)//当为null时表示该路径已经结束，那么判断改路径的黑色节点（pathblack） 和其他路径的黑色节点（blacCount）是否相同
			{
				return false;
			}
			return true;
		}

		if (root->_col == RED)
		{
			if (root->_left && root->_right && (root->_left->_col == RED || root->_right->_col == RED))
			{
				cout << "有连续的红色节点" << endl;
				return false;
			}
		}

		if (root->_col == BLACK)
		{
			pathBlack++;//某条路径的黑节点个数
		}

		//前序遍历
		return _IsValidRBTRee(root->_left, blackCount, pathBlack) &&
			_IsValidRBTRee(root->_right, blackCount, pathBlack);
	}

//	// 为了操作树简单起见：获取根节点
	//Node*& GetRoot();


	void RotateR(Node* parent)
	{
		Node* SubL = parent->_left;//此处就为 cur
		Node* SubLR = SubL->_right;

		//parent的左换成cur的右
		parent->_left = SubLR;
		//把cur的右孩子换成parent
		SubL->_right = parent;

		//注意还要修改其父指针
		Node* Ppnode = parent->_parent;

		parent->_parent = SubL;
		if (SubLR)//cur的右边可能为空
			SubLR->_parent = parent;

		if (_root == parent)//如果parent为根节点，则需要把subR改变成根节点并且其父亲为nullptr
		{
			_root = SubL;
			SubL->_parent = nullptr;
		}
		else
		{
			//同时还要考虑父亲 是祖先的左或右
			if (Ppnode->_left == parent)
			{
				Ppnode->_left = SubL;
			}
			else
			{
				Ppnode->_right = SubL;
			}
			SubL->_parent = Ppnode;
		}

	}

	// 左单旋
	// 同理
	void RotateL(Node* parent)
	{
		Node* SubR = parent->_right;//此处就为 cur
		Node* SubRL = SubR->_left;

		//parent的右换成cur的左
		parent->_right = SubRL;
		//把cur的左孩子换成parent
		SubR->_left = parent;

		Node* Ppnode = parent->_parent;

		//注意 还要修改其父指针

		parent->_parent = SubR;
		if (SubRL)//右边可能为空
			SubRL->_parent = parent;

		if (_root == parent)//如果parent为根节点，则需要把subR改变成根节点并且其父亲为nullptr
		{
			_root = SubR;
			SubR->_parent = nullptr;
		}
		else
		{
			//同时还要考虑父亲 是祖先的左或右
			if (Ppnode->_left == parent)
			{
				Ppnode->_left = SubR;
			}
			else
			{
				Ppnode->_right = SubR;
			}
			SubR->_parent = Ppnode;
		}
	}

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
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409

本章完。预知后事如何，暂听下回分解。

如果有任何问题欢迎讨论哈！

如果觉得这篇文章对你有所帮助的话点点赞吧！

持续更新大量C++细致内容，早关注不迷路。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/408059