紅黑樹

紅黑樹（英語：Red–black tree）是一種自平衡二元搜尋樹，是在電腦科學中用到的一種資料結構，典型用途是實現關聯陣列。它在1972年由魯道夫·貝爾發明，被稱為「對稱二元B樹」，它現代的名字源於利奧尼達斯·J·吉巴斯和羅伯特·塞奇威克於1978年寫的一篇論文。紅黑樹的結構複雜，但它的操作有著良好的最壞情況執行時間，並且在實踐中高效：它可以在${\text{O}}(\log n)$時間內完成尋找、插入和刪除，這裡的$n$是樹中元素的數目。

紅黑樹
類型	樹
發明時間	1978年
發明者	利奧尼達斯·J·吉巴斯、羅伯特·塞奇威克
用大O符號表示的時間複雜度
演算法 平均 最差 空間 $O(n)$ 搜尋 $O(\log n)$ $O(\log n)$ 插入 $O(1)$ $O(\log n)$ 刪除 $O(1)$ $O(\log n)$

歷史

1972年，魯道夫·拜爾發明了一種資料結構，那是一個B樹的四階特殊情況。此結構會維持所有從根到樹葉的路徑都具有相同數量的節點，創造了一個完美的平衡樹。然而，他們並不是二元搜尋樹。拜爾在他的論文中稱呼他們為「對稱二元B樹」（Symmetric binary B-tree），後來他們以2-3-4樹或是2-4樹的形式開始流行。

在一篇1972年的論文〈A Dichromatic Framework for Balanced Trees〉中，利奧尼達斯·J·吉巴斯和羅伯特·塞奇威克從對稱二元B樹+中推導出了紅黑樹。之所以選擇「紅色」是因為這是作者在帕羅奧多研究中心公司（Xerox PARC）工作時用彩色雷射列印機可以產生的最好看的顏色。另一種說法來自吉巴斯，是因為紅色和黑色的筆是他們當時可用來繪製樹的顏色。

用途和好處

紅黑樹和AVL樹一樣都對插入時間、刪除時間和尋找時間提供了最好可能的最壞情況擔保。這不只是使它們在時間敏感的應用，如即時應用中有價值，而且使它們有在提供最壞情況擔保的其他資料結構中作為基礎模板的價值；例如，在計算幾何中使用的很多資料結構都可以基於紅黑樹實現。

紅黑樹在函數式程式設計中也特別有用，在這裡它們是最常用的持久資料結構之一，它們用來構造關聯陣列和集合，每次插入、刪除之後它們能保持為以前的版本。除了${\text{O}}(\log n)$的時間之外，紅黑樹的持久版本對每次插入或刪除需要${\text{O}}(\log n)$的空間。

紅黑樹是2-3-4樹的一種等同。換句話說，對於每個2-3-4樹，都存在至少一個資料元素是同樣次序的紅黑樹。在2-3-4樹上的插入和刪除操作也等同於在紅黑樹中顏色翻轉和旋轉。這使得2-3-4樹成為理解紅黑樹背後的邏輯的重要工具，這也是很多介紹演算法的教科書在紅黑樹之前介紹2-3-4樹的原因，儘管2-3-4樹在實踐中不經常使用。

紅黑樹相對於AVL樹來說，犧牲了部分平衡性以換取插入和刪除操作時少量的旋轉操作，整體來說效能要優於AVL樹。

性質

紅黑樹是每個節點都帶有顏色屬性的二元搜尋樹，顏色為紅色或黑色。在二元搜尋樹強制一般要求以外，對於任何有效的紅黑樹我們增加了如下的額外要求：

1. 節點是紅色或黑色。
2. 根是黑色。
3. 所有葉子都是黑色（葉子是NIL節點）。
4. 每個紅色節點必須有兩個黑色的子節點。（或者說從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。）（或者說不存在兩個相鄰的紅色節點，相鄰指兩個節點是父子關係。）（或者說紅色節點的父節點和子節點均是黑色的。）
5. 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。

下面是一個具體的紅黑樹的圖例：

An example of a red-black tree

