数据结构-红黑树

àì夳堔傛蜴生んèń 2022-07-15 23:37 226阅读 0赞

# 红黑树\[[编辑][Link 1]\] #

**红黑树**（英语：Red–black tree）是一种[自平衡二叉查找树][Link 2]，是在[计算机科学][Link 3]中用到的一种[数据结构][Link 4]，典型的用途是实现[关联数组][Link 5]。它是在1972年由[鲁道夫·贝尔][Link 6]发明的，他称之为"对称二叉B树"，它现代的名字是在Leo J. Guibas和[Robert Sedgewick][]于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况[运行时间][Link 7]，并且在实践中是高效的：它可以在[O][](log *n*)时间内做查找，插入和删除，这里的*n*是树中元素的数目。

## 目录 ##

\[[隐藏][Link 8]\]

*  [1用途和好处][1]
 *  [2性质][2]
 *  [3操作][3]
    
     *  [3.1插入][3.1]
     *  [3.2删除][3.2]
     *  [3.3C++示例代码][3.3C]
 *  [4渐进边界的证明][4]
 *  [5参见][5]
 *  [6引用][6]
 *  [7外部链接][7]

## 用途和好处\[[编辑][Link 9]\] ##

红黑树和[AVL树][AVL]一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如[实时应用][Link 10]（real time application）中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在[计算几何][Link 11]中使用的很多数据结构都可以基于红黑树。

红黑树在[函数式编程][Link 12]中也特别有用，在这里它们是最常用的[持久数据结构][Link 13]（persistent data structure）之一，它们用来构造[关联数组][Link 5]和[集合][Link 14]，每次插入、删除之后它们能保持为以前的版本。除了O(log *n*)的时间之外，红黑树的持久版本对每次插入或删除需要O(log *n*)的空间。

红黑树是[2-3-4树][2-3-4]的一种等同。换句话说，对于每个2-3-4树，都存在至少一个数据元素是同样次序的红黑树。在2-3-4树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得2-3-4树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍2-3-4树的原因，尽管2-3-4树在实践中不经常使用。

红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。

## 性质\[[编辑][Link 15]\] ##

红黑树是每个节点都带有*颜色*属性的[二叉查找树][Link 16]，颜色为*红色*或*黑色*。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

1.  节点是红色或黑色。
2.  根是黑色。
3.  所有叶子都是黑色（叶子是NIL节点）。
4.  每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5.  从任一节点到其每个叶子的所有[简单路径][Link 17]都包含相同数目的黑色节点。

下面是一个具体的红黑树的图例：

[![An example of a red-black tree][]][An example of a red-black tree 1]

这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的[二叉查找树][Link 18]。

要知道为什么这些性质确保了这个结果，注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

在很多树数据结构的表示中，一个节点有可能只有一个子节点，而叶子节点包含数据。用这种范例表示红黑树是可能的，但是这会改变一些性质并使算法复杂。为此，本文中我们使用"nil叶子"或"空（null）叶子"，如上图所示，它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略，导致了这些树好像同上述原则相矛盾，而实际上不是这样。与此有关的结论是所有节点都有两个子节点，尽管其中的一个或两个可能是空叶子。

## 操作\[[编辑][Link 19]\] ##

因为每一个红黑树也是一个特化的[二叉查找树][Link 18]，因此红黑树上的只读操作与普通[二叉查找树][Link 18]上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再匹配红黑树的性质。恢复红黑树的性质需要少量（[O][](log *n*)）的颜色变更（实际是非常快速的）和不超过三次[树旋转][Link 20]（对于插入操作是两次）。虽然插入和删除很复杂，但操作时间仍可以保持为O(log *n*)次。

### 插入\[[编辑][Link 21]\] ###

我们首先[以二叉查找树的方法][Link 22]增加节点并标记它为红色。（如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换（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下它可能是叶子节点。

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中的*左*和*右*应当对调。

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

