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 if ( !IsRoot ( *g ) ) g->color = RB_RED; //g若非根,则转红 0027 solveDoubleRed ( g ); //继续调整g(类似于尾递归,可优化为迭代形式) 0028 } 0029 }