【查找结构4】红黑树 [RBT]

大部分转载： http://yanglongylj.blog.163.com/blog/static/563834532009113021438417/

红黑树的性质与定义

红黑树(red-black tree) 是一棵满足下述性质的二叉查找树：

1. 每一个结点要么是红色，要么是黑色。

2. 根结点是黑色的。

3. 所有叶子结点都是黑色的（实际上都是Null指针，下图用NIL表示）。叶子结点不包含任何关键字信息，所有查询关键字都在非终结点上。

4. 每个红色结点的两个子节点必须是黑色的。换句话说：从每个叶子到根的所有路径上不能有两个连续的红色结点

5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点

黑深度 —— 从某个结点x出发(不包括结点x本身)到叶结点(包括叶子结点)的路径上的黑结点个数,称为该结点x的黑深度,记为bd(x),根结点的黑深度就是该红黑树的黑深度。叶子结点的黑深度为0。 比如：上图bd(13)=2，bd(8)=2，bd(1)=1

内部结点 —— 红黑树的非终结点

外部节点 —— 红黑树的叶子结点

红黑树相关定理

1. 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

      根据上面的性质5我们知道上图的红黑树每条路径上都是3个黑结点。因此最短路径长度为2(没有红结点的路径)。再根据性质4(两个红结点不能相连)和性质1，2(叶子和根必须是黑结点)。那么我们可以得出：一条具有3个黑结点的路径上最多只能有2个红结点(红黑间隔存在)。也就是说黑深度为2（根结点也是黑色）的红黑树最长路径为4，最短路径为2。 从这一点我们可以看出红黑树是 大致平衡的。 (当然比平衡二叉树要差一些，AVL的平衡因子最多为1)

2. 红黑树的树高(h)不大于两倍的红黑树的黑深度(bd)，即h<=2bd

      根据定理1，我们不难说明这一点。bd是红黑树的最短路径长度。而可能的最长路径长度(树高的最大值)就是红黑相间的路径，等于2bd。因此h<=2bd。

3. 一棵拥有n个内部结点(不包括叶子结点)的红黑树的树高h<=2log(n+1)

      下面我们首先证明一颗有n个内部结点的红黑树满足n>=2^bd-1。这可以用数学归纳法证明，施归纳于树高h。当h=0时，这相当于是一个叶结点，黑高度bd为0，而内部结点数量n为0，此时0>=2^0-1成立。假设树高h<=t时，n>=2^bd-1成立，我们记一颗树高 为t+1的红黑树的根结点的左子树的内部结点数量为nl，右子树的内部结点数量为nr，记这两颗子树的黑高度为bd'（注意这两颗子树的黑高度必然一 样），显然这两颗子树的树高<=t，于是有nl>=2^bd'-1以及nr>=2^bd'-1，将这两个不等式相加有nl+nr>=2^(bd'+1)-2，将该不等式左右加1，得到n>=2^(bd'+1)-1，很显然bd'+1>=bd，于是前面的不等式可以 变为n>=2^bd-1，这样就证明了一颗有n个内部结点的红黑树满足n>=2^bd-1。

        在根据定理2，h<=2bd。即n>=2^(h/2)-1，那么h<=2log(n+1)

         从这里我们能够看出，红黑树的查找长度最多不超过2log(n+1)，因此其查找时间复杂度也是O(log N)级别的。

红黑树的操作

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

插入操作

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

假设新加入的结点为N，父亲结点为P，叔父结点为Ui(叔父结点就是一些列P的兄弟结点)，祖父结点G(父亲结点P的父亲)。下面会给出每一种情况，我们将使用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位于树的根上，没有父结点。

       此时很简单，我们将直接插入一个黑结点N（满足性质2），其他情况下插入的N为红色（原因在前面提到了）。

     void insert_case1(node n) {
     if (n->parent == NULL)
         n->color = BLACK;
     else
         insert_case2(n); //插入情况2
 }
  

情况2. 新结点N的父结点P是黑色。

       在这种情况下，我们插入一个红色结点N(满足性质5)。

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

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

情况3.如果父节点P和叔父节点U二者都是红色。

        如下图，因为新加入的N结点必须为红色，那么我们可以将父结点P(保证性质4)，以及N的叔父结点U(保证性质5)重新绘制成黑色。如果此时祖父结点G是根，则结束变化。如果不是根，则祖父结点重绘为红色(保证性质5)。但是，G的父亲也可能是红色的，为了保证性质4。我们把G递归当做新加入的结点N在进行各种情况的重新检查。

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

  

注意：在情形4和5下，我们假定父节点P 是祖父结点G 的左子节点。如果它是右子节点，情形4和情形5中的左和右应当对调。

情况4. 父节点P是红色而叔父节点U是黑色或缺少; 另外，新节点N是其父节点P的右子节点，而父节点P又是祖父结点G的左子节点。

       如下图, 在这种情形下，我们进行一次左旋转调换新节点和其父节点的角色（与AVL树的左旋转相同）; 这导致某些路径通过它们以前不通过的新节点N或父节点P中的一个，但是这两个节点都是红色的，所以性质5没有失效。但目前情况将违反性质4，所以接着，我们按下面的情况5继续处理以前的父节点P。

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

情况5. 父节点P是红色而叔父节点U 是黑色或缺少，新节点N 是其父节点的左子节点，而父节点P又是祖父结点的G的左子节点。

       如下图： 在这种情形下，我们进行针对祖父节点P 的一次右旋转; 在旋转产生的树中，以前的父节点P现在是新节点N和以前的祖父节点G 的父节点。我们知道以前的祖父节点G是黑色，否则父节点P就不可能是红色。我们切换以前的父节点P和祖父节点G的颜色，结果的树满足性质4[3]。性质 5[4]也仍然保持满足，因为通过这三个节点中任何一个的所有路径以前都通过祖父节点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(grandparent(n));
     } else {
         /* Here, n == n->parent->right && n->parent == grandparent(n)->right */
         rotate_left(grandparent(n));
     }
 }
  

删除操作

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

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

需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候，这是一种复杂的情况。我们首先把要删除的节点替换为它的儿子。出于方便，称呼这个儿子为 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);
}
  

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

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