Red Black Tree: Insert(新增資料)與Fixup(修正)

Posted by Chiu CC on 1 27, 2016


先備知識與注意事項*

(完整範例程式碼也可以看這裡:RBT_Insert_Delete.cpp)

RBT也是一棵BST,而RBT之Insert(新增資料)方法便是先沿用InsertBST(),再對顏色進行修正。而修正的方法將用上Rotation(),因此,建議在閱讀本篇文章之前,先熟悉Binary Search Tree: Search(搜尋資料)、Insert(新增資料)Red Black Tree: Rotation(旋轉)會很有幫助。


目錄


如同於BST中Insert(新增資料)

RBT也是一棵BST,在Insert(新增資料)時,必須滿足:Key(L)<Key(Current)<Key(R),因此,RBT的InsertRBT()前半部演算法與BST的函式:InsertBST()大同小異

需要修改/擴充的部分有三處:

  1. NIL:所有原先在BST中指向NULL的pointer,在RBT中需要修正成指向NIL,包括「條件式」與「新增node的child pointer」。
  2. 顏色:如同在RBT:Rotation(旋轉)所說,一般預設新增node為紅色,因此,若新增node接在黑色node之後,仍能滿足RBT的特徵。但是若新增node接在紅色node之後,則違反了RBT之第四點特徵,必須進行修正。
  3. 引進函式:InsertFixedUpRBT()進行修正。

InsertRBT()的程式範例如下:

// C++ code
void RBT::InsertRBT(int key, string str){
    // 前半部與 InsertBST()之邏輯完全相同, 僅僅需要修改 NULL <-> NIL
    TreeNode *y = neel;
    TreeNode *x = root;
    TreeNode *insert_node = new TreeNode(key, str);

    while (x != neel) {     // 把root初始化成neel, 這裡就可以用neel來做判斷
        y = x;
        if (insert_node->key < x->key){
            x = x->leftchild;
        }
        else{
            x = x->rightchild;
        }
    }

    insert_node->parent = y;

    if (y == neel){
        this->root = insert_node;
    }
    else if (insert_node->key < y->key){
        y->leftchild = insert_node;
    }
    else{
        y->rightchild = insert_node;
    }

    // 以下是對RBT之node的設定, 將child pointer指向NIL, 顏色設為紅色
    insert_node->leftchild = neel;
    insert_node->rightchild = neel;
    insert_node->color = 0;             // 顏色可以在constructor中預設

    InsertFixedUpRBT(insert_node);      // 對可能出現紅色與紅色node相連之情形做修正
}


修正:InsertFixUpRBT()

什麼情況需要對InsertRBT()做修正?
當新增node接在紅色的node的child pointer,形成紅色與紅色相連時。

考慮以下情況,如圖一(a),新增的node將要接在node(X)上:

  • node(X)為其parent,顏色為紅色;
  • node(Y)為其uncle,其顏色可能為紅色或黑色
  • node(Z)為其grandparent,顏色必定為黑色(因為node(X)是紅色);
  • node(W)的顏色可能是紅色或黑色
  • 所有灰色node(如node(a)、node(b)、node(c)、node(d))表示:只要不影響RBT之特徵,其顏色、是否實際攜帶資料或是否為NIL並不影響結果。

bst

圖一(a):。

根據uncle的顏色是紅色或者黑色,可以將修正(FixUp)分成三種情形(case):

  1. Case1:uncle是紅色,不論新增的node是node(X)的leftchildrightchild
  2. Case2:uncle是黑色,而且新增的node為node(X)的rightchild
  3. Case3:uncle是黑色,而且新增的node為node(X)的leftchild

Case1

圖一(b)左,此時current指向新增的node(A),而node(A)成為node(X)的rightchild,其uncle:node(Y)是紅色的。
修正的方法就是「把債還給上一代的上一代」:

  • parent塗成黑色:node(X)塗成黑色;
  • uncle塗成黑色:node(Y)塗成黑色;
  • parent->parent塗成紅色:node(Z)塗成紅色:
  • current從node(A)移到node(Z)。

此時,如圖一(b)右,從node(Z)出發往其descendant leaves的任一path上之黑色node數皆相同,這個subtree便滿足了RBT的特徵。

bst

圖一(b):。

接著必需根據node(W)的顏色採取不同行動:

  • 若node(W)為黑色,就不需要再做調整;
  • 若node(W)為紅色,則node(Z)與node(W)再次形成紅色node與紅色node相連,必須重複同樣的判斷流程。

