紅黑樹的使用詳解

2020-01-26 16:18:17

字體：大中小

來源：轉(zhuǎn)載

供稿：網(wǎng)友

（學(xué)習(xí)的參考資料主要是《算法導(dǎo)論》）

　　首先是紅黑樹的性質(zhì)。一棵二叉查找樹滿足以下的紅黑性質(zhì)，則為一棵紅黑樹。

　　1)每個結(jié)點或是紅的，或是黑的。

　　2)根結(jié)點是黑的。

　　3)每個葉結(jié)點(NIL)是黑的。

　　4)紅結(jié)點的兩個孩子都是黑的。

　　5)對任意結(jié)點，從它到其子孫結(jié)點所有路徑上包含相同數(shù)目的黑結(jié)點。

　　初學(xué)時并不在意，但是仔細研究相關(guān)算法就會知道，算法都是圍繞保持這些性質(zhì)來進行的。性質(zhì)5）保證了紅黑樹使用時的高效。定理證明了n個內(nèi)結(jié)點的紅黑樹高度至多為2lg(n+1)。

　　不同于一般二叉查找樹，紅黑樹一般采用一個哨兵結(jié)點代表NIL，這對算法的使用提供了很多方便，具體編寫時可以體會的到。哨兵設(shè)置為黑色，它是根的父結(jié)點，也是所有的葉子結(jié)點。而它的其他域可以設(shè)置為任意值。我用關(guān)鍵字把它和普通的結(jié)點進行區(qū)分。

　　旋轉(zhuǎn)是紅黑樹的特有操作。以前搞不清左旋和右旋究竟是如何進行的，現(xiàn)在比較明白，可以這樣概括：以x結(jié)點左旋即為，使x從一棵子樹的根變成這個子樹的左孩子；對稱的，同理。旋轉(zhuǎn)是紅黑樹插入和刪除時為了維持紅黑性質(zhì)而可能進行的操作。

　　插入的原理：

　　除了空指針的處理，插入的過程和二叉查找樹相同，但是插入后需要進行獨有的調(diào)整算法以保證紅黑性質(zhì)。下面的描述是我的個人概括，看上去比較混亂，和算法以及實例相對照著可能容易理解一些。

　　新插入的點z直接染成紅色，再根據(jù)其父結(jié)點是否為紅(與性質(zhì)4沖突)和插入的結(jié)點是否為根（與性質(zhì)2沖突）進行調(diào)整。后者直接把根染黑即可。

　　對于前者，找到z的叔叔y（找叔叔y雖然需要分情況處理，但比較簡單，不詳寫），根據(jù)y是紅還是黑進一步分清況。z的父親為左孩子時，前者只需要把z的父親和叔叔同時變黑、z的父結(jié)點的父結(jié)點變紅、令z指向z的父結(jié)點的父結(jié)點迭代處理即可；后者進一步分z是左孩子還是右孩子處理。z是左孩子時直接以z的父結(jié)點進行旋轉(zhuǎn)讓z的父親左旋并成為新z即成為后一種情況。在后一種情況中，將z的父親染黑，祖父染紅，以z的祖父右旋就能獲得。

　　刪除的原理:

　　算法導(dǎo)論上的刪除算法把兩種情況同時進行處理，確實很有技巧。紅黑樹的刪除除了最后需要根據(jù)對于刪除結(jié)點的顏色來判斷是否需要進行調(diào)整外，和普通的二叉查找樹沒有區(qū)別，這里稍微做一下分析。

復(fù)制代碼代碼如下:

RB-DELETE(T, z)    　　　　　　　　　　　　　　　　 // 　　情況1　　　　　　　　　　 ||　　情況2
 if left[z] = nil[T] or right[z] = nil[T]　　　　//　　z最多一個孩子時　　　　　　 ||　　z有兩個孩子時
   then y ← z　　　　　　　　　　　　　　　　　　　　//　　 令y=z　　　　　　　　　　　||　  令y是z后繼(此時y必然不是z的右孩子)
   else y ← TREE-SUCCESSOR(z)　　　　　　　　　　 //===============================================================================
 if left[y] ≠ nil[T]　　　　　　　　　　　　　　　 //　　令x為y的孩子或哨兵　　　　　 ||　　 令x是y的右孩子(x必然不為左孩子，否則y不可能是z的后繼)
    then x ← left[y]　　　　　　　　　　　　　　　 //                     　　　　 ||    將來x會代替y的位置
    else x ← right[y]　　　　　　　　　　　　　　　//================================================================================
 p[x] ← p[y]　　　　　　　　　　　　　　　　　　　　//
 if p[y] = nil[T]　　　　　　　　　　　　　　　　　//
     then root[T] ← x　　　　　　　　　　　　　　 //                         x與x的新父親之間建立關(guān)系
     else if y = left[p[y]]　　　　　　　　　　　//
           then left[p[y]] ← x　　　　　　　　  //
           else right[p[y]] ← x　　　　　　　　 //=================================================================================
 if y !≠ z　　　　　　　　　　　　　　　　　　　　　// 　　　　　　　　　　　　　　　  ||
     then key[z] ← key[y]                     //       刪完后整體上移   　　　　||　　　　替代，用于替代的原結(jié)點刪除
         copy y's satellite data into z       //                             ||
 if color[y] = BLACK                          //                             ||
     then RB-DELETE-FIXUP(T, x)               //                             ||
  return y