<table style="font-size:14px"> 
 <tbody> 
  <tr> 
   <td> 
    <div style="clear:right; float:right; position:relative; margin:0px 0px 0.5em 0.5em; border:0px"> 
     <a href="https://zh.wikipedia.org/wiki/File:Red-black_tree_insert_case_5.png" title="情形5示意图" style="text-decoration:none; color:rgb(11,0,128)" rel="nofollow"><img alt="情形5示意图" src="https://upload.wikimedia.org/wikipedia/commons/6/66/Red-black_tree_insert_case_5.png" width="310" height="138" style="border:none; vertical-align:middle"></a> 
    </div> <p style="margin-top:0.5em; margin-bottom:0.5em; line-height:inherit"><strong>情形5</strong>：父节点P是红色而叔父节点U是黑色或缺少，新节点N是其父节点的左子节点，而父节点P又是其父节点G的左子节点。在这种情形下，我们进行针对祖父节点G的一次<a href="https://zh.wikipedia.org/wiki/%E6%A0%91%E6%97%8B%E8%BD%AC" title="树旋转" style="text-decoration:none; color:rgb(11,0,128)" rel="nofollow">右旋转</a>；在旋转产生的树中，以前的父节点P现在是新节点N和以前的祖父节点G的父节点。我们知道以前的祖父节点G是黑色，否则父节点P就不可能是红色（如果P和G都是红色就违反了性质4，所以G必须是黑色）。我们切换以前的父节点P和祖父节点G的颜色，结果的树满足性质4。性质5也仍然保持满足，因为通过这三个节点中任何一个的所有路径以前都通过祖父节点G，现在它们都通过以前的父节点P。在各自的情形下，这都是三个节点中唯一的黑色节点。</p> </td> 
  </tr> 
 </tbody> 
</table>

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(grandparent(n));
         } else {
          
             /* Here, n == n->parent->right && n->parent == grandparent (n)->right */
             rotate_left(grandparent(n));
         }
     }

注意插入实际上是[原地算法][Link 23]，因为上述所有调用都使用了[尾部递归][Link 24]。

### 删除\[[编辑][Link 25]\] ###

**如果需要删除的节点有两个儿子，那么问题可以被转化成删除另一个只有一个儿子的节点的问题**（为了表述方便，这里所指的儿子，为非叶子节点的儿子）。对于二叉查找树，在删除带有两个非叶子儿子的节点的时候，我们找到要么在它的左子树中的最大元素、要么在它的右子树中的最小元素，并把它的值转移到要删除的节点中（如在[这里][Link 18]所展示的那样）。我们接着删除我们从中复制出值的那个节点，它必定有少于两个非叶子的儿子。因为只是复制了一个值，不违反任何性质，这就把问题简化为如何删除最多有一个儿子的节点的问题。它不关心这个节点是最初要删除的节点还是我们从中复制出值的那个节点。

在本文余下的部分中，**我们只需要讨论删除只有一个儿子的节点**（如果它两个儿子都为空，即均为叶子，我们任意将其中一个看作它的儿子）。如果我们删除一个红色节点（此时该节点的儿子将都为叶子节点），它的父亲和儿子一定是黑色的。所以我们可以简单的用它的黑色儿子替换它，并不会破坏性质3和性质4。通过被删除节点的所有路径只是少了一个红色节点，这样可以继续保证性质5。另一种简单情况是在被删除节点是黑色而它的儿子是红色的时候。如果只是去除这个黑色节点，用它的红色儿子顶替上来的话，会破坏性质5，但是如果我们重绘它的儿子为黑色，则曾经通过它的所有路径将通过它的黑色儿子，这样可以继续保持性质5。

**需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候**，这是一种复杂的情况。我们首先把要删除的节点替换为它的儿子。出于方便，称呼这个儿子为**N**（在新的位置上），称呼它的兄弟（它父亲的另一个儿子）为**S**。在下面的示意图中，我们还是使用**P**称呼N的父亲，**SL**称呼S的左儿子，**SR**称呼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是它父亲的左儿子。如果它是右儿子，则在这些情形下的*左*和*右*应当对调。

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);
    }

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);
    }

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);
    }

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);
    }

