本文参考邓俊辉《数据结构（第3版）》

定义

  • (1) 树根始终为黑色
  • (2) 外部节点均为黑色
  • (3) 某节点若为红色，则其孩子节点必为黑色

  • (4) 从任一外部节点到根节点的沿途，黑节点的数目相等 （黑平衡）

    红黑树转换为4阶B树

    在红黑树中，每当遇到红节点，就将其向上移动合并到父节点（红节点不为根，且其父节点必为黑节点），即可转换为一颗4阶B树。
    图片.png

    插入与双红修正

    插入后，将新节点染色为红色，这时可能会破坏规则（3），需要进行双红修正。

    1. template <typename T> 
    2. BinNodePosi<T> RedBlack<T>::insert ( const T& e ) { //将e插入红黑树
    3.  BinNodePosi<T> & x = search ( e ); if ( x ) return x; //确认目标不存在（留意对_hot的设置）
    4.  x = new BinNode<T> ( e, _hot, NULL, NULL, 0 ); _size++; //创建红节点x：以_hot为父，黑高度0
    5.  BinNodePosi<T> xOld = x; solveDoubleRed ( x ); return xOld; //经双红修正后，即可返回
    6. }

    在下面，设插入节点为x，其父亲为p，爷爷为g，p的兄弟为u

    红红-黑修正

    x红，p红（g必黑），u黑。
    只需要进行一次局部的3-4旋转，再对节点重新染色。修正后黑高度恢复，且新生成的局部根节点为黑色，不需要继续调整，算法结束。
    图片.png3-4旋转：将任意失衡需要旋转的三个节点与他们的四颗子树进行调整，变成如下的平衡形式。
    图片.png

    1. // a,b,c为三个待调整节点，T0~T3为他们的四颗子树，均按照中序遍历顺序传入
    2. template <typename T>
    3. BinNodePosi<T> BST<T>::connect34(
    4.   BinNodePosi<T> a, BinNodePosi<T> b, BinNodePosi<T> c,
    5.   BinNodePosi<T> T0, BinNodePosi<T> T1, BinNodePosi<T> T2, BinNodePosi<T> T3
    6. ) {
    7.   a->lc = T0; if (T0) T0->parent = a;
    8.   a->rc = T1; if (T1) T1->parent = a; updateHeight(a);
    9.   c->lc = T2; if (T2) T2->parent = c;
    10.   c->rc = T3; if (T3) T3->parent = c; updateHeight(c);
    11.   b->lc = a; a->parent = b;
    12.   b->rc = c; c->parent = b; updateHeight(b);
    13.   return b; //该子树新的根节点
    14. }

    红红-红修正

    x为红色，p红色，u红色。
    从等效四阶B树的角度看，节点内有四个key，发生了上溢，为了便于修正，将g选择为向上溢出的节点，节点向上合并需要染成红色，于是把g的黑高度传给他的两个儿子，将p和u染成黑色，保持了黑高度不变。此时局部根节点为红色，需要继续向上进行双红修正，当局部根节点为整个RBTree的根节点时，将其染黑，树的黑高度+1。与B树一样，红黑树从根上长高。

    图片.png双红修正的代码

    1. template <typename T> void RedBlack<T>::solveDoubleRed ( BinNodePosi<T> x ) { //x当前必为红
    2.  if ( IsRoot ( *x ) ) //若已（递归）转至树根，则将其转黑，整树黑高度也随之递增
    3.     {  _root->color = RB_BLACK; _root->height++; return;  } //否则，x的父亲p必存在
    4.  BinNodePosi<T> p = x->parent; if ( IsBlack ( p ) ) return; //若p为黑，则可终止调整。否则
    5.  BinNodePosi<T> g = p->parent; //既然p为红，则x的祖父必存在，且必为黑色
    6.  BinNodePosi<T> u = uncle ( x ); //以下，视x叔父u的颜色分别处理
    8.  if ( IsBlack ( u ) ) { //u为黑色（含NULL）时 
    9.     if ( IsLChild ( *x ) == IsLChild ( *p ) ) //若x与p同侧（即zIg-zIg或zAg-zAg），则
    10.        p->color = RB_BLACK; //p由红转黑，x保持红
    11.     else //若x与p异侧（即zIg-zAg或zAg-zIg），则
    12.        x->color = RB_BLACK; //x由红转黑，p保持红
    13.     g->color = RB_RED; //g必定由黑转红
    14. ///// 以上虽保证总共两次染色，但因增加了判断而得不偿失
    15. ///// 在旋转后将根置黑、孩子置红，虽需三次染色但效率更高
    16.     BinNodePosi<T> gg = g->parent; //曾祖父（great-grand parent）
    17.     BinNodePosi<T> r = FromParentTo ( *g ) = rotateAt ( x ); //调整后的子树根节点
    18.     // FromParentTo获取从父节点指过来的指针，rotateAt自动进行3-4旋转
    20.     r->parent = gg; //与原曾祖父联接
    21.  } else { //若u为红色 //*DSA*/printf("  case RR-2:\n");
    22.     p->color = RB_BLACK; p->height++; //p由红转黑
    23.     u->color = RB_BLACK; u->height++; //u由红转黑
    24.     if ( !IsRoot ( *g ) ) g->color = RB_RED; //g若非根，则转红
    25.     solveDoubleRed ( g ); //继续调整g（类似于尾递归，可优化为迭代形式）
    26.  }
    27. }

    删除与双黑修正

    删除时保证删除节点无左孩子（否则将key与其直接后继交换，然后去删除其直接后继）
    此时记被删除节点为 x，其替代节点（右孩子）为 r，父节点为 p 。

