別眨眼網

1。 紅黑樹

1。1 紅黑樹概述

紅黑樹和我們以前學過的AVL樹類似，都是在進行插入和刪除操作時透過特定操作保持二叉查詢樹的平衡，從而獲得較高的查詢效能。不過自從紅黑樹出來後，AVL樹就被放到了博物館裡，據說是紅黑樹有更好的效率，更高的統計效能。這一點在我們瞭解了紅黑樹的實現原理後，就會有更加深切的體會。

紅黑樹和AVL樹的區別在於它使用顏色來標識結點的高度，它所追求的是區域性平衡而不是AVL樹中的非常嚴格的平衡。學過資料結構的人應該都已經領教過AVL樹的複雜，但AVL樹的複雜比起紅黑樹來說簡直是小巫見大巫，紅黑樹才是真正的變態級資料結構。

由於STL中的關聯式容器預設的底層實現都是紅黑樹，因此紅黑樹對於後續學習STL原始碼還是很重要的，有必要掌握紅黑樹的實現原理和原始碼實現。

紅黑樹是AVL樹的變種，紅黑樹透過一些著色法則確保沒有一條路徑會比其它路徑長出兩倍，因而達到接近平衡的目的。所謂紅黑樹，不僅是一個二叉搜尋樹，而且必須滿足一下規則：

1、每個節點不是紅色就是黑色。

2、根節點為黑色。

3、如果節點為紅色，其子節點必須為黑色。

4、任意一個節點到到NULL（樹尾端）的任何路徑，所含之黑色節點數必須相同。

上面的這些約束保證了這個樹大致上是平衡的，這也決定了紅黑樹的插入、刪除、查詢等操作是比較快速的。 根據規則4，新增節點必須為紅色；根據規則3，新增節點之父節點必須為黑色。當新增節點根據二叉搜尋樹的規則到達其插入點時，卻未能符合上述條件時，就必須調整顏色並旋轉樹形，如下圖：

假設我們為上圖分別插入節點3、8、35、75，根據二叉搜尋樹的規則，插入這四個節點後，我們會發現它們都破壞了紅黑樹的規則，因此我們必須調整樹形，也就是旋轉樹形並改變節點的顏色。

1。2 紅黑樹上結點的插入

在討論紅黑樹的插入操作之前必須要明白，任何一個即將插入的新結點的初始顏色都為紅色。這一點很容易理解，因為插入黑點會增加某條路徑上黑結點的數目，從而導致整棵樹黑高度的不平衡。但如果新結點的父結點為紅色時（如下圖所示），將會違反紅黑樹的性質：一條路徑上不能出現相鄰的兩個紅色結點。這時就需要透過一系列操作來使紅黑樹保持平衡。

為了清楚地表示插入操作以下在結點中使用“新”字表示一個新插入的結點；使用“父”字表示新插入點的父結點；使用“叔”字表示“父”結點的兄弟結點；使用“祖”字表示“父”結點的父結點。插入操作分為以下幾種情況：

1。2。1 黑父

如下圖所示，如果新節點的父結點為黑色結點，那麼插入一個紅點將不會影響紅黑樹的平衡，此時插入操作完成。紅黑樹比AVL樹優秀的地方之一在於黑父的情況比較常見，從而使紅黑樹需要旋轉的機率相對AVL樹來說會少一些。

1。2。2 紅父

如果新節點的父結點為紅色，這時就需要進行一系列操作以保證整棵樹紅黑性質。如下圖所示，由於父結點為紅色，此時可以判定，祖父結點必定為黑色。這時需要根據叔父結點的顏色來決定做什麼樣的操作。青色結點表示顏色未知。由於有可能需要根結點到新點的路徑上進行多次旋轉操作，而每次進行不平衡判斷的起始點（我們可將其視為新點）都不一樣。所以我們在此使用一個藍色箭頭指向這個起始點，並稱之為判定點。

1。2。2。1 紅叔

當叔父結點為紅色時，如下圖所示，無需進行旋轉操作，只要將父和叔結點變為黑色，將祖父結點變為紅色即可。但由於祖父結點的父結點有可能為紅色，從而違反紅黑樹性質。此時必須將祖父結點作為新的判定點繼續向上（迭代）進行平衡操作。