<table style="font-size:14px"> 
 <tbody> 
  <tr> 
   <td> 
    <div style="clear:right; float:right; position:relative; margin:0px 0px 0.5em 0.5em; border:0px"> 
     <a href="https://zh.wikipedia.org/wiki/File:Red-black_tree_delete_case_6.png" title="情形6示意图" style="text-decoration:none; color:rgb(11,0,128)" rel="nofollow"><img alt="情形6示意图" src="https://upload.wikimedia.org/wikipedia/commons/3/31/Red-black_tree_delete_case_6.png" width="299" height="143" style="border:none; vertical-align:middle"></a> 
    </div> <p style="margin-top:0.5em; margin-bottom:0.5em; line-height:inherit"><strong>情形6：</strong>&nbsp;S是黑色，S的右儿子是红色，而N是它父亲的左儿子。在这种情形下我们在N的父亲上做左旋转，这样S成为N的父亲（P）和S的右儿子的父亲。我们接着交换N的父亲和S的颜色，并使S的右儿子为黑色。子树在它的根上的仍是同样的颜色，所以性质3没有被违反。但是，N现在增加了一个黑色祖先：要么N的父亲变成黑色，要么它是黑色而S被增加为一个黑色祖父。所以，通过N的路径都增加了一个黑色节点。</p> <p style="margin-top:0.5em; margin-bottom:0.5em; line-height:inherit">此时，如果一个路径不通过N，则有两种可能性：</p> 
    <ul style="margin:0.3em 0px 0px 1.6em; padding:0px"> 
     <li style="margin-bottom:0.1em">它通过N的新兄弟。那么它以前和现在都必定通过S和N的父亲，而它们只是交换了颜色。所以路径保持了同样数目的黑色节点。</li> 
     <li style="margin-bottom:0.1em">它通过N的新叔父，S的右儿子。那么它以前通过S、S的父亲和S的右儿子，但是现在只通过S，它被假定为它以前的父亲的颜色，和S的右儿子，它被从红色改变为黑色。合成效果是这个路径通过了同样数目的黑色节点。</li> 
    </ul> <p style="margin-top:0.5em; margin-bottom:0.5em; line-height:inherit">在任何情况下，在这些路径上的黑色节点数目都没有改变。所以我们恢复了性质4。在示意图中的白色节点可以是红色或黑色，但是在变换前后都必须指定相同的颜色。</p> </td> 
  </tr> 
 </tbody> 
</table>

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);
            }
    }

同样的，函数调用都使用了[尾部递归][Link 24]，所以算法是[原地算法][Link 23]。此外，在旋转之后不再做递归调用，所以进行了恒定数目（最多3次）的旋转。

### C++示例代码\[[编辑][Link 26]\] ###

#define BLACK 1
    #define RED 0
    
    using namespace std;
    
    class bst {
          
    private:
    
        struct Node {
          
            int value;
            bool color;
            Node *leftTree, *rightTree, *parent;
    
            Node() {
          
                color = RED;
                leftTree = NULL;
                rightTree = NULL;
                parent = NULL;
                value = 0;
            }
    
            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;
            }
        }
    
        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());
                else
                    rotate_right(p->sibling());
            }
            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);
                        rotate_right (p);
                        p->color = BLACK;
                        p->leftTree->color = p->rightTree->color = RED;
                    } else if(p->parent->leftTree == p && p->grandparent()->rightTree == p->parent) {
          
                        rotate_right (p);
                        rotate_left (p);
                        p->color = BLACK;
                        p->leftTree->color = p->rightTree->color = RED;
                    } 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;
    };

## 渐进边界的证明\[[编辑][Link 27]\] ##

包含*n*个内部节点的红黑树的高度是O(log(n))。

**定义**：

*  h(*v*) = 以节点*v*为根的子树的高度。
 *  bh(*v*) = 从*v*到子树中任何叶子的黑色节点的数目（如果*v*是黑色则不计数它，也叫做黑色高度）。

**引理**：以节点*v*为根的子树有至少2bh(v)−1![2^\{\{bh(v)\}\}-1][2_bh_v_-1]个内部节点。

引理的证明（通过归纳高度）：

基础：h(*v*) = 0

如果*v*的高度是零则它必定是nil，因此bh(*v*) = 0。所以：