若 x 为根，则用 r 替代 x ，并将 r 染黑，此时树的黑高度减1。

当 x 为红时（由于 x 无左孩子，根据定义其一定无右孩子，于是为叶子节点），直接删去由 r 来替代（即设为NULL，颜色为黑），不会对树的平衡性造成影响。

当 x 为黑色， r 为红色时，由 r 来继承 x 的黑高度，删去 x 由 r 来替代，并将 r 染黑，对数的黑高度无任何影响，删除结束。

当 x 与 r 均为黑色时，需要进行双黑调整。

  1. template <typename T> 
  2. bool RedBlack<T>::remove ( const T& e ) { //从红黑树中删除关键码e
  3.    BinNodePosi<T> & x = search ( e ); if ( !x ) return false; //确认目标存在（留意_hot的设置）
  4.    BinNodePosi<T> r = removeAt ( x, _hot ); if ( ! ( --_size ) ) return true; //实施删除
  5. // assert: _hot某一孩子刚被删除，且被r所指节点（可能是NULL）接替。以下检查是否失衡，并做必要调整
  6.    if ( ! _hot ) //若刚被删除的是根节点，则将其置黑，并更新黑高度
  7.       { _root->color = RB_BLACK; updateHeight ( _root ); return true; }
  8. // assert: 以下，原x（现r）必非根，_hot必非空
  9.    if ( BlackHeightUpdated ( *_hot ) ) return true; //若所有祖先的黑深度依然平衡，则无需调整
  10.    if ( IsRed ( r ) ) //否则，若r为红，则只需令其转黑
  11.       { r->color = RB_BLACK; r->height++; return true; }
  12. // assert: 以下，原x（现r）均为黑色
  13.    //*DSA*/printBinTree(_hot, 0, 0);
  14.    solveDoubleBlack ( r ); return true; //经双黑调整后返回
  15. }

图片.png
图中w必为NULL（黑色）

双黑修正时，原黑节点x的兄弟必然非空（否则不满足黑平衡），将其记作s；x 的父亲记作p，其颜色不确定。

case1：黑黑-黑带红修正

x、r 均为黑，s 也为黑，且 s 有红色的孩子 t。
图片.png
由于存在调整时递归向上传递问题，r 可能不为 NULL

按照B树来看，x 无左孩子，且右孩子为黑色，其为一个只有一个key的节点，将 x 删除后B树发生下溢，若 其兄弟 s 有红色孩子，则按照B树来看该兄弟节点的key足够借，故从兄弟节点借一个关键字。
此时按照红黑树来看，相当于在 t 、s、 p 之间做了一次3-4旋转。旋转后，由于 s 被借走，其所属B树节点可能只剩下一个红key，由于此时B树的高度并不应该改变，故需要让 t 继承 s 的黑高度，将其染黑，s 则继承原来 p 的颜色，p 继承原属于 x 的黑色。

对于 t 为 s 的右孩子，处理方式类似，在3-4旋转后统一进行染色，可以避免复杂的判断。

黑黑-黑不带红