若node(A)成為node(X)的leftchild,如圖一(c),修正的方法同上。

bst

圖一(c):。

Case3

圖一(d),新增的node(A)成為node(X)的leftchild,其uncle:node(Y)是黑色。

bst

圖一(d):。

事實上,若current指向之node(此為node(A))是新增的node,則根據RBT之第五點特徵,其uncle:node(Y)必定是NIL,如圖一(e)左。

不過,在稍後的範例中將會看到,current不一定是「剛剛新增的node」,也有可能是「修正到一半,出現紅色與紅色相連的node」,但因為是「修正到一半」,尚未調整node(Z)的顏色,因此所有從node(Z)往其descendant leaves的任意path上之黑色node數必定不變,此時,若node(Y)不為NIL,則node(X)以及node(A)必定還有黑色的child pointer,如圖一(e)右所示,node(a)、node(b)與node(c)皆為黑色。

bst

圖一(e):。

修正方法如下,見圖一(f):

  • parent塗成黑色:node(X)塗成黑色;
  • parent->parent塗成紅色:node(Z)塗成紅色;
  • parent->parentnode(Z)進行Right Rotation(向右旋轉)

bst

圖一(f):。

經過Case3的修正,必定會滿足RBT之規則,原因在於:

  • 先考慮圖一(e),若從node(A)往其descendant leaves的任意path上之黑色node數為\(M\),則從node(Z)往其descendant leaves的任意path上之黑色node數為\(M+1\)
  • 再看圖一(g),因為在修正的過程中,node(Z)從黑色被修改成紅色,因此從node(Z)往其descendant leaves的任意path上之黑色node數下修為\(M\),與node(A)相同,使得整棵樹滿足RBT之特徵。

bst

圖一(g):。

Case2

圖一(h),新增的node(A)成為node(X)的rightchild,其uncle:node(Y)是黑色。

bst

圖一(h):。

如同Case3,圖一(h)的uncle:node(Y)同樣有兩種可能:攜帶實際資料的黑色node,或者NIL,如圖一(i):

bst

圖一(i):。

而修正Case2的方法就是將其轉換成Case3,再利用上述Case3的方法調整成正確的RBT。
從Case2調整成Case3,如圖一(j):

  • current移至current->parent:將current從node(A)移到node(X);
  • 對新的current進行Left Rotation:對node(X)進行Left Rotation。

圖一(j)右符合Case3:「current成為其parentleftchild,且其unclenode(Y)是黑色」,因此,只要再進行如同圖一(f)之修正流程即可。

bst

圖一(j):。


幾個範例

Example1

考慮一棵RBT如圖二(a):

bst

圖二(a):。

若想新增node(75),由於其將接在node(80)的leftchild位置上,而node(80)為紅色,因此需要進行修正。
接著觀察,node(75)之uncle:node(60),是紅色,因此可以使用Case1的方法修正,如圖二(b):

  • parentuncle塗黑:node(80)與node(60)塗黑;
  • 將grandparent塗紅:node(70)塗紅;
  • current移至node(70);
  • 進入下一個迴圈判斷node(70)是否與其parent形成紅色與紅色node相連。

恰好,node(50)為root,一定是黑色,因此新增node(75)便算是完成。

bst

圖二(b):。

若想繼續新增node(25),由於其將接在node(30)的leftchild,而node(30)為紅色,因此需要修正。
接著觀察,node(25)之uncleNIL是黑色,而node(25)本身是leftchild,因此可以使用Case3的方法,如圖二(c):

  • parent塗成黑色:node(30)塗成黑色;
  • parent->parent塗成紅色:node(40)塗成紅色;
  • parent->parent:node(40)進行Right Rotation(向右旋轉)

bst

圖二(c):。

若想繼續新增node(79),由於其將接在node(75)的rightchild,而node(75)為紅色,因此需要修正。
接著觀察,node(79)之uncleNIL是黑色,而node(79)本身是rightchild,因此可以使用Case2的方法,先將問題從Case2轉換成Case3,再由Case3之方法修正,如圖二(d):

bst

圖二(d):。


Example2

考慮一棵RBT如圖三(a):

bst

圖三(a):。

要在其中新增node(4),則會依序經歷case1、case2直到case3完成修正,如圖三(b)、圖三(c)、圖三(d)與圖三(e)所示。

bst

圖三(b):。

bst

圖三(c):。

bst

圖三(d):。

bst

圖三(e):。

