数据结构-红黑树
1、红黑树简介
红黑树（red-black tree）是一种平衡的搜索树，常见的平衡搜索树包括AVL树、B树、AA树、treap树、SBT树、替罪羊树、伸展树、跳表等。红黑树支持在最坏情况下对动态集合操作的时间复杂度为$O(lgn)$。平衡树的时间复杂度均为$O(lgn)$，但是红黑树的性能最优，有很多应用。如C++的STL中的集合(set、multiset)、映射（map、multimap），在java中的TreeSet和TreeMap数据结构均用到红黑树。
红黑树的性质
红黑树是一棵二叉搜索树，每个结点均有一个颜色位（RED or BLACK）。通过对任何一条从根到叶子的简单路径上各个接待你的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍。因此是近似平衡的。
红黑树结点
红黑树每个结点包括基本的5个域：Color、left、right、p、key。如果一个结点没有子结点或父节点，则该结点相应指针指向 NIL。我们可以把 NIL实现为 空指针（nullptr）或 哨兵结点。我们可以把 NIL视为指向叶结点（外部结点）的指针，而把带有关键字的结点视为内部结点。
红黑树的5个性质
1、每个结点为BLACK或BLACK
2、根节点颜色为BLACK
3、每个叶结点（NIL）为BLACK。
4、如果一个结点为RED，那么它的两个子结点均为BLACK
5、对于每个结点，该结点到其所有后代叶结点的简单路径上，均包含数据相同的BLACK结点。
在后面的实现中，NIL采用哨兵来实现。
下面是一个红黑树的示例图：
该树满足上面红黑树的5个性质。在后面的具体实现中，我们令根和子结点为空的结点相应的指针指向 $T.nil$。
定理：对于n个结点一棵红黑树，它的高度之多为 $2lg(n+1)$。具体证明过程看算法导论。
2、红黑树的操作
旋转
红黑树是基于旋转来维持平衡的，类是有伸展树，AVL树。也有无旋转的平衡搜索树，如：替罪羊树、fhq reap树。几乎所有的平衡树都是基于旋转来进行操作。通过旋转来维持平衡树的性质，同时可以保持树的中序遍历结果不变。
红黑树的旋转只有左旋和右旋。分别是左旋和右旋的示意图。
下面是LEFT-ROTATE的伪代码，对树$T$中的$x$进行左旋，其中假设$x.right != T.nil$，且根节点的父节点为$T.nil$。1
2
3
4
5
6
7
8
9
10
11
12
13
14LEFT-ROTATE(T,x)
y = x.right //获取x的右孩子
x.right = y.left //获取新的右孩子
if y.left != T.nil
y.left.p = x
y.p = x.p //更新与父亲结点间的链接
if x.p == T.nil
T.root = y
elseif x == x.p.left
x.p.left = y
else
x.p.right = y
y.left = x //将x作为y的左孩子
x.p = y
右旋的操作与左旋的操作对称，因此只需要将其中出现的left和right进行对调即可。
下面是左旋和右旋的实例操作。
插入操作
红黑树的插入操作（RB-INSERT）与BST的插入操作基本一致，插入操作后，需要额外的操作，如通过旋转，变换颜色等操作进行调整，使之满足红黑树的性质，这些操作在RB-INSERT-FIXUP中完成。
下面是插入操作RB-INSERT的伪代码，将结点$z$，插入$T$中合适为止。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18RB-INSERT(T,z)
y = T.nil //父节点为止
x = T.root //插入位置
while x != T.nil
y = x
if z.key < x.key
x = x.left
else
x = x.right
z.p = y
if y == T.nil
T.root = z
elseif z.key < y.key
y.left = z
else y.right = z
z.left = z.right = T.nil
z.color = RED
RB-INSERT-FIXUP(T,z) //对树进行调整
这里不具体证明算法的正确性，可以参考算法导论。
下面是RB-INSERT-FIXUP的伪代码。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19RB-INSERT-FIXUP(T,z)
while z.p.color == RED
if z.p == z.p.p.left
y = z.p.p.left //uncle node
if y.color == RED
z.p.color = BLACK //case 1
y.color = BLACK //case 1
z.p.p.color = RED //case 1
z = z.p.p //case 1
else
if z == z.p.right
z = z.p //case 2
LEFT-ROTATE(T,z)//case 2
z.p.color = BLACK //case 3
z.p.p.color = RED //case 3
RIGHT-ROTATE(T,z.p.p)//case 3
else(same as then clause
with "right" and "left" exchanged)
T.root.color = BLACK
实际上红黑树的插入调整操作一共有6种情况，但是当$x.p$为右子树时，与作为左子树的情况相对称，因此，只需要将处理左子树的情况中的left和right进行对调即可。后面将结合例子讲以上这三种情况。这三种情况并不是相互独立，其中 case 2 完成后就可以变为 case 3。
在红黑树的插入调整操作中，case 1 通过变色来上升$z$，使$z$的叔结点代码中的$y$变为黑色转化为case 2、3，而case 2 和case 3各通过旋转，最终使其满足红黑树性质。因此只有case 1 可以不断迭代，直至根节点时，它的$z.p = T.nil$。此时恒成立推出，因此时间复杂度为$lgn$。
情况 1：z的叔结点y为红色
如图所示，$z$所指为当前发生冲突的结点，它与$z.p$颜色均为红色。同时叔结点$y$为红色。此时$z$是左孩子还是右孩子均属该情况。根据上面case 1的伪代码，实质上通过将父节点$z.p$ 和叔结点$y$变为黑色，同时令$z.p.p$变为新的$z$，令它为红色。通过这样的操作，实质上是将$z$转移上升，最终或者到达根节点，那么推出while后置根节点为黑色，或者使之得到新的叔结点y的颜色为黑色，转化为case 2 or 3。
情况 2：z的叔结点y为黑色的且z是一个右孩子
情况 3：z的叔结点y为黑色的且z是一个左孩子
如图所示，在case2、3中，此时叔结点$y$为黑色。如果为case 2，当前$z$为有右孩子，那么将$z$变为$z.p$，同时对结点$z$进行一次左旋，使之变为情况3。在case 3中，将此时$z$为左孩子，将$z.p$置为黑色，同时将$z.p.p$置为红色，对$z.p.p$进行一次右旋。完成case 3的操作后，此时已经满足了红黑树的性质。
对于case 2而言，实际是通过旋转和变色，使$z$转化为一个左孩子，然后在case 3中，我们通过旋转和变色，相当于将C的黑色传递给B，令B代替C继续连接上层结点，同时满足红黑树的性质。
无论是从case 2到case 3还是直接从case 1到case 3。最多进行2次旋转，可在常数时间内完成，结合case 1。RB-TREE-FIXUP的时间复杂度为$O(lgn)$。因此，对于一次插入操作，总的时间复杂度为$O(lgn)$。
删除操作
红黑树的删除操作（RB-DELETE）相比插入操作更复杂一点。类似BST的实现，删除某个结点，利用该结点的后继代替该结点位置，若后继存在右孩子，将其右孩子代替后继的位置。处理完成后，类似插入操作，需要对树进行调整，从而满足红黑树的性质，该过程通过RB-DELETE-FIXUP函数完成。
下面使删除操作的伪代码，将树$T$中的结点$z$删除。
删除过程中，需要采用一个结点替换另外一个结点的位置，采用RB-TRANSPLANT(T,x,y)实现，该函数实现用$y$结点（可以为空，我们的T.nil采用哨兵实现，一定存在，因此可以当成内部结点处理）。
下面是RB-TRANSPLANT的伪代码1
2
3
4
5
6
7
8RB-TRANSPLANT(T,u,v)
if u.p == T.nil //u为根节点
T.root = v
elseif u == u.p.left
u.p.left = v
else
u.p.right = v
v.p = u.p
下面是删除操作TREE-DELETE的伪代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24RB-DELETE(T,z)
y = z
y_original_color = y.color
if z.left == T.nil //左子树为空，采用右子树代替z
x = z.right
RB-TRANSPLANT(T,z,z.right)
elseif z.right == T.nil//右子树为空，采用左子树代替z
x = z.right
RB-TRANSPLANT(T,z,z.left)
else
y = TREE-MINIMUM(z.right) //采用后继代替
y_original_color = y.color
x = y.right
if y.p == z //后继是z的右孩子
x.p = y
else RB-TRANSPLANT(T,y,y.right)//不是右孩子，需要将y用其右孩子替换
y.right = z.right
y.right.p = y
RB-TRANSPLANT(T,z,y)
y.left = z.left
y.left.p = y
y.color = z.color
if y_original_color == BLACK //被取走的后继是黑色，需要进行调整
RB-DELETE-FIXUP(T,x)
删除操作中$y$记录被删除的结点$z$或作为替换$z$的结点，同时$y_original_color$记录它的颜色。同时记录$y$的右子树$x$，它是替换$y$的结点，同时后面可能需要对$x$为根的子树进行调整。
- 假设$z$只有单个孩子或没有孩子，那么$y = z$即是被删除的结点。 $x = x.right$为替换$y$的结点。同时记录$y_original_color$，如果$y_original_color$为红色，$\because y = z$最多只有一个孩子，删除它后用它的孩子代替，不会影响红黑树的性质。否则如果$y$为黑色，那么将会引起$x$为根的子树的黑高减1，需要进行调整。即最后一行判断语句。
- 假设$z$存在两个孩子，那么取$y =$TREE-MINIMUM($x.right$)，此时$y$记录替换$z$的结点。同时更新$y_original_color$和$x$。如果$y$是$z$的右孩子，此时我们令$x.p = y$，后面只需要执行
RB-TRANSPLANT(T,z,y)用$y$替换$z$，更新$y$的左子树链接，否则，需要用$x = y.right$先替换$y$，更新$y$的右子树链接。和上面相同，用$y$替换$z$，如果$y$的颜色是黑色，会引起$x$为根的子树的黑高-1，需要后面进行调整。
详细的证明参考算法导论
最后是RB-DELETE-FIXUP的伪代码
1 | RB-DELETE-FIXUP(T,x) |
上面讲到，用删除 $y$ 或 $y$ 代替$z$后，如果$y_original_color$为黑色，会引起$x$为根的子树的黑高减1。对于这个黑高减1，我们可以把它理解为 将$y$ 的黑色加到了结点$x$上，此时$x$为双黑色或红黑色，RB-DELETE-FIXUP的过程实质上就是通过旋转和变色等操作，将结点$x$上多出来的黑色抽取出来，放在另一个节点上，然后通过调整树，使之满足红黑树的性质。
红黑树的删除调整操作中，可以分为8种情况，类似插入调整操作。删除调整操作根据结点$x$是左孩子还是右孩子分为对称的4种操作。这里实现$x$为左孩子的情形，当$x$为右孩子时，只需要将处理左孩子的情况中出现的left和right进行对调即可。
首先注意，$while$循环时，$x$始终指向双黑色结点，直到$x$到达根节点，或者$x.color = RED$,即$x$抽取出黑色，放置到其他点上，并满足红黑树的性质。
这里简单概述下这4种情况。这4种情况并不是相互独立的。
- 对于case 1，兄弟结点$w$为红色时，那么可以通过旋转变色获取$w$的一个黑色孩子，作为自己新的兄弟。当$x$的兄弟为黑色时，此时转化为case 2，3，4。
- 在$w$的孩子均为黑色结点时，此时为case 2，我们可以将$x$和$w$的黑色抽出，传递给$x.p$，此时$x.p$成为新的$x$进入下一轮循环。
- 若$w$左孩子为红色，右孩子为黑色，此时为case 3，然后我们通过旋转和变色，令$w$的右孩子为红色，从而转化为case 4。
- 当case 4时，$w$为红色，同时它的右孩子为红色，然后通过旋转和变色，将$w$的黑色抽取出来，放置在原来的父结点上，同时令$x = T.root$跳出循环。
下面将具体讨论$x$为左孩子的4种情况。
情况 1：x的兄弟结点w是红色的
如图，此时结点$x$为双黑色，结点$w$为红色，那么根据红黑树的性质4，$w$的父子结点均为黑色。我们将$x.p$和$w$的颜色交换，然后对$x.p$进行进行一次左旋，最后更新$w$，通过这样的操作，我们将原来$w$的一个黑色的孩子作为$x$的兄弟。从而换为case 2，3，4。
情况 2：x的兄弟结点w是黑色的，而且w的两个子结点都是黑色的
如图，其中灰色的结点对颜色无要求，既可以是红色也可以是黑色，实际编程中，不存在灰色结点。
此时，$w$为黑色，同时孩子均为黑色。此时，我们将$w.color = RED$，该操作实质上是将$x$和$w$的黑色抽出，放置到$x.p$中，然后$x = x.p$，此时$x.p$称为新的$x$，因为此时它具有双重颜色，或者红黑色，或者双黑色。如果是通过case 1转化为case 2，那么新的$x$为红黑色，此时将会跳出循环，同时，我们令$x.color = BLACK$，完成后，此时成功将$x$的黑色抽出放在另一个结点上，同时满足红黑树性质。如果$x.p$原来为黑色，那么它将变为双黑色，则进入下一次$while$循环。
最坏情况下，每次$w$和它的孩子均是黑色，此时时间复杂度为$lg(n)$。
情况 3：x的兄弟结点w是黑色的，w的左孩子是红色的，w的右孩子是黑色的。
在case 2下面的else分支时，此时$w$为黑色，进入该分支，说明$w$的左子树或者右子树为红色。我们的最终目的是使$w$的右孩子为红色结点。因此，在下面的 if x.right.color == BLACK分支中，说明$w$的左孩子为红色，此时，我们通过交换$w$和$w.left$的颜色，然后对$w$进行一次右旋，从而使$w$获得一个红色的右孩子，最后更新$w = x.p.right$，成功为case 4。如果$if$分支不成立，说明本身具备红色的右孩子，后面的操作也不需要关注左孩子的颜色，此时即为case 4。
如图：
情况 4：x的兄弟结点w是黑色的，w的右孩子是红色的
如图，当$w$为红色，其他的右孩子是红色时，此时，我们可以交换$x.p$和$w$的颜色，同时将$x.right$置为黑色，然后左旋$x.p$结点。最终满足红黑树性质。令$x.p$为黑色，实质上是使$x$为根的子树的黑高加1，相当于抽取出，x为黑色，此时x满足性质1，x为根的子树黑高加1满足性质5，同时w的左子树，即图中的C的黑高不变。但是此时$w$的右子树黑高减1，但是我们可以通过将$w.right$即图中的E置为黑色，从而使其黑高不变，此时整体满足红黑树性质，置$x = T.root$退出循环。
对于RB-DELETE-FIXUP唯一可能进行迭代的是case 2，沿树上升至多$O(lgn)$次期间不进行任何旋转，对于case 1，3，4的旋转操作，最多尽量3次。因此RB-DELETE-FIXUP的时间复杂度为$O(lgn)$。
3、红黑树的实现
下面红黑树采用C++实现，为了和上面的伪代码形式一致，便于理解，没有采用类封装操作，只包含一些C++特性。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
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
using namespace std;
//定义颜色宏
enum COLOR{RED,BLACK};
//结点定义
template<typename T>
struct Node
{
Node<T>* left;
Node<T>* right;
Node<T>* p;
T key;
COLOR color;
Node():color(BLACK){}
};
//结点指针定义
template<typename T>
using pNode=Node<T>*;
//红黑树定义
template<typename T>
struct RBTree
{
static pNode<T> nil;
/**
* Singleton Model
* 采用local-static对象
* 使模板参数相同的对象公用一个nil
* 在main函数前被使用。
* 具体参考 下面这篇博客
* https://blog.csdn.net/qq_40512922/article/details/90589657#41_274
*/
static pNode<T> getInstance(){
static Node<T> one_instance;
return &one_instance;
}
pNode<T> root;
RBTree():root(nil){}
};
//初始化 nil
template<typename T>
pNode<T> RBTree<T>::nil=RBTree<T>::getInstance();
/*
Function Decleration
----------------------------------------
*/
template<typename T>//插入
void RBTree_insert(RBTree<T> &t,pNode<T> z);
template<typename T>//插入调整
void RBTree_insert_fixup(RBTree<T> &t,pNode<T> z);
template<typename T>//删除
void RBTree_delete(RBTree<T> &t,pNode<T> z);
template<typename T>//删除调整
void RBTree_delete_fixup(RBTree<T> &t,pNode<T> x);
template<typename T>//O(1)空间复杂度迭代中序遍历
void inorder_travel_iterative(pNode<T> x);
template<typename T>//常规递归中序遍历
void inorder_travel_recursive(pNode<T> x);
template<typename T>//结点x的后继
pNode<T> tree_successor(pNode<T> x);
template<typename T>//利用后继函数在O(n)有序遍历
void tree_travel_successor(pNode<T> x);
template<typename T>//左旋
void left_rotate(RBTree<T> &t,pNode<T> z);
template<typename T>//右旋
void right_rotate(RBTree<T> &t,pNode<T> z);
template<typename T>//结点x为根的子树的最小值
pNode<T> tree_minimum(pNode<T> x);
template<typename T>//初始化Vector
void getInitVec(vector<pNode<T>> &vec);
template<typename T>//释放内存
void freeVec(vector<pNode<T>> &vec);
template<typename T>//打印结点x
void print(const Node<T>*x);
/*
Function Definition
----------------------------------------
*/
template<typename T>
void print(const Node<T>*x)
{
cout << x->key;
if(x->color==BLACK)
cout << "[BLACK] ";
else
cout << "[RED] ";
}
template<typename T>
void inorder_travel_recursive(pNode<T> x)
{
if(x!=RBTree<T>::nil)
{
inorder_travel_recursive(x->left);
print(x);
inorder_travel_recursive(x->right);
}
}
template<typename T>
void inorder_travel_iterative(pNode<T> x)
{
if(x==RBTree<T>::nil)return;
pNode<T> y=RBTree<T>::nil;
while(true)
{
if(y!=x->left)
while(x->left!=RBTree<T>::nil)
x=x->left;
if(x->right!=RBTree<T>::nil)
{
x=x->right;
continue;
}
do{
y=x;
x=x->p;
if(x==RBTree<T>::nil)
return;
}while(y==x->right);
}
}
template<typename T>
void left_rotate(RBTree<T> &t,pNode<T> x)
{
pNode<T> y=x->right;
x->right=y->left;
if(y->left!=RBTree<T>::nil)
y->left->p=x;
y->p=x->p;
if(x->p==RBTree<T>::nil)
t.root=y;
else if(x->p->left==x)
x->p->left=y;
else
x->p->right=y;
y->left=x;
x->p=y;
}
template<typename T>
void right_rotate(RBTree<T> &t,pNode<T> x)
{
pNode<T> y=x->left;
x->left=y->right;
if(y->right!=RBTree<T>::nil)
y->right->p=x;
y->p=x->p;
if(x->p==RBTree<T>::nil)
t.root=y;
else if(x->p->left==x)
x->p->left=y;
else
x->p->right=y;
y->right=x;
x->p=y;
}
template<typename T>
void RBTree_insert(RBTree<T> &t,pNode<T> z)
{
pNode<T> y=RBTree<T>::nil;
pNode<T> x=t.root;
while(x!=RBTree<T>::nil)
{
y=x;
if(z->key<x->key)
x=x->left;
else
x=x->right;
}
z->p=y;
if(y==RBTree<T>::nil)
t.root=z;
else if(z->key<y->key)
y->left=z;
else
y->right=z;
z->left=z->right=RBTree<T>::nil;
z->color=RED;
RBTree_insert_fixup(t,z);
}
template<typename T>
void RBTree_insert_fixup(RBTree<T> &t,pNode<T> z)
{
while(z->p->color==RED)
{
if(z->p==z->p->p->left)
{
pNode<T> y=z->p->p->right;
if(y->color==RED)
{
z->p->color=BLACK; //case 1
y->color=BLACK;
z->p->p->color=RED;
z=z->p->p;
}
else
{
if(z==z->p->right)
{
z=z->p; //case 2
left_rotate(t,z);
}
z->p->color=BLACK; //case 3
z->p->p->color=RED;
right_rotate(t,z->p->p);
}
}//end-if
else
{
pNode<T> y=z->p->p->left;
if(y->color==RED)
{
z->p->color=BLACK;
y->color=BLACK;
z->p->p->color=RED;
z=z->p->p;
}
else
{
if(z==z->p->left)
{
z=z->p;
right_rotate(t,z);
}
z->p->color=BLACK;
z->p->p->color=RED;
left_rotate(t,z->p->p);
}
}//end-else
}//end while
t.root->color=BLACK;
}
template<typename T>
pNode<T> tree_minimum(pNode<T> x)
{
while(x->left!=RBTree<T>::nil)
x=x->left;
return x;
}
template<typename T>
void RBTree_transplant(RBTree<T> &t,pNode<T> u,pNode<T> v)
{
if(u->p==RBTree<T>::nil)
t.root=v;
else if(u==u->p->left)
u->p->left=v;
else
u->p->right=v;
v->p=u->p;
}
template<typename T>
void RBTree_delete(RBTree<T> &t,pNode<T> z)
{
pNode<T> y=z;
pNode<T> x;
COLOR y_original_color=y->color;
if(z->left==RBTree<T>::nil)
{
x=z->right;
RBTree_transplant(t,z,z->right);
}
else if(z->right==RBTree<T>::nil)
{
x=z->left;
RBTree_transplant(t,z,z->left);
}
else
{
y=tree_minimum(z->right);
y_original_color=y->color;
x=y->right;
if(y->p==z)
x->p=y;
else
{
RBTree_transplant(t,y,y->right);
y->right=z->right;
y->right->p=y;
}
RBTree_transplant(t,z,y);
y->left=z->left;
y->left->p=y;
y->color=z->color;
}
if(y_original_color==BLACK)
RBTree_delete_fixup(t,x);
}
template<typename T>
void RBTree_delete_fixup(RBTree<T> &t,pNode<T> x)
{
while(x!=t.root&&x->color==BLACK)
{
if(x==x->p->left)
{
pNode<T> w=x->p->right;//兄弟
if(w->color==RED)
{
w->color=BLACK; //case 1
x->p->color=RED;
left_rotate(t,x->p);
w=x->p->right;
}
if(w->left->color==BLACK&&w->right->color==BLACK)
{
w->color=RED; //case 2
x=x->p;
}
else
{
if(w->right->color==BLACK)
{
w->left->color=BLACK; //case 3
w->color=RED;
right_rotate(t,w);
w=x->p->right;
}
w->color=x->p->color; //case 4
x->p->color=BLACK;
w->right->color=BLACK;
left_rotate(t,x->p);
x=t.root;
}
}//end-if
else
{
pNode<T> w=x->p->left;//兄弟
if(w->color==RED)
{
w->color=BLACK; //case 1
x->p->color=RED;
right_rotate(t,x->p);
w=x->p->left;
}
if(w->left->color==BLACK&&w->right->color==BLACK)
{
w->color=RED; //case 2
x=x->p;
}
else
{
if(w->left->color==BLACK)
{
w->right->color=BLACK; //case 3
w->color=RED;
left_rotate(t,w);
w=x->p->left;
}
w->color=x->p->color; //case 4
x->p->color=BLACK;
w->left->color=BLACK;
right_rotate(t,x->p);
x=t.root;
}
}//end-else
}
x->color=BLACK;
}
template<typename T>
pNode<T> RBTree_search(RBTree<T> t,T key)
{
pNode<T> x=t.root;
while(x!=RBTree<T>::nil)
{
if(key==x->key)
return x;
else if(key<x->key)
x=x->left;
else
x=x->right;
}
return x;
}
template<typename T>
pNode<T> tree_successor(pNode<T> x)
{
if(x->right!=RBTree<T>::nil)
return tree_minimum(x->right);
pNode<T> y=x->p;
while(y!=RBTree<T>::nil&&x==y->right)
{
x=y;
y=y->p;
}
return y;
}
template<typename T>
void tree_travel_successor(pNode<T> x)
{
if(x==RBTree<T>::nil)
return;
x=tree_minimum(x);
do{
print(x);
x=tree_successor(x);
}while(x!=RBTree<T>::nil);
}
/*
*特例化 integer类型的随机初始化模板。
*因为下面的 uniform_int_distrbution只支持整型。
*/
template<> void getInitVec(vector<pNode<int>> &vec)
{
static default_random_engine e(time(nullptr));
static uniform_int_distribution<int> d(0,50000);
int key;
for(auto &i:vec){
i=new Node<int>();
i->key=d(e);
}
}
/*
* 特例化double类型的随机初始化模板
*/
template<> void getInitVec(vector<pNode<double>> &vec)
{
static default_random_engine e(time(nullptr));
static uniform_real_distribution<double> d(0,50000);
double key;
for(auto &i:vec){
i=new Node<double>();
i->key=d(e);
}
}
template<typename T>
void freeVec(vector<pNode<T>> &vec)
{
for(auto i:vec)
{
delete i;
i=nullptr;
}
}
void RBTree_property_test()
{
int cnt;
cout << "Input the cnt:" << endl;
cin >> cnt;
RBTree<int> T;
vector<pNode<int>> vec(cnt);
getInitVec(vec);
clock_t sta=clock();
for(auto i:vec)
RBTree_insert(T,i);
for(auto i:vec)
RBTree_delete(T,i);
clock_t interval=clock()-sta;
cout << "CLOCKS_PER_SEC = " << CLOCKS_PER_SEC << endl;
cout << "succed\n" << interval << " clocks (when CLOCKS_PER_SEC=1000,equal to ms)" << endl;
cout << interval/CLOCKS_PER_SEC << " s" << endl;
}
int main()
{
RBTree_property_test();
return 0;
}