需要注意的是，無論“父節點”在“叔節點”的左邊還是右邊，無論“新節點”是“父節點”的左孩子還是右孩子，它們的操作都是完全一樣的（其實這種情況包括4種，只需調整顏色，不需要旋轉樹形）。

1。2。2。2 黑叔

當叔父結點為黑色時，需要進行旋轉，以下圖示了所有的旋轉可能：

Case 1：

Case 2：

Case 3：

Case 4：

可以觀察到，當旋轉完成後，新的旋轉根全部為黑色，此時不需要再向上回溯進行平衡操作，插入操作完成。需要注意，上面四張圖的“叔”、“1”、“2”、“3”結點有可能為黑哨兵結點。

其實紅黑樹的插入操作不是很難，甚至比AVL樹的插入操作還更簡單些。紅黑樹的插入操作原始碼如下：

// 元素插入操作  insert_unique（）// 插入新值：節點鍵值不允許重複，若重複則插入無效// 注意，返回值是個pair，第一個元素是個紅黑樹迭代器，指向新增節點// 第二個元素表示插入成功與否templatepair：：iterator ， bool>rb_tree：：insert_unique（const Value &v）{    rb_tree_node* y = header；    // 根節點root的父節點    rb_tree_node* x = root（）；    // 從根節點開始    bool comp = true；    while（x ！= 0）    {        y = x；        comp = key_compare（KeyOfValue（）（v） ， key（x））；    // v鍵值小於目前節點之鍵值？        x = comp ？ left（x） ： right（x）；   // 遇“大”則往左，遇“小於或等於”則往右    }    // 離開while迴圈之後，y所指即插入點之父節點（此時的它必為葉節點）    iterator j = iterator（y）；     // 令迭代器j指向插入點之父節點y    if（comp）     // 如果離開while迴圈時comp為真（表示遇“大”，將插入於左側）    {        if（j == begin（））    // 如果插入點之父節點為最左節點            return pair（_insert（x ， y ， z） ， true）；        else     // 否則（插入點之父節點不為最左節點）            ——j；   // 調整j，回頭準備測試    }    if（key_compare（key（j。node） ， KeyOfValue（）（v） ））        // 新鍵值不與既有節點之鍵值重複，於是以下執行安插操作        return pair（_insert（x ， y ， z） ， true）；    // 以上，x為新值插入點，y為插入點之父節點，v為新值     // 進行至此，表示新值一定與樹中鍵值重複，那麼就不應該插入新值    return pair（j ， false）；} // 真正地插入執行程式 _insert（）templatetypename：：_insert（base_ptr x_ ， base_ptr y_ ， const Value &v）{    // 引數x_ 為新值插入點，引數y_為插入點之父節點，引數v為新值    link_type x = （link_type） x_；    link_type y = （link_type） y_；    link_type z；     // key_compare 是鍵值大小比較準則。應該會是個function object    if（y == header || x ！= 0 || key_compare（KeyOfValue（）（v） ， key（y） ））    {        z = create_node（v）；    // 產生一個新節點        left（y） = z；           // 這使得當y即為header時，leftmost（） = z        if（y == header）        {            root（） = z；            rightmost（） = z；        }        else if（y == leftmost（））     // 如果y為最左節點            leftmost（） = z；          // 維護leftmost（），使它永遠指向最左節點    }    else    {        z = create_node（v）；        // 產生一個新節點        right（y） = z；              // 令新節點成為插入點之父節點y的右子節點        if（y == rightmost（））            rightmost（） = z；       // 維護rightmost（），使它永遠指向最右節點    }    parent（z） = y；      // 設定新節點的父節點    left（z） = 0；        // 設定新節點的左子節點    right（z） = 0；       // 設定新節點的右子節點    // 新節點的顏色將在_rb_tree_rebalance（）設定（並調整）    _rb_tree_rebalance（z ， header->parent）；      // 引數一為新增節點，引數二為根節點root    ++node_count；       // 節點數累加    return iterator（z）；  // 返回一個迭代器，指向新增節點}  // 全域性函式// 重新令樹形平衡（改變顏色及旋轉樹形）// 引數一為新增節點，引數二為根節點rootinline void _rb_tree_rebalance（_rb_tree_node_base* x ， _rb_tree_node_base*& root）{    x->color = _rb_tree_red；    //新節點必為紅    while（x ！= root && x->parent->color == _rb_tree_red）    // 父節點為紅    {        if（x->parent == x->parent->parent->left）      // 父節點為祖父節點之左子節點        {            _rb_tree_node_base* y = x->parent->parent->right；    // 令y為伯父節點            if（y && y->color == _rb_tree_red）    // 伯父節點存在，且為紅            {                x->parent->color = _rb_tree_black；           // 更改父節點為黑色                y->color = _rb_tree_black；                   // 更改伯父節點為黑色                x->parent->parent->color = _rb_tree_red；     // 更改祖父節點為紅色                x = x->parent->parent；            }            else    // 無伯父節點，或伯父節點為黑色            {                if（x == x->parent->right）   // 如果新節點為父節點之右子節點                {                    x = x->parent；                    _rb_tree_rotate_left（x ， root）；    // 第一個引數為左旋點                }                x->parent->color = _rb_tree_black；     // 改變顏色                x->parent->parent->color = _rb_tree_red；                _rb_tree_rotate_right（x->parent->parent ， root）；    // 第一個引數為右旋點            }        }        else          // 父節點為祖父節點之右子節點        {            _rb_tree_node_base* y = x->parent->parent->left；    // 令y為伯父節點            if（y && y->color == _rb_tree_red）    // 有伯父節點，且為紅            {                x->parent->color = _rb_tree_black；           // 更改父節點為黑色                y->color = _rb_tree_black；                   // 更改伯父節點為黑色                x->parent->parent->color = _rb_tree_red；     // 更改祖父節點為紅色                x = x->parent->parent；          // 準備繼續往上層檢查            }            else    // 無伯父節點，或伯父節點為黑色            {                if（x == x->parent->left）        // 如果新節點為父節點之左子節點                {                    x = x->parent；                    _rb_tree_rotate_right（x ， root）；    // 第一個引數為右旋點                }                x->parent->color = _rb_tree_black；     // 改變顏色                x->parent->parent->color = _rb_tree_red；                _rb_tree_rotate_left（x->parent->parent ， root）；    // 第一個引數為左旋點            }        }    }//while    root->color = _rb_tree_black；    // 根節點永遠為黑色}  // 左旋函式inline void _rb_tree_rotate_left（_rb_tree_node_base* x ， _rb_tree_node_base*& root）{    // x 為旋轉點    _rb_tree_node_base* y = x->right；          // 令y為旋轉點的右子節點    x->right = y->left；    if（y->left ！= 0）        y->left->parent = x；           // 別忘了回馬槍設定父節點    y->parent = x->parent；     // 令y完全頂替x的地位（必須將x對其父節點的關係完全接收過來）    if（x == root）    // x為根節點        root = y；    else if（x == x->parent->left）         // x為其父節點的左子節點        x->parent->left = y；    else                                  // x為其父節點的右子節點        x->parent->right = y；    y->left = x；    x->parent = y；}  // 右旋函式inline void _rb_tree_rotate_right（_rb_tree_node_base* x ， _rb_tree_node_base*& root）{    // x 為旋轉點    _rb_tree_node_base* y = x->left；          // 令y為旋轉點的左子節點    x->left = y->right；    if（y->right ！= 0）        y->right->parent = x；           // 別忘了回馬槍設定父節點    y->parent = x->parent；     // 令y完全頂替x的地位（必須將x對其父節點的關係完全接收過來）    if（x == root）        root = y；    else if（x == x->parent->right）         // x為其父節點的右子節點        x->parent->right = y；    else                                  // x為其父節點的左子節點        x->parent->left = y；    y->right = x；    x->parent = y；}

