【数据结构】红黑树_红黑树判断csdn

一、红黑树的概念

红黑树也是一个二叉搜索树，他是通过对任何一条从根到叶子的路径上各个结点着色方式的限制，最长路径长度不超过最短路径长度的 2 倍保持近似平衡。他在每个节点添加了一个变量用来表示颜色 ：Black或者Red，为了满足上面的条件，着色必须满足性质：

1️⃣每个结点不是红色就是黑色
2️⃣ 根节点是黑色的
3️⃣ 如果一个节点是红色的，则它的两个孩子结点是黑色的(没有连续的红色节点)
4️⃣ 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5️⃣ 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

由此可以满足最长路径长度不超过最短路径长度的 2 倍（通过第四点就可以看出）。

既然不能保证绝对平衡，那么搜索性能肯定不如AVL树，那么为什么还要有红黑树呢？

首先要知道AVL树保持平衡的方法是频繁的旋转，而红黑树则不需要严格的平衡，会少很多旋转。

二、红黑树的接口

红黑树节点定义：
节点需要有个颜色的变量，可以使用枚举的方法：

enum Colour
{
	RED,
	BLACK,
};

template <class K, class V>
struct RBTreeNode
{
	RBTreeNode(const pair<K, V>& kv)
		: _kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}

	pair<K, V> _kv;
	AVLNode<K, V>* _left;
	AVLNode<K, V>* _right;
	AVLNode<K, V>* _parent;
	Colour _col;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.1 插入

我们可以看到节点初始化的时候默认为RED，因为如果要插入BLACK，那么一定会导致错误，不满足对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。
所以只能把新节点默认设置为RED，因为如果是红色有可能父节点是黑色，这样就没有出现连续的红色。
总结一下：

插入黑色节点一定有问题，插入红色节点有可能会出问题。

插入的流程根AVL树一样，检查父亲节点，如果是黑就结束，如果是红就要调整红黑树。

为了方便说明，cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
首先要知道最主要的是看u
情况一：cur为红，p为红，g为黑，u存在且为红 :

为什么要看u节点，因为如果cur为红且p为红，那么g一定为黑。所以唯一的变数就为u

它的调整方法为：

首先p肯定要变黑，而为了使g两边的子树黑节点数目相同，u也要变黑。至于g，我们先把它变红，因为如果这颗树是子树而g还是黑，那么相当于这颗子树的黑节点多了一个，会影响到别的子树。如果g为根那么就把g变为黑。
这里要注意继续往上处理：
把g当成cur，继续向上调整。

举个例子：

可以看到绿色部分就为上面的抽象图，就这么往上循环改变颜色即可。

情况二：cur为红，p为红，g为黑，u不存在/u为黑

此时要对u分情况讨论：

1️⃣ u不存在时，那么cur一定是新增节点，因为如果cur不是新增节点，那么cur和p一定有一个节点为黑，这样就不满足黑节点数目相同的条件。

处理方式就为右单旋

2️⃣ u存在且为黑

总结一下：

u不存在则cur是新增节点，u存在那么就是由情况一变换过来的。
情况二的处理方法就是旋转+变色。

情况三: cur为红，p为红，g为黑，u不存在/u为黑

情况三与情况二的区别就是情况二是直线，情况三是折线，经过AVL的学习我们知道这种情况要双旋。

情况三也是由其他情况变过来的。
此时我们就需要进行双旋调整红黑树。

左单旋后变成了情况二，那么按照情况二的方法进行右旋即可。

以上三种情况的代码如下：

while (parent && parent->_col == RED)
{
	// 找g 与 u
	Node* g = parent->_parent;
	if (parent == g->_left)
	{
		Node* u = g->_right;
		// 情况一 u存在且为红
		if (u && u->_col == RED)
		{
			parent->_col = u->_col = BLACK;
			g->_col = RED;
			// 继续往上处理
			cur = g;
			parent = cur->_parent;
		}
		else // 情况二或情况三
		{
			if (cur == parent->_left)// 情况二
			{
				//   g
				//  p
				// c
				RotateR(g);
				parent->_col = BLACK;
				g->_col = RED;
			}
			else// 情况三
			{
				//  g
				// p
				//  c
				RotateL(parent);
				RotateR(g);
				//   c
				// p   g
				cur->_col = BLACK;
				g->_col = RED;
			}
			break;
		}
	}
	else
	{
		Node* u = g->_left;
		// 情况一
		if (u && u->_col == RED)
		{
			u->_col = parent->_col = BLACK;
			g->_col = RED;
			cur = g;
			parent = cur->_parent;
		}
		else
		{
			// 情况二
			// g
			//  p
			//   c
			if (cur == parent->_right)
			{
				RotateL(g);
				parent->_col = BLACK;
				g->_col = RED;
			}
			else// 情况三
			{
				// g
				//  p
				// c
				RotateR(parent);
				RotateL(g);
				cur->_col = BLACK;
				g->_col = RED;
			}
			break;
		}
	}
}
// 上面有可能把_root的颜色变为红
_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

三、验证

想要验证是否是红黑树，首先要保证是搜索树（中序遍历有序）。
其次还要判断根节点是否为黑，是否有两个红的相连（检查红节点的父亲），每条路径上的黑节点数目相同（随便找一条路径测出标准值）。

怎么测每条路径的黑节点数目是否相同？

