大部分轉(zhuǎn)載： http://yanglongylj.blog.163.com/blog/static/563834532009113021438417/

?

?

紅黑樹(shù)的性質(zhì)與定義

紅黑樹(shù)(red-black tree) 是一棵滿足下述性質(zhì)的二叉查找樹(shù)：

1. 每一個(gè)結(jié)點(diǎn)要么是紅色，要么是黑色。

2. 根結(jié)點(diǎn)是黑色的。

3. 所有葉子結(jié)點(diǎn)都是黑色的（實(shí)際上都是Null指針，下圖用NIL表示）。葉子結(jié)點(diǎn)不包含任何關(guān)鍵字信息，所有查詢關(guān)鍵字都在非終結(jié)點(diǎn)上。

4. 每個(gè)紅色結(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)必須是黑色的。換句話說(shuō)：從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色結(jié)點(diǎn)

5. 從任一結(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色結(jié)點(diǎn)

?

?

黑深度 —— 從某個(gè)結(jié)點(diǎn)x出發(fā)(不包括結(jié)點(diǎn)x本身)到葉結(jié)點(diǎn)(包括葉子結(jié)點(diǎn))的路徑上的黑結(jié)點(diǎn)個(gè)數(shù),稱為該結(jié)點(diǎn)x的黑深度,記為bd(x),根結(jié)點(diǎn)的黑深度就是該紅黑樹(shù)的黑深度。葉子結(jié)點(diǎn)的黑深度為0。 比如：上圖bd(13)=2，bd(8)=2，bd(1)=1

內(nèi)部結(jié)點(diǎn) —— 紅黑樹(shù)的非終結(jié)點(diǎn)

外部節(jié)點(diǎn) —— 紅黑樹(shù)的葉子結(jié)點(diǎn)

?

紅黑樹(shù)相關(guān)定理

1. 從根到葉子的最長(zhǎng)的可能路徑不多于最短的可能路徑的兩倍長(zhǎng)。

????? 根據(jù)上面的性質(zhì)5我們知道上圖的紅黑樹(shù)每條路徑上都是3個(gè)黑結(jié)點(diǎn)。因此最短路徑長(zhǎng)度為2(沒(méi)有紅結(jié)點(diǎn)的路徑)。再根據(jù)性質(zhì)4(兩個(gè)紅結(jié)點(diǎn)不能相連)和性質(zhì)1，2(葉子和根必須是黑結(jié)點(diǎn))。那么我們可以得出：一條具有3個(gè)黑結(jié)點(diǎn)的路徑上最多只能有2個(gè)紅結(jié)點(diǎn)(紅黑間隔存在)。也就是說(shuō)黑深度為2（根結(jié)點(diǎn)也是黑色）的紅黑樹(shù)最長(zhǎng)路徑為4，最短路徑為2。 從這一點(diǎn)我們可以看出紅黑樹(shù)是 大致平衡的。 (當(dāng)然比平衡二叉樹(shù)要差一些，AVL的平衡因子最多為1)

?

2. 紅黑樹(shù)的樹(shù)高(h)不大于兩倍的紅黑樹(shù)的黑深度(bd)，即h<=2bd

????? 根據(jù)定理1，我們不難說(shuō)明這一點(diǎn)。bd是紅黑樹(shù)的最短路徑長(zhǎng)度。而可能的最長(zhǎng)路徑長(zhǎng)度(樹(shù)高的最大值)就是紅黑相間的路徑，等于2bd。因此h<=2bd。

?

3. 一棵擁有n個(gè)內(nèi)部結(jié)點(diǎn)(不包括葉子結(jié)點(diǎn))的紅黑樹(shù)的樹(shù)高h(yuǎn)<=2log(n+1)

????? 下面我們首先證明一顆有n個(gè)內(nèi)部結(jié)點(diǎn)的紅黑樹(shù)滿足n>=2^bd-1。這可以用數(shù)學(xué)歸納法證明，施歸納于樹(shù)高h(yuǎn)。當(dāng)h=0時(shí)，這相當(dāng)于是一個(gè)葉結(jié)點(diǎn)，黑高度bd為0，而內(nèi)部結(jié)點(diǎn)數(shù)量n為0，此時(shí)0>=2^0-1成立。假設(shè)樹(shù)高h(yuǎn)<=t時(shí)，n>=2^bd-1成立，我們記一顆樹(shù)高 為t+1的紅黑樹(shù)的根結(jié)點(diǎn)的左子樹(shù)的內(nèi)部結(jié)點(diǎn)數(shù)量為nl，右子樹(shù)的內(nèi)部結(jié)點(diǎn)數(shù)量為nr，記這兩顆子樹(shù)的黑高度為bd'（注意這兩顆子樹(shù)的黑高度必然一 樣），顯然這兩顆子樹(shù)的樹(shù)高<=t，于是有nl>=2^bd'-1以及nr>=2^bd'-1，將這兩個(gè)不等式相加有nl+nr>=2^(bd'+1)-2，將該不等式左右加1，得到n>=2^(bd'+1)-1，很顯然bd'+1>=bd，于是前面的不等式可以 變?yōu)閚>=2^bd-1，這樣就證明了一顆有n個(gè)內(nèi)部結(jié)點(diǎn)的紅黑樹(shù)滿足n>=2^bd-1。

