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 ( !HasLChild ( *x ) ) //若*x的左子树为空,则可 0011 succ = x = x->rc; //直接将*x替换为其右子树 0012 else if ( !HasRChild ( *x ) ) //若右子树为空,则可 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 release ( w->data ); release ( w ); return succ; //释放被摘除节点,返回接替者 0023 } //release()负责释放复杂结构,与算法无直接关系,具体实现详见代码包