当 s 没有红孩子时，从B树的角度来看，此时属于下溢且兄弟不够借，依据 p 的颜色又可分为2种情形。

case2：p 为红

此时在B树中，p所在的节点必然还有一个黑色的key，于是将p借下来把，将 x 与 s 粘合在一起，之后再去删除 x
由于 p 所在节点还有其他key，故借走 p 不会引起再一次的下溢，该过程不需要递归执行。
粘合后的 s、p、x 节点的key的颜色为 黑、红、黑，并不符合红黑树向B树转换的规定（只有红节点向上合并），需要染色为 红、黑、红，之后再去删除 x 节点和 x 左孩子（NULL）。
该过程体现在红黑树上就是将 p 染黑，s 染红。
图片.png

case3：p 为黑

此时按照对应B树来看，属于下溢出且兄弟不够借，父节点也只有一个key的情景。
此时的操作方式与前面类似，需要将 s 染红，p 保持黑色，这时按照B树来看，父节点只有一个key，借走后会再一次下溢，这也是红黑树删除时唯一需要递归调整的地方。此时递归向上时，相当于虚拟一个新的 x 节点替代 p 节点原来的位置，同时令其左子树为空，右孩子为 p。
图片.png

case4：黑黑-红修正

最后一种情况，考虑 s 为红色，此时 s 一定有两个黑孩子，且 p 一定为黑色，从B树的角度考虑，交换 s 与 p 的颜色对B树没有任何影响，反应到红黑树上，相当于以 p 点为轴做一次左旋（对称的情景下做右旋），并交换 s 与 p 的颜色。这样做不能解决双黑缺陷，但是转换后有一个新的兄弟 s’ ，且一定是黑色，并且 p 一定是红色，此时将变成 case1或 case2，再进行一次调整即可。
case4的处理存在一些技巧性的操作，个人想不到怎么从B树的角度来看待。
图片.png

双黑修正代码

  1. template <typename T> 
  2. void RedBlack<T>::solveDoubleBlack ( BinNodePosi<T> r ) {
  3.    BinNodePosi<T> p = r ? r->parent : _hot; if ( !p ) return; //r的父亲
  4.    BinNodePosi<T> s = ( r == p->lc ) ? p->rc : p->lc; //r的兄弟
  5.    if ( IsBlack ( s ) ) { //兄弟s为黑
  6.       BinNodePosi<T> t = NULL; //s的红孩子（若左、右孩子皆红，左者优先；皆黑时为NULL）
  7.       if ( IsRed ( s->rc ) ) t = s->rc; //右子
  8.       if ( IsRed ( s->lc ) ) t = s->lc; //左子
  9.       if ( t ) { // case1：黑黑-黑带红
  10.           RBColor oldColor = p->color; //备份原子树根节点p颜色，并对t及其父亲、祖父
  11.       // 以下，通过旋转重平衡，并将新子树的左、右孩子染黑
  12.          BinNodePosi<T> b = FromParentTo ( *p ) = rotateAt ( t ); //以t的爷爷为总轴进行3-4旋转
  13.          if ( HasLChild ( *b ) ) { b->lc->color = RB_BLACK; updateHeight ( b->lc ); } //左子
  14.          if ( HasRChild ( *b ) ) { b->rc->color = RB_BLACK; updateHeight ( b->rc ); } //右子
  15.          b->color = oldColor; updateHeight ( b ); //新子树根节点继承原根节点的颜色
  17.       } else { //case2、3：黑黑-黑无红孩子
  18.          s->color = RB_RED; s->height--; //s转红
  19.          if ( IsRed ( p ) ) { //case2：p为红
  20.             p->color = RB_BLACK; //p转黑，但黑高度不变
  21.          } else { //case3：p为黑
  22.             p->height--; //p保持黑，但黑高度下降
  23.             solveDoubleBlack ( p ); //递归上溯
  24.          }
  25.       }
  26.    } else { //case4：黑黑-红
  27.       s->color = RB_BLACK; p->color = RB_RED; //s转黑，p转红
  28.       BinNodePosi<T> t = IsLChild ( *s ) ? s->lc : s->rc; //取t与其父s同侧
  29.       _hot = p; FromParentTo ( *p ) = rotateAt ( t ); //对t及其父亲、祖父做平衡调整
  30.       solveDoubleBlack ( r ); //继续修正r处双黑——此时的p已转红，故后续只能是BB-1或BB-2R
  31.    }
  32. }