原文地址：http://imlazy.ycool.com/post.1104022.html

（閱讀本文之前請(qǐng)先了解二叉搜索樹）

紅黑樹（Red-Black Tree）

紅黑樹（Red-Black Tree）是二叉搜索樹（Binary Search Tree）的一種改進(jìn)。我們知道二叉搜索樹在最壞的情況下可能會(huì)變成一個(gè)鏈表（當(dāng)所有節(jié)點(diǎn)按從小到大的順序依次插入后）。而紅黑樹在每一次插入或刪除節(jié)點(diǎn)之后都會(huì)花O（log N）的時(shí)間來對(duì)樹的結(jié)構(gòu)作修改，以保持樹的平衡。也就是說，紅黑樹的查找方法與二叉搜索樹完全一樣；插入和刪除節(jié)點(diǎn)的的方法前半部分節(jié)與二叉搜索樹完全一樣，而后半部分添加了一些修改樹的結(jié)構(gòu)的操作。

紅黑樹的每個(gè)節(jié)點(diǎn)上的屬性除了有一個(gè)key、3個(gè)指針：parent、lchild、rchild以外，還多了一個(gè)屬性：color。它只能是兩種顏色：紅或黑。而紅黑樹除了具有二叉搜索樹的所有性質(zhì)之外，還具有以下4點(diǎn)性質(zhì)：（為什么只要這些性質(zhì)就能解決這個(gè)問題，其實(shí)還是一個(gè)問題）

1. 根節(jié)點(diǎn)是黑色的。

2. 空節(jié)點(diǎn)是黑色的（紅黑樹中，根節(jié)點(diǎn)的parent以及所有葉節(jié)點(diǎn)lchild、rchild都不指向NULL，而是指向一個(gè)定義好的空節(jié)點(diǎn)）。

3. 紅色節(jié)點(diǎn)的父、左子、右子節(jié)點(diǎn)都是黑色。

4. 在任何一棵子樹中，每一條從根節(jié)點(diǎn)向下走到空節(jié)點(diǎn)的路徑上包含的黑色節(jié)點(diǎn)數(shù)量都相同。
    如下圖就是一棵紅黑樹：

有了這幾條規(guī)則，就可以保證整棵樹的平衡，也就等于保證了搜索的時(shí)間為O（log N）。

但是在插入、刪除節(jié)點(diǎn)后，就有可能破壞了紅黑樹的性質(zhì)。所以我們要做一些操作來把整棵樹修補(bǔ)好。下面我就來介紹一下。

首先有一個(gè)預(yù)備知識(shí)，那就是節(jié)點(diǎn)的Left-Rotate和Right-Rotate操作。所謂Left-Rotate(x)就是把節(jié)點(diǎn)x向左下方向移動(dòng)一格，然后讓x原來的右子節(jié)點(diǎn)代替它的位置。而Right-Rotate當(dāng)然就是把Left-Rotate左、右互反一下。如下圖：

注意，Left-Rotate(x)后，x的右子樹變成了原來y的左子樹，Right-Rotate反之。思考一下，這樣一次變換后，仍然滿足二叉搜索樹的性質(zhì)（中序遍歷并沒有改變）。在紅黑樹的插入、刪除中，要用到很多Left-Rotate和Right-Rotate操作。

//把一個(gè)節(jié)點(diǎn)向左下方移一格，并讓他原來的右子節(jié)點(diǎn)代替它的位置。
   void leftRotate(RBTNode* node)

 {
        RBTNode* right = node->rchild;
        node->rchild = right->lchild;
        node->rcount = right->lcount;
        node->rchild->parent = node;
        right->parent = node->parent;
        if (right->parent == m_null) {
            m_root = right;
        }
        else if (node == node->parent->lchild) {
            node->parent->lchild = right;
        }
        else {
            node->parent->rchild = right;
        }
        right->lchild = node;
        right->lcount += node->lcount + 1;
        node->parent = right;
    }

    //把一個(gè)節(jié)點(diǎn)向右下方移一格，并讓他原來的左子節(jié)點(diǎn)代替它的位置。
    inline void rightRotate(RBTNode* node) {
        RBTNode* left = node->lchild;
        node->lchild = left->rchild;
        node->lcount = left->rcount;
        node->lchild->parent = node;
        left->parent = node->parent;
        if (left->parent == m_null) {
            m_root = left;
        }
        else if (node == node->parent->lchild) {
            node->parent->lchild = left;
        }
        else {
            node->parent->rchild = left;
        }
        left->rchild = node;
        left->rcount += node->rcount + 1;
        node->parent = left;
    }

 

