说说"红黑树"

红太狼 2022-06-07 02:55 134阅读 0赞

**--摘自维基百科**

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

## 用途和好处 ##

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

红黑树在[函数式编程][Link 9]中也特别有用，在这里它们是最常用的[持久数据结构][Link 10]之一，它们用来构造[关联数组][Link 4]和[集合][Link 11]，在突变之后它们能保持为以前的版本。除了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 树在实践中不经常使用。

## 性质 ##

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

性质1. 节点是红色或黑色。

性质2. 根是黑色。

性质3. 所有叶子都是黑色（叶子是NIL节点）。

性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点到其每个叶子的所有[简单路径][Link 13]都包含相同数目的黑色节点。

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

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

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

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

## 操作 ##

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

### 插入 ###

我们首先[以二叉查找树的方法][Link 16]增加节点并标记它为红色。（如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。） 下面要进行什么操作取决于其他临近节点的颜色。同人类的家族树中一样，我们将使用术语*叔父节点*来指一个节点的父节点的兄弟节点。注意:

*  性质1[\[1\]][1]和性质3[\[2\]][2]总是保持着。
 *  性质4[\[3\]][3]只在增加红色节点、重绘黑色节点为红色，或做旋转时受到威胁。
 *  性质5[\[4\]][4]只在增加黑色节点、重绘红色节点为黑色，或做旋转时受到威胁。

在下面的示意图中，将要插入的节点标为**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\]][5]。因为它在每个路径上对黑节点数目增加一，性质5[\[4\]][4]符合。

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

**情形2**: 新节点的父节点**P**是黑色，所以性质4[\[3\]][3]没有失效（新节点是红色的）。在这种情形下，树仍是有效的。性质5[\[4\]][4]也未受到威胁，尽管新节点**N**有两个黑色叶子子节点；但由于新节点**N**是红色，通过它的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点，所以依然满足这个性质。

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

**注意:** 在下列情形下我们假定新节点的父节点为红色，所以它有祖父节点；因为如果父节点是根节点，那父节点就应当是黑色。所以新节点总有一个叔父节点，尽管在情形4和5下它可能是叶子节点。

<table style=""> 
 <tbody> 
  <tr> 
   <td> 
    <div style="clear:right; float:right; position:relative; margin:0px 0px 0.5em 0.5em; border:0px"> 
     <a href="http://zh.wikipedia.org/wiki/File:Red-black_tree_insert_case_3.png" title="情况 3 示意图" style="text-decoration:none; color:rgb(11,0,128)" rel="nofollow"><img alt="情况 3 示意图" src="http://upload.wikimedia.org/wikipedia/commons/c/c8/Red-black_tree_insert_case_3.png" height="139" width="300" style="border:none; vertical-align:middle"></a> 
    </div> <p style="margin:0.4em 0px 0.5em; line-height:1.5em"><strong>情形3</strong>: 如果父节点<strong>P</strong>和叔父节点<strong>U</strong>二者都是红色，(此时新插入节点N做为P的左子节点或右子节点都属于情形3,这里右图仅显示N做为P左子的情形)则我们可以将它们两个重绘为黑色并重绘祖父节点<strong>G</strong>为红色(用来保持性质5<sup><a href="http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_note-property5-3" style="text-decoration:none; color:rgb(11,0,128); white-space:nowrap" rel="nofollow">[4]</a></sup>)。现在我们的新节点<strong>N</strong>有了一个黑色的父节点<strong>P</strong>。因为通过父节点<strong>P</strong>或叔父节点<strong>U</strong>的任何路径都必定通过祖父节点<strong>G</strong>，在这些路径上的黑节点数目没有改变。但是，红色的祖父节点<strong>G</strong>的父节点也有可能是红色的，这就违反了性质4<sup><a href="http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_note-property4-2" style="text-decoration:none; color:rgb(11,0,128); white-space:nowrap" rel="nofollow">[3]</a></sup>。为了解决这个问题，我们在祖父节点<strong>G</strong>上递归地进行<strong>情形1</strong>的整个过程。（把<strong>G</strong>当成是新加入的节点进行各种情况的检查）</p> </td> 
  </tr> 
 </tbody> 