??????? 在根據(jù)定理2，h<=2bd。即n>=2^(h/2)-1，那么h<=2log(n+1)

????? ?? 從這里我們能夠看出，紅黑樹(shù)的查找長(zhǎng)度最多不超過(guò)2log(n+1)，因此其查找時(shí)間復(fù)雜度也是O(log N)級(jí)別的。

?

紅黑樹(shù)的操作

?

因?yàn)槊恳粋€(gè)紅黑樹(shù)也是一個(gè)特化的二叉查找樹(shù)， 因此紅黑樹(shù)上的查找操作與普通二叉查找樹(shù)上的查找操作相同。 然而，在紅黑樹(shù)上進(jìn)行插入操作和刪除操作會(huì)導(dǎo)致不 再符合紅黑樹(shù)的性質(zhì)。 恢復(fù)紅黑樹(shù)的屬性需要少量(O(log n))的顏色變更(實(shí)際是非常快速的)和不超過(guò)三次樹(shù)旋轉(zhuǎn)(對(duì)于插入操作是兩次)。 雖然插入和刪除很復(fù)雜， 但操作時(shí)間仍可以保持為 O(log n) 次 。

?

插入操作

我們首先 以二叉查找樹(shù)的方法增加節(jié)點(diǎn)并標(biāo)記它為紅色。 （ 如果設(shè)為黑色，就會(huì)導(dǎo)致根到葉子的路徑上有一條路上，多一個(gè)額外的黑節(jié)點(diǎn)，這個(gè)是很難調(diào)整的。但是設(shè)為紅色節(jié)點(diǎn)后，可能會(huì)導(dǎo)致出現(xiàn)兩個(gè)連續(xù)紅色節(jié)點(diǎn)的沖突，那么可以通過(guò)顏色調(diào)換（color flips）和樹(shù)旋轉(zhuǎn)來(lái)調(diào)整。） 下面要進(jìn)行什么操作取決于其他臨近節(jié)點(diǎn)的顏色。同人類的家族樹(shù)中一樣，我們將使用術(shù)語(yǔ)叔父節(jié)點(diǎn)來(lái)指一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)。

?

假設(shè)新加入的結(jié)點(diǎn)為N，父親結(jié)點(diǎn)為P，叔父結(jié)點(diǎn)為Ui(叔父結(jié)點(diǎn)就是一些列P的兄弟結(jié)點(diǎn))，祖父結(jié)點(diǎn)G(父親結(jié)點(diǎn)P的父親)。下面會(huì)給出每一種情況，我們將使用C示例代碼來(lái)展示。通過(guò)下列函數(shù)，可以找到一個(gè)節(jié)點(diǎn)的叔父和祖父節(jié)點(diǎn): ?

    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. 當(dāng)前紅黑樹(shù)為空，新結(jié)點(diǎn)N位于樹(shù)的根上，沒(méi)有父結(jié)點(diǎn)。

?

?????? 此時(shí)很簡(jiǎn)單，我們將直接插入一個(gè)黑結(jié)點(diǎn)N（滿足性質(zhì)2），其他情況下插入的N為紅色（原因在前面提到了）。

     void insert_case1(node n) {
     if (n->parent == NULL)
         n->color = BLACK;
     else
         insert_case2(n); //插入情況2
 }
  

情況2. 新結(jié)點(diǎn)N的父結(jié)點(diǎn)P是黑色。

?

