紅黑樹是一種二叉搜索樹，每個節(jié)點都有一個額外的屬性：顏色，它可以是紅色或黑色。我們還需要跟蹤每個節(jié)點的父節(jié)點，這樣一棵紅黑樹的節(jié)點結(jié)構(gòu)將是：

結(jié)構(gòu) t_red_black_node {
    枚舉{紅色，黑色}顏色；
    無效*項目；
    結(jié)構(gòu) t_red_black_node *left,
                     *正確的，
                     *父母;
    }

出于討論的目的，終止樹的 NULL 節(jié)點被認(rèn)為是葉子，并被涂成黑色。

紅黑樹的定義

紅黑樹是一種二叉搜索樹，具有以下紅黑特性：

1.每個節(jié)點不是紅色就是黑色。

2.每片葉子(NULL)都是黑色的。

3.如果一個節(jié)點是紅色的，那么它的兩個子節(jié)點都是黑色的。

4.從節(jié)點到后代葉子的每條簡單路徑都包含相同數(shù)量的黑色節(jié)點。

一個基本的紅黑樹

添加了哨兵節(jié)點的基本紅黑樹

紅黑樹算法的實現(xiàn)通常包括哨兵節(jié)點，作為標(biāo)記您已到達葉節(jié)點的便捷方式。它們是屬性 2 的 NULL 黑色節(jié)點。

從但不包括節(jié)點x到葉子的任何路徑上的黑色節(jié)點的數(shù)量稱為節(jié)點的黑色高度，表示為bh(x)。我們可以證明以下引理：

引理

具有n 個內(nèi)部節(jié)點 的紅黑樹的高度最多為 2 log( n +1)。

(有關(guān)證明，請參見 Cormen，第 264 頁)

這說明了為什么紅黑樹是一棵好的搜索樹：它總是可以在O(log n)時間內(nèi)被搜索到。

與堆一樣，紅黑樹的添加和刪除會破壞紅黑屬性，因此我們需要恢復(fù)它。為此，我們需要查看一些對紅黑樹的操作。

旋轉(zhuǎn)

旋轉(zhuǎn)是搜索樹中的局部操作，它保留了按順序遍歷鍵的順序。

請注意，在兩棵樹中，有序遍歷產(chǎn)生：

A x B y C

left_rotate 操作可以被編碼：

left_rotate（樹 T，節(jié)點 x）{
    節(jié)點 y;
    y = x->右；
    /* 將 y 的左子樹變成 x 的右子樹 */
    x->右=y->左；
    如果 ( y->left != NULL )
        y->左->父= x；
    /* y 的新父級是 x 的父級 */
    y->父= x->父；
    /* 設(shè)置父節(jié)點指向 y 而不是 x */
    /* 首先看看我們是否在根目錄 */
    if ( x->parent == NULL ) T->root = y;
    別的
        if ( x == (x->parent)->left )
            /* x 在其父級的左側(cè) */
            x->父->左= y;
        別的
            /* x 必須在右邊 */
            x->父->右=y；
    /* 最后，把 x 放在 y 的左邊 */
    y->左= x；
    x->父母= y;
    }

插入

插入有些復(fù)雜，涉及多種情況。請注意，我們首先使用tree_insert函數(shù)在樹中插入新節(jié)點x，就像我們對任何其他二叉樹所做的那樣。這個新節(jié)點被標(biāo)記為紅色，并且可能破壞了紅黑屬性。主循環(huán)向上移動樹，恢復(fù)紅黑屬性。

rb_insert（樹 T，節(jié)點 x）{
    /* 以通常的方式插入樹中 */
    樹插入（T，x）；
    /* 現(xiàn)在恢復(fù)紅黑屬性 */
    x->顏色=紅色；
    while ( (x != T->root) && (x->parent->colour == red) ) {
       if ( x->parent == x->parent->parent->left ) {
           /* 如果 x 的父級是左，y 是 x 的右“叔叔”?? */
           y = x->父->父->右；
           如果（y->顏色==紅色）{
               /* case 1 - 改變顏色 */
               x->父級->顏色=黑色；
               y->顏色=黑色；
               x->父級->父級->顏色=紅色；
               /* 在樹上移動 x */
               x = x->父級->父級；
               }
           別的 {
               /* y 是一個黑色節(jié)點 */
               if ( x == x->parent->right ) {
                   /* 和 x 在右邊 */
                   /* case 2 - 向上移動 x 并旋轉(zhuǎn) */
                   x = x->父級；
                   左旋轉(zhuǎn)（T，x）；
                   }
               /* 案例 3 */
               x->父級->顏色=黑色；
               x->父級->父級->顏色=紅色；
               right_rotate(T, x->parent->parent);
               }
           }
       別的 {
           /* 左右重復(fù)“if”部分
              交換*/
           }
       }
    /* 將根著色為黑色 */
    T->根->顏色=黑色；
    }

以上就是關(guān)于“二叉搜索樹之紅黑樹的實現(xiàn)”介紹，大家如果對此比較感興趣，不妨來看看簡述數(shù)據(jù)結(jié)構(gòu)中7種樹，里面有更多的相關(guān)知識可以學(xué)習(xí)，相信對大家一定會有所幫助的。