這些約束確保了紅黑樹的關鍵特性：從根到葉子的最長的可能路徑不多於最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和尋找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同於普通的二元搜尋樹。

要知道為什麼這些性質確保了這個結果，注意到性質4導致了路徑不能有兩個毗連的紅色節點就足夠了。最短的可能路徑都是黑色節點，最長的可能路徑有交替的紅色和黑色節點。因為根據性質5所有最長的路徑都有相同數目的黑色節點，這就表明了沒有路徑能多於任何其他路徑的兩倍長。

在很多樹資料結構的表示中，一個節點有可能只有一個子節點，而葉子節點包含資料。用這種範例表示紅黑樹是可能的，但是這會改變一些性質並使演算法複雜。為此，本文中我們使用「nil葉子」，如上圖所示，它不包含資料而只充當樹在此結束的指示。這些節點在繪圖中經常被省略，導致了這些樹好像同上述原則相矛盾，而實際上不是這樣。與此有關的結論是所有節點都有兩個子節點，儘管其中的一個或兩個可能是空葉子。

操作

因為每一個紅黑樹也是一個特化的二元搜尋樹，因此紅黑樹上的唯讀操作與普通二元搜尋樹上的唯讀操作相同。然而，在紅黑樹上進行插入操作和刪除操作會導致不再符合紅黑樹的性質。恢復紅黑樹的性質需要少量（${\text{O}}(\log n)$）的顏色變更（實際是非常快速的）和不超過三次樹旋轉（對於插入操作是兩次）。雖然插入和刪除很複雜，但操作時間仍可以保持為${\text{O}}(\log n)$次。

插入

我們首先以二元搜尋樹的方法增加節點並標記它為紅色。（如果設為黑色，就會導致根到葉子的路徑上有一條路上，多一個額外的黑節點，這個是很難調整的。但是設為紅色節點後，可能會導致出現兩個連續紅色節點的衝突，那麼可以通過顏色調換（color flips）和樹旋轉來調整。）下面要進行什麼操作取決於其他臨近節點的顏色。同人類的家族樹中一樣，我們將使用術語叔父節點來指一個節點的父節點的兄弟節點。注意：

• 性質1和性質3總是保持著。
• 性質4只在增加紅色節點、重繪黑色節點為紅色，或做旋轉時受到威脅。
• 性質5只在增加黑色節點、重繪紅色節點為黑色，或做旋轉時受到威脅。

在下面的示意圖中，將要插入的節點標為N，N的父節點標為P，N的祖父節點標為G，N的叔父節點標為U。在圖中展示的任何顏色要麼是由它所處情形這些所作的假定，要麼是假定所暗含（imply）的。

對於每一種情形，我們將使用C範例程式碼來展示。通過下列函式，可以找到一個節點的叔父和祖父節點：

 node* grandparent(node *n){
     return n->parent->parent;
 }

 node* uncle(node *n){
     if(n->parent == grandparent(n)->left)
         return grandparent (n)->right;
     else
         return grandparent (n)->left;
 }

情形1:新節點N位於樹的根上，沒有父節點。在這種情形下，我們把它重繪為黑色以滿足性質2。因為它在每個路徑上對黑節點數目增加一，性質5符合。

 void insert_case1(node *n){
     if(n->parent == NULL)
         n->color = BLACK;
     else
         insert_case2 (n);
 }

情形2:新節點的父節點P是黑色，所以性質4沒有失效（新節點是紅色的）。在這種情形下，樹仍是有效的。性質5也未受到威脅，儘管新節點N有兩個黑色葉子子節點；但由於新節點N是紅色，通過它的每個子節點的路徑就都有同通過它所取代的黑色的葉子的路徑同樣數目的黑色節點，所以依然滿足這個性質。

 void insert_case2(node *n){
     if(n->parent->color == BLACK)
         return; /* 树仍旧有效*/
     else
         insert_case3 (n);
 }

注意：在下列情形下我們假定新節點的父節點為紅色，所以它有祖父節點；因為如果父節點是根節點，那父節點就應當是黑色。所以新節點總有一個叔父節點，儘管在情形4和5下它可能是葉子節點。