2。 紅黑樹

Linux核心紅黑樹的演算法都定義在

linux-2。6。38。8/include/linux/rbtree。h和linux-2。6。38。8/lib/rbtree。c兩個檔案中。

2。1 結構體

紅黑樹和我們以

struct rb_node{    unsigned long  rb_parent_color；#define RB_RED      0#define RB_BLACK    1    struct rb_node *rb_right；    struct rb_node *rb_left；} __attribute__（（aligned（sizeof（long））））；

這裡的巧妙之處是使用成員rb_parent_color同時儲存兩種資料，一是其雙親結點的地址，另一是此結點的著色。__attribute__（（aligned（sizeof（long））））屬性保證了紅黑樹中的每個結點的首地址都是32位對齊的（在32位機上），也就是說每個結點首地址的bit［1］和bit［0］都是0，因此就可以使用bit［0］來儲存結點的顏色屬性而不干擾到其雙親結點首地址的儲存。

操作rb_parent_color的函式：

#define rb_parent（r）   （（struct rb_node *）（（r）->rb_parent_color & ~3））  //獲得其雙親結點的首地址#define rb_color（r）   （（r）->rb_parent_color & 1） //獲得顏色屬性#define rb_is_red（r）   （！rb_color（r））   //判斷顏色屬性是否為紅#define rb_is_black（r） rb_color（r） //判斷顏色屬性是否為黑#define rb_set_red（r）  do { （r）->rb_parent_color &= ~1； } while （0）  //設定紅色屬性#define rb_set_black（r）  do { （r）->rb_parent_color |= 1； } while （0） //設定黑色屬性 static inline void rb_set_parent（struct rb_node *rb， struct rb_node *p）  //設定其雙親結點首地址的函式{    rb->rb_parent_color = （rb->rb_parent_color & 3） | （unsigned long）p；}static inline void rb_set_color（struct rb_node *rb， int color） //設定結點顏色屬性的函式{    rb->rb_parent_color = （rb->rb_parent_color & ~1） | color；}

初始化新結點：

static inline void rb_link_node（struct rb_node * node， struct rb_node * parent，                struct rb_node ** rb_link）{    node->rb_parent_color = （unsigned long ）parent；   //設定其雙親結點的首地址（根結點的雙親結點為NULL），且顏色屬性設為黑色    node->rb_left = node->rb_right = NULL；   //初始化新結點的左右子樹     *rb_link = node；  //指向新結點}

指向紅黑樹根結點的指標：

struct rb_root{    struct rb_node *rb_node；}；  #define RB_ROOT （struct rb_root） { NULL， }  //初始化指向紅黑樹根結點的指標#define rb_entry（ptr， type， member） container_of（ptr， type， member） //用來獲得包含struct rb_node的結構體的首地址 #define RB_EMPTY_ROOT（root） （（root）->rb_node == NULL） //判斷樹是否為空#define RB_EMPTY_NODE（node） （rb_parent（node） == node）  //判斷node的雙親結點是否為自身#define RB_CLEAR_NODE（node） （rb_set_parent（node， node）） //設定雙親結點為自身

2。2 插入

首先像二叉查詢樹一樣插入一個新結點，然後根據情況作出相應的調整，以使其滿足紅黑樹的顏色屬性（其實質是維持紅黑樹的平衡）。

函式rb_insert_color使用while迴圈不斷地判斷雙親結點是否存在，且顏色屬性為紅色。

若判斷條件為真，則分成兩部分執行後續的操作：

（1）、當雙親結點是祖父結點左子樹的根時，則：

a、存在叔父結點，且顏色屬性為紅色。

b、當node是其雙親結點右子樹的根時，則左旋，然後執行第c步。

c、當node是其雙親結點左子樹的根時。

（2）當雙親結點是祖父結點右子樹的根時的操作與第（1）步大致相同，這裡略過不談。

若為假，則始終設定根結點的顏色屬性為黑色。

void rb_insert_color（struct rb_node *node， struct rb_root *root）{    struct rb_node *parent， *gparent；     while （（parent = rb_parent（node）） && rb_is_red（parent）） //雙親結點不為NULL，且顏色屬性為紅色    {        gparent = rb_parent（parent）； //獲得祖父結點         if （parent == gparent->rb_left） //雙親結點是祖父結點左子樹的根        {            {                register struct rb_node *uncle = gparent->rb_right； //獲得叔父結點                if （uncle && rb_is_red（uncle）） //叔父結點存在，且顏色屬性為紅色                {                    rb_set_black（uncle）； //設定叔父結點為黑色                    rb_set_black（parent）； //設定雙親結點為黑色                    rb_set_red（gparent）； //設定祖父結點為紅色                    node = gparent；  //node指向祖父結點                     continue； //繼續下一個while迴圈                }            }             if （parent->rb_right == node）  //當node是其雙親結點右子樹的根時            {                register struct rb_node *tmp；                __rb_rotate_left（parent， root）； //左旋                tmp = parent；  //調整parent和node指標的指向                parent = node；                node = tmp；            }             rb_set_black（parent）； //設定雙親結點為黑色            rb_set_red（gparent）； //設定祖父結點為紅色            __rb_rotate_right（gparent， root）； //右旋        } else { // ！（parent == gparent->rb_left）            {                register struct rb_node *uncle = gparent->rb_left；                if （uncle && rb_is_red（uncle））                {                    rb_set_black（uncle）；                    rb_set_black（parent）；                    rb_set_red（gparent）；                    node = gparent；                    continue；                }            }             if （parent->rb_left == node）            {                register struct rb_node *tmp；                __rb_rotate_right（parent， root）；                tmp = parent；                parent = node；                node = tmp；            }             rb_set_black（parent）；            rb_set_red（gparent）；            __rb_rotate_left（gparent， root）；        } //end if （parent == gparent->rb_left）    } //end while （（parent = rb_parent（node）） && rb_is_red（parent））     rb_set_black（root->rb_node）；}

2。3 刪除

像二叉查詢樹的刪除操作一樣，首先需要找到所需刪除的結點，然後根據該結點左右子樹的有無分為三種情形：

若node結點的顏色屬性為黑色，則需要呼叫__rb_erase_color函式來進行調整。

void rb_erase（struct rb_node *node， struct rb_root *root）{    struct rb_node *child， *parent；    int color；     if （！node->rb_left） //刪除結點無左子樹        child = node->rb_right；    else if （！node->rb_right） //刪除結點無右子樹        child = node->rb_left；    else //左右子樹都有    {        struct rb_node *old = node， *left；         node = node->rb_right；        while （（left = node->rb_left） ！= NULL）            node = left；         if （rb_parent（old）） {            if （rb_parent（old）->rb_left == old）                rb_parent（old）->rb_left = node；            else                rb_parent（old）->rb_right = node；        } else            root->rb_node = node；         child = node->rb_right；        parent = rb_parent（node）；        color = rb_color（node）；         if （parent == old） {            parent = node；        } else {            if （child）                rb_set_parent（child， parent）；            parent->rb_left = child；             node->rb_right = old->rb_right；            rb_set_parent（old->rb_right， node）；        }         node->rb_parent_color = old->rb_parent_color；        node->rb_left = old->rb_left；        rb_set_parent（old->rb_left， node）；         goto color；    }  //end else     parent = rb_parent（node）； //獲得刪除結點的雙親結點    color = rb_color（node）； //獲取刪除結點的顏色屬性     if （child）        rb_set_parent（child， parent）；    if （parent）    {        if （parent->rb_left == node）            parent->rb_left = child；        else            parent->rb_right = child；    }    else        root->rb_node = child；  color：    if （color == RB_BLACK） //如果刪除結點的顏色屬性為黑色，則需呼叫__rb_erase_color函式來進行調整        __rb_erase_color（child， parent， root）；}

2。4 遍歷

rb_first和rb_next函式可組成中序遍歷，即以升序遍歷紅黑樹中的所有結點。

struct rb_node *rb_first（const struct rb_root *root）{    struct rb_node  *n；     n = root->rb_node；    if （！n）        return NULL；    while （n->rb_left）        n = n->rb_left；    return n；} struct rb_node *rb_next（const struct rb_node *node）{    struct rb_node *parent；     if （rb_parent（node） == node）        return NULL；     /* If we have a right-hand child， go down and then left as far       as we can。 */    if （node->rb_right） {        node = node->rb_right；         while （node->rb_left）            node=node->rb_left；        return （struct rb_node *）node；    }     /* No right-hand children。  Everything down and left is       smaller than us， so any ‘next’ node must be in the general       direction of our parent。 Go up the tree； any time the       ancestor is a right-hand child of its parent， keep going       up。 First time it‘s a left-hand child of its parent， said       parent is our ’next‘ node。 */    while （（parent = rb_parent（node）） && node == parent->rb_right）        node = parent；     return parent；}