一、 插入

插入首先是按部就班二叉搜索樹的插入步驟，把新節(jié)點(diǎn)z插入到某一個(gè)葉節(jié)點(diǎn)的位置上。
    接下來把z的顏色設(shè)成紅色。為什么？還記得紅黑樹的性質(zhì)嗎，從根節(jié)點(diǎn)向下到空節(jié)點(diǎn)的每一條路徑上的黑色節(jié)點(diǎn)數(shù)要相同。如果新插入的是黑色節(jié)點(diǎn)，那么它所在的路徑上就多出了一個(gè)黑色的節(jié)點(diǎn)了。所以新插入的節(jié)點(diǎn)一定要設(shè)成紅色。但是這樣可能又有一個(gè)矛盾，如果z的父節(jié)點(diǎn)也是紅色，怎么辦，前面說過紅色節(jié)點(diǎn)的子節(jié)點(diǎn)必須是黑色。因此我們要執(zhí)行下面一個(gè)迭代的過程，稱為Insert-Fixup，來修補(bǔ)這棵紅黑樹。

在Insert-Fixup中，每一次迭代的開始，指針z一定都指向一個(gè)紅色的節(jié)點(diǎn)。如果z->parent是黑色，那我們就大功告成了；如果z->parent是紅色，顯然這就違返了紅黑的樹性質(zhì)，那么我們要想辦法把z或者z->parent變成黑色，但這要建立在不破壞紅黑樹的其他性質(zhì)的基礎(chǔ)上。

這里再引入兩個(gè)指針：grandfather，指向z->parent->parent，也就是z的爺爺(顯然由于z->parent為紅色，grandfather一定是黑色)；uncle，指向grandfather除了z->parent之外的另一個(gè)子節(jié)點(diǎn)，也就是z的父親的兄弟，所以叫uncle。

（為了說話方便，我們這里都假設(shè)z->parent是grandfather的左子節(jié)點(diǎn)，而uncle是grandfather的右子節(jié)點(diǎn)。如果遇到的實(shí)際情況不是這樣，那也只要把所有操作中的左、右互反就可以了。）

在每一次迭代中，我們可能遇到以下三種情況。

Case 1. uncle也是紅色。這時(shí)只要把z->parent和uncle都設(shè)成黑色，并把grandfather設(shè)成紅色。這樣仍然確保了每一條路徑上的黑色節(jié)點(diǎn)數(shù)不變。然后把z指向grandfather，并開始新一輪的迭代。如下圖：

注1：我們可以看出左邊的圖，各條路徑包含黑顏色的數(shù)目是正確的，只是顏色不對(duì)而已，我們把它分成兩邊來看，即到節(jié)點(diǎn)D應(yīng)該包含N+1個(gè)黑色節(jié)點(diǎn)，其中這個(gè)1是C，而N是C以上的黑色節(jié)點(diǎn)個(gè)數(shù)。同理A也應(yīng)該是N+1，B也是N+1，調(diào)整以后，看看我們確實(shí)沒有改變到A、B、D的所包含的黑色節(jié)點(diǎn)數(shù)。下面的情況也可以同樣的方法來分析。

Case 2. uncle是黑色，并且z是z->parent的右子節(jié)點(diǎn)。這時(shí)我們只要把z指向z->parent，然后做一次Left-Rotate(z)。就可以把情況轉(zhuǎn)化成Case 3。

Case 3. uncle是黑色，并且z是z->parent的左子節(jié)點(diǎn)。到了這一步，我們就剩最后一步了。只要把z->parent設(shè)成黑色，把grandfather設(shè)成紅色，再做一次Right-Rotate(grandfather)，整棵樹就修補(bǔ)完畢了?？梢运伎家幌拢@樣一次操作之后，確實(shí)滿足了所有紅黑樹的性質(zhì)。Case 2和Case 3如下圖：

   反復(fù)進(jìn)行迭代，直到某一次迭代開始時(shí)z->parent為黑色而告終，也就是當(dāng)遇到Case 3后，做完它而告終。