情形3示意圖 情形3:如果父節點P和叔父節點U二者都是紅色，（此時新插入節點N做為P的左子節點或右子節點都屬於情形3，這裡右圖僅顯示N做為P左子的情形）則我們可以將它們兩個重繪為黑色並重繪祖父節點G為紅色（用來保持性質5）。現在我們的新節點N有了一個黑色的父節點P。因為通過父節點P或叔父節點U的任何路徑都必定通過祖父節點G，在這些路徑上的黑節點數目沒有改變。但是，紅色的祖父節點G可能是根節點，這就違反了性質2，也有可能祖父節點G的父節點是紅色的，這就違反了性質4。為了解決這個問題，我們在祖父節點G上遞迴地進行情形1的整個過程。（把G當成是新加入的節點進行各種情形的檢查）

 void insert_case3(node *n){
     if(uncle(n) != NULL && uncle (n)->color == RED) {
         n->parent->color = BLACK;
         uncle (n)->color = BLACK;
         grandparent (n)->color = RED;
         insert_case1(grandparent(n));
     }
     else
         insert_case4 (n);
 }

注意：在餘下的情形下，我們假定父節點P是其祖父G的左子節點。如果它是右子節點，情形4和情形5中的左和右應當對調。

情形4示意圖 情形4:父節點P是紅色而叔父節點U是黑色或缺少，並且新節點N是其父節點P的右子節點而父節點P又是其父節點的左子節點。在這種情形下，我們進行一次左旋轉調換新節點和其父節點的角色;接著，我們按情形5處理以前的父節點P以解決仍然失效的性質4。注意這個改變會導致某些路徑通過它們以前不通過的新節點N（比如圖中1號葉子節點）或不通過節點P（比如圖中3號葉子節點），但由於這兩個節點都是紅色的，所以性質5仍有效。

 void insert_case4(node *n){
     if(n == n->parent->right && n->parent == grandparent(n)->left) {
         rotate_left(n);
         n = n->left;
     } else if(n == n->parent->left && n->parent == grandparent(n)->right) {
         rotate_right(n);
         n = n->right;
     }
     insert_case5 (n);
 }

情形5示意圖 情形5：父節點P是紅色而叔父節點U是黑色或缺少，新節點N是其父節點的左子節點，而父節點P又是其父節點G的左子節點。在這種情形下，我們進行針對祖父節點G的一次右旋轉；在旋轉產生的樹中，以前的父節點P現在是新節點N和以前的祖父節點G的父節點。我們知道以前的祖父節點G是黑色，否則父節點P就不可能是紅色（如果P和G都是紅色就違反了性質4，所以G必須是黑色）。我們切換以前的父節點P和祖父節點G的顏色，結果的樹滿足性質4。性質5也仍然保持滿足，因為通過這三個節點中任何一個的所有路徑以前都通過祖父節點G，現在它們都通過以前的父節點P。在各自的情形下，這都是三個節點中唯一的黑色節點。

 void insert_case5(node *n){
     n->parent->color = BLACK;
     grandparent (n)->color = RED;
     if(n == n->parent->left && n->parent == grandparent(n)->left) {
         rotate_right(n->parent);
     } else {
         /* Here, n == n->parent->right && n->parent == grandparent (n)->right */
         rotate_left(n->parent);
     }
 }

注意插入實際上是原地演算法，因為上述所有呼叫都使用了尾端遞迴。

刪除

如果需要刪除的節點有兩個兒子，那麼問題可以被轉化成刪除另一個只有一個兒子的節點的問題（為了表述方便，這裡所指的兒子，為非葉子節點的兒子）。對於二元搜尋樹，在刪除帶有兩個非葉子兒子的節點的時候，我們要麼找到它左子樹中的最大元素、要麼找到它右子樹中的最小元素，並把它的值轉移到要刪除的節點中（如在這裡所展示的那樣）。我們接著刪除我們從中複製出值的那個節點，它必定有少於兩個非葉子的兒子。因為只是複製了一個值（沒有複製顏色），不違反任何性質，這就把問題簡化為如何刪除最多有一個兒子的節點的問題。它不關心這個節點是最初要刪除的節點還是我們從中複製出值的那個節點。

