0001 /******************************************************************************************
0002  * BST节点删除算法：删除位置x所指的节点（全局静态模板函数，适用于AVL、Splay、RedBlack等各种BST）
0003  * 目标x在此前经查找定位，并确认非NULL，故必删除成功；与searchIn不同，调用之前不必将hot置空
0004  * 返回值指向实际被删除节点的接替者，hot指向实际被删除节点的父亲——二者均有可能是NULL
0005  ******************************************************************************************/
0006 template <typename T>
0007 static BinNodePosi<T> removeAt( BinNodePosi<T>& x, BinNodePosi<T>& hot ) {
0008    BinNodePosi<T> w = x; //实际被摘除的节点，初值同x
0009    BinNodePosi<T> succ = NULL; //实际被删除节点的接替者
0010    if ( !x->lc ) //若x的左子树为空，则可
0011       succ = x = x->rc; //直接将x替换为其右子树
0012    else if ( !x->rc ) //若右子树为空，则可
0013       succ = x = x->lc; //对称地处理——注意：此时succ != NULL
0014    else { //若左右子树均存在，则选择x的直接后继作为实际被摘除节点，为此需要
0015       w = w->succ(); //（在右子树中）找到x的直接后继w
0016       swap( x->data, w->data ); //交换x和w的数据元素
0017       BinNodePosi<T> u = w->parent;
0018       ( ( u == x ) ? u->rc : u->lc ) = succ = w->rc; //隔离节点w
0019    }
0020    hot = w->parent; //记录实际被删除节点的父亲
0021    if ( succ ) succ->parent = hot; //并将被删除节点的接替者与hot相联
0022    delete w; return succ; //释放被摘除节点，返回接替者
0023 }