</table>

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

<table style=""> 
 <tbody> 
  <tr> 
   <td> 
    <div style="clear:right; float:right; position:relative; margin:0px 0px 0.5em 0.5em; border:0px"> 
     <a href="http://zh.wikipedia.org/wiki/File:Red-black_tree_insert_case_4.png" title="情况 4 示意图" style="text-decoration:none; color:rgb(11,0,128)" rel="nofollow"><img alt="情况 4 示意图" src="http://upload.wikimedia.org/wikipedia/commons/5/56/Red-black_tree_insert_case_4.png" height="138" width="283" style="border:none; vertical-align:middle"></a> 
    </div> <p style="margin:0.4em 0px 0.5em; line-height:1.5em"><strong>情形4</strong>: 父节点<strong>P</strong>是红色而叔父节点<strong>U</strong>是黑色或缺少，并且新节点<strong>N</strong>是其父节点<strong>P</strong>的右子节点而父节点<strong>P</strong>又是其父节点的左子节点。在这种情形下，我们进行一次<a href="http://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>调换新节点和其父节点的角色; 接着，我们按<strong>情形5</strong>处理以前的父节点<strong>P</strong>以解决仍然失效的性质4<sup><a href="http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_note-property4-2" style="text-decoration:none; color:rgb(11,0,128); white-space:nowrap" rel="nofollow">[3]</a></sup>。注意这个改变会导致某些路径通过它们以前不通过的新节点<strong>N</strong>（比如图中1号叶子节点）或不通过节点<strong>P</strong>（比如图中3号叶子节点），但由于这两个节点都是红色的，所以性质5<sup><a href="http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_note-property5-3" style="text-decoration:none; color:rgb(11,0,128); white-space:nowrap" rel="nofollow">[4]</a></sup>仍有效。</p> </td> 
  </tr> 
 </tbody> 
</table>

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=""> 
 <tbody> 
  <tr> 
   <td> 
    <div style="clear:right; float:right; position:relative; margin:0px 0px 0.5em 0.5em; border:0px"> 
     <a href="http://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="http://upload.wikimedia.org/wikipedia/commons/6/66/Red-black_tree_insert_case_5.png" height="138" width="310" style="border:none; vertical-align:middle"></a> 
    </div> <p style="margin:0.4em 0px 0.5em; line-height:1.5em"><strong>情形5</strong>: 父节点<strong>P</strong>是红色而叔父节点<strong>U</strong>&nbsp;是黑色或缺少，新节点<strong>N</strong>&nbsp;是其父节点的左子节点，而父节点<strong>P</strong>又是其父节点<strong>G</strong>的左子节点。在这种情形下，我们进行针对祖父节点<strong>G</strong>&nbsp;的一次<a href="http://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>; 在旋转产生的树中，以前的父节点<strong>P</strong>现在是新节点<strong>N</strong>和以前的祖父节点<strong>G</strong>&nbsp;的父节点。我们知道以前的祖父节点<strong>G</strong>是黑色，否则父节点<strong>P</strong>就不可能是红色 (如果&nbsp;<strong>P</strong>&nbsp;和&nbsp;<strong>G</strong>&nbsp;都是红色就违反了性质4，所以&nbsp;<strong>G</strong>&nbsp;必须是黑色)。我们切换以前的父节点<strong>P</strong>和祖父节点<strong>G</strong>的颜色，结果的树满足性质4<sup><a href="http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_note-property4-2" style="text-decoration:none; color:rgb(11,0,128); white-space:nowrap" rel="nofollow">[3]</a></sup>。性质5<sup><a href="http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_note-property5-3" style="text-decoration:none; color:rgb(11,0,128); white-space:nowrap" rel="nofollow">[4]</a></sup>也仍然保持满足，因为通过这三个节点中任何一个的所有路径以前都通过祖父节点<strong>G</strong>&nbsp;，现在它们都通过以前的父节点<strong>P</strong>。在各自的情形下，这都是三个节点中唯一的黑色节点。</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 17]，因为上述所有调用都使用了[尾部递归][Link 18]。