在本文餘下的部分中，我們只需要討論刪除只有一個兒子的節點（如果它兩個兒子都為空，即均為葉子，我們任意將其中一個看作它的兒子）。如果我們刪除一個紅色節點（此時該節點的兒子將都為葉子節點），它的父親和兒子一定是黑色的。所以我們可以簡單的用它的黑色兒子替換它，並不會破壞性質3和性質4。通過被刪除節點的所有路徑只是少了一個紅色節點，這樣可以繼續保證性質5。另一種簡單情況是在被刪除節點是黑色而它的兒子是紅色的時候。如果只是去除這個黑色節點，用它的紅色兒子頂替上來的話，會破壞性質5，但是如果我們重繪它的兒子為黑色，則曾經通過它的所有路徑將通過它的黑色兒子，這樣可以繼續保持性質5。

需要進一步討論的是在要刪除的節點和它的兒子二者都是黑色的時候，這是一種複雜的情況（這種情況下該節點的兩個兒子都是葉子節點，否則若其中一個兒子是黑色非葉子節點，另一個兒子是葉子節點，那麼從該節點通過非葉子節點兒子的路徑上的黑色節點數最小為2，而從該節點到另一個葉子節點兒子的路徑上的黑色節點數為1，違反了性質5）。我們首先把要刪除的節點替換為它的兒子。出於方便，稱呼這個兒子為N（在新的位置上），稱呼它的兄弟（它父親的另一個兒子）為S。在下面的示意圖中，我們還是使用P稱呼N的父親，S_L稱呼S的左兒子，S_R稱呼S的右兒子。我們將使用下述函式找到兄弟節點：

struct node *
sibling(struct node *n)
{
        if(n == n->parent->left)
                return n->parent->right;
        else
                return n->parent->left;
}

我們可以使用下列程式碼進行上述的概要步驟，這裡的函式replace_node替換child到n在樹中的位置。出於方便，在本章節中的程式碼將假定空葉子被用不是NULL的實際節點對象來表示（在插入章節中的程式碼可以同任何一種表示一起工作）。

void
delete_one_child(struct node *n)
{
        /*
         * Precondition: n has at most one non-null child.
         */
        struct node *child = is_leaf(n->right)? n->left : n->right;
 
        replace_node(n, child);
        if(n->color == BLACK){
                if(child->color == RED)
                        child->color = BLACK;
                else
                        delete_case1 (child);
        }
        free (n);
}

如果N和它初始的父親是黑色，則刪除它的父親導致通過N的路徑都比不通過它的路徑少了一個黑色節點。因為這違反了性質5，樹需要被重新平衡。有幾種情形需要考慮：

情形1: N是新的根。在這種情形下，我們就做完了。我們從所有路徑去除了一個黑色節點，而新根是黑色的，所以性質都保持著。

void
delete_case1(struct node *n)
{
        if(n->parent != NULL)
                delete_case2 (n);
}

注意：在情形2、5和6下，我們假定N是它父親的左兒子。如果它是右兒子，則在這些情形下的左和右應當對調。

情形2示意圖 情形2： S是紅色。在這種情形下我們在N的父親上做左旋轉，把紅色兄弟轉換成N的祖父，我們接著對調N的父親和祖父的顏色。完成這兩個操作後，儘管所有路徑上黑色節點的數目沒有改變，但現在N有了一個黑色的兄弟和一個紅色的父親（它的新兄弟是黑色因為它是紅色S的一個兒子），所以我們可以接下去按情形4、情形5或情形6來處理。 （注意：這裡的圖中沒有顯示出來，N是刪除了黑色節點後替換上來的子節點，所以這個過程中由P->X->N變成了P->N，實際上是少了一個黑色節點，也可以理解為Parent(Black)和Silbing(Red)那麼他們的孩子黑色節點的數目肯定不等，讓他們做新兄弟肯定是不平衡的，還需後面繼續處理。這裡看英文版本的[1] （頁面存檔備份，存於網際網路檔案館）比較的明了）

