0001 template <typename T> bool Splay<T>::remove( const T& e ) { //从伸展树中删除关键码e 0002 if ( !_root || ( e != search( e )->data ) ) return false; //若目标存在,则伸展至根 0003 BinNodePosi<T> L = _root->lc, R = _root->rc; release( _root ); //记下左、右子树L、R后,释放之 0004 if ( !R ) { //若R空,则 0005 if ( L ) L->parent = NULL; _root = L; //L即是余树 0006 } else { //否则 0007 _root = R; R->parent = NULL; search( e ); //在R中再次查找e:注定失败,但其中的最小节点必 0008 if (L) L->parent = _root; _root->lc = L; //伸展至根(且无左孩子),故可令其以L作为左子树 0009 } 0010 if ( --_size ) _root->updateHeight(); return true; //更新规模及树高,报告删除成功 0011 }