0001 /******************************************************************************************
0002  * RedBlack双红调整算法：解决节点x与其父均为红色的问题。分为两大类情况：
0003  *    RR-1：2次颜色翻转，2次黑高度更新，1~2次旋转，不再递归
0004  *    RR-2：3次颜色翻转，3次黑高度更新，0次旋转，需要递归
0005  ******************************************************************************************/
0006 template <typename T> void RedBlack<T>::solveDoubleRed( BinNodePosi<T> x ) { // x当前必为红
0007    if ( IsRoot( *x ) ) //若已（递归）转至树根，则将其转黑，整树黑高度也随之递增
0008       {  _root->color = RB_BLACK; _root->height++; return;  } //否则，x的父亲p必存在
0009    BinNodePosi<T> p = x->parent; if ( IsBlack( p ) ) return; //若p为黑，则可终止调整。否则
0010    BinNodePosi<T> g = p->parent; //既然p为红，则x的祖父必存在，且必为黑色
0011    BinNodePosi<T> u = uncle( x ); //以下，视x叔父u的颜色分别处理
0012    if ( IsBlack( u ) ) { // u为黑色（含NULL）时
0013       if ( IsLChild( *x ) == IsLChild( *p ) ) //若x与p同侧（即zIg-zIg或zAg-zAg），则
0014          p->color = RB_BLACK; //p由红转黑，x保持红
0015       else //若x与p异侧（即zIg-zAg或zAg-zIg），则
0016          x->color = RB_BLACK; //x由红转黑，p保持红
0017       g->color = RB_RED; //g必定由黑转红
0018 ///// 以上虽保证总共两次染色，但因增加了判断而得不偿失
0019 ///// 在旋转后将根置黑、孩子置红，虽需三次染色但效率更高
0020       BinNodePosi<T> gg = g->parent; //曾祖父（great-grand parent）
0021       BinNodePosi<T> r = FromParentTo( *g ) = rotateAt( x ); //调整后的子树根节点
0022       r->parent = gg; //与原曾祖父联接
0023    } else { //若u为红色
0024       p->color = RB_BLACK; p->height++; //p由红转黑
0025       u->color = RB_BLACK; u->height++; //u由红转黑
0026       g->color = RB_RED; //在B-树中g相当于上交给父节点的关键码，故暂标记为红
0027       solveDoubleRed( g ); //继续调整：若已至树根，接下来的递归会将g转黑（尾递归，不难改为迭代）
0028    }
0029 }