数据结构与算法－二叉排序树

一棵二叉排序树(Binary Sort Tree)(又称二叉查找树)或者是一棵空二叉树，或者是具有下列性质的二叉树：

1. 若它的左子树不空，则左子树上所有结点的键值均小于它的根结点键值；

2. 若它的右子树不空，则右子树上所有结点的键值均大于它的根结点键值；

3. 根的左、右子树也分别为二叉排序树。

由上图可知，二叉排序树是一棵特殊的二叉树，由于它的特殊性质，中序遍历一棵二叉排序树所得的结点访问序列是键值的递增序列。

二叉树的二叉链表类型定义如下：

typedef struct btnode{
    KeyType key;
    // 指向左右孩子的指针
    struct btnode *lchild ,*rchild;
    // BinTree为指向二叉链表结点的指针类型
}BSTNode ,*BinTree;
// bst为指向二叉排序树根结点的指针
BinTree bst;

1. 二叉排序树的查找

当二叉排序树不为空时，首先将给定值和根结点的关键字比较，若相等，则查找成功；否则根据给定值与根结点关键字间的大小关系，分别在左子树和右子树上继续进行查找。算法描述如下：

BinTree SearchBST(BinTree bst ,KeyType key){ 
    // 不成功时返回 NULL 作为标记
    if (bst== NULL){
        return NULL; 
    // 成功时返回结点地址
    }else if (key==bst->key) {
        return bst;
    // 继续在左子树中查找
    }else if ( key<bst->key){
        return SearchBST (bst->lchild, key);
    // 继续在右子树中查找
    }else{
        return SearchBST (bst->rchild, key);
    }

}

在二叉排序树上进行查找，若查找成功，则是从根结点出发走 了一条从根结点到待查结点的路径；若查找不成功，则是从根结点出发走了一条从根到某个叶子的路径。因此与二分查找类似，关键字比较的次数不超过二叉树的深度。

2. 二叉排序树的插入

由于二叉排序树这种动态树表是在查找过程中，不断的往树中插入不存在的键值而形成的，所以插入算法必须包含查找过程，并且是在查找不成功时进行插入新结点的操作。

在二叉排序树上进行插入的原则是：必须要保证插入一个新结点之后，仍为一棵二叉排序树，这个结点是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子。

二叉排序树的插入算法描述：

int InsertBST(BinTree bst, KeyType key){
    BSTNode *p,*t,*f;
    // f为指向查到结点的双亲，初始值为NULL
    f = null;
    t = SearchBST(bst,key,f);
    // 查找不成功时插入新结点
    if(t == NULL){
        p = malloc(sizeof(btnode));
        p->key = key;
        p->lchild = NULL;
        P->rchild = NULL;

        if(f ==NULL){
            // 被插入结点为新的根结点
            bst = p;
        }else if(key<f->key){
            // 被插入结点p为f左孩子
            f->lchild = p;
        }else{
            // 被插入结点p为f右孩子
            f->rchild = p;
        };
        return 1;
    }else{
        // 查找成功时不用插入结点
        return 0
    }
}

二叉排序树的建树过程：

3. 二叉排序树的分析

二叉排序树上的平均查找长度是介于O(n)和O(log2n)之间的，其查找效率与树的形态有关。

上图a中的平均查找长度是O(log2n)，图b的二叉树为一条单枝，查找算法退化为顺序查找，平均查找长度上升为(n+1)/2，即平均查找长度为O(n)，为了提高二叉排序树的查找效率，避免图b这样的情况，需要在二叉排序树的动态变化过程中随时调整其形态，使之保持“平衡”，也就是平衡二叉树的概念。