數(shù)據結構

昵稱23617 2007-04-03

展開全文

紅黑樹理論及實現(xiàn)

上一篇:DFS非遞歸實現(xiàn)方式下一篇:AVL樹的C語言實現(xiàn)

作者:dzf 閱讀次數(shù):253 時間:2006-12-3 13:41:25 數(shù)據結構

紅黑樹

二叉樹在平衡時或者葉子結點到根結點的高度在一定的范圍內時工作起來是最有效的。紅黑樹算法是平衡樹的一種算法。這個名字就是由于樹的每個結點都被著上了紅色或者黑色，結點所著的顏色被用來檢測樹的平衡性。在對結點插入和刪除的操作中，可能會被旋轉來保持樹的平衡性。平均和最壞情況插入，刪除，查找時間都是 O (lg n)。詳細內容請參考 Cormen [2001]。

理論

一個紅黑樹是一顆二叉查找樹，具有下列的屬性:

1. 所有的結點都被著色為紅色或者是黑色。

2. 每一個葉子結點都是空結點，并且被著為黑色。

3. 如果父結點是紅色的，那么兩個子結點都是黑色的。

4. 結點到其子孫結點的每條簡單路徑上都包含相同數(shù)目的黑色結點。

5. 根結點永遠是黑色的。

從根結點到葉結點的黑色結點數(shù)被稱為樹的黑色高度。前面關于紅黑樹的性質保證了從根結點到葉結點的路徑長度不會超過任何其他路徑的兩倍。

我們來看一下為什么這個結論是正確的。考慮一顆黑色高度為3 得紅黑樹，從根結點到葉結點的最短路徑長度是2(黑-黑-黑)，最長路徑為4(黑-紅-黑-紅-黑)。由于第4條性質，不可能在最長路徑中加入更多的黑色結點，因為性質3規(guī)定紅色結點的子結點必須是黑色的，因此在同一簡單路徑中不允許有兩個連續(xù)的紅色結點。因此，我們能夠建立的最長路徑將是一個紅黑交替的路徑。

概括起來：對于給定的黑色高度為n的紅黑樹，從根結點到葉結點的簡單路徑的最短長度為n-1，最大長度為2(n-1)。所有對樹的操作必須保持上面列出的屬性。特別要指出的是，插入和刪除樹的結點的操作必須遵循這些原則。

插入

要插入結點，搜索這棵樹，找到插入點并添加結點。新的結點替代一個已經存在的在樹底部的空結點，并且將擁有兩個作為子結點的空結點，在簡單的實現(xiàn)中，空結點就是就是一個指向被染為黑色的監(jiān)視結點的指針，提醒C語言程序員 — 這不是一個空指針！插入新的結點之后，新的結點被染為紅色。而后，結點的父結點會被測試看看紅黑樹的屬性有沒有被保留下來。如果需要，做一些調整已適應平衡樹的需求。

當插入一個紅色結點以及他帶的兩個空的子結點時符合性質4，我們還必須確保紅色結點的兩個子結點都是黑色的(性質3)。盡管如此，新結點的子結點是黑色時，插入紅色的子結點將是違反屬性的。這時存在兩種要考慮的情況。

紅色父結點，父結點的紅色兄弟結點

圖3-6 描述了一個紅-紅錯誤。結點 X 是新插入的結點, 父結點和父親兄弟結點都被著為紅色。一個簡單的著色就可以解決這個紅-紅錯誤。在重著色后必須檢查祖父結點 (結點 B )是否合法，因為它的父結點也可能是紅色的，我們不允許連續(xù)出現(xiàn)兩個紅色結點。這樣會產生使紅色結點上移的效果。結束時根結點應當是黑色的，如果它原先是紅色的，則紅黑樹的黑色高度將增1。

圖 3-6: 插入 -紅色父結點，父結點的紅色兄弟結點
紅色父結點,父結點的黑色兄弟結點
圖 3-7 描述了一個紅-紅錯誤，父親的兄弟結點是黑色的。如果我們試圖給結點重新著色,將結點 A 著成黑色, 這棵樹就不平衡了因為我們增加了左支的黑色高度而沒有同時增加右支的黑色高度。如果我們同時將結點B改成紅色, 兩支的黑色高度減小，而且樹還是不平衡。如果我們將節(jié)點 A 染成黑色，節(jié)點C染成紅色。情況更為糟糕。因為我們增加了左支的黑色高度，但是減小了右支的黑色高度。為了解決這個問題，我們將要旋轉并且重新為結點作如下的著色。在這點上，這個算法就結束了，因為子樹的頂點 (節(jié)點A)被著為黑色，這樣就沒有紅-紅沖突了。

