0001 template <typename T> bool RedBlack<T>::remove ( const T& e ) { //从红黑树中删除关键码e 0002 BinNodePosi(T) & x = search ( e ); if ( !x ) return false; //确认目标存在(留意_hot的设置) 0003 BinNodePosi(T) r = removeAt ( x, _hot ); if ( ! ( --_size ) ) return true; //实施删除 0004 // assert: _hot某一孩子刚被删除,且被r所指节点(可能是NULL)接替。以下检查是否失衡,并做必要调整 0005 if ( ! _hot ) //若刚被删除的是根节点,则将其置黑,并更新黑高度 0006 { _root->color = RB_BLACK; updateHeight ( _root ); return true; } 0007 // assert: 以下,原x(现r)必非根,_hot必非空 0008 if ( BlackHeightUpdated ( *_hot ) ) return true; //若所有祖先的黑深度依然平衡,则无需调整 0009 if ( IsRed ( r ) ) //否则,若r为红,则只需令其转黑 0010 { r->color = RB_BLACK; r->height++; return true; } 0011 // assert: 以下,原x(现r)均为黑色 0012 solveDoubleBlack ( r ); return true; //经双黑调整后返回 0013 } //若目标节点存在且被删除,返回true;否则返回false