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 while ( 1 ) { 0011 BinNodePosi<T> p = r ? r->parent : _hot; if ( !p ) return; //r的父亲 0012 BinNodePosi<T> s = ( r == p->lc ) ? p->rc : p->lc; //r的兄弟 0013 if ( IsBlack( s ) ) { //兄弟s为黑 0014 // s的红孩子t：若左、右孩子皆红，左者优先；皆黑时为NULL 0015 BinNodePosi<T> t = IsRed( s->lc ) ? s->lc : IsRed( s->rc ) ? s->rc : NULL; 0016 if ( t ) { //黑s有红孩子：BB-1 0017 RBColor oldColor = p->color; //备份原子树根节点p颜色 0018 // 以下，通过旋转重平衡，并将新子树的左、右孩子染黑 0019 BinNodePosi<T> b = rotateAt( t ); //旋转 0020 if ( b->lc ) { b->lc->color = RB_BLACK; b->lc->updateHeight(); } //左子 0021 if ( b->rc ) { b->rc->color = RB_BLACK; b->rc->updateHeight(); } //右子 0022 b->color = oldColor; b->updateHeight(); return; //子树新根继承原根的颜色 0023 } else { //黑s无红孩子 0024 s->color = RB_RED; s->height--; //s转红 0025 if ( IsRed( p ) ) { p->color = RB_BLACK; return; } //BB-2R：p转黑，但黑高度不变 0026 else { p->height--; r = p; } //BB-2B：p保持黑，但黑高度下降；继续上溯 0027 } 0028 } else { //兄弟s为红：BB-3 0029 s->color = RB_BLACK; p->color = RB_RED; //s转黑，p转红 0030 BinNodePosi<T> t = ( s == p->lc ) ? s->lc : s->rc; //取t与其父s同侧 0031 _hot = p; rotateAt( t ); //对t及其父亲、祖父做平衡调整 0032 //继续迭代，修正r处的双黑——此时的p已转红，故接下来只能是BB-1或BB-2R 0033 } 0034 } //while 0035 }