建議先看看前言：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
| Node* RBTreeDelete(RBTree T, Node *z)
{
Node *x, *y;
// z是要刪除的節點,而y是要替換z的節點
if(z->lchild == NULL || z->rchild == NULL)
y = z; // 當要刪除的z至多有一個子樹，則y=z；
else
y = RBTreeSuccessor(z); // y是z的后繼
if(y->lchild != NULL)
x = y->lchild;
else
x = y->rchild;
// 無條件執行p[x] = p[y]
x->parent = y->parent;
if(y->parent == NULL)
T = x;
else if(y == y->parent->lchild)
y->parent->lchild = x;
else
y->parent->rchild = x;
if(y != z)
z->key = y->key;
if(y->color == BLACK)
RBDeleteFixup(T, x);
return y;
} |
注意代碼倒數第二和第三行，只有當后繼結點y的顏色是黑色時，才做調整。
由此，引導出幾個問題：
1.問：考慮為何當y的顏色是黑色時，才調整？當y的顏色是紅黑時，會不會破壞性質4？
答：這里我一開始糾結了，后來反復看了幾次BST的刪除，再算想通。在BST中，刪除結點z，并不是真的把z給移除了，其實刪除的不是z，而是y！因為z始終沒有動過，只是把y刪除了，然后把y的key賦值給z的key。所以，在紅黑樹中，z的顏色沒有變，依然符合紅黑性質。（這里我先開始理解為y->color也要賦值給z->color，汗。。。）
2.問：考慮y為黑色時，破壞了哪幾條紅黑性質？
答：當y是根時，且y的一個孩子是紅色，若此時這個孩子成為根結點。———>破壞了性質2
當x和p[y]都是紅色時。 ———>破壞了性質4
包含y的路徑中，黑高度都減少了。 ———>破壞了性質5
解決方法：
上一篇我解釋過，性質五涉及到了整棵樹，難以控制。
因此將x的顏色增加一重黑色，那么當:
①.x原先顏色為RED時——->x包含RED和BLACK兩顏色
②.x原先顏色是BLACK時—–>x包含BLACK, BLACK兩顏色。
此時性質5解決，但是又破壞了性質1.
接下來就是恢復性質1，2，4了。
將額外的一重黑色一直沿樹向上移，直到x是根或者是紅色結點。
看看具體的實現代碼：
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
| void RBDeleteFixup(RBTree &T, Node *x)
{
while(x != T && x->color == BLACK)
{
if(x == x->parent->lchild)
{
Node *w = x->parent->rchild;
///////////// Case 1 /////////////
if(w->color == RED)
{
w->color = BLACK;
x->parent->color = RED;
LeftRotate(T, x->parent);
w = x->parent->rchild;
}
///////////// Case 2 /////////////
if(w->lchild->color == BLACK && w->rchild->color == BLACK)
{
w->color = RED;
x = x->parent;
}
else
{
///////////// Case 3 /////////////
if(w->rchild->color == BLACK)
{
w->lchild->color = BLACK;
w->color = RED;
RightRotate(T, w);
w = x->parent->rchild;
}
///////////// Case 4 /////////////
w->color = x->parent->color;
x->parent->color = BLACK;
w->rchild->color = BLACK;
LeftRotate(T, x->parent);
x = T;
}
}
else
{
Node *w = x->parent->lchild;
if(w->color == RED)
{
w->color = BLACK;
x->parent->color = RED;
RightRotate(T, x->parent);
w = x->parent->lchild;
}
if(w->lchild->color == BLACK && w->rchild->color == BLACK)
{
w->color = RED;
x = x->parent;
}
else
{
if(w->lchild->color == BLACK)
{
w->rchild->color = BLACK;
w->color = RED;
LeftRotate(T, w);
w = x->parent->lchild;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->lchild->color = BLACK;
RightRotate(T, x->parent);
x = T;
}
}
}
x->color = BLACK;
} |
對于刪除的調整，共八種情況(左右對稱各四種)，這里在書上P175面講的很詳細，所以我也就不再畫圖了，大家可以自己拿起筆在草稿紙上畫一
在我獨立博客上的原文：http://www.wutianqi.com/?p=2449
歡迎大家互相討論，一起進步！
posted on 2011-05-11 11:52
Tanky Woo 閱讀(1866)
評論(1) 編輯 收藏 引用