void
delete_case2(struct node *n)
{
        struct node *s = sibling (n);
 
        if(s->color == RED){
                n->parent->color = RED;
                s->color = BLACK;
                if(n == n->parent->left)
                        rotate_left(n->parent);
                else
                        rotate_right(n->parent);
        } 
        delete_case3 (n);
}

情形3示意圖 情形3： N的父親、S和S的兒子都是黑色的。在這種情形下，我們簡單的重繪S為紅色。結果是通過S的所有路徑，它們就是以前不通過N的那些路徑，都少了一個黑色節點。因為刪除N的初始的父親使通過N的所有路徑少了一個黑色節點，這使事情都平衡了起來。但是，通過P的所有路徑現在比不通過P的路徑少了一個黑色節點，所以仍然違反性質5。要修正這個問題，我們要從情形1開始，在P上做重新平衡處理。

void
delete_case3(struct node *n)
{
        struct node *s = sibling (n);
 
        if((n->parent->color == BLACK)&&
(s->color == BLACK)&&
(s->left->color == BLACK)&&
(s->right->color == BLACK)) {
                s->color = RED;
                delete_case1(n->parent);
        } else
                delete_case4 (n);
}

情形4示意圖 情形4： S和S的兒子都是黑色，但是N的父親是紅色。在這種情形下，我們簡單的交換N的兄弟和父親的顏色。這不影響不通過N的路徑的黑色節點的數目，但是它在通過N的路徑上對黑色節點數目增加了一，添補了在這些路徑上刪除的黑色節點。

void
delete_case4(struct node *n)
{
        struct node *s = sibling (n);
 
        if（(n->parent->color == RED)&&
(s->color == BLACK)&&
(s->left->color == BLACK)&&
(s->right->color == BLACK)) {
                s->color = RED;
                n->parent->color = BLACK;
        } else
                delete_case5 (n);
}

情形5示意圖 情形5： S是黑色，S的左兒子是紅色，S的右兒子是黑色，而N是它父親的左兒子。在這種情形下我們在S上做右旋轉，這樣S的左兒子成為S的父親和N的新兄弟。我們接著交換S和它的新父親的顏色。所有路徑仍有同樣數目的黑色節點，但是現在N有了一個黑色兄弟，他的右兒子是紅色的，所以我們進入了情形6。N和它的父親都不受這個變換的影響。

void
delete_case5(struct node *n)
{
        struct node *s = sibling (n);
 
        if（s->color == BLACK){ /* this if statement is trivial, 
due to Case 2(even though Case two changed the sibling to a sibling's child, 
the sibling's child can't be red, since no red parent can have a red child). */
// the following statements just force the red to be on the left of the left of the parent, 
// or right of the right, so case six will rotate correctly.
                if((n == n->parent->left)&&
(s->right->color == BLACK)&&
(s->left->color == RED)) { // this last test is trivial too due to cases 2-4.
                        s->color = RED;
                        s->left->color = BLACK;
                        rotate_right (s);
                } else if((n == n->parent->right)&&
(s->left->color == BLACK)&&
(s->right->color == RED)) {// this last test is trivial too due to cases 2-4.
                        s->color = RED;
                        s->right->color = BLACK;
                        rotate_left (s);
                }
        }
        delete_case6 (n);
}

情形6示意圖 情形6： S是黑色，S的右兒子是紅色，而N是它父親的左兒子。在這種情形下我們在N的父親上做左旋轉，這樣S成為N的父親（P）和S的右兒子的父親。我們接著交換N的父親和S的顏色，並使S的右兒子為黑色。子樹在它的根上的仍是同樣的顏色，所以性質3沒有被違反。但是，N現在增加了一個黑色祖先：要麼N的父親變成黑色，要麼它是黑色而S被增加為一個黑色祖父。所以，通過N的路徑都增加了一個黑色節點。 此時，如果一個路徑不通過N，則有兩種可能性： 它通過N的新兄弟。那麼它以前和現在都必定通過S和N的父親，而它們只是交換了顏色。所以路徑保持了同樣數目的黑色節點。 它通過N的新叔父，S的右兒子。那麼它以前通過S、S的父親和S的右兒子，但是現在只通過S，它被假定為它以前的父親的顏色，和S的右兒子，它被從紅色改變為黑色。合成效果是這個路徑通過了同樣數目的黑色節點。 在任何情況下，在這些路徑上的黑色節點數目都沒有改變。所以我們恢復了性質4。在示意圖中的白色節點可以是紅色或黑色，但是在變換前後都必須指定相同的顏色。