　　刪除后，如果刪除的結(jié)點是黑色，可能會造成性質(zhì)2、4、5的違反。調(diào)整算法思想是使得代替y的x多染一層黑色而成為紅黑或二重黑色結(jié)點。這個處理只是用指針x標示，并不用改變結(jié)點color域的內(nèi)容。調(diào)整算法按8種情況，其中兩兩對稱，只描述4種。

　　用w表示x的兄弟。

　　情況1為w紅。此時調(diào)整w為黑，p[x]為紅，以p[x]左旋，w指向x的新兄弟，此時則成為情況2或3或4。

　　情況2為w黑，且w的兩個孩子均黑。此時把w染紅，令p[x]成為新的x。這相當于把x剝離了一層黑色，使這層黑色上移。

　　情況3為w黑，w的左孩子為紅，右孩子為黑。這時交換w和左孩子顏色，并對w右旋，此時成為情況4。

　　情況4為w黑，w有孩子為紅。這時使w成為p[x]的顏色，p[x]置為黑色，w的右孩子置為黑，對p[x]左旋。令x為根。這時相當于把原先x上的一重黑色傳給了其父親并于它一起下移，而w代替了其父親原先的顏色和位置。這是不存在紅黑結(jié)點或二重黑結(jié)點。

　　每次處理都判斷x是否為根且x是否為黑。x不為根且為黑時才代表有紅黑結(jié)點或二重黑結(jié)點，需要進行新一輪循環(huán)。循環(huán)結(jié)束后把根染黑就結(jié)束了。

　　最后附上一個我自己用C寫的紅黑樹操作。插入操作驗證無誤，刪除操作驗證次數(shù)有限，可能有bug存在。

復(fù)制代碼代碼如下:

#include <stdlib.h>
#include <stdio.h>

#define T_nil -1
//T_nil is a key of nil[T] in the book.
#define RED 1
#define BLACK 0//T_nil is BLACK

//T_nil's p is itself. need to set.

struct rb_tree {
    int color;
    int key; //normally a positive number.
    struct rb_tree *left;
    struct rb_tree *right;
    struct rb_tree *p;
};

int rb_walk(struct rb_tree *node) {
    if (node->key != T_nil) {
        rb_walk(node->left);
        printf("%d, color is %s/n",node->key,(node->color?"RED":"BLACK"));
        rb_walk(node->right);
    }
    return 1;
}

struct rb_tree* rb_search(struct rb_tree *node, int k) {
if ((node->key == T_nil) || (node->key == k))
return node;

    if ( k < node->key )
        return rb_search(node->left,k);
    else
        return rb_search(node->right,k);
}

struct rb_tree* tree_minimum(struct rb_tree *node) {
    if (node->key == T_nil)
        return node;
    while (node->left->key != T_nil)
        node = node->left;
    return node;
}

struct rb_tree* tree_maximum(struct rb_tree *node) {
    if (node->key == T_nil)
        return node;
    while (node->right->key != T_nil)
        node = node->right;
    return node;
}

struct rb_tree* tree_successor(struct rb_tree *node) {
    struct rb_tree *y;
    if (node->right->key != T_nil)
        return tree_minimum(node->right);
    y = node->p;
    while ((y->key != T_nil) && (node == y->right)) {
        node = y;
        y = y->p;
    }
    return y;
}
//3 function of below is copy from tree.

struct rb_tree * left_rotate(struct rb_tree *rb, struct rb_tree *x) {
    struct rb_tree *y;
    //if (x->right->key == T_nil) {
    //    printf("have no right child,rotation cancel./n");
    //    return rb;
    //}
    y = x->right;
    x->right = y->left;
    if (y->left->key != T_nil)
        y->left->p = x;
    y->p = x->p;
    if    (x->p->key == T_nil)
        rb = y;
    else if (x == x->p->left)
        x->p->left = y;
    else
        x->p->right = y;
    y->left = x;
    x->p = y;
    return rb;
}

struct rb_tree *right_rotate(struct rb_tree *rb, struct rb_tree *x) {
    struct rb_tree *y;
    //if (x->left->key == T_nil ) {
    //    printf("have no left child,rotation cancel./n");
    //    return rb;
    //}
    y = x->left;
    x->left = y->right;
    if (y->right->key != T_nil )
        y->right->p = x;
    y->p = x->p;
    if (x->p->key == T_nil)
        rb = y;
    else if (x == x->p->left)
        x->p->left = y;
    else
        x->p->right = y;
    y->right = x;
    x->p = y;
    return rb;
}