void insertFixup(RBTNode* insertNode) {
        RBTNode* p = insertNode;
        while (p->parent->color == RED) {

//z->parent是grandfather的左子節(jié)點(diǎn),下面是三種情況
            if (p->parent == p->parent->parent->lchild) {
                RBTNode* parentRight = p->parent->parent->rchild;
                if (parentRight->color == RED) {
                    p->parent->color = BLACK;
                    parentRight->color = BLACK;
                    p->parent->parent->color = RED;
                    p = p->parent->parent;
                }
                else {
                    if (p == p->parent->rchild) {
                        p = p->parent;
                        leftRotate(p);
                    }
                    p->parent->color = BLACK;
                    p->parent->parent->color = RED;
                    rightRotate(p->parent->parent);
                }
            }
            else {
                RBTNode* parentLeft = p->parent->parent->lchild;
                if (parentLeft->color == RED) {
                    p->parent->color = BLACK;
                    parentLeft->color = BLACK;
                    p->parent->parent->color = RED;
                    p = p->parent->parent;
                }
                else {
                    if (p == p->parent->lchild) {
                        p = p->parent;
                        rightRotate(p);
                    }
                    p->parent->color = BLACK;
                    p->parent->parent->color = RED;
                    leftRotate(p->parent->parent);
                }
            }
        }
        m_root->color = BLACK;
    }

二、刪除

讓我們來回顧一下二叉搜索樹的刪除節(jié)點(diǎn)z的過程：如果z沒有子節(jié)點(diǎn)，那么直接刪除即可；如果z只有一個(gè)子節(jié)點(diǎn)，那么讓這個(gè)子節(jié)點(diǎn)來代替z的位置，然后把z刪除即可；如果z有兩個(gè)子節(jié)點(diǎn)，那么找到z在中序遍歷中的后繼節(jié)點(diǎn)s（也就是從z->rchild開始向左下方一直走到底的那一個(gè)節(jié)點(diǎn)），把s的key賦值給z的key，然后刪除s。

紅黑樹中刪除一個(gè)節(jié)點(diǎn)z的方法也是首先按部就班以上的過程。

按照二叉搜索樹的刪除方法刪除節(jié)點(diǎn)，如果刪除節(jié)點(diǎn)是紅色的，那并不會(huì)改變紅黑樹的性質(zhì)。如果刪除的節(jié)點(diǎn)是黑色的，那么顯然它所在的路徑上就少一個(gè)黑色節(jié)點(diǎn)，那么紅黑樹的性質(zhì)就被破壞了。這時(shí)我們就要執(zhí)行一個(gè)稱為Delete-Fixup的過程，來修補(bǔ)這棵樹。下面我就來講解一下。

一個(gè)節(jié)點(diǎn)被刪除之后，一定有一個(gè)它的子節(jié)點(diǎn)代替了它的位置（即使是葉節(jié)點(diǎn)被刪除后，也會(huì)有一個(gè)空節(jié)點(diǎn)來代替它的位置。前面說過，在紅黑樹中，空節(jié)點(diǎn)是一個(gè)實(shí)際存在的節(jié)點(diǎn)。）。我們就設(shè)指針x指向這個(gè)代替位置的節(jié)點(diǎn)。
顯然，如果x是紅色的，那么我們只要把它設(shè)成黑色，它所在的路徑上就重新多出了一個(gè)黑色節(jié)點(diǎn)，那么紅黑樹的性質(zhì)就滿足了。
    然而，如果x是黑色的，那我們就要假想x上背負(fù)了2個(gè)單位的黑色。那么紅黑樹的性質(zhì)也同樣不破壞，但是我們要找到某一個(gè)紅色的節(jié)點(diǎn)，把x上“超載”的這1個(gè)單位的黑色丟給它，這樣才算完成。Delete-Fixup做的就是這個(gè)工作。

注：刪除了一個(gè)黑色節(jié)點(diǎn)以后，遍歷到節(jié)點(diǎn)一下的葉子節(jié)點(diǎn)比遍歷其他分支的葉子節(jié)點(diǎn)的黑色節(jié)點(diǎn)數(shù)就少了一個(gè)，這就要是找到一個(gè)紅色，把這個(gè)節(jié)點(diǎn)換成黑色來擬補(bǔ)這個(gè)刪除的黑色節(jié)點(diǎn)，使得遍歷到葉子節(jié)點(diǎn)經(jīng)過黑色節(jié)點(diǎn)的數(shù)目一樣。

Delete-Fixup同樣是一個(gè)循環(huán)迭代的過程。每一次迭代開始時(shí)，如果指針x指向一個(gè)紅色節(jié)點(diǎn)，那么大功告成，把它設(shè)成黑色即告終。相反如果x黑色，那么我們就會(huì)面對(duì)以下4種情況。