void
delete_case6(struct node *n)
{
        struct node *s = sibling (n);
 
        s->color = n->parent->color;
        n->parent->color = BLACK;
 
        if(n == n->parent->left){
                s->right->color = BLACK;
                rotate_left(n->parent);
        } else {
                s->left->color = BLACK;
                rotate_right(n->parent);
        }
}

同樣的，函式呼叫都使用了尾端遞迴，所以演算法是原地演算法。此外，在旋轉之後不再做遞迴呼叫，所以進行了恆定數目（最多3次）的旋轉。

C++範例程式碼

#define NIL   NULL
#define BLACK 1
#define RED 0
#include <iostream>

using namespace std;

class bst {
private:

    struct Node {
        int value;
        bool color;
        Node *leftTree, *rightTree, *parent;

        Node() : value(0), color(RED), leftTree(NULL), rightTree(NULL), parent(NULL) { }        

        Node* grandparent() {
            if(parent == NULL){
                return NULL;
            }
            return parent->parent;
        }

        Node* uncle() {
            if(grandparent() == NULL) {
                return NULL;
            }
            if(parent == grandparent()->rightTree)
                return grandparent()->leftTree;
            else
                return grandparent()->rightTree;
        }

        Node* sibling() {
            if(parent->leftTree == this)
                return parent->rightTree;
            else
                return parent->leftTree;
        }
    };

    void rotate_right(Node *p){
        Node *gp = p->grandparent();
        Node *fa = p->parent;
        Node *y = p->rightTree;

        fa->leftTree = y;

        if(y != NIL)
            y->parent = fa;
        p->rightTree = fa;
        fa->parent = p;

        if(root == fa)
            root = p;
        p->parent = gp;

        if(gp != NULL){
            if(gp->leftTree == fa)
                gp->leftTree = p;
            else
                gp->rightTree = p;
        }

    }

    void rotate_left(Node *p){
        if(p->parent == NULL){
            root = p;
            return;
        }
        Node *gp = p->grandparent();
        Node *fa = p->parent;
        Node *y = p->leftTree;

        fa->rightTree = y;

        if(y != NIL)
            y->parent = fa;
        p->leftTree = fa;
        fa->parent = p;

        if(root == fa)
            root = p;
        p->parent = gp;

        if(gp != NULL){
            if(gp->leftTree == fa)
                gp->leftTree = p;
            else
                gp->rightTree = p;
        }
    }

    void inorder(Node *p){
        if(p == NIL)
            return;

        if(p->leftTree)
            inorder(p->leftTree);

        cout << p->value << " ";
                
        if(p->rightTree)
            inorder(p->rightTree);
    }

    string outputColor (bool color) {
        return color ? "BLACK" : "RED";
    }

    Node* getSmallestChild(Node *p){
        if(p->leftTree == NIL)
            return p;
        return getSmallestChild(p->leftTree);
    }

    bool delete_child(Node *p, int data){
        if(p->value > data){
            if(p->leftTree == NIL){
                return false;
            }
            return delete_child(p->leftTree, data);
        } else if(p->value < data){
            if(p->rightTree == NIL){
                return false;
            }
            return delete_child(p->rightTree, data);
        } else if(p->value == data){
            if(p->rightTree == NIL){
                delete_one_child (p);
                return true;
            }
            Node *smallest = getSmallestChild(p->rightTree);
            swap(p->value, smallest->value);
            delete_one_child (smallest);

            return true;
        }else{
           return false;
         }
    }

