定义

二叉排序树(Binary Sort Tree)或者是一棵空树;或者是具有以下性质的二叉树：
1.若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值;
2.若它的右子树不为空，则右子树上所有结点的值均小于它的根结点的值;
3.它的左右子树也分别为二叉排序树;

二叉排序树又称二叉查找树，它的查找过程与次优二叉树类似。

二叉排序树的查找

Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p){
   //若查找不成功p指向最后一个结点，f为其双亲，返回FALSE
   //若查找成功p指向该结点，返回TRUE 
    if(!T){p=f; return FALSE;}
    else if EQ(key,T.data.key) {p=T; return TRUE;}
    else if LT(key,T.data.key){ return SearchBST(T.lchild,key,T,p);}
    else return SearchBST(T.rchild,key,T,p);
}

二叉排序树的插入

Status InsertBST(BiTree T,KeyType key){
    //若插入成功返回TRUE，否则FALSE
    BiTree f,p;
    if(SearchBST(T,key,f,p)) return FALSE;
    else { 
        s=(BiTree)malloc(sizeof(BiNode));
        s->data=key; 
        s->lchild=s->rchild=NULL;
        if(!p) T=s;
        else if LT(key,p->data.key) p->lchild=s;
        else p->rchild=s;
        return TRUE;
    }
}

二叉排序树的删除

普通的二叉树删去一个结点变为森林，没有任何意义，而对于二叉排序树来说删去一个结点只要保证其排序特性即可。
综合来说有三种情形：
1.左右子树均为空，则直接删去结点即可。
2.左子树或者右子树不为空，则用其左子树或者右子树代替即可。
3.左右子树均不为空，则不能简单的处理：
1.用其左子树或者右子树代替，并将原来的左子树或右子树成为其前驱的左子树或右子树。
2.用其直接前驱或者直接后继代替;当用其前驱代替时，将直接前驱的前驱成为直接前驱的双亲的右子树;当用直接后继代替时，将直接后继的后继成为直接后继的双亲的左子树。

void DeleteBST(BiTree &p){
    if(p->lchild==NULL){
        q=p;p=p->rchild;free(q);
    }
    else if(p->rchild==NULL){
        q=p;p=p->lchild;free(q);
    }
    else{
        q=p;p=p->lchild;
        while(p->rchild){
           p=p->rchild;
        }
        q->data=p->data;
        q=p;
        p=p->lchild;
        free(q);
    }//if
}//DeleteBST

二叉排序树的性能分析

二叉查找树查找关键字的过程即为从根结点到该关键字记录结点的路径，查找关键字的个数是路径长度+1，并且不超过树的深度。

在随机情况下，二叉排序树的平均查找长度和logn是等数量级的。

平衡二叉树

定义

平衡二叉树(Balanced Binary Tree或Height-Balanced Tree)又称为AVL树。它或者是一棵空树，或者是具有以下性质的二叉树：
它的左子树和右子树都是平衡二叉树，且左右子树深度只差的绝对值不超过1.

将二叉树结点的平衡因子BF(Balance Factor)定义为该结点左子树深度减去它的右子树深度。

算法

#define LH +1
#define EH 0
#define RH -1
typedef struct{
    ElemType data;
    int bf;
    struct BSTNode *lchild,*rchild;
}BBSTNode,*BBSTree;

void Left_Rotate(BBSTree &p){
    q=p;
    p=p->rchild;
    q->rchild=p->lchild;
    p->lchild=q;
}

void Right_Rotate(BBSTree &p){
    q=p;
    p=p->lchild;
    q->lchild=p->rchild;
    p->rchild=q;
}
void LeftBalance(BBSTree &T){
    switch(T->rchild->bf)
        case RH:
              T->bf=0;
             break;
        case LH:
             Right_Rotate(T->rchild);
            break;
    }//switch
     Left_Rotate(T);
     T->bf=0;
}
void RightBalance(BBSTree &T){
    switch(T->lchild->bf)
        case LH:
              T->bf=0;
            break;
        case RH:
            Left_Rotate(T->lchild);
            break;
    }//switch
     Right_Rotate(T);
     T->bf=0;

}
Status InsertAVT(BBSTree &T,ElemType e,Boolean &taller){
//若平衡二叉树中不存在和e相同的关键字记录，则插入并返回1,否则返回0
//若因插入而使二叉排序树失去平衡，则taller=TRUE;
    if(!T){
        T=(BBSTree)malloc(sizeof(BBSTNode));T->data=e;
        T->lchild=T->rchild=NULL;taller=TRUE;return 1;
    }
    else if EQ(e,T->data) {
        taller=FALSE;
        return 0;
    }
    else if LT(e,T->data){
        if(InsertAVL(T->lchild,e,taller))
            if(taller)
                switch(T->bf){
                    case LH:
                        RightBalance(T);T->bf=0;taller=FALSE;
                        break;
                    case EH:
                        T->bf=LH;taller=TRUE:
                        break;
                    case RH:
                        T->bf=EH;taller=FALSE;
                        break;
        }//switch
    }//if
    else if RT(e,T->data){
        if(InsertAVL(T->lchild,e,taller))
            if(taller)
                switch(T->bf){
                    case LH:
                        T->bf=EH;taller=FALSE;
                        break;
                    case EH:
                        T->bf=RH;taller=TRUE:
                        break;
                    case RH:
                        LeftBalance(T);T->bf=0;taller=FALSE;
                        break;
         }//switch
    }//if
}//InsertAVL

平衡二叉树的性能分析

与二叉排序树相同