### 删除 ###

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

在本文余下的部分中，**我们只需要讨论删除只有一个儿子的节点**(如果它两个儿子都为空，即均为叶子，我们任意将其中一个看作它的儿子)。如果我们删除一个红色节点（此时该节点的儿子将都为叶子节点），它的父亲和儿子一定是黑色的。所以我们可以简单的用它的黑色儿子替换它，并不会破坏属性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 的路径都比不通过它的路径少了一个黑色节点。因为这违反了属性 4，树需要被重新平衡。有几种情况需要考虑:

**情况 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);
    }

<table style=""> 
 <tbody> 
  <tr> 
   <td> 
    <div style="float:left; clear:left; position:relative; margin:0px 0.5em 0.5em 0px; border:0px"> 
     <a href="http://zh.wikipedia.org/wiki/File:Red-black_tree_delete_case_3.png" title="情况 3 示意图" style="text-decoration:none; color:rgb(11,0,128)" rel="nofollow"><img alt="情况 3 示意图" src="http://upload.wikimedia.org/wikipedia/commons/c/c7/Red-black_tree_delete_case_3.png" height="132" width="313" style="border:none; vertical-align:middle"></a> 
    </div> <p style="margin:0.4em 0px 0.5em; line-height:1.5em"><strong>情况 3:</strong>&nbsp;N 的父亲、S 和 S 的儿子都是黑色的。在这种情况下，我们简单的重绘 S 为红色。结果是通过S的所有路径，它们就是以前<em>不</em>通过 N 的那些路径，都少了一个黑色节点。因为删除 N 的初始的父亲使通过 N 的所有路径少了一个黑色节点，这使事情都平衡了起来。但是，通过 P 的所有路径现在比不通过 P 的路径少了一个黑色节点，所以仍然违反属性4。要修正这个问题，我们要从情况 1 开始，在 P 上做重新平衡处理。</p> </td> 
  </tr> 
 </tbody> 
</table>

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

<table style=""> 
 <tbody> 
  <tr> 
   <td> 
    <div style="float:left; clear:left; position:relative; margin:0px 0.5em 0.5em 0px; border:0px"> 
     <a href="http://zh.wikipedia.org/wiki/File:Red-black_tree_delete_case_5.png" title="情况 5 示意图" style="text-decoration:none; color:rgb(11,0,128)" rel="nofollow"><img alt="情况 5 示意图" src="http://upload.wikimedia.org/wikipedia/commons/3/30/Red-black_tree_delete_case_5.png" height="133" width="247" style="border:none; vertical-align:middle"></a> 
    </div> <p style="margin:0.4em 0px 0.5em; line-height:1.5em"><strong>情况 5:</strong>&nbsp;S 是黑色，S 的左儿子是红色，S 的右儿子是黑色，而 N 是它父亲的左儿子。在这种情况下我们在 S 上做右旋转，这样 S 的左儿子成为 S 的父亲和 N 的新兄弟。我们接着交换 S 和它的新父亲的颜色。所有路径仍有同样数目的黑色节点，但是现在 N 有了一个右儿子是红色的黑色兄弟，所以我们进入了情况 6。N 和它的父亲都不受这个变换的影响。</p> </td> 
  </tr> 
 </tbody> 
