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

（閱讀本文之前請先了解二叉搜索樹）

紅黑樹（Red-Black Tree）

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

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

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

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

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

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

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

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

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

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

//把一個節(jié)點向左下方移一格，并讓他原來的右子節(jié)點代替它的位置。
   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;
    }

    //把一個節(jié)點向右下方移一格，并讓他原來的左子節(jié)點代替它的位置。
    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é)點z插入到某一個葉節(jié)點的位置上。
    接下來把z的顏色設(shè)成紅色。為什么？還記得紅黑樹的性質(zhì)嗎，從根節(jié)點向下到空節(jié)點的每一條路徑上的黑色節(jié)點數(shù)要相同。如果新插入的是黑色節(jié)點，那么它所在的路徑上就多出了一個黑色的節(jié)點了。所以新插入的節(jié)點一定要設(shè)成紅色。但是這樣可能又有一個矛盾，如果z的父節(jié)點也是紅色，怎么辦，前面說過紅色節(jié)點的子節(jié)點必須是黑色。因此我們要執(zhí)行下面一個迭代的過程，稱為Insert-Fixup，來修補這棵紅黑樹。

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

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

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

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

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

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

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

Case 3. uncle是黑色，并且z是z->parent的左子節(jié)點。到了這一步，我們就剩最后一步了。只要把z->parent設(shè)成黑色，把grandfather設(shè)成紅色，再做一次Right-Rotate(grandfather)，整棵樹就修補完畢了。可以思考一下，這樣一次操作之后，確實滿足了所有紅黑樹的性質(zhì)。Case 2和Case 3如下圖：

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

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

//z->parent是grandfather的左子節(jié)點,下面是三種情況
            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é)點z的過程：如果z沒有子節(jié)點，那么直接刪除即可；如果z只有一個子節(jié)點，那么讓這個子節(jié)點來代替z的位置，然后把z刪除即可；如果z有兩個子節(jié)點，那么找到z在中序遍歷中的后繼節(jié)點s（也就是從z->rchild開始向左下方一直走到底的那一個節(jié)點），把s的key賦值給z的key，然后刪除s。

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

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

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

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

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

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

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

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

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

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

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

Case 4. w是黑色，并且w的右子節(jié)點是紅色。一但遇到Case 4，就勝利在望了。我看下面一張圖。先把w與x->parent的顏色互換，再做Left-Rotate(x->parent)。這時圖中節(jié)點E（也就是原w->rchild）所在的路徑就肯定少了一個黑色，而x所在的路徑則多了一個黑色。那么我們就把x上多余的1個單位的黑色丟給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;

}