圖 3-7: 插入 - 紅色父結點,父結點的黑色兄弟結點
結束
為了插入一個結點，我們可能要對結點進行重新著色或者旋轉來確保紅黑樹的屬性。如果完成了旋轉，作了簡單的重著色，我們看到的是紅色的結點在子樹的頂部，必需遍歷這棵樹，重復這個過程以確保黑色高度屬性的保持。最壞的情況是，我們會一直執(zhí)行到根結點。插入時間為O(lg n).刪除的技術方法和時間與此類似。

// C語言實現(xiàn)

// red-black tree

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

//////////////////////
// supplied by user //
//////////////////////

typedef int KeyType;            // type of key

typedef struct {                // value related to key
    int stuff;
} ValType;

// how to compare keys
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)

/////////////////////////////////////
// implementation independent code //
/////////////////////////////////////

typedef enum {
    RBT_STATUS_OK,
    RBT_STATUS_MEM_EXHAUSTED,
    RBT_STATUS_DUPLICATE_KEY,
    RBT_STATUS_KEY_NOT_FOUND
} RbtStatus;

typedef enum { BLACK, RED } nodeColor;

typedef struct NodeTag {
    struct NodeTag *left;       // left child
    struct NodeTag *right;      // right child
    struct NodeTag *parent;     // parent
    nodeColor color;            // node color (BLACK, RED)
    KeyType key;                // key used for searching
    ValType val;                // data related to key
} NodeType;

#define SENTINEL &sentinel      // all leafs are sentinels
static NodeType sentinel = { SENTINEL, SENTINEL, 0, BLACK, 0};

static NodeType *root = SENTINEL; // root of red-black tree

static void rotateLeft(NodeType *x) {

    // rotate node x to left

    NodeType *y = x->right;

    // establish x->right link
    x->right = y->left;
    if (y->left != SENTINEL) y->left->parent = x;

    // establish y->parent link
    if (y != SENTINEL) y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->left)
            x->parent->left = y;
        else
            x->parent->right = y;
    } else {
        root = y;
    }

    // link x and y
    y->left = x;
    if (x != SENTINEL) x->parent = y;
}

static void rotateRight(NodeType *x) {

    // rotate node x to right

    NodeType *y = x->left;

    // establish x->left link
    x->left = y->right;
    if (y->right != SENTINEL) y->right->parent = x;

    // establish y->parent link
    if (y != SENTINEL) y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->right)
            x->parent->right = y;
        else
            x->parent->left = y;
    } else {
        root = y;
    }

    // link x and y
    y->right = x;
    if (x != SENTINEL) x->parent = y;
}