2bh(v)−1=20−1=1−1=0![2^\{\{bh(v)\}\}-1=2^\{\{0\}\}-1=1-1=0][2_bh_v_-1_2_0_-1_1-1_0]

归纳假设：h(*v*) = k的*v*有2bh(v)−1−1![2^\{\{bh(v)-1\}\}-1][2_bh_v_-1_-1]个内部节点暗示了h(v′![v'][v]) = k+1的v′![v'][v]有2bh(v′)−1![2^\{\{bh(v')\}\}-1][2_bh_v_-1 1]个内部节点。

因为v′![v'][v]有h(v′![v'][v])> 0所以它是个内部节点。同样的它有黑色高度要么是bh(v′![v'][v])要么是bh(v′![v'][v])-1（依据v′![v'][v]是红色还是黑色）的两个儿子。通过归纳假设每个儿子都有至少2bh(v′)−1−1![2^\{\{bh(v')-1\}\}-1][2_bh_v_-1_-1 1]个内部接点，所以v′![v'][v]有：

2bh(v′)−1−1+2bh(v′)−1−1+1=2bh(v′)−1![2^\{\{bh(v')-1\}\}-1+2^\{\{bh(v')-1\}\}-1+1=2^\{\{bh(v')\}\}-1][2_bh_v_-1_-1_2_bh_v_-1_-1_1_2_bh_v_-1]

个内部节点。

使用这个引理我们现在可以展示出树的高度是对数性的。因为在从根到叶子的任何路径上至少有一半的节点是黑色（根据红黑树性质4），根的黑色高度至少是h(root)/2。通过引理我们得到：

n⩾2h(root)2−1↔log⁡(n+1)⩾h(root)2↔h(root)⩽2log⁡(n+1)![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)\}][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]

因此根的高度是O(log(n))。

[Link 1]: https://zh.wikipedia.org/w/index.php?title=%E7%BA%A2%E9%BB%91%E6%A0%91&action=edit&section=0&summary=/*%20top%20*/%20
[Link 2]: https://zh.wikipedia.org/wiki/%E8%87%AA%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91
[Link 3]: https://zh.wikipedia.org/wiki/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6
[Link 4]: https://zh.wikipedia.org/wiki/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84
[Link 5]: https://zh.wikipedia.org/wiki/%E5%85%B3%E8%81%94%E6%95%B0%E7%BB%84
[Link 6]: https://zh.wikipedia.org/wiki/%E9%B2%81%E9%81%93%E5%A4%AB%C2%B7%E8%B4%9D%E5%B0%94
[Robert Sedgewick]: https://zh.wikipedia.org/wiki/Robert_Sedgewick
[Link 7]: https://zh.wikipedia.org/wiki/%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90
[O]: https://zh.wikipedia.org/wiki/%E5%A4%A7O%E7%AC%A6%E5%8F%B7
[Link 8]: https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#
[1]: https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#.E7.94.A8.E9.80.94.E5.92.8C.E5.A5.BD.E5.A4.84
[2]: https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#.E6.80.A7.E8.B4.A8
[3]: https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#.E6.93.8D.E4.BD.9C
[3.1]: https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#.E6.8F.92.E5.85.A5
[3.2]: https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#.E5.88.A0.E9.99.A4
[3.3C]: https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#C.2B.2B.E7.A4.BA.E4.BE.8B.E4.BB.A3.E7.A0.81
[4]: https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#.E6.B8.90.E8.BF.9B.E8.BE.B9.E7.95.8C.E7.9A.84.E8.AF.81.E6.98.8E
[5]: https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#.E5.8F.82.E8.A7.81
[6]: https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#.E5.BC.95.E7.94.A8
[7]: https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#.E5.A4.96.E9.83.A8.E9.93.BE.E6.8E.A5
[Link 9]: https://zh.wikipedia.org/w/index.php?title=%E7%BA%A2%E9%BB%91%E6%A0%91&action=edit&section=1
[AVL]: https://zh.wikipedia.org/wiki/AVL%E6%A0%91
[Link 10]: https://zh.wikipedia.org/w/index.php?title=%E5%8D%B3%E6%97%B6%E8%AE%A1%E7%AE%97&action=edit&redlink=1
[Link 11]: https://zh.wikipedia.org/wiki/%E8%AE%A1%E7%AE%97%E5%87%A0%E4%BD%95
[Link 12]: https://zh.wikipedia.org/wiki/%E5%87%BD%E6%95%B8%E5%BC%8F%E7%B7%A8%E7%A8%8B
[Link 13]: https://zh.wikipedia.org/w/index.php?title=%E6%8C%81%E4%B9%85%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84&action=edit&redlink=1
[Link 14]: https://zh.wikipedia.org/wiki/%E9%9B%86%E5%90%88_%28%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6%29
[2-3-4]: https://zh.wikipedia.org/wiki/2-3-4%E6%A0%91
[Link 15]: https://zh.wikipedia.org/w/index.php?title=%E7%BA%A2%E9%BB%91%E6%A0%91&action=edit&section=2
[Link 16]: https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9
[Link 17]: https://zh.wikipedia.org/wiki/%E9%81%93%E8%B7%AF_%28%E5%9B%BE%E8%AE%BA%29
[An example of a red-black tree]: https://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/450px-Red-black_tree_example.svg.png
[An example of a red-black tree 1]: https://zh.wikipedia.org/wiki/File:Red-black_tree_example.svg
[Link 18]: https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91
[Link 19]: https://zh.wikipedia.org/w/index.php?title=%E7%BA%A2%E9%BB%91%E6%A0%91&action=edit&section=3
[Link 20]: https://zh.wikipedia.org/wiki/%E6%A0%91%E6%97%8B%E8%BD%AC
[Link 21]: https://zh.wikipedia.org/w/index.php?title=%E7%BA%A2%E9%BB%91%E6%A0%91&action=edit&section=4
[Link 22]: https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91#.E6.8F.92.E5.85.A5
[C]: https://zh.wikipedia.org/wiki/C%E8%AF%AD%E8%A8%80
[Link 23]: https://zh.wikipedia.org/wiki/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95
[Link 24]: https://zh.wikipedia.org/wiki/%E5%B0%BE%E9%83%A8%E9%80%92%E5%BD%92
[Link 25]: https://zh.wikipedia.org/w/index.php?title=%E7%BA%A2%E9%BB%91%E6%A0%91&action=edit&section=5
[Link 26]: https://zh.wikipedia.org/w/index.php?title=%E7%BA%A2%E9%BB%91%E6%A0%91&action=edit&section=6
[Link 27]: https://zh.wikipedia.org/w/index.php?title=%E7%BA%A2%E9%BB%91%E6%A0%91&action=edit&section=7
[2_bh_v_-1]: https://wikimedia.org/api/rest_v1/media/math/render/svg/bd20e4a4bb09ff8a0b1f669e13d80a767fd380dc
[2_bh_v_-1_2_0_-1_1-1_0]: https://wikimedia.org/api/rest_v1/media/math/render/svg/ff9f9c03b2a1d90a61e2c983de3a4a32859f7a0e
[2_bh_v_-1_-1]: https://wikimedia.org/api/rest_v1/media/math/render/svg/ffbd6a112daa51591194b8a2e89d158aeb673253
[v]: https://wikimedia.org/api/rest_v1/media/math/render/svg/19f1c5b0af1f30c41cb8bc0ba3bfea98681da268
[2_bh_v_-1 1]: https://wikimedia.org/api/rest_v1/media/math/render/svg/89836b789850ab1dbccb41765e54847a9734d57a
[2_bh_v_-1_-1 1]: https://wikimedia.org/api/rest_v1/media/math/render/svg/0216c4028ab1738e9ea784c87a506f1f8d050dd4
[2_bh_v_-1_-1_2_bh_v_-1_-1_1_2_bh_v_-1]: https://wikimedia.org/api/rest_v1/media/math/render/svg/8a1682e47a748de66e8bbb72355a047216b3ede7
[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]: https://wikimedia.org/api/rest_v1/media/math/render/svg/16f0c429691a200154c7dcd7b81ae57266f01440