C++ RBTree红黑树的性质与实现

时间：2023-03-09来源：系统城装机大师作者：佚名

一、红黑树的概念

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

ps:树的路径是从根节点走到空节点（此处为NIL 节点）才算一条路径

二、红黑树的性质

每个结点不是红色就是黑色
根结点是黑色的
如果一个结点是红色的，则它的两个孩子结点是黑色的（没有连续的红色结点）
对于每个结点，从该节点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
每个叶子结点都是黑色的（此处的叶子结点指的是空节点,NIL节点），如果是空树，空节点也是黑色，符合第一个性质

理解最长路径长度不超过最短路径长度的 2 倍：

根据第三个性质：红黑树不会出现连续的红色结点，根据第四个性质：从每个结点到所有后代结点的路径上包含相同数目的黑色结点。

极端场景：最短路径上全黑，一条路径黑色节点的数量，最长路径上是一黑一红相间的路径

三、红黑树节点的定义

三叉链结构，对比AVL数节点的定义，把平衡因子替换成节点颜色，采用枚举的方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 //结点颜色
enum Color
{
RED,
BLACK,
};
template<class K, class V >
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Color _col;
RBTreeNode(const pair<K,V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
{}
};

这里可以清楚的看到，构造结点时默认设置为红色,问题来了：

如果插入的是黑色结点那就是不符合第四个性质（路径上均包含相同的黑色结点），此时我们必须要去进行维护每条路径的黑色结点

如果插入的是红色结点那就是不符合第三个性质（没有出现连续的红色结点），但是我们并不一定需要调整，如果根刚好为黑色，就不需要进行调整。

所以如果插入为红色结点，不一定会破坏结构，但是如果插入黑色结点我们就必须去进行维护了

四、红黑树的插入

红黑树插入的操作部分和AVL树的插入一样：

找到待插入位置
将待插入结点插入到树中
调整：若插入结点的父结点是红色的，我们就需要对红黑树进行调整

前两步大差不差

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论

关键在于对红黑树进行调整：为了能够展示出各种情况，这里有一个基本的模型：

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

情况一：cur为红，p为红，g为黑，u存在且为红 :

cur为红，p为红，g为黑，u存在且为红

关键看u结点，根结点的颜色为黑色，不能有连续的红色结点，所以上面的情况已经出现连续的红色结点了，此时我们需要进行调整：

把p结点改为黑色，同时把u结点也改为黑色（符合性质四：每条路径上的黑色节点数量相同），最后在把g结点改为红色；如果g是子树的话，g一定会有双亲，为了维持每条路径上黑色节点的数量，g必须变红，不然会多出一个黑色节点，在把g结点当做cur结点继续往上调整，当g为根结点时，在把g置为黑色：

代码实现：

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 while (parent && parent->_col == RED)
{
Node* grandfater = parent->_parent;
if (parent == grandfater->_left)
{
Node* uncle = grandfater->_right;
//情况一：u存在且为红
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
cur = grandfater;
parent = cur->_parent;
}
else//其他情况
{
}
}
else//parent==grandfater->_right
{
Node* uncle = grandfater->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;

cur = grandfater;
parent = cur->_parent;
}
else
{
}
}
}
_root->_col = BLACK;

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

此时u的情况：

如果u结点不存在，则cur一定是新增结点，因为如果cur不是新增结点：则cur和p一定有一个节点时黑色，就不满足每条路径都有相同的黑色结点的性质。

如果u结点存在，则其一定是黑色的，那么c节点原来的颜色一定是黑色，在其子树调整过程中变为了红色

如果p为g的左孩子，cur为p的左孩子，则进行右单旋转；

如果p为g的右孩子，cur为p的右孩子，则进行左单旋转，

同时，p、g变色–p变黑，g变红

以下情况：u不存在，cur为新增节点，进行右单旋：

以下情况：u结点存在且为黑：

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

这时候我们就需要进行双旋了：

p为g的左孩子，cur为p的右孩子，对p做左单旋转；

p为g的右孩子，cur为p的左孩子，对p做右单旋转; 旋转之后则转换成了情况2，在继续进行调整即可

五、代码实现

送上源码：

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 #pragma once
#include <iostream>
#include <assert.h>
#include <time.h>
using namespace std;
enum Color
{
RED,
BLACK,
};
template<class K, class V >
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Color _col;
RBTreeNode(const pair<K,V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
{}
};
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 (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);
cur->_col = RED;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
while (parent && parent->_col == RED)
{
Node* grandfater = parent->_parent;
if (parent == grandfater->_left)
{
Node* uncle = grandfater->_right;
//情况一：u存在且为红
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
//向上调整
cur = grandfater;
parent = cur->_parent;
}
else
{
//情况2
if (cur == parent->_left)
{
RotateR(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
//情况3
else
{
// g
// p
// c
RotateL(parent);
RotateR(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
else//parent==grandfater->_right
{
Node* uncle = grandfater->_left;
//情况1：u存在且为红色
if (uncle && uncle->_col == RED)
{
uncle->_col = parent->_col = BLACK;
grandfater->_col = RED;
//向上调整
cur = grandfater;
parent = cur->_parent;
}
else
{
//情况2：u不存在/u存在为黑色
//g
// p
// c
if (cur == parent->_right)
{
RotateL(grandfater);
grandfater->_col = RED;
parent->_col = BLACK;
}
//情况3
// g
// p
// c
else
{
RotateR(parent);
RotateL(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
}
//根变黑
_root->_col = BLACK;
return true;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (ppNode == nullptr)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* ppNode = parent->_parent;
parent->_parent = subL;
subL->_right = parent;
if (ppNode == nullptr)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
void InOrder()
{
_InOrder(_root);
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
bool Check(Node*root,int blackNum,int ref)
{
if (root == nullptr)
{
//cout << blackNum << endl;
if (blackNum != ref)
{
cout << "违反规则：本条路径的黑色结点的数量根最左路径不相等" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "违反规则：出现连续的红色结点" << endl;
return false;
}
if (root->_col == BLACK)
{
++blackNum;
}
return Check(root->_left,blackNum,ref)
&& Check(root->_right,blackNum,ref);
}
bool IsBalance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_col != BLACK)
{
return false;
}
int ref = 0;
Node* left = _root;
while (left)
{
if (left->_col == BLACK)
{
++ref;
}
left = left->_left;
}
return Check(_root,0,ref);
}
private:
Node* _root = nullptr;
};
void TestRBTree1()
{
//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
RBTree<int, int> t;
for (auto e : a)
{
t.Insert(make_pair(e, e));
}
t.InOrder();
cout << t.IsBalance() << endl;
}
void TestRBTree2()
{
srand(time(0));
const size_t N = 100000;
RBTree<int, int> t;
for (size_t i = 0; i < N; i++)
{
size_t x = rand();
t.Insert(make_pair(x, x));
}
cout << t.IsBalance() << endl;
}