635
紅黑樹-插入刪除
操作
因為每一個紅黑樹也是一個特化的二叉查找樹，因此紅黑樹上的隻讀操作與普通二叉查找樹上的隻讀操作相同。然而，在紅黑樹上進行插入操作和刪除操作會導致不再符合紅黑樹的性質。恢複紅黑樹的屬性需要少量(O(log n))的顏色變更(實際是非常快速的)和不超過三次樹旋轉(對於插入操作是兩次)。雖然插入和刪除很複雜，但操作時間仍可以保持為 O(log n) 次。
插入
我們首先以二叉查找樹的方法增加節點並標記它為紅色。（如果設為黑色，就會導致根到葉子的路徑上有一條路上，多一個額外的黑節點，這個是很難調整的。但是設為紅色節點後，可能會導致出現兩個連續紅色節點的衝突，那麼可以通過顏色調換（color flips）和樹旋轉來調整。） 下麵要進行什麼操作取決於其他臨近節點的顏色。同人類的家族樹中一樣，我們將使用術語叔父節點來指一個節點的父節點的兄弟節點。注意:
在下麵的示意圖中，將要插入的節點標為N，N的父節點標為P，N的祖父節點標為G，N的叔父節點標為U。在圖中展示的任何顏色要麼是由它所處情形所作的假定，要麼是這些假定所暗含 (imply) 的。
對於每一種情況，我們將使用 C 示例代碼來展示。通過下列函數，可以找到一個節點的叔父和祖父節點:
node grandparent(node n) {
return n->parent->parent;
}
node uncle(node n) {
if (n->parent == grandparent(n)->left)
return grandparent(n)->right;
else
return grandparent(n)->left;
}
情形1: 新節點N位於樹的根上，沒有父節點。在這種情形下，我們把它重繪為黑色以滿足性質2[5]。因為它在每個路徑上對黑節點數目增加一，性質5[4]符合。
void insert_case1(node n) {
if (n->parent == NULL)
n->color = BLACK;
else
insert_case2(n);
}
情形2: 新節點的父節點P是黑色，所以性質4[3]沒有失效（新節點是紅色的）。在這種情形下，樹仍是有效的。性質5[4]受到威脅，因為新節點N有兩個黑色葉子兒子；但是由於新節點N是紅色，通過它的每個子節點的路徑就都有同通過它所取代的黑色的葉子的路徑同樣數目的黑色節點，所以這個性質依然滿足。
void insert_case2(node n) {
if (n->parent->color == BLACK)
return; /* 樹仍舊有效 */
else
insert_case3(n);
}
注意: 在下列情形下我們假定新節點有祖父節點，因為父節點是紅色；並且如果它是根，它就應當是黑色。所以新節點總有一個叔父節點，盡管在情形4和5下它可能是葉子。
|
情形3: 如果父節點P和叔父節點U二者都是紅色，(此時新插入節點N做為P的左子節點或右子節點都屬於情形3,這裏右圖僅顯示N做為P左子的情形)則我們可以將它們兩個重繪為黑色並重繪祖父節點G為紅色(用來保持性質5[4])。現在我們的新節點N有了一個黑色的父節點P。因為通過父節點P或叔父節點U的任何路徑都必定通過祖父節點G，在這些路徑上的黑節點數目沒有改變。但是，紅色的祖父節點G的父節點也有可能是紅色的，這就違反了性質4[3]。為了解決這個問題，我們在祖父節點G上遞歸地進行情形1的整個過程。（把G當成是新加入的節點進行各種情況的檢查） |
void insert_case3(node n) {
if (uncle(n) != NULL && uncle(n)->color == RED) {
n->parent->color = BLACK;
uncle(n)->color = BLACK;
grandparent(n)->color = RED;
insert_case1(grandparent(n));
}
else
insert_case4(n);
}
注意: 在餘下的情形下，我們假定父節點P 是其父親G 的左子節點。如果它是右子節點，情形4和情形5中的左和右應當對調。
|
情形4: 父節點P是紅色而叔父節點U是黑色或缺少; 還有，新節點N是其父節點P的右子節點，而父節點P又是其父節點的左子節點。在這種情形下，我們進行一次左旋轉調換新節點和其父節點的角色; 接著，我們按情形5處理以前的父節點P。這導致某些路徑通過它們以前不通過的新節點N或父節點P中的一個，但是這兩個節點都是紅色的，所以性質5[4]沒有失效。 |
void insert_case4(node n) {
if (n == n->parent->right && n->parent == grandparent(n)->left) {
rotate_left(n->parent);
n = n->left;
} else if (n == n->parent->left && n->parent == grandparent(n)->right) {
rotate_right(n->parent);
n = n->right;
}
insert_case5(n);
}
|
情形5: 父節點P是紅色而叔父節點U 是黑色或缺少，新節點N 是其父節點的左子節點，而父節點P又是其父節點G的左子節點。在這種情形下，我們進行針對祖父節點G 的一次右旋轉; 在旋轉產生的樹中，以前的父節點P現在是新節點N和以前的祖父節點G 的父節點。我們知道以前的祖父節點G是黑色，否則父節點P就不可能是紅色 (如果 P 和 G 都是紅色就違反了性質4，所以 G 必須是黑色)。我們切換以前的父節點P和祖父節點G的顏色，結果的樹滿足性質4[3]。性質5[4]也仍然保持滿足，因為通過這三個節點中任何一個的所有路徑以前都通過祖父節點G ，現在它們都通過以前的父節點P。在各自的情形下，這都是三個節點中唯一的黑色節點。 |
void insert_case5(node n) {
n->parent->color = BLACK;
grandparent(n)->color = RED;
if (n == n->parent->left && n->parent == grandparent(n)->left) {
rotate_right(grandparent(n));
} else {
/* Here, n == n->parent->right && n->parent == grandparent(n)->right */
rotate_left(grandparent(n));
}
}
注意插入實際上是原地算法，因為上述所有調用都使用了尾部遞歸。
刪除
如果需要刪除的節點有兩個兒子，那麼問題可以被轉化成刪除另一個隻有一個兒子的節點的問題（為了表述方便，這裏所指的兒子，為非葉子節點的兒子）。對於二叉查找樹，在刪除帶有兩個非葉子兒子的節點的時候，我們找到要麼在它的左子樹中的最大元素、要麼在它的右子樹中的最小元素，並把它的值轉移到要刪除的節點中(如在這裏所展示的那樣)。我們接著刪除我們從中複製出值的那個節點，它必定有少於兩個非葉子的兒子。因為隻是複製了一個值而不違反任何屬性，這就把問題簡化為如何刪除最多有一個兒子的節點的問題。它不關心這個節點是最初要刪除的節點還是我們從中複製出值的那個節點。
在本文餘下的部分中，我們隻需要討論刪除隻有一個兒子的節點(如果它兩個兒子都為空，即均為葉子，我們任意將其中一個看作它的兒子)。如果我們刪除一個紅色節點，它的父親和兒子一定是黑色的。所以我們可以簡單的用它的黑色兒子替換它，並不會破壞屬性3和4。通過被刪除節點的所有路徑隻是少了一個紅色節點，這樣可以繼續保證屬性5。另一種簡單情況是在被刪除節點是黑色而它的兒子是紅色的時候。如果隻是去除這個黑色節點，用它的紅色兒子頂替上來的話，會破壞屬性5，但是如果我們重繪它的兒子為黑色，則曾經通過它的所有路徑將通過它的黑色兒子，這樣可以繼續保持屬性5。
需要進一步討論的是在要刪除的節點和它的兒子二者都是黑色的時候，這是一種複雜的情況。我們首先把要刪除的節點替換為它的兒子。出於方便，稱唿這個兒子為N，稱唿它的兄弟(它父親的另一個兒子)為S。在下麵的示意圖中，我們還是使用P稱唿N的父親，SL稱唿S的左兒子，SR稱唿S的右兒子。我們將使用下述函數找到兄弟節點:
struct node *
sibling(struct node *n)
{
if (n == n->parent->left)
return n->parent->right;
else
return n->parent->left;
}
我們可以使用下列代碼進行上述的概要步驟，這裏的函數 replace_node 替換 child 到 n 在樹中的位置。出於方便，在本章節中的代碼將假定空葉子被用不是 NULL 的實際節點對象來表示(在插入章節中的代碼可以同任何一種表示一起工作)。
void
delete_one_child(struct node *n)
{
/*
* Precondition: n has at most one non-null child.
*/
struct node *child = is_leaf(n->right) ? n->left : n->right;
replace_node(n, child);
if (n->color == BLACK) {
if (child->color == RED)
child->color = BLACK;
else
delete_case1(child);
}
free(n);
}
如果 N 和它初始的父親是黑色，則刪除它的父親導致通過 N 的路徑都比不通過它的路徑少了一個黑色節點。因為這違反了屬性 4，樹需要被重新平衡。有幾種情況需要考慮:
情況 1: N 是新的根。在這種情況下，我們就做完了。我們從所有路徑去除了一個黑色節點，而新根是黑色的，所以屬性都保持著。
void
delete_case1(struct node *n)
{
if (n->parent != NULL)
delete_case2(n);
}
注意: 在情況2、5和6下，我們假定 N 是它父親的左兒子。如果它是右兒子，則在這些情況下的左和右應當對調。
|
情況 2: S 是紅色。在這種情況下我們在N的父親上做左旋轉，把紅色兄弟轉換成N的祖父。我們接著對調 N 的父親和祖父的顏色。盡管所有的路徑仍然有相同數目的黑色節點，現在 N 有了一個黑色的兄弟和一個紅色的父親，所以我們可以接下去按 4、5或6情況來處理。(它的新兄弟是黑色因為它是紅色S的一個兒子。) |
void
delete_case2(struct node *n)
{
struct node *s = sibling(n);
if (s->color == RED) {
n->parent->color = RED;
s->color = BLACK;
if (n == n->parent->left)
rotate_left(n->parent);
else
rotate_right(n->parent);
}
delete_case3(n);
}
|
情況 3: N 的父親、S 和 S 的兒子都是黑色的。在這種情況下，我們簡單的重繪 S 為紅色。結果是通過S的所有路徑，它們就是以前不通過 N 的那些路徑，都少了一個黑色節點。因為刪除 N 的初始的父親使通過 N 的所有路徑少了一個黑色節點，這使事情都平衡了起來。但是，通過 P 的所有路徑現在比不通過 P 的路徑少了一個黑色節點，所以仍然違反屬性4。要修正這個問題，我們要從情況 1 開始，在 P 上做重新平衡處理。 |
void
delete_case3(struct node *n)
{
struct node *s = sibling(n);
if ((n->parent->color == BLACK) &&
(s->color == BLACK) &&
(s->left->color == BLACK) &&
(s->right->color == BLACK)) {
s->color = RED;
delete_case1(n->parent);
} else
delete_case4(n);
}
|
情況 4: S 和 S 的兒子都是黑色，但是 N 的父親是紅色。在這種情況下，我們簡單的交換 N 的兄弟和父親的顏色。這不影響不通過N 的路徑的黑色節點的數目，但是它在通過 N 的路徑上對黑色節點數目增加了一，添補了在這些路徑上刪除的黑色節點。 |
void
delete_case4(struct node *n)
{
struct node *s = sibling(n);
if ((n->parent->color == RED) &&
(s->color == BLACK) &&
(s->left->color == BLACK) &&
(s->right->color == BLACK)) {
s->color = RED;
n->parent->color = BLACK;
} else
delete_case5(n);
}
|
情況 5: S 是黑色，S 的左兒子是紅色，S 的右兒子是黑色，而 N 是它父親的左兒子。在這種情況下我們在 S 上做右旋轉，這樣 S的左兒子成為 S 的父親和 N 的新兄弟。我們接著交換 S 和它的新父親的顏色。所有路徑仍有同樣數目的黑色節點，但是現在 N 有了一個右兒子是紅色的黑色兄弟，所以我們進入了情況 6。N 和它的父親都不受這個變換的影響。 |
void
delete_case5(struct node *n)
{
struct node *s = sibling(n);
if (s->color == BLACK) /* this if statement is trivial,
due to Case 2 (even though Case two changed the sibling to a sibling's child,
the sibling's child can't be red, since no red parent can have a red child). */
// the following statements just force the red to be on the left of the left of the parent,
// or right of the right, so case six will rotate correctly.
if ((n == n->parent->left) &&
(s->right->color == BLACK) &&
(s->left->color == RED)) { // this last test is trivial too due to cases 2-4.
s->color = RED;
s->left->color = BLACK;
rotate_right(s);
} else if ((n == n->parent->right) &&
(s->left->color == BLACK) &&
(s->right->color == RED)) {// this last test is trivial too due to cases 2-4.
s->color = RED;
s->right->color = BLACK;
rotate_left(s);
}
}
delete_case6(n);
}
|
情況 6: S 是黑色，S 的右兒子是紅色，而 N 是它父親的左兒子。在這種情況下我們在 N 的父親上做左旋轉，這樣 S 成為 N 的父親和 S 的右兒子的父親。我們接著交換 N 的父親和 S 的顏色，並使 S 的右兒子為黑色。子樹在它的根上的仍是同樣的顏色，所以屬性 3 沒有被違反。但是，N 現在增加了一個黑色祖先: 要麼 N 的父親變成黑色，要麼它是黑色而 S 被增加為一個黑色祖父。所以，通過 N 的路徑都增加了一個黑色節點。 此時，如果一個路徑不通過 N，則有兩種可能性:
在任何情況下，在這些路徑上的黑色節點數目都沒有改變。所以我們恢複了屬性 4。在示意圖中的白色節點可以是紅色或黑色，但是在變換前後都必須指定相同的顏色。 |
void
delete_case6(struct node *n)
{
struct node *s = sibling(n);
s->color = n->parent->color;
n->parent->color = BLACK;
if (n == n->parent->left) {
s->right->color = BLACK;
rotate_left(n->parent);
} else {
s->left->color = BLACK;
rotate_right(n->parent);
}
}
同樣的，函數調用都使用了尾部遞歸，所以算法是就地的。此外，在旋轉之後不再做遞歸調用，所以進行了恒定數目(最多 3 次)的旋轉。
漸進邊界的證明
包含n個內部節點的紅黑樹的高度是 O(log(n))。
定義:
- h(v) = 以節點v為根的子樹的高度。
- bh(v) = 從v到子樹中任何葉子的黑色節點的數目(如果v是黑色則不計數它)(也叫做黑色高度)。
引理: 以節點v為根的子樹有至少2bh(v) − 1個內部節點。
引理的證明(通過歸納高度):
基礎: h(v) = 0
如果v的高度是零則它必定是 nil，因此 bh(v) = 0。所以:
2bh(v) − 1 = 20 − 1 = 1 − 1 = 0
歸納假設: h(v) = k 的v有 2bh(v) − 1 − 1 個內部節點暗示了 h(v') = k+1 的 v'有2bh(v') − 1 個內部節點。
因為 v' 有 h(v') > 0 所以它是個內部節點。同樣的它有黑色高度要麼是 bh(v') 要麼是 bh(v')-1 (依據v'是紅色還是黑色)的兩個兒子。通過歸納假設每個兒子都有至少 2bh(v') − 1 − 1 個內部接點，所以 v' 有:
2bh(v') − 1 − 1 + 2bh(v') − 1 − 1 + 1 = 2bh(v') − 1
個內部節點。
使用這個引理我們現在可以展示出樹的高度是對數性的。因為在從根到葉子的任何路徑上至少有一半的節點是黑色(根據紅黑樹屬性4)，根的黑色高度至少是h(root)/2。通過引理我們得到:
因此根的高度是O(log(n))。
最後更新：2017-04-03 20:51:32