    void delete_one_child(Node *p){
        Node *child = p->leftTree == NIL ? p->rightTree : p->leftTree;
        if(p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL){
            p = NULL;
            root = p;
            return;
        }
        
        if(p->parent == NULL){
            delete  p;
            child->parent = NULL;
            root = child;
            root->color = BLACK;
            return;
        }
        
        if(p->parent->leftTree == p){
            p->parent->leftTree = child;
        } else {
            p->parent->rightTree = child;
        }
        child->parent = p->parent;

        if(p->color == BLACK){
            if(child->color == RED){
                child->color = BLACK;
            } else
                delete_case (child);
        }

        delete p;
    }

    void delete_case(Node *p){
        if(p->parent == NULL){
            p->color = BLACK;
            return;
        }
        if(p->sibling()->color == RED) {
            p->parent->color = RED;
            p->sibling()->color = BLACK;
            if(p == p->parent->leftTree)
                //rotate_left(p->sibling());
                rotate_left(p->parent);
            else
                //rotate_right(p->sibling());
                rotate_right(p->parent);
        }
        if(p->parent->color == BLACK && p->sibling()->color == BLACK
                && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {
            p->sibling()->color = RED;
            delete_case(p->parent);
        } else if(p->parent->color == RED && p->sibling()->color == BLACK
                && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {
            p->sibling()->color = RED;
            p->parent->color = BLACK;
        } else {
            if(p->sibling()->color == BLACK) {
                if(p == p->parent->leftTree && p->sibling()->leftTree->color == RED
                        && p->sibling()->rightTree->color == BLACK) {
                    p->sibling()->color = RED;
                    p->sibling()->leftTree->color = BLACK;
                    rotate_right(p->sibling()->leftTree);
                } else if(p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK
                        && p->sibling()->rightTree->color == RED) {
                    p->sibling()->color = RED;
                    p->sibling()->rightTree->color = BLACK;
                    rotate_left(p->sibling()->rightTree);
                }
            }
            p->sibling()->color = p->parent->color;
            p->parent->color = BLACK;
            if(p == p->parent->leftTree){
                p->sibling()->rightTree->color = BLACK;
                rotate_left(p->sibling());
            } else {
                p->sibling()->leftTree->color = BLACK;
                rotate_right(p->sibling());
            }
        }
    }

    void insert(Node *p, int data){
        if(p->value >= data){
            if(p->leftTree != NIL)
                insert(p->leftTree, data);
            else {
                Node *tmp = new Node();
                tmp->value = data;
                tmp->leftTree = tmp->rightTree = NIL;
                tmp->parent = p;
                p->leftTree = tmp;
                insert_case (tmp);
            }
        } else {
            if(p->rightTree != NIL)
                insert(p->rightTree, data);
            else {
                Node *tmp = new Node();
                tmp->value = data;
                tmp->leftTree = tmp->rightTree = NIL;
                tmp->parent = p;
                p->rightTree = tmp;
                insert_case (tmp);
            }
        }
    }

    void insert_case(Node *p){
        if(p->parent == NULL){
            root = p;
            p->color = BLACK;
            return;
        }
        if(p->parent->color == RED){
            if(p->uncle()->color == RED) {
                p->parent->color = p->uncle()->color = BLACK;
                p->grandparent()->color = RED;
                insert_case(p->grandparent());
            } else {
                if(p->parent->rightTree == p && p->grandparent()->leftTree == p->parent) {
                    rotate_left(p);
                    p->color = BLACK;
                    p->parent->color = RED;
                    rotate_right(p);
                } else if(p->parent->leftTree == p && p->grandparent()->rightTree == p->parent) {
                    rotate_right(p);
                    p->color = BLACK;
                    p->parent->color = RED;
                    rotate_left(p);
                } else if(p->parent->leftTree == p && p->grandparent()->leftTree == p->parent) {
                    p->parent->color = BLACK;
                    p->grandparent()->color = RED;
                    rotate_right(p->parent);
                } else if(p->parent->rightTree == p && p->grandparent()->rightTree == p->parent) {
                    p->parent->color = BLACK;
                    p->grandparent()->color = RED;
                    rotate_left(p->parent);
                }
            }
        }
    }

    void DeleteTree(Node *p){
        if(!p || p == NIL){
            return;
        }
        DeleteTree(p->leftTree);
        DeleteTree(p->rightTree);
        delete p;
    }
public:

    bst() {
        NIL = new Node();
        NIL->color = BLACK;
        root = NULL;
    }

    ~bst() {
        if (root)
            DeleteTree (root);
        delete NIL;
    }

    void inorder() {
        if(root == NULL)
            return;
        inorder (root);
        cout << endl;
    }

    void insert (int x) {
        if(root == NULL){
            root = new Node();
            root->color = BLACK;
            root->leftTree = root->rightTree = NIL;
            root->value = x;
        } else {
            insert(root, x);
        }
    }

    bool delete_value (int data) {
        return delete_child(root, data);
    }
private:
    Node *root, *NIL;
};

漸近邊界的證明

包含n個內部節點的紅黑樹的高度是${\text{O}}(\log n)$。

定義：

• $h(v)$表示以節點$v$為根的子樹的高度。
• $bh(v)$表示從$v$到子樹中任何葉子的黑色節點的數目（如果$v$是黑色則不計數它，也叫做黑色高度）。

引理：以節點$v$為根的子樹有至少$2^{bh(v)}-1$個內部節點。

引理的證明（通過歸納高度）：

基礎：$h(v)=0$

如果$v$的高度是零則它必定是NIL，因此$bh(v)=0$。所以：

$2^{bh(v)}-1=2^{0}-1=1-1=0$

歸納假設：$h(v)=k$的$v$有$2^{bh(v)-1}-1$個內部節點暗示了h($v'$) = k+1的$v'$有$2^{bh(v')}-1$個內部節點。

因為$v'$有h($v'$)> 0所以它是個內部節點。同樣的它有黑色高度要麼是bh($v'$)要麼是bh($v'$)-1（依據$v$是紅色還是黑色）的兩個兒子。通過歸納假設每個兒子都有至少$2^{bh(v')-1}-1$個內部接點，所以$v'$有：

$2^{bh(v')-1}-1+2^{bh(v')-1}-1+1=2^{bh(v')}-1$

個內部節點。

使用這個引理我們現在可以展示出樹的高度是對數性的。因為在從根到葉子的任何路徑上至少有一半的節點是黑色（根據紅黑樹性質4），根的黑色高度至少是${\frac {h(root)}{2}}$。通過引理我們得到：

$n\geqslant 2^{\frac {h(root)}{2}}-1\leftrightarrow \;\log {(n+1)}\geqslant {\frac {h(root)}{2}}\leftrightarrow \;h(root)\leqslant 2\log {(n+1)}$

因此根的高度是${\text{O}}(\log n)$。

參見

• AVL樹
• B樹
• 跳躍列表 一種有可能替代平衡樹的資料結構
• dancing tree
• 伸展樹
• 2-3-4樹
• Treap

參照

• Mathworld: Red-Black Tree （頁面存檔備份，存於網際網路檔案館）
• San Diego State University: CS 660: Red-Black tree notes （頁面存檔備份，存於網際網路檔案館）, by Roger Whitney
• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms. Massachusetts: The MIT Press, 2002. pp273-77. ISBN 0-07-013151-1

外部連結

• An applet + quick explanation （頁面存檔備份，存於網際網路檔案館）
• Red/Black Tree Demonstration （頁面存檔備份，存於網際網路檔案館）
• An example（animated GIF, 200KB）
• An example（static picture）
• Another explanation（pictures, source code, and Java interactive animation）
• Red-Black Tree Demonstration by David M. Howard
• RBT: A SmallEiffel Red-Black Tree Library （頁面存檔備份，存於網際網路檔案館）
• libredblack: A C Red-Black Tree Library （頁面存檔備份，存於網際網路檔案館）
• Data Structures and Algorithm Analysis in C (2nd edition) （頁面存檔備份，存於網際網路檔案館）
• Red-Black Tree C++ Code
• Red-Black Trees by Thomas Niemann
• 紅黑樹的介紹和實現