[数据结构与算法]浅谈二叉排序树（BST）

1.二叉排序树的定义

二叉排序树（也称二叉查找树）或者是一棵空树，或者是具有下列特性的二叉树：

1. 若左子树非空，则左子树上所有结点的值均小于根结点的值。
2. 若右子树非空，则右子树上所有结点的值均大于根结点的值。
3. 左右子树也分别是一棵二叉排序树。

根据二叉排序树的定义，左子树结点值<根结点值<右子树结点值，所以，对二叉查找树进行中序遍历可以得到一个递增的有序序列。

2.二叉查找树的查找

????????二叉查找树的查找是从根结点开始，沿某个分支逐层向下比较的过程，若二叉排序树非空，先将给定值与根结点的关键字比较，若相等，则查找成功，若不等，如果小于根结点的关键字，则在根结点的左子树上查找，否则在根结点的右子树上查找，这显然是一个递归的过程。

?二叉排序树的非递归查找算法：

BSTNode *BST_Search(BiTree T,ElemType key){
    while(T!=NULL&&key!=T->data){    //若树空或者等于根结点值，则结束循环
        if(key<T->data) T=T->lchild;    //小于，则在左子树上查找
        else T=T->rchild;
    }
    return T;
}

同理，递归算法如下：

BSTNode *BST_Search(BiTree T,ElemType key){
    if(T==null){
        return null;    //如果树为空，则返回null
    }
    if(key == T->data)    //如果key与根结点的值相等
        return T;
    if(key<T->data)
        return BST_Search(T->lchild,key);
    if(key>T->data)
        return BST_Search(T->rchild,key);
}

3.二叉排序树的插入：

????????二叉排序树作为一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找过程中，当书不存在关键字值等于给定值的特点时再进行插入的。

????????插入结点的过程如下：若原二叉排序树为空，则直接插入该结点，否则，若关键字k小于根结点值，则插入到左子树，若关键字k大于根结点值，则插入到右子树，插入的结点一定是一个新添加的叶节点，且是查找失败时查找路径上的访问的最后一个结点的左孩子或右孩子，过程如下图所示：

int BST_Insert(BiTree &T,KeyType k){
    if(T==NULL){
        T=(BiTree)malloc(sizeof(BSTNode));
        T->key=k;
        T->lchild=T->rchild=NULL;
        return 1;    //返回1，插入成功
    }
    else if(k==T->key){    //树中存在相同关键字的结点，插入失败
        return 0;
    }
    else if(k<T->key){
        return BST_Insert(T->lchild,k);
    }
    else{
        return BST_Insert(T->rchild,k);
    }
}

?4.二叉排序树的构造：

void Creat_BST(BiTree &T,KeyType str[],int n){
    T=NULL;    //初始时T为空树
    int i=0;
    while(i<n){    //依次将每个关键字插入到二叉排序树中
        BST_Insert(T,str[i]);
        i++;
    }
}

5.二叉排序树的删除

? ? ? ? 在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表重新连接起来，同时确保二叉排序树的性质不会丢失。

1. ?若被删除的结点z是叶子结点，则直接删除，不会破坏二叉排序树的性质。
2. 若结点z只有一棵左子树或是右子树，则让z的子树成为z父结点的子树，替代z的位置。
3. 若结点z有左、右两棵子树，则令z的直接后继或直接前驱替代z，然后从二叉排序树中删去这个直接后继（或者直接前驱），这样就转换成了第一或第二种情况。?

?6.二叉排序树的查找效率分析

? ? ? ? 二叉排序树的查找效率，主要取决于树的高度，若二叉排序树的左、右子树的高度之差的绝对值不超过1，则这样的二叉排序树称为平衡二叉树，它的平均查找长度为O(log2n)。若二叉排序树是一个只有左（右）孩子的单支树（类似于有序的单链表），则其平均查找长度为O(n)。

? ? ? ? 在最坏情况下，即构造二叉排序树的输入序列是有序的，则会形成一个倾斜的单支树，此时二叉排序树的性能显著变坏，树的高度也增加为元素个数n

? ? ? ? 在等概率下，上图的查找成功的平均查找长度为：

? ? ? ? ASL = (1+2*2+3*4+4*2)/10 = 2.5

?从查找过程看，二叉排序树与二分查找相似，就平均时间性能而言，二叉排序树上的查找和二分查找差不多，但二分查找的判定树唯一，而二叉排序树的查找不唯一，相同的关键字其输入顺序不同可能生成不同的二叉排序树。

? ? ? ? 就维护表的有序性而言，二叉排序树无序移动结点，只需修改指针即可完成插入部和删除操作，平均时间为O(log2n)。二分查找的对象是有序顺序表，若有插入和删除结点操作，所花的代价是O(n)；若有序表是动态查找表，则应选择二叉排序树作为其逻辑结构。

?

?