测一条路径的黑节点数目当作标准值，递归过程中遇到黑节点就记录，到空说明该路径走完，比对标准值，如果不同就返回false。

bool _IsBalance(Node* root, int i, int flag)
{
	if (root == nullptr)
	{
		if (i != flag)
		{
			cout << "errno: 左右子树黑色节点数目不同" << endl;
			return false;
		}
		return true;
	}
	// 红节点时判断父亲
	if (root->_col == RED)
	{
		if (root->_parent->_col == RED)
		{
			cout << "errno: 红-红" << endl;
			return false;
		}
	}
	if (root->_col == BLACK)
	{
		i++;
	}

	return _IsBalance(root->_left, i, flag) 
		&& _IsBalance(root->_right, i, flag);
}

bool IsBalance()
{
	if (_root == nullptr)
	{
		return true;
	}
	if (_root->_col != BLACK)
	{
		return false;
	}
	// 找标准值
	Node* cur = _root;
	int flag = 0;
	while (cur)
	{
		if (cur->_col == BLACK)
		{
			flag++;
		}
		cur = cur->_left;
	}
	int i = 0;
	return _IsBalance(_root, i, flag);
}
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

四、源码

#pragma once
#include <iostream>
#include <cstdlib>
#include <cassert>
#include <string>

using namespace std;

enum Colour
{
	RED,
	BLACK,
};

template <class K, class V>
struct RBTreeNode
{
	RBTreeNode(const pair<K, V>& kv)
		: _kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}

	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Colour _col;
};

template <class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _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;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			// 找g 与 u
			Node* g = parent->_parent;
			if (parent == g->_left)
			{
				Node* u = g->_right;
				// 情况一 u存在且为红
				if (u && u->_col == RED)
				{
					parent->_col = u->_col = BLACK;
					g->_col = RED;
					// 继续往上处理
					cur = g;
					parent = cur->_parent;
				}
				else // 情况二或情况三
				{
					if (cur == parent->_left)// 情况二
					{
						//   g
						//  p
						// c
						RotateR(g);
						parent->_col = BLACK;
						g->_col = RED;
					}
					else// 情况三
					{
						//  g
						// p
						//  c
						RotateL(parent);
						RotateR(g);
						//   c
						// p   g
						cur->_col = BLACK;
						g->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* u = g->_left;
				// 情况一
				if (u && u->_col == RED)
				{
					u->_col = parent->_col = BLACK;
					g->_col = RED;
					cur = g;
					parent = cur->_parent;
				}
				else
				{
					// 情况二
					// g
					//  p
					//   c
					if (cur == parent->_right)
					{
						RotateL(g);
						parent->_col = BLACK;
						g->_col = RED;
					}
					else// 情况三
					{
						// g
						//  p
						// c
						RotateR(parent);
						RotateL(g);
						cur->_col = BLACK;
						g->_col = RED;
					}
					break;
				}
			}
		}
		// 上面有可能把_root的颜色变为红
		_root->_col = BLACK;
		return true;
	}

	void RotateL(Node* parent)
	{
		Node* top = parent->_parent;
		Node* right = parent->_right;
		parent->_right = right->_left;
		if (right->_left) right->_left->_parent = parent;
		right->_left = parent;
		parent->_parent = right;
		if (top)// 子树
		{
			if (parent == top->_left) top->_left = right;
			else top->_right = right;
			right->_parent = top;
		}
		else// 完整的树
		{
			_root = right;
			_root->_parent = nullptr;
		}
	}

	void RotateR(Node* parent)
	{
		Node* top = parent->_parent;
		Node* left = parent->_left;
		Node* leftR = left->_right;
		parent->_left = leftR;
		if (leftR) leftR->_parent = parent;
		left->_right = parent;
		parent->_parent = left;
		if (top)
		{
			if (parent == top->_left) top->_left = left;
			else top->_right = left;
			left->_parent = top;
		}
		else
		{
			_root = left;
			_root->_parent = nullptr;
		}
	}

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

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

	void Inorder()
	{
		_Inorder(_root);
	}

	bool _IsBalance(Node* root, int i, int flag)
	{
		if (root == nullptr)
		{
			if (i != flag)
			{
				cout << "errno: 左右子树黑色节点数目不同" << endl;
				return false;
			}
			return true;
		}
		// 红节点时判断父亲
		if (root->_col == RED)
		{
			if (root->_parent->_col == RED)
			{
				cout << "errno: 红-红" << endl;
				return false;
			}
		}
		if (root->_col == BLACK)
		{
			i++;
		}

		return _IsBalance(root->_left, i, flag) 
			&& _IsBalance(root->_right, i, flag);
	}

	bool IsBalance()
	{
		if (_root == nullptr)
		{
			return true;
		}
		if (_root->_col != BLACK)
		{
			return false;
		}
		// 找标准值
		Node* cur = _root;
		int flag = 0;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				flag++;
			}
			cur = cur->_left;
		}
		int i = 0;
		return _IsBalance(_root, i, flag);
	}

private:
	Node* _root = nullptr;
};

void test()
{
	RBTree<int, int> bb;
	const int N = 10000;
	srand(time(0));
	for (int i = 0; i < N; i++)
	{
		size_t x = rand();
		bb.insert(make_pair(x, x));
	}
	/*int a[] = { 16, 3, 7, 11, 9, 26, 18, 14};
	for (auto e : a)
	{
		bb.insert(make_pair(e, e));
	}*/
	cout << bb.IsBalance();
}
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