建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
插入結點用到了上一次BST的插入函數(做了一點添加)，并且在此基礎上增加了保持紅黑性質的調整函數。
還是先看看插入函數：
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
|
void RBTreeInsert(RBTree &T, int k)
{
//T->parent->color = BLACK;
Node *y = NULL;
Node *x = T;
Node *z = new Node;
z->key = k;
z->lchild = z->parent = z->rchild = NULL;
while(x != NULL)
{
y = x;
if(k < x->key)
x = x->lchild;
else
x = x->rchild;
}
z->parent = y;
if(y == NULL)
{
T = z;
T->parent = NULL;
T->parent->color = BLACK;
}
else
if(k < y->key)
y->lchild = z;
else
y->rchild = z;
z->lchild = NULL;
z->rchild = NULL;
z->color = RED;
RBInsertFixup(T, z);
}
|
和上一次的BST基本沒區別，只是添加了對新加結點z的顏色和子節點的處理。
這里把z的顏色設置為紅色，然后進行處理。
問：考慮為何把z的顏色設置為紅色？
答：個人認為如果設置為黑色，則破壞了性質五，而性質五關于黑高度的問題，涉及到了整棵樹，全局性難以把握，所以這里設置為紅色，雖然破壞了性質4，然是相對破壞性質5來說，更容易恢復紅黑性質。大家如果有不同的想法，也可以留言談談。
接下來，就是對整棵樹的調整了。
答：考慮插入z結點后，破壞的哪幾條紅黑性質？
答：破壞了性質2和性質4.
5條紅黑性質要熟記，我這里再貼出來：
1. 每個結點或是紅色，或是是黑色。
2. 根結點是黑的。
3. 所有的葉結點(NULL)是黑色的。（NULL被視為一個哨兵結點，所有應該指向NULL的指針，都看成指向了NULL結點。）
4. 如果一個結點是紅色的，則它的兩個兒子節點都是黑色的。
5. 對每個結點，從該結點到其子孫結點的所有路徑上包含相同數目的黑結點。
所以我們要做的就是恢復性質2和性質4.
先來看看具體實現的代碼(這里只貼出部分代碼)：
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
|
void RBInsertFixup(RBTree &T, Node *z)
{
while(z->parent->color == RED)
{
if(z->parent == z->parent->parent->lchild)
{
Node *y = z->parent->parent->rchild;
//////////// Case1 //////////////
if(y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
////////////// Case 2 //////////////
if(z == z->parent->rchild)
{
z = z->parent;
LeftRotate(T, z);
}
////////////// Case 3 //////////////
z->parent->color = BLACK;
z->parent->parent->color = RED;
RightRotate(T, z->parent->parent);
}
}
else
{
///////////////////////
}
}
T->color = BLACK;
}
|
分三種情況，在代碼中已用Case 1, Case 2, Case 3標記出。
大致說下判斷情況：
1.首先讓一個指針y指向z的叔父結點(z是要刪除的結點)。
2.如果y的顏色是紅色，Case 1。則使z的父親結點和叔父結點的顏色改為黑，z的祖父結點顏色改為紅。然后讓z轉移到z的祖父結點。
3.當y的顏色是黑色時，
①.首先判斷z是否是其父親結點的右兒子，若是，則調整為左兒子(用旋轉)。
②.其次使z的父親結點顏色為黑，z的祖父結點顏色為紅，并以z的祖父結點為軸右旋。
具體我還是在草稿紙上畫出。。。(可憐買不起數碼相機，只能用手機拍了。。。)
（弱弱的問一句，看見網上有很多朋友做的一些代碼講解圖很給力，不知道大家有什么軟件嗎？求推薦。。。）
以下是插入的完整代碼：
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
|
void RBInsertFixup(RBTree &T, Node *z)
{
while(z->parent->color == RED)
{
if(z->parent == z->parent->parent->lchild)
{
Node *y = z->parent->parent->rchild;
//////////// Case1 //////////////
if(y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
////////////// Case 2 //////////////
if(z == z->parent->rchild)
{
z = z->parent;
LeftRotate(T, z);
}
////////////// Case 3 //////////////
z->parent->color = BLACK;
z->parent->parent->color = RED;
RightRotate(T, z->parent->parent);
}
}
else
{
Node *y = z->parent->parent->lchild;
if(y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
if(z == z->parent->lchild)
{
z = z->parent;
RightRotate(T, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
LeftRotate(T, z->parent->parent);
}
}
}
T->color = BLACK;
}
void RBTreeInsert(RBTree &T, int k)
{
//T->parent->color = BLACK;
Node *y = NULL;
Node *x = T;
Node *z = new Node;
z->key = k;
z->lchild = z->parent = z->rchild = NULL;
while(x != NULL)
{
y = x;
if(k < x->key)
x = x->lchild;
else
x = x->rchild;
}
z->parent = y;
if(y == NULL)
{
T = z;
T->parent = NULL;
T->parent->color = BLACK;
}
else
if(k < y->key)
y->lchild = z;
else
y->rchild = z;
z->lchild = NULL;
z->rchild = NULL;
z->color = RED;
RBInsertFixup(T, z);
}
|
下一篇是關于紅黑樹的刪除。