</table>

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=""> 
 <tbody> 
  <tr> 
   <td> 
    <div style="clear:right; float:right; position:relative; margin:0px 0px 0.5em 0.5em; border:0px"> 
     <a href="http://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="http://upload.wikimedia.org/wikipedia/commons/3/31/Red-black_tree_delete_case_6.png" height="143" width="299" style="border:none; vertical-align:middle"></a> 
    </div> <p style="margin:0.4em 0px 0.5em; line-height:1.5em"><strong>情况 6:</strong>&nbsp;S 是黑色，S 的右儿子是红色，而 N 是它父亲的左儿子。在这种情况下我们在 N 的父亲上做左旋转，这样 S 成为 N 的父亲和 S 的右儿子的父亲。我们接着交换 N 的父亲和 S 的颜色，并使 S 的右儿子为黑色。子树在它的根上的仍是同样的颜色，所以属性 3 没有被违反。但是，N 现在增加了一个黑色祖先: 要么 N 的父亲变成黑色，要么它是黑色而 S 被增加为一个黑色祖父。所以，通过 N 的路径都增加了一个黑色节点。</p> <p style="margin:0.4em 0px 0.5em; line-height:1.5em">此时，如果一个路径不通过 N，则有两种可能性:</p> 
    <ul style="line-height:1.5em; list-style-type:square; 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:0.4em 0px 0.5em; line-height:1.5em">在任何情况下，在这些路径上的黑色节点数目都没有改变。所以我们恢复了属性 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 18]，所以算法是[原地算法][Link 17]。此外，在旋转之后不再做递归调用，所以进行了恒定数目(最多 3 次)的旋转。 红黑树是很复杂的数据结构，在一般的情况下是用不到的，仅在大学中提及，在研究生时学到，希望大家能掌握红黑树

## 渐进边界的证明 ##

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

定义:

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

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

引理的证明(通过归纳高度):

基础: h(*v*) = 0