這里引入另一個(gè)指針w，指向x的兄弟。這里我們都默認(rèn)x是x->parent的左子節(jié)點(diǎn)，則w是x->parent的右子節(jié)點(diǎn)。（如果實(shí)際遇到相反的情況，只要把所有操作中的左、右互反一下就可以了。）

Case 1. w是紅色。這時(shí)我們根據(jù)紅黑樹的性質(zhì)可以肯定x->parent是黑色、w->lchild是黑色。我們把x->parent與w的顏色互換，然后做一次Left-Rotate(x->parent)。做完之后x就有了一個(gè)新的兄弟：原w->lchild，前面說過它一定是黑色的。那么我們就在不破壞紅黑樹性質(zhì)的前提下，把Case 1轉(zhuǎn)換成了Case2、3、4中的一個(gè)，也就是w是黑色的情況。思考一下，這樣做不會(huì)改變每條路徑上黑色節(jié)點(diǎn)的個(gè)數(shù)，如下圖：

注：可以看出這樣變化以后就變成了Case2了。

Case 2. w是黑色，并且w的兩個(gè)子節(jié)點(diǎn)都是黑色。這時(shí)我們只要把w設(shè)成紅色。然后把x移到x->parent，開始下一輪迭代（注意，那“超載”的1單位的黑色始終是跟著指針x走的，直到x走到了一個(gè)紅色節(jié)點(diǎn)上才能把它“卸下”）。思考一下，這一次操作不會(huì)破壞紅黑樹的性質(zhì)。如下圖（圖中節(jié)點(diǎn)B不一定是紅色，也可能是黑色）：

注：這里只要把B變成紅色就大功告成了。

Case 3. w是黑色，并且w的兩個(gè)子節(jié)點(diǎn)左紅右黑。這時(shí)我們把w與w->lchild的顏色互換，然后做Right-Rotate(w)。思考一下，這樣做之后不會(huì)破壞紅黑樹的性質(zhì)。這時(shí)x的新的兄弟就是原w->lchild。而Case 3被轉(zhuǎn)化成了Case 4。

Case 4. w是黑色，并且w的右子節(jié)點(diǎn)是紅色。一但遇到Case 4，就勝利在望了。我看下面一張圖。先把w與x->parent的顏色互換，再做Left-Rotate(x->parent)。這時(shí)圖中節(jié)點(diǎn)E（也就是原w->rchild）所在的路徑就肯定少了一個(gè)黑色，而x所在的路徑則多了一個(gè)黑色。那么我們就把x上多余的1個(gè)單位的黑色丟給E就可以了。至此，Delete-Fixup就順利完成了。

注：通過注1我們可以看出問題在Case4后已經(jīng)解決了。

void delFixup(RBTNode* delNode) {

    RBTNode* p = delNode;

    while (p != m_root && p->color == BLACK) {

       if (p == p->parent->lchild) {//左邊情況，以下是四種不同的Case

           RBTNode* sibling = p->parent->rchild;

           if (sibling->color == RED) {

              sibling->color = BLACK;

              p->parent->color = RED;

              leftRotate(p->parent);

              sibling = p->parent->rchild;

           }

           if (sibling->lchild->color == BLACK

              && sibling->rchild->color == BLACK

              ) {

              sibling->color = RED;

              p = p->parent;

           }

           else {

              if (sibling->rchild->color == BLACK) {

                  sibling->lchild->color = BLACK;

                  sibling->color = RED;

                  rightRotate(sibling);

                  sibling  = sibling->parent;

              }

              sibling->color = sibling->parent->color;

              sibling->parent->color = BLACK;

              sibling->rchild->color = BLACK;

              leftRotate(sibling->parent);

              p = m_root;

           }

       }

       else {//右邊情況

           RBTNode* sibling = p->parent->lchild;

           if (sibling->color == RED) {

              sibling->color = BLACK;

              p->parent->color = RED;

              rightRotate(p->parent);

              sibling = p->parent->lchild;

           }

           if (sibling->lchild->color == BLACK

              && sibling->rchild->color == BLACK

              ) {

              sibling->color = RED;

              p = p->parent;

           }

           else {

              if (sibling->lchild->color == BLACK) {

                  sibling->rchild->color = BLACK;

                  sibling->color = RED;

                  leftRotate(sibling);

                  sibling = sibling->parent;

              }

              sibling->color = sibling->parent->color;

              sibling->parent->color = BLACK;

              sibling->lchild->color = BLACK;

              rightRotate(sibling->parent);

              p = m_root;

           }

       }

    }

    p->color = BLACK;

}