建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
插入結(jié)點(diǎn)用到了上一次BST的插入函數(shù)(做了一點(diǎn)添加)，并且在此基礎(chǔ)上增加了保持紅黑性質(zhì)的調(diào)整函數(shù)。
還是先看看插入函數(shù)：
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基本沒(méi)區(qū)別，只是添加了對(duì)新加結(jié)點(diǎn)z的顏色和子節(jié)點(diǎn)的處理。
這里把z的顏色設(shè)置為紅色，然后進(jìn)行處理。
問(wèn)：考慮為何把z的顏色設(shè)置為紅色？
答：個(gè)人認(rèn)為如果設(shè)置為黑色，則破壞了性質(zhì)五，而性質(zhì)五關(guān)于黑高度的問(wèn)題，涉及到了整棵樹(shù)，全局性難以把握，所以這里設(shè)置為紅色，雖然破壞了性質(zhì)4，然是相對(duì)破壞性質(zhì)5來(lái)說(shuō)，更容易恢復(fù)紅黑性質(zhì)。大家如果有不同的想法，也可以留言談?wù)劇?/span>
接下來(lái)，就是對(duì)整棵樹(shù)的調(diào)整了。
答：考慮插入z結(jié)點(diǎn)后，破壞的哪幾條紅黑性質(zhì)？
答：破壞了性質(zhì)2和性質(zhì)4.
5條紅黑性質(zhì)要熟記，我這里再貼出來(lái)：
1. 每個(gè)結(jié)點(diǎn)或是紅色，或是是黑色。
2. 根結(jié)點(diǎn)是黑的。
3. 所有的葉結(jié)點(diǎn)(NULL)是黑色的。（NULL被視為一個(gè)哨兵結(jié)點(diǎn)，所有應(yīng)該指向NULL的指針，都看成指向了NULL結(jié)點(diǎn)。）
4. 如果一個(gè)結(jié)點(diǎn)是紅色的，則它的兩個(gè)兒子節(jié)點(diǎn)都是黑色的。
5. 對(duì)每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其子孫結(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑結(jié)點(diǎn)。
所以我們要做的就是恢復(fù)性質(zhì)2和性質(zhì)4.
先來(lái)看看具體實(shí)現(xiàn)的代碼(這里只貼出部分代碼)：
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標(biāo)記出。
大致說(shuō)下判斷情況：
1.首先讓一個(gè)指針y指向z的叔父結(jié)點(diǎn)(z是要?jiǎng)h除的結(jié)點(diǎn))。
2.如果y的顏色是紅色，Case 1。則使z的父親結(jié)點(diǎn)和叔父結(jié)點(diǎn)的顏色改為黑，z的祖父結(jié)點(diǎn)顏色改為紅。然后讓z轉(zhuǎn)移到z的祖父結(jié)點(diǎn)。
3.當(dāng)y的顏色是黑色時(shí)，
①.首先判斷z是否是其父親結(jié)點(diǎn)的右兒子，若是，則調(diào)整為左兒子(用旋轉(zhuǎn))。
②.其次使z的父親結(jié)點(diǎn)顏色為黑，z的祖父結(jié)點(diǎn)顏色為紅，并以z的祖父結(jié)點(diǎn)為軸右旋。
具體我還是在草稿紙上畫(huà)出。。。(可憐買不起數(shù)碼相機(jī)，只能用手機(jī)拍了。。。)
（弱弱的問(wèn)一句，看見(jiàn)網(wǎng)上有很多朋友做的一些代碼講解圖很給力，不知道大家有什么軟件嗎？求推薦。。。）
以下是插入的完整代碼：
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);
}
|
下一篇是關(guān)于紅黑樹(shù)的刪除。
在我獨(dú)立博客上的原文：http://www.wutianqi.com/?p=2446
歡迎大家互相學(xué)習(xí)，互相討論！