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

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

紅黑樹（Red-Black Tree）

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

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

1. 根節點是黑色的。

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

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

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

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

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

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

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

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

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

 

一、 插入

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

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

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

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

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

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

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

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

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

   反復進行迭代，直到某一次迭代開始時z->parent為黑色而告終，也就是當遇到Case 3后，做完它而告終。

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

//z->parent是grandfather的左子節點,下面是三種情況
            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;
    }

二、刪除

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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;

}