如果*v*的高度是零则它必定是 nil，因此 bh(*v*) = 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*有 ![2^\{bh(v)-1\}-1][2_bh_v_-1_-1] 个内部节点暗示了 h(![v'][v]) = k+1 的 ![v'][v]有![2^\{bh(v')\}-1][2_bh_v_-1 1] 个内部节点。

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

![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 \\geq 2^\{\{h(root) \\over 2\}\} - 1 \\leftrightarrow \\; \\log\{(n+1)\} \\geq \{h(root) \\over 2\} \\leftrightarrow \\; h(root) \\leq 2\\log\{(n+1)\}][n _geq 2_h_root_ _over 2_ - 1 _leftrightarrow _ _log_n_1_ _geq _h_root_ _over 2_ _leftrightarrow _ h_root_ _leq 2_log_n_1]

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

## 参见 ##

*  [AVL树][AVL 1]
 *  [B树][B]
 *  [dancing tree][]
 *  [伸展树][Link 20]
 *  [2-3-4树][2-3-4]
 *  [Treap][]

## 注释 ##

1.  **[^][Link 21]** 性质1. 节点是红色或黑色。
2.  **[^][Link 22]** 性质3. 所有叶子都是黑色。
3.  ^ [**3.0**][3.0] [**3.1**][3.1] [**3.2**][3.2] [**3.3**][3.3] [**3.4**][3.4] 性质4. 每个红色节点的两个子节点都是黑色。
4.  ^ [**4.0**][4.0] [**4.1**][4.1] [**4.2**][4.2] [**4.3**][4.3] [**4.4**][4.4] [**4.5**][4.5] 性质5. 从每个叶子到根的所有路径都包含相同数目的黑色节点。
5.  **[^][Link 23]** 性质2. 根是黑色。

## 引用 ##

*  [Mathworld: Red-Black Tree][Mathworld_ Red-Black Tree]
 *  [San Diego State University: CS 660: Red-Black tree notes][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][An applet _ quick explanation]
 *  [Red/Black Tree Demonstration][Red_Black Tree Demonstration]
 *  [An example][] (animated GIF, 200KB)
 *  [An example][An example 1] (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][RBT_ A SmallEiffel Red-Black Tree Library]
 *  [libredblack: A C Red-Black Tree Library][libredblack_ A C Red-Black Tree Library]
 *  [Red-Black Tree C++ Code][Red-Black Tree C_ Code]
 *  [Red-Black Trees][] by [Thomas Niemann][]
 *  [红黑树的介绍和实现][Link 24]

[Link 1]: http://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 2]: http://zh.wikipedia.org/wiki/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6
[Link 3]: http://zh.wikipedia.org/wiki/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84
[Link 4]: http://zh.wikipedia.org/wiki/%E5%85%B3%E8%81%94%E6%95%B0%E7%BB%84
[1972]: http://zh.wikipedia.org/wiki/1972%E5%B9%B4
[Link 5]: http://zh.wikipedia.org/wiki/%E9%B2%81%E9%81%93%E5%A4%AB%C2%B7%E8%B4%9D%E5%B0%94
[Robert Sedgewick]: http://zh.wikipedia.org/wiki/Robert_Sedgewick
[1978]: http://zh.wikipedia.org/wiki/1978%E5%B9%B4
[Link 6]: http://zh.wikipedia.org/w/index.php?title=%E7%AE%97%E6%B3%95%E5%88%86%E6%9E%90&action=edit&redlink=1
[O]: http://zh.wikipedia.org/wiki/%E5%A4%A7O%E7%AC%A6%E5%8F%B7
[AVL]: http://zh.wikipedia.org/wiki/AVL%E6%A0%91
[Link 7]: http://zh.wikipedia.org/w/index.php?title=%E5%8D%B3%E6%97%B6%E8%AE%A1%E7%AE%97&action=edit&redlink=1
[Link 8]: http://zh.wikipedia.org/wiki/%E8%AE%A1%E7%AE%97%E5%87%A0%E4%BD%95
[Link 9]: http://zh.wikipedia.org/wiki/%E5%87%BD%E6%95%B8%E5%BC%8F%E7%B7%A8%E7%A8%8B
[Link 10]: http://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 11]: http://zh.wikipedia.org/w/index.php?title=%E9%9B%86%E5%90%88%28%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6%29&action=edit&redlink=1
[2-3-4]: http://zh.wikipedia.org/wiki/2-3-4%E6%A0%91
[Link 12]: http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9
[Link 13]: http://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]: /images/20220607/de7de9438bae4db780fb2ca90d8508b6.png
[_An example of a red-black tree]: http://zh.wikipedia.org/wiki/File:Red-black_tree_example.svg
[Link 14]: http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91
[Link 15]: http://zh.wikipedia.org/wiki/%E6%A0%91%E6%97%8B%E8%BD%AC
[Link 16]: http://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
[1]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_note-property1-0
[2]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_note-property3-1
[3]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_note-property4-2
[4]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_note-property5-3
[C]: http://zh.wikipedia.org/wiki/C%E8%AF%AD%E8%A8%80
[5]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_note-property2-4
[Link 17]: http://zh.wikipedia.org/wiki/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95
[Link 18]: http://zh.wikipedia.org/wiki/%E5%B0%BE%E9%83%A8%E9%80%92%E5%BD%92
[Link 19]: http://zh.wikipedia.org/w/index.php?title=Binary_search_tree&action=edit&redlink=1
[2_bh_v_-1]: /images/20220607/f4c1818fee8b48ef871b13f67db941ba.png
[2_bh_v_-1 _ 2_0_-1 _ 1-1 _ 0]: /images/20220607/142c72fb73d8417c8c649d4e8ff95916.png
[2_bh_v_-1_-1]: http://upload.wikimedia.org/wikipedia/zh/math/e/f/0/ef0caf42b39fc2b2612d3aad0551a2d7.png
[v]: /images/20220607/1367744d137f4b5cb99e4559554ce7ba.png
[2_bh_v_-1 1]: /images/20220607/170737f0a6124653bcf625499a2bb837.png
[2_bh_v_-1_-1 1]: http://upload.wikimedia.org/wikipedia/zh/math/e/c/e/eceb5c4a4cc92b4f6296d47d755ed755.png
[2_bh_v_-1_-1 _ 2_bh_v_-1_-1 _ 1 _ 2_bh_v_-1]: /images/20220607/1e8c82d612af4f3eab6f5ce5fbc3e638.png
[n _geq 2_h_root_ _over 2_ - 1 _leftrightarrow _ _log_n_1_ _geq _h_root_ _over 2_ _leftrightarrow _ h_root_ _leq 2_log_n_1]: /images/20220607/79b87bc5544041b0a0814968382a1dde.png
[AVL 1]: http://zh.wikipedia.org/wiki/AVL%E6%A8%B9
[B]: http://zh.wikipedia.org/wiki/B%E6%A0%91
[dancing tree]: http://zh.wikipedia.org/w/index.php?title=Dancing_tree&action=edit&redlink=1
[Link 20]: http://zh.wikipedia.org/wiki/%E4%BC%B8%E5%B1%95%E6%A8%B9
[Treap]: http://zh.wikipedia.org/wiki/Treap
[Link 21]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_ref-property1_0-0
[Link 22]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_ref-property3_1-0
[3.0]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_ref-property4_2-0
[3.1]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_ref-property4_2-1
[3.2]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_ref-property4_2-2
[3.3]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_ref-property4_2-3
[3.4]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_ref-property4_2-4
[4.0]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_ref-property5_3-0
[4.1]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_ref-property5_3-1
[4.2]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_ref-property5_3-2
[4.3]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_ref-property5_3-3
[4.4]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_ref-property5_3-4
[4.5]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_ref-property5_3-5
[Link 23]: http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#cite_ref-property2_4-0
[Mathworld_ Red-Black Tree]: http://mathworld.wolfram.com/Red-BlackTree.html
[San Diego State University_ CS 660_ Red-Black tree notes]: http://www.eli.sdsu.edu/courses/fall95/cs660/notes/RedBlackTree/RedBlack.html#RTFToC2
[ISBN 0-07-013151-1]: http://zh.wikipedia.org/wiki/Special:%E7%BD%91%E7%BB%9C%E4%B9%A6%E6%BA%90/0070131511
[An applet _ quick explanation]: http://www.ibr.cs.tu-bs.de/lehre/ss98/audii/applets/BST/RedBlackTree-Example.html
[Red_Black Tree Demonstration]: http://gauss.ececs.uc.edu/RedBlack/redblack.html
[An example]: http://www.aisee.com/anim/maple.htm
[An example 1]: http://www.aisee.com/gallery/graph7.htm
[Another explanation]: http://ciips.ee.uwa.edu.au/%7Emorris/Year2/PLDS210/red_black.html
[Red-Black Tree Demonstration]: http://geocities.com/dmh2000/articles/code/red-blacktree.html
[David M. Howard]: http://zh.wikipedia.org/w/index.php?title=David_M._Howard&action=edit&redlink=1
[RBT_ A SmallEiffel Red-Black Tree Library]: http://efsa.sourceforge.net/archive/durian/red_black_tree.htm
[libredblack_ A C Red-Black Tree Library]: http://libredblack.sourceforge.net/
[Red-Black Tree C_ Code]: http://web.mit.edu/%7Eemin/www/source_code/cpp_trees/index.html
[Red-Black Trees]: http://ciips.ee.uwa.edu.au/%7Emorris/Year2/PLDS210/niemann/s_rbt.htm
[Thomas Niemann]: http://zh.wikipedia.org/w/index.php?title=Thomas_Niemann&action=edit&redlink=1
[Link 24]: http://saturnman.blog.163.com/blog/static/5576112010969420383/