static void insertFixup(NodeType *x) {

    // maintain red-black tree balance
    // after inserting node x

    // check red-black properties
    while (x != root && x->parent->color == RED) {
        // we have a violation
        if (x->parent == x->parent->parent->left) {
            NodeType *y = x->parent->parent->right;
            if (y->color == RED) {

                // uncle is RED
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {

                // uncle is BLACK
                if (x == x->parent->right) {
                    // make x a left child
                    x = x->parent;
                    rotateLeft(x);
                }

                // recolor and rotate
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateRight(x->parent->parent);
            }
        } else {

            // mirror image of above code
            NodeType *y = x->parent->parent->left;
            if (y->color == RED) {

                // uncle is RED
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {

                // uncle is BLACK
                if (x == x->parent->left) {
                    x = x->parent;
                    rotateRight(x);
                }
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateLeft(x->parent->parent);
            }
        }
    }
    root->color = BLACK;
}

// insert new node (no duplicates allowed)
RbtStatus rbtInsert(KeyType key, ValType val) {
    NodeType *current, *parent, *x;

    // allocate node for data and insert in tree

    // find future parent
    current = root;
    parent = 0;
    while (current != SENTINEL) {
        if (compEQ(key, current->key)) 
            return RBT_STATUS_DUPLICATE_KEY;
        parent = current;
        current = compLT(key, current->key) ?
            current->left : current->right;
    }

    // setup new node
    if ((x = malloc (sizeof(*x))) == 0)
        return RBT_STATUS_MEM_EXHAUSTED;
    x->parent = parent;
    x->left = SENTINEL;
    x->right = SENTINEL;
    x->color = RED;
    x->key = key;
    x->val = val;

    // insert node in tree
    if(parent) {
        if(compLT(key, parent->key))
            parent->left = x;
        else
            parent->right = x;
    } else {
        root = x;
    }

    insertFixup(x);

    return RBT_STATUS_OK;
}

static void deleteFixup(NodeType *x) {

    // maintain red-black tree balance
    // after deleting node x

    while (x != root && x->color == BLACK) {
        if (x == x->parent->left) {
            NodeType *w = x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rotateLeft (x->parent);
                w = x->parent->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    rotateRight (w);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                rotateLeft (x->parent);
                x = root;
            }
        } else {
            NodeType *w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rotateRight (x->parent);
                w = x->parent->left;
            }
            if (w->right->color == BLACK && w->left->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    rotateLeft (w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rotateRight (x->parent);
                x = root;
            }
        }
    }
    x->color = BLACK;
}

// delete node
RbtStatus rbtErase(NodeType * z) {
    NodeType *x, *y;

    if (z->left == SENTINEL || z->right == SENTINEL) {
        // y has a SENTINEL node as a child
        y = z;
    } else {
        // find tree successor with a SENTINEL node as a child
        y = z->right;
        while (y->left != SENTINEL) y = y->left;
    }

    // x is y‘s only child
    if (y->left != SENTINEL)
        x = y->left;
    else
        x = y->right;

    // remove y from the parent chain
    x->parent = y->parent;
    if (y->parent)
        if (y == y->parent->left)
            y->parent->left = x;
        else
            y->parent->right = x;
    else
        root = x;

    if (y != z) {
        z->key = y->key;
        z->val = y->val;
    }


    if (y->color == BLACK)
        deleteFixup (x);

    free (y);

    return RBT_STATUS_OK;
}

// find key
NodeType *rbtFind(KeyType key) {
    NodeType *current;
    current = root;
    while(current != SENTINEL) {
        if(compEQ(key, current->key)) {
            return current;
        } else {
            current = compLT (key, current->key) ?
                current->left : current->right;
        }
    }
    return NULL;
}

// in-order walk of tree
void rbtInorder(NodeType *p, void (callback)(NodeType *)) {
    if (p == SENTINEL) return;
    rbtInorder(p->left, callback);
    callback(p);
    rbtInorder(p->right, callback);
}

// delete nodes depth-first
void rbtDelete(NodeType *p) {
    if (p == SENTINEL) return;
    rbtDelete(p->left);
    rbtDelete(p->right);
    free(p);
}

void displayNode(NodeType *p) {
    printf("%d %d\n", p->key, p->val.stuff);
}

int main(int argc, char **argv) {
    int maxnum, ct;
    KeyType key;
    RbtStatus status;

    // command-line:
    //
    //   rbt 2000
    //      process 2000 records

    NodeType *p;

    maxnum = atoi(argv[1]);

    printf("maxnum = %d\n", maxnum);
    for (ct = maxnum; ct; ct--) {
        key = rand() % 90 + 1;
        if ((p = rbtFind(key)) != NULL) {
            if (p->val.stuff != 10*key) printf("fail val\n");
            status = rbtErase(p);
            if (status) printf("fail: status = %d\n", status);
        } else {
            ValType val;
            val.stuff = 10*key;
            status = rbtInsert(key, val);
            if (status) printf("fail: status = %d\n", status);
        }
    }

    // output nodes in order
    rbtInorder(root, displayNode);

    rbtDelete(root);

    return 0;
}
 C語言實現(xiàn)
            一個用 ANSI-C 實現(xiàn)的紅黑樹包含在這里。 Typedefs  recType ,  keyType , 以及  compLT  和 compEQ  應當改變以反映在樹中的數(shù)據存儲。每一個結點都由 left ,  right , 和  parent  指針組成。指出每個子結點和父結點。結點的顏色存儲在 color 中, 或者是  RED 或者是  BLACK . 所有的椰子結點都是一個監(jiān)視結點。
            函數(shù)  insert  分配了一個新的結點并且將這個結點插入樹當中。而后，它調用 insertFixup 來確保紅黑樹屬性的維持  erase  從樹中刪除
            個結點，為了維護紅黑樹的屬性,  deleteFixup  會被調用。函數(shù) find 查找樹中的一個特殊值