【C++】红黑树

个人主页：🍝在肯德基吃麻辣烫
我的gitee：C++仓库
个人专栏：C++专栏

---

---

前言

本文着重讲解红黑树的原理和性质及其难点。

---

以下是本篇文章正文内容

一、什么是红黑树？

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

二、红黑树的性质

• 1. 每个结点不是红色就是黑色
• 2. 根节点是黑色的
• 3. 如果一个节点是红色的，则它的两个孩子结点是黑色的（反过来说，不能有连续的红色节点出现）
• 4. 每一条路径的黑色节点数量均相同
• 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

为什么满足了上述性质，这棵红黑树就满足最长路径不超过最短路径的2倍？

在极限情况下，最短路径是全黑的路径，最长路径是一黑一红相间的路径，其余的每条路径的长度就是介于这两个节点的路径长度之间。所以只要符合上述性质，一定能满足最长路径不超过最短路径的2倍。

三、红黑书节点的定义

enum Colour
{
	RED,
	BLACK
};

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

	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	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
24
25

四、红黑树的插入操作

• 1）找到待插入位置

由于红黑树也是一棵二叉搜索树，所以如果插入节点的值比根小，则向左走；如果插入节点的值比根大，则向右走。

注意这里有一些细节：

• • 1）新插入的节点一定是红色的。
• • • 如果新插入节点是黑色的，则会违反性质4，会影响到整棵树，影响到每一条路径黑色节点数量是否相等。
• • • 如果新插入节点是红色的，假如插入节点的父亲是红色的，则违反性质3，在后续进行变色调整即可，如果插入节点的父亲是黑色的，则没有影响，直接就可以结束插入操作。

• 2）插入完成后，判断还是否符合红黑树的性质

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

下面的情况是p在g的左的情况。

情况1：变色

• 1.如果cur为红，p为红，u存在且为红，则需要进行变色。
• 
  将p和u从红色变成黑色，再让g由黑色变成红色。

注意，这里有一个细节，这棵树有可能只是一棵局部的树，也就是说，g可能还有父亲。

如果g的父亲是红色，则让cur走到g的位置，p走到g的父亲的位置，继续向上调整。

如果g的父亲是黑色，则结束了，退出。

如果g没有父亲（g是根节点），让g再变回黑色即可。

情况2：旋转+变色

• 2.如果cur为红，p为红，u不存在/u存在且为黑

下面是u存在且为黑的情况

2.1） 如果cur是p的左孩子，此时的情况就是单纯的左边高，对g进行右旋，最后变色即可。

具体的旋转过程参考上一篇文章AVL树的旋转，所有旋转细节都已经讲清楚了。

变色前：
cur是红的，p是红的，g是黑的，u是黑的
变色后：
cur是红的，p是黑的，g是红的，u是黑的

注意这里的细节：如果旋转前g有父亲，则旋转后需要让p指向g之前的父亲。

下面是u不存在的情况：

u不存在就更简单了，操作过程同上。

如果cur是p的右孩子，此时的情况就是折线形，也就是下面的情况：

此时需要进行左右双旋。
1.对p进行左旋后，再对g进行右旋，最后变色即可。

变色前：cur是红，p是红，g是黑。
变色后：cur是黑，p是红，g是红。

u不存在就更简单了，操作过程同上。

注意这里的细节：如果旋转前g有父亲，则旋转后需要让p指向g之前的父亲。

如果是p在g的右的情况
每种情况都是一样的，只不过是方向变了，照葫芦画瓢即可。

总结：

重点是看u（叔叔）节点

如果p是g的左的情况：

• 情况1：变色

• • 1）如果cur为红，p为红，u存在且为红，则需要进行变色。

• 情况2：旋转+变色

• • 1）如果cur为红，p为红，u不存在/u存在且为黑
• • • 如果cur是p的左，则为单纯的左边高，对g进行右旋后，再进行变色即可。
• • • 如果cur是p的右，则为折线形，先对p进行左旋，再对g进行右旋，最后进行变色即可。