?????? 在這種情況下，我們插入一個(gè)紅色結(jié)點(diǎn)N(滿足性質(zhì)5)。

     void insert_case2(node n) {
     if (n->parent->color == BLACK)
         return; // 樹(shù)仍舊有效
     else
         insert_case3(n); //插入情況3
 }
  

?

注意：在情況3，4，5下，我們假定新節(jié)點(diǎn)有祖父節(jié)點(diǎn)，因?yàn)楦腹?jié)點(diǎn)是紅色；并且如果它是根，它就應(yīng)當(dāng)是黑色。所以新節(jié)點(diǎn)總有一個(gè)叔父節(jié)點(diǎn)，盡管在情形4和5下它可能是葉子。

?

情況3.如果父節(jié)點(diǎn)P和叔父節(jié)點(diǎn)U二者都是紅色。

?

??????? 如下圖，因?yàn)樾录尤氲腘結(jié)點(diǎn)必須為紅色，那么我們可以將父結(jié)點(diǎn)P(保證性質(zhì)4)，以及N的叔父結(jié)點(diǎn)U(保證性質(zhì)5)重新繪制成黑色。如果此時(shí)祖父結(jié)點(diǎn)G是根，則結(jié)束變化。如果不是根，則祖父結(jié)點(diǎn)重繪為紅色(保證性質(zhì)5)。但是，G的父親也可能是紅色的，為了保證性質(zhì)4。我們把G遞歸當(dāng)做新加入的結(jié)點(diǎn)N在進(jìn)行各種情況的重新檢查。

?????

     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);
 }

  

?

注意：在情形4和5下，我們假定父節(jié)點(diǎn)P 是祖父結(jié)點(diǎn)G 的左子節(jié)點(diǎn)。如果它是右子節(jié)點(diǎn)，情形4和情形5中的左和右應(yīng)當(dāng)對(duì)調(diào)。

?

情況4. 父節(jié)點(diǎn)P是紅色而叔父節(jié)點(diǎn)U是黑色或缺少; 另外，新節(jié)點(diǎn)N是其父節(jié)點(diǎn)P的右子節(jié)點(diǎn)，而父節(jié)點(diǎn)P又是祖父結(jié)點(diǎn)G的左子節(jié)點(diǎn)。

?

?????? 如下圖, 在這種情形下，我們進(jìn)行一次左旋轉(zhuǎn)調(diào)換新節(jié)點(diǎn)和其父節(jié)點(diǎn)的角色（與AVL樹(shù)的左旋轉(zhuǎn)相同）; 這導(dǎo)致某些路徑通過(guò)它們以前不通過(guò)的新節(jié)點(diǎn)N或父節(jié)點(diǎn)P中的一個(gè)，但是這兩個(gè)節(jié)點(diǎn)都是紅色的，所以性質(zhì)5沒(méi)有失效。但目前情況將違反性質(zhì)4，所以接著，我們按下面的情況5繼續(xù)處理以前的父節(jié)點(diǎn)P。

?

     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. 父節(jié)點(diǎn)P是紅色而叔父節(jié)點(diǎn)U 是黑色或缺少，新節(jié)點(diǎn)N 是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)，而父節(jié)點(diǎn)P又是祖父結(jié)點(diǎn)的G的左子節(jié)點(diǎn)。

?

?????? 如下圖： 在這種情形下，我們進(jìn)行針對(duì)祖父節(jié)點(diǎn)P 的一次右旋轉(zhuǎn); 在旋轉(zhuǎn)產(chǎn)生的樹(shù)中，以前的父節(jié)點(diǎn)P現(xiàn)在是新節(jié)點(diǎn)N和以前的祖父節(jié)點(diǎn)G 的父節(jié)點(diǎn)。我們知道以前的祖父節(jié)點(diǎn)G是黑色，否則父節(jié)點(diǎn)P就不可能是紅色。我們切換以前的父節(jié)點(diǎn)P和祖父節(jié)點(diǎn)G的顏色，結(jié)果的樹(shù)滿足性質(zhì)4[3]。性質(zhì) 5[4]也仍然保持滿足，因?yàn)橥ㄟ^(guò)這三個(gè)節(jié)點(diǎn)中任何一個(gè)的所有路徑以前都通過(guò)祖父節(jié)點(diǎn)G ，現(xiàn)在它們都通過(guò)以前的父節(jié)點(diǎn)P。在各自的情形下，這都是三個(gè)節(jié)點(diǎn)中唯一的黑色節(jié)點(diǎn)。