struct rb_tree* rb_insert_fixup(struct rb_tree *rb, struct rb_tree *z) {
    struct rb_tree *y;
    while (z->p->color == RED) {
        if (z->p == z->p->p->left) {
            y = z->p->p->right;
            if (y->color == RED)    {
                z->p->color = BLACK;
                y->color = BLACK;
                z->p->p->color = RED;
                z = z->p->p;
            }
            else {
                if (z == z->p->right) {
                    z= z->p;
                    rb = left_rotate(rb,z);
                }
                z->p->color = BLACK;
                z->p->p->color = RED;
                rb = right_rotate(rb,z->p->p);
            }
        }
        else {//same as right and left exchanged
            y = z->p->p->left;
            if (y->color == RED)    {
                z->p->color = BLACK;
                y->color = BLACK;
                z->p->p->color = RED;
                z = z->p->p;
            }
            else {
                if (z == z->p->left) {
                    z= z->p;
                    rb = right_rotate(rb,z);
                }
                z->p->color = BLACK;
                z->p->p->color = RED;
                rb = left_rotate(rb,z->p->p);
            }
        }
    }
    rb->color = BLACK;
    return rb;
}

struct rb_tree* rb_insert(struct rb_tree *rb, int k) {
    struct rb_tree *y = rb->p;
    struct rb_tree *x = rb;
    struct rb_tree *z;
    z= (struct rb_tree *)malloc(sizeof(struct rb_tree));
    z->key = k;
    while (x->key != T_nil) {
        y = x;
        if (k< x->key)
            x = x->left;
        else
            x = x->right;
    }
    z->p = y;
    if (y->key == T_nil)
        rb = z;
    else if (z->key <y->key)
        y->left = z;
    else
        y->right =z;
    z->left = rb->p;
    z->right = rb->p;
    z->color = RED;
    return rb_insert_fixup(rb,z);
}

struct rb_tree* rb_delete_fixup(struct rb_tree *rb, struct rb_tree *x) {
    struct rb_tree *w;
    while ((x !=rb)&&(x->color == BLACK)) {
        if (x == x->p->left) {
            w = x->p->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->p->color = RED;
                left_rotate(rb,x->p);
                w = x->p->right;
            }
            if ((w->left->color == BLACK)&&(w->right->color == BLACK)) {
                w->color = RED;
                x = x->p;
            }
            else if (w->right->color == BLACK) {
                w->left->color = BLACK;
                w->color = RED;
                right_rotate(rb,w);
                w = x->p->right;
            }
            w->color = x->p->color;
            x->p->color = BLACK;
            w->right->color = BLACK;
            left_rotate(rb,x->p);
            x = rb;
        }
        else { //same as right and left exchanged
            w = x->p->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->p->color = RED;
                right_rotate(rb,x->p);
                w = x->p->right;
            }
            if ((w->right->color == BLACK)&&(w->left->color == BLACK)) {
                w->color = RED;
                x = x->p;
            }
            else if (w->left->color == BLACK) {
                w->right->color = BLACK;
                w->color = RED;
                left_rotate(rb,w);
                w = x->p->left;
            }
            w->color = x->p->color;
            x->p->color = BLACK;
            w->left->color = BLACK;
            right_rotate(rb,x->p);
            x = rb;
        }
    }
    x->color = BLACK;
}

struct rb_tree* rb_delete(struct rb_tree *rb, struct rb_tree *z) {
    struct rb_tree *x,*y;
    if ((z->left->key == T_nil) || (z->right->key == T_nil))
        y = z;
    else y = tree_successor(z);
    if (y->left->key != T_nil)
        x = y->left;
    else
        x = y->right;

x->p = y->p;

    if (y->p->key == T_nil)
        rb = x;
    else if (y==x->p->left)
        y->p->left = x;
    else
        y->p->right = x;

    if (y!=x) //copy y's data to z
        z->key = y->key;
    if (y->color == BLACK)
        rb_delete_fixup(rb,x);
    free(y);
    return rb;
}

int main () {
    struct rb_tree *p,*root;
    struct rb_tree tree_nil = {BLACK,T_nil,&tree_nil,&tree_nil,&tree_nil};
    root = &tree_nil;
    root = rb_insert(root,15);
    root = rb_insert(root,5);
    root = rb_insert(root,16);
    root = rb_insert(root,3);
    root = rb_insert(root,12);
    root = rb_insert(root,20);
    root = rb_insert(root,10);
    root = rb_insert(root,13);
    root = rb_insert(root,6);
    root = rb_insert(root,7);
    root = rb_insert(root,18);
    root = rb_insert(root,23);
    rb_walk(root);
    p = rb_search(root,18);
    root = rb_delete(root,p);
    rb_walk(root);
    return 1;
}