红黑树插入节点代码

bool Insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;
	}

	Node* cur = _root;
	Node* cur_parent = _root;

	//1.找到待插入位置
	while (cur)
	{
		if (cur->_kv.first < kv.first)
		{
			cur_parent = cur;
			cur = cur->_right;
		}
		else if (cur->_kv.first > kv.first)
		{
			cur_parent = cur;
			cur = cur->_left;
		}
		else
			return false;
	}

	//2.先判断待插入节点是在parent的左边还是右边
	cur = new Node(kv);
	//新插入的节点必须是红的
	cur->_col = RED;
	if (cur_parent->_kv.first > kv.first)
	{
		cur_parent->_left = cur;
	}
	else
	{
		cur_parent->_right = cur;
	}
	//连接parent
	cur->_parent = cur_parent;

	//开始判断是否还符合红黑树的性质

	while (cur_parent && cur_parent ->_col == RED)
	{
		Node* grandfather = cur_parent->_parent;
		//左边的情况
		if (grandfather->_left == cur_parent)
		{
			Node* uncle = grandfather->_right;

			//u存在且为红
			if (uncle && uncle->_col == RED)
			{
				cur_parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
				Node* ppNode = grandfather->_parent;
				if (ppNode == nullptr)
				{
					grandfather->_col = BLACK;
					//g是根，变色后可以break了
					break;
				}
				//向上调整
				else if (ppNode->_col == RED)
				{
					cur = grandfather;
					cur_parent = ppNode;
				}
				else
				{
					//ppNode是黑色，已经完成了，可以break
					break;
				}
			}

			//u不存在/u存在且为黑
			else 
			{
				//单纯左边高，右单旋
				if (cur == cur_parent->_left)
				{
					RotateR(grandfather);
					//变色
					cur_parent->_col = BLACK;
					grandfather->_col = RED;
				}
				//折线形
				//    g
				//  p
				//    c
				else
				{
					RotateL(cur_parent);
					RotateR(grandfather);
					//变色
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				//旋转+变色后，一定平衡了，可以break了
				break;
			}
			
		}

		//右边的情况
		//   g                g
		//     p      或         p
		//       c            c
		else
		{
			Node* uncle = grandfather->_left;

			//u存在且为红
			if (uncle && uncle->_col == RED)
			{
				cur_parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
				Node* ppNode = grandfather->_parent;
				//1.ppNode为空
				if (ppNode == nullptr)
				{
					grandfather->_col = BLACK;
					//g是根，变色后可以break了
					break;
				}
				//2.ppNode存在且为红
				//向上调整
				else if (ppNode->_col == RED)
				{
					cur = grandfather;
					cur_parent = ppNode;
				}
				
				else
				{
					//ppNode是黑色，已经完成了，可以break
					break;
				}
			}

			//u不存在/u存在且为黑
			//   g                g
			//     p      或         p
			//       c            c
			else
			{
				//单纯右边高，左单旋
				if (cur == cur_parent->_right)
				{
					RotateL(grandfather);
					//变色
					cur_parent->_col = BLACK;
					grandfather->_col = RED;
				}

				//折线形
				//    g
				//      p
				//    c
				else
				{
					RotateR(cur_parent);
					RotateL(grandfather);
					//变色
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				//旋转+变色后，一定平衡了，可以break了
				break;
			}
		}

	}
	//不管发生什么样的情况，这个代码一定没有错
	_root->_col = BLACK;
	return true;
}


//左单旋
void RotateL(Node* parent)
{
	++CountRotate;
	Node* cur = parent->_right;
	Node* curleft = cur->_left; //这个是cur的左子树，旋转后变成了parent的右孩子
	Node* ppNode = parent->_parent;

	parent->_right = curleft;
	if (curleft)
		curleft->_parent = parent;

	cur->_left = parent;
	parent->_parent = cur;

	if (!ppNode)
	{
		_root = cur;
		cur->_parent = nullptr;
	}
	else
	{
		if (ppNode->_right == parent)
		{
			ppNode->_right = cur;
		}
		else
		{
			ppNode->_left = cur;
		}

		cur->_parent = ppNode;
	}

}

//右单旋
void RotateR(Node* parent)
{
	++CountRotate;
	Node* cur = parent->_left;
	Node* curright = cur->_right;
	Node* ppNode = parent->_parent;

	parent->_left = curright;
	//如果cur的右子树是空
	if (curright)
		curright->_parent = parent;

	cur->_right = parent;
	parent->_parent = cur;

	if (!ppNode)
	{
		_root = cur;
		cur->_parent = nullptr;
	}
	else
	{
		cur->_parent = ppNode;
		//要知道根的左边是cur还是右边是cur
		if (ppNode->_left == parent)
		{
			ppNode->_left = cur;
		}
		else
		{
			ppNode->_right = cur;
		}
	}

}

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

	RotateL(parent->_left);
	RotateR(parent);

}

