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