根據以上說明,可以歸納出對於InsertRBT()的修正(Fix-Up)之情形(Case)間的循環圖,如圖四:

  • 當新增node之parent為紅色時,需要對RBT進行修正;
  • 若進入Case1,有可能執行一次即完成,也有可能再次出現紅色與紅色相連的情況,如圖三(b)-(c);
  • 若進入Case2,就轉換成Case3的情境;
  • 一旦進入Case3,經過修正後必定能滿足RBT之特徵限制。

bst

圖四:。

最後還有一點需要說明。

圖五中:

  • 左圖是本篇文章介紹修正(Fix-Up)的出發點:將新增的node接在node(X)上,而node(X)是node(Z)的leftchild(亦即,新增的node之parentparent->parentleftchild);
  • 還有另外一半的情況就如圖五之右圖:將新增的node接在node(Y)上,而node(Y)是node(Z)的rightchild(亦即,新增的node之parentparent->parentrightchild)。

bst

圖五:。

必須要區分這兩者的原因有二:

  • 一是uncle:因為parentuncle分別為parent->parentleftchildrightchild,若parentleft-uncle就要是right-,反之亦然,兩者屬於互斥(exclusive)事件,不可能同時發生;
  • 二是Rotation(旋轉):在Case2與Case3中必須使用Left/Right Rotation,因此,延續第一點原因,考慮到parentleftchild或是rightchild的不同,Left/Right Rotation的方向也會相反。


程式碼

InsertFixedUpRBT()之範例程式碼分成以下幾個部分:

  • 定義color\(0\)為紅色,\(1\)為黑色;
  • 如同圖四所示,修正的過程可能歷經不止一個Case,因此利用while迴圈實現,條件式便是判斷當前currentparent是否為紅色;
  • 分別進行Case1(圖一(b)與圖一(c))、Case2(圖一(j))與Case3(圖一(f))之修正;
  • 最後,有一行root->color=1,確保root之顏色是黑色,這是為了Case1所設,由於Case1之修正方法是把「紅色與紅色node相連」之可能性往root方向傳遞,有可能root恰好是current的grandparent而被塗成紅色,如圖六,但因為RBT之第二點特徵要求root一定是黑色,因此必須作此預防。

bst

圖六:。

// C++ code
void RBT::InsertFixedUpRBT(TreeNode *current){

    // case0: parent是黑色, 就不用進回圈
    while (current->parent->color == 0) {   // 若parent是紅色即進入迴圈

        // 上半部:parent是grandparent的left child
        if (current->parent == current->parent->parent->leftchild) { 
            TreeNode *uncle = current->parent->parent->rightchild;
            // case1: 若uncle是紅色
            if (uncle->color == 0) {
                current->parent->color = 1;
                uncle->color = 1;
                current->parent->parent->color = 0;              //grandparent改成紅色
                current = current->parent->parent;
            }
            // case2 & 3: uncle是黑色
            else {  
                if (current == current->parent->rightchild){     // case2
                    current = current->parent;
                    LeftRotation(current);
                }
                // case3
                current->parent->color = 1;                      //把parent塗黑
                current->parent->parent->color = 0;              // grandparent塗紅
                RightRotation(current->parent->parent);
            }
        }
        // 下半部:parent是grandparent的right child, 與上半部對稱
        else {  
            TreeNode *uncle = current->parent->parent->leftchild;
            // case1: 若uncle是紅色
            if (uncle->color == 0) {
                current->parent->color = 1;
                uncle->color = 1;
                current->parent->parent->color = 0;              //grandparent改成紅色
                current = current->parent->parent;
            }
            // case2 & 3: uncle是黑色
            else {
                if (current == current->parent->leftchild) {     // case2
                    current = current->parent;
                    RightRotation(current);
                }
                // case3
                current->parent->color = 1;
                current->parent->parent->color = 0;
                LeftRotation(current->parent->parent);
            }
        }
    }
    root->color = 1;    // 確保root是黑色
}


以上便是於Red Black Tree(紅黑樹)中進行Insert(新增資料)與Insert後的Fixup(修正)之介紹。

下一篇文章將介紹於Red Black Tree(紅黑樹)中進行Delete(刪除資料)與Delete後的Fixup(修正)。



參考資料:


RBT系列文章

Red Black Tree: Intro(簡介)
Red Black Tree: Rotation(旋轉)
Red Black Tree: Insert(新增資料)與Fixup(修正)
Red Black Tree: Delete(刪除資料)與Fixup(修正)

回到目錄:

目錄:演算法與資料結構