void RotateRL(Node* parent)
{
	Node* cur = parent->_right;
	Node* curleft = cur->_left;

	RotateR(parent->_right);
	RotateL(parent);

}
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

五、验证一棵树是否为红黑树

• 1）验证中序遍历是否是有序序列
• 2）验证红黑树的各个性质

	int Height()
	{
		return _Height(_root);
	}


	bool IsRBTree()
	{
		cout << "IsRBTree():";
		return _IsRBTree(_root);
	}

	//判断一棵树是否为红黑树
	//1.判断他的中序遍历
	//2.判断红黑树的每一个性质


	bool _IsRBTree(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		
		//性质1，每个节点不是红就是黑，不用判断
		//性质2，根为黑
		if (root->_col == RED)
		{
			cout << "根不是黑色的，不是红黑树" << endl;
			return false;
		}

		//检测3和4
		//性质3
		//不能出现连续的红节点
		//性质4
		//每条路径上的黑色节点个数相同
		int benchmark = 0;
		Node* benchNode = root;
		//基准路径选最左边
		while (benchNode)
		{
			if (benchNode->_col == BLACK)
				++benchmark;
			benchNode = benchNode->_left;
		}

		if (!CheckColour(root,0,benchmark))
		{
			return false;
		}
		return true;
	}

	//检验性质3，检验自己和父亲的颜色比检验自己和左右孩子的颜色更方便
	//检验性质4，先随便求一条路径的黑色节点，然后再求其他路径的节点
	//跟这条基准路径对比，不匹配就不符合性质4
	//就算基准路径求出来是错的，其他路径是对的，如果两者对不上，那就不是红黑树
	bool CheckColour(Node* root,int blacknum,int benchmark)
	{
		if (root == nullptr)
		{
			if (blacknum != benchmark)
				return false;
			
			return true;
		}

		if (root->_col == BLACK)
			++blacknum;
		
		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << "出现了连续的红节点，不是红黑树" << endl;
			return false;
		}

		return CheckColour(root->_left,blacknum,benchmark) && CheckColour(root->_right, blacknum, benchmark);
	}



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

		int left = _Height(root->_left);
		int right = _Height(root->_right);
		return left > right ? left + 1 : right + 1;
	}

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

六、比较AVL树和红黑树

可见，红黑树和AVL树的查找次数是在同一个量级的，但由于AVL树要保持绝对平衡，所以需要更频繁地旋转操作。

当我用一千万个随机数进行测试时，结果如下：

AVL树的旋转次数在400多万次左右，红黑树的旋转次数在300多万，相差了几十万次，这里就体现出了差距。

不过，如果插入的数据是有序的，则AVL树的效率相对更高一点：

插入的数越随机，红黑树的效率越占优势。

所以实际上，红黑树的效率是比AVL树的效率要高一些的。实际中更多应用的也是红黑树

---

总结

这篇文章主要讲述对红黑树的插入操作，在插入节点后需要保证红黑树的性质，所以引出了变色，旋转+变色等操作。