二叉排序树（BST）

也称为二叉查找树。二叉排序树或者为空树，或者为非空树，当为非空树时，满足（递归定义）：

若左子树非空，则左子树上所有结点关键字值均小于根结点的关键字；
若右子树非空，则右子树上所有结点关键字值均大于根结点的关键字；
左子树、右子树本身也分别是一棵二叉排序树。

组织内存索引

二叉排序树是适用于内存储器的一种重要树形索引（常用红黑树、伸展树等以维持平衡）
外存常用B/B+数

中序遍历序列：1、2、3、4、5、7、8、10、16（依次递增）

左子树结点值$<$根结点值$<$右子树结点值

二叉排序树中序遍历序列是一个递增有序序列

查找

二叉树非空时，查找根结点，若相等则查找成功；
若不等，则当小于根结点值时，查找左子树；当大于根结点值时，查找右子树；
当查找到叶子结点仍没找到相应的值，则查找失败。

BSTNode *BST_Search(BiTree T, ElemType key, BSNode *&p){		// 指针引用
    p=NULL;
    while(T!=NULL && key!=T->data){
        p=T;
        if(key<T->data)
            T=T->lchild;
        else
            T=T->rchild;
    }
    return T;
}

插入

若二叉排序树为空，则直接插入结点；
若二叉排序树非空，当值小于根结点时，插入左子树；当值大于根结点时，插入右子树；当值等于根节点时，不进行插入。

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

构造

读入一个元素并建立结点，若二叉树为空将其作为根结点；
若二叉排序树非空，当值小于根结点时，插入左子树；当值大于根结点时，插入右子树；当值等于根结点时，不进行插入。

void Create_BST(BiTree &T, KeyType str[], int n){
    T=NULL;
    int i=0;
    while(i<n){
        BST_Insert(T,str[i]);
        ++i;
    }
}

构造二叉排序树时，即使插入的值相同，但如果插入顺序不同，则构造完成的二叉排序树也不同

删除

若被删除的结点$z$是叶子结点，则直接删除；
若被删除的结点$z$有一棵子树，则让$z$的子树成为$z$父结点的子树，代替$z$结点；
若被删除的结点$z$有两棵子树，则让$z$的中序序列直接后继代替$z$，并删去直接后继结点。

中序遍历序列永远是递增的

问题

在二叉排序树中删除并插入某个结点，得到的二叉排序树是否与原来相同？

查找效率

平均查找长度（ASL）取决于树的高度：$O(log_2n)$

最坏的情况：$O(n)$，即构造序列有序的情况

$ASL=(1+2 \cdot 2+3)/4=2$

$1$：表示只经历了一个根结点

$2\cdot 2$：表示有两个结点（1、4）经历了2个结点

$3$：表示只有一个结点（3）经历了3个结点

$4$：结点总数