紅黑樹

總想有一個簡單的RBTree類，又不想自己實作，找來找去找到這篇好文，除了講解的清楚簡明外，代碼也不錯，無遞歸的疊代，而且很容易“拿來”做成模闆，如果你也不想"再發明一次輪子"的話...

正文如下:

紅黑樹（附标準代碼）（閱讀本文之前請先了解二叉搜尋樹）

紅黑樹（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操作。

一、 插入

插入首先是按部就班二叉搜尋樹的插入步驟，把新節點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，并開始新一輪的疊代。如下圖：

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後，做完它而告終。

二、删除

讓我們來回顧一下二叉搜尋樹的删除節點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是黑色的情況。如下圖：

Case 2. w是黑色，并且w的兩個子節點都是黑色。這時我們隻要把w設成紅色。然後把x移到x->parent，開始下一輪疊代（注意，那“超載”的1機關的 黑色始終是跟着指針x走的，直到x走到了一個紅色節點上才能把它“卸下”）。思考一下，這一次操作不會破壞紅黑樹的性質。這如下圖（圖中節點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就順利完成了。

以下是我的紅黑樹代碼，其中的所有函數都不包含遞歸（當然，由于樹的層數不會很大，要寫成遞歸也可以）... 

struct Key {         int value;     };     struct RBTNode {         Key key;         int lcount;         int rcount;         RBTNode* lchild;         RBTNode* rchild;         RBTNode* parent;         bool color;     };     class RBT {     private:         const static bool RED = true;         const static bool BLACK = false;         RBTNode* m_null;         RBTNode* m_root;         void clear() {//             RBTNode* p = m_root;             while (p != m_null) {                 if (p->lchild != m_null) {                     p = p->lchild;                 }else if (p->rchild != m_null) {                     p = p->rchild;                 }else {                     RBTNode* temp = p;                     p = p->parent;                     if (temp == p->lchild) {                         p->lchild = m_null;                     }else {                         p->rchild = m_null;                     }                     delete temp;                 }             }             m_root = m_null;         }         void delFixup(RBTNode* delNode) {             RBTNode* p = delNode;             while (p != m_root && p->color == BLACK) {                 if (p == p->parent->lchild) {                     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;         }         void insertFixup(RBTNode* insertNode) {             RBTNode* p = insertNode;             while (p->parent->color == RED) {                 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;         }         inline int keyCmp(const Key& key1, const Key& key2) {             //比較兩個Key的大小。這裡可能有更複雜的比較，如字元串比較等。             return key1.value - key2.value;         }         inline 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;         }         RBTNode* treeMax(RBTNode* root) {//找到子樹中最大的一個節點             RBTNode* result = root;             while (result->rchild != m_null) {                 result = result->rchild;             }             return result;         }         RBTNode* treeMin(RBTNode* root) {//找到子樹中最小的一個節點             RBTNode* result = root;             while (result->lchild != m_null) {                 result = result->lchild;             }             return result;         }     public:         RBT() {             m_null = new RBTNode;             m_null->color = BLACK;             m_null->lchild = m_null->rchild = m_null;             m_root = m_null;         }         ~RBT() {             clear();             delete m_null;         }         RBTNode* atIndex(int i) {//找到從小到大排序後下标為i的節點。i從0開始。             RBTNode* result = m_root;             if (i > result->lcount + result->rcount) {                 result = NULL;             }else {                 while (i != result->lcount) {                     if (i < result->lcount) {                         result = result->lchild;                     }else {                         i -= result->lcount + 1;                         result = result->rchild;                     }                 }             }             return result;         }         void del(RBTNode* node) {//删除一個節點             RBTNode* toDel = node;             if (node->lchild != m_null && node->rchild != m_null) {                 toDel = treeNext(node);//找到中序後繼：即右子樹最左節點             }             RBTNode* temp = toDel;             while (temp->parent != m_null) {                 if (temp == temp->parent->lchild) {                     temp->parent->lcount--;                 }else {                     temp->parent->rcount--;                 }                 temp = temp->parent;             }             RBTNode* replace = toDel->lchild != m_null? toDel->lchild: toDel->rchild;             replace->parent = toDel->parent;             if (replace->parent == m_null) {                 m_root = replace;             }else if (toDel == toDel->parent->lchild) {                 replace->parent->lchild = replace;             }else {                 replace->parent->rchild = replace;             }             if (toDel != node) {                 node->key = toDel->key;             }             if (toDel->color == BLACK) {                 //修改樹，以保持平衡。                 delFixup(replace);             }             delete toDel;         }         void insert(const Key& key) {//插入一個節點             RBTNode* node = new RBTNode;             node->key = key;             node->lcount = 0;             node->rcount = 0;             node->lchild = m_null;             node->rchild = m_null;             node->color = RED;             RBTNode* p = m_root;             RBTNode* leaf = m_null;             while (p != m_null) {                 leaf = p;                 if (keyCmp(node->key, p->key) < 0) {                     p->lcount++;                     p = p->lchild;                 }else {                     p->rcount++;                     p = p->rchild;                 }             }             node->parent = leaf;             if (leaf == m_null) {//如果是空樹。                 m_root = node;             }else if (keyCmp(node->key, leaf->key) < 0) {                 leaf->lchild = node;             }else {                 leaf->rchild = node;             }             //修改樹，以保持平衡。             insertFixup(node);         }         int nodeCount() {             return m_root != m_null? m_root->lcount + m_root->rcount + 1: 0;         }         RBTNode* search(const Key& key) {//按照key查找一個節點。             RBTNode* result = m_root;             while (result != m_null && keyCmp(key, result->key) != 0) {                 result = keyCmp(key, result->key) < 0 ? result->lchild : result->rchild;             }             return result == m_null? NULL: result;         }         void toArray(int* array) {//把樹中節點的值放進一個數組。             RBTNode* p = treeMin(m_root);             int i = 0;             while (p != m_null) {                 array[i] = p->key.value;                 i++;                 p = treeNext(p);             }         }         RBTNode* treeNext(RBTNode* node) {//一個節點在中序遍列中的下一個節點。後繼             RBTNode* result;             if (node->rchild != m_null) {                 result = treeMin(node->rchild);             }else {                 result = node->parent;                 RBTNode* temp = node;                 while (result != m_null && temp == result->rchild) {                     temp = result;                     result = result->parent;                 }             }             return result;         }         RBTNode* treePre(RBTNode* node) {//一個節點在中序遍列中的前一個節點。前驅             RBTNode* result;             if (node->lchild != m_null) {                 result = treeMax(node->lchild);             }else {                 result = node->parent;                 RBTNode* temp = node;                 while (result != m_null && temp == result->lchild) {                     temp = result;                     result = result->parent;                 }             }             return result;         }     };