BST的概念，以及查找，插入，删除算法

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;
}