BST的概念
BST,又叫平衡二叉树,是一种循关键码访问的二叉树,并且要求保持顺序性,即任一节点不小于其左后代,不大于其右后代(注意是后代,不是孩子)。BST的顺序性使得其中序遍历序列一定是单调非降的。
BST的查找算法
BinNodePos(T) BST_Search1(BinNodePos(T)&v,const T& e,BinNodePos(T)hot) { if(v==null||v->data=e){return v;}//递归基 hot=v; //当前非空节点 BinNodePos(T)next=(v->data>e)?v->lc:v->rc;//根据当前节点的大小确定下一次搜索的转向 return BST_Search1(next,e,hot); //递归查找 }上述是查找算法的递归实现,接口语义是hot指向被查找到的那个节点的父亲,若在树中没找到该节点,则hot为最后一个试图转向的节点。
BinNodePos(T) BST_Search2(BinNodePos(T)&v,const T& e,BinNodePos(T)hot) { while(true) { if(v->data==e||v==NULL)return v; else if(v->data>e) { hot=v;v=v->lc; } else { hot=v;v=v->rc; } } return v; }BST的插入算法
得益于BST查找算法良好的语义接口,BST的插入算法很容易实现。
template<typename T> BinNodePos(T)BST<T>::insert(const T &e) { BinNodePos(T) hot; BinNodePos(T) &x=BST_Search(_root,e,hot); if(!x) { x=new BinNode<T>(e,hot); _size++; updateHeightAbove(x) } return x; }BST的删除
BST的删除有些复杂,分为两种情况:
(1)删除的节点没有左孩子或者是没有右孩子,此时直接把另一个非空的子节点取代删除节点即可。
(2)删除的节点既有左孩子,也有右孩子
为了保证BST的顺序性,此时应该用待删除节点的下一个节点(指中序序列中)取代待删除节点,并且调整节点间的父子关系。
BinNodePos(T) BST_Remove(BinNodePos(T)&x,BinNodePos(T)&hot) { BinNodePos(T)w=x; BinNodePos(T)succ=null; if(!x->HasLChild)succ=w->rc; else if(!x->HasRChild)succ=w->lc; else { BinNOdePos(T)pc=w->rc; while(true)//迭代找到待删除节点的下一个节点 { if(pc==null) { succ=pc->parent; } pc=pc->lc; } } swap(w->data,succ->data);//交换待删除节点和下一个节点的数据; if(succ->parent==w)//如果待删除节点是下一个节点的父亲(当待删除节点的右子节点没有左子时) { w->rc=succ->rc; } else//非第一种情况 { succ->parent->lc=succ->rc;// succ->rc->parent=succ->parent; } hot=w->parent;//hot为待删除节点之父 if(succ)succ->parent=hot; Release(x); Rease(x->data); return succ; }