????????

     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));
     }
 }
  

刪除操作

?

如果需要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)兒子，那么問(wèn)題可以被轉(zhuǎn)化成刪除另一個(gè)只有一個(gè)兒子的節(jié)點(diǎn)的問(wèn)題（為了表述方便，這里所指的兒子，為非葉子節(jié)點(diǎn)的兒子）。 對(duì)于二叉查找樹(shù)，在刪除帶有兩個(gè)非葉子兒子的節(jié)點(diǎn)的時(shí)候，我們找到要么在它的左子樹(shù)中的最大元素、要么在它的右子樹(shù)中的最小元素，并把它的值轉(zhuǎn)移到要?jiǎng)h除 的節(jié)點(diǎn)中(如在這里所展示的那樣)。我們接著刪除我們從中復(fù)制出值的那個(gè)節(jié)點(diǎn)，它必定有少于兩個(gè)非葉子的兒子。因?yàn)橹皇菑?fù)制了一個(gè)值而不違反任何屬性，這 就把問(wèn)題簡(jiǎn)化為如何刪除最多有一個(gè)兒子的節(jié)點(diǎn)的問(wèn)題。它不關(guān)心這個(gè)節(jié)點(diǎn)是最初要?jiǎng)h除的節(jié)點(diǎn)還是我們從中復(fù)制出值的那個(gè)節(jié)點(diǎn)。

?

在本文余下的部分中，我們只需要討論刪除只有一個(gè)兒子的節(jié)點(diǎn)(如果它兩個(gè)兒子都為空，即均為葉子，我們?nèi)我鈱⑵渲幸粋€(gè)看作它的兒子)。如果我們刪除一個(gè)紅色節(jié)點(diǎn)，它的父親和兒子一定是黑色的。所以我們可以簡(jiǎn)單的用它的黑色兒子替換它，并不會(huì)破壞屬性3和4。通過(guò)被刪除節(jié)點(diǎn)的所有路徑只是少了一個(gè)紅色 節(jié)點(diǎn)，這樣可以繼續(xù)保證屬性5。另一種簡(jiǎn)單情況是在被刪除節(jié)點(diǎn)是黑色而它的兒子是紅色的時(shí)候。如果只是去除這個(gè)黑色節(jié)點(diǎn)，用它的紅色兒子頂替上來(lái)的話，會(huì) 破壞屬性4，但是如果我們重繪它的兒子為黑色，則曾經(jīng)通過(guò)它的所有路徑將通過(guò)它的黑色兒子，這樣可以繼續(xù)保持屬性4。

?

需要進(jìn)一步討論的是在要?jiǎng)h除的節(jié)點(diǎn)和它的兒子二者都是黑色的時(shí)候，這是一種復(fù)雜的情況。我們首先把要?jiǎng)h除的節(jié)點(diǎn)替換為它的兒子。出于方便，稱呼這個(gè)兒子為 N，稱呼它的兄弟(它父親的另一個(gè)兒子)為S。在下面的示意圖中，我們還是使用P稱呼N的父親，SL稱呼S的左兒子，SR稱呼S的右兒子。我們將使用下述 函數(shù)找到兄弟節(jié)點(diǎn):

    struct node * sibling(struct node *n)
{
        if (n == n->parent->left)
                return n->parent->right;
        else
                return n->parent->left;
}
  

?我們可以使用下列代碼進(jìn)行上述的概要步驟，這里的函數(shù) replace_node 替換 child 到 n 在樹(shù)中的位置。出于方便，在本章節(jié)中的代碼將假定空葉子被用不是 NULL 的實(shí)際節(jié)點(diǎn)對(duì)象來(lái)表示(在插入章節(jié)中的代碼可以同任何一種表示一起工作)。

    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 和它初始的父親是黑色，則刪除它的父親導(dǎo)致通過(guò) N 的路徑都比不通過(guò)它的路徑少了一個(gè)黑色節(jié)點(diǎn)。因?yàn)檫@違反了屬性 4，樹(shù)需要被重新平衡。有幾種情況需要考慮:

?

情況1. N 是新的根。

    void delete_case1(struct node *n)
{
        if (n->parent != NULL)
                delete_case2(n);
}
  

    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);
}
  

    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);
}
  

    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);
}
  

    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);
}
  

    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);
        }
}