0001 /****************************************************************************************** 0002 * RedBlack双黑调整算法:解决节点x与被其替代的节点均为黑色的问题 0003 * 分为三大类共四种情况: 0004 * BB-1 :2次颜色翻转,2次黑高度更新,1~2次旋转,不再递归 0005 * BB-2R:2次颜色翻转,2次黑高度更新,0次旋转,不再递归 0006 * BB-2B:1次颜色翻转,1次黑高度更新,0次旋转,需要递归 0007 * BB-3 :2次颜色翻转,2次黑高度更新,1次旋转,转为BB-1或BB2R 0008 ******************************************************************************************/ 0009 template <typename T> void RedBlack<T>::solveDoubleBlack( BinNodePosi<T> r ) { 0010 BinNodePosi<T> p = r ? r->parent : _hot; if ( !p ) return; //r的父亲 0011 BinNodePosi<T> s = ( r == p->lc ) ? p->rc : p->lc; //r的兄弟 0012 if ( IsBlack( s ) ) { //兄弟s为黑 0013 BinNodePosi<T> t = NULL; //s的红孩子(若左、右孩子皆红,左者优先;皆黑时为NULL) 0014 if ( IsRed( s->rc ) ) t = s->rc; //右子 0015 if ( IsRed( s->lc ) ) t = s->lc; //左子 0016 if ( t ) { //黑s有红孩子:BB-1 0017 RBColor oldColor = p->color; //备份原子树根节点p颜色,并对t及其父亲、祖父 0018 // 以下,通过旋转重平衡,并将新子树的左、右孩子染黑 0019 BinNodePosi<T> b = FromParentTo( *p ) = rotateAt( t ); //旋转 0020 if ( HasLChild( *b ) ) { b->lc->color = RB_BLACK; b->lc->updateHeight(); } //左子 0021 if ( HasRChild( *b ) ) { b->rc->color = RB_BLACK; b->rc->updateHeight(); } //右子 0022 b->color = oldColor; b->updateHeight(); //新子树根节点继承原根节点的颜色 0023 } else { //黑s无红孩子 0024 s->color = RB_RED; s->height--; //s转红 0025 if ( IsRed( p ) ) { // BB-2R 0026 p->color = RB_BLACK; //p转黑,但黑高度不变 0027 } else { //BB-2B 0028 p->height--; //p保持黑,但黑高度下降 0029 solveDoubleBlack( p ); //递归上溯 0030 } 0031 } 0032 } else { //兄弟s为红:BB-3 0033 s->color = RB_BLACK; p->color = RB_RED; //s转黑,p转红 0034 BinNodePosi<T> t = IsLChild( *s ) ? s->lc : s->rc; //取t与其父s同侧 0035 _hot = p; FromParentTo( *p ) = rotateAt( t ); //对t及其父亲、祖父做平衡调整 0036 solveDoubleBlack( r ); //继续修正r处双黑——此时的p已转红,故后续只能是BB-1或BB-2R 0037 } 0038 }