7.2 二叉排序树

二叉排序树的定义、查找、插入、构造与删除（三种情况），以及查找效率分析。

定义

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

查找

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

插入与构造

二叉排序树作为一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字值等于给定值的结点时再进行插入的。插入的结点一定是一个新添加的叶结点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子。

从一棵空树出发，依次输入元素，将它们插入二叉排序树中的合适位置，即可构造一棵二叉排序树：

1int BST_Insert(BiTree &T, KeyType k) {
2    if (T == NULL) {                    // 原树为空，新插入的结点为根
3        T = (BiTree)malloc(sizeof(BSTNode));
4        T->key = k; T->lchild = T->rchild = NULL;
5        return 1;
6    } else if (k == T->key)             // 存在相同关键字，插入失败
7        return 0;
8    else if (k < T->key)
9        return BST_Insert(T->lchild, k);
10    else
11        return BST_Insert(T->rchild, k);
12}

在上面的控件中把模式切换为「查找」或「删除」，可以分别观察查找路径和删除过程。

删除

在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失。删除操作的实现过程按 3 种情况来处理：

查找效率分析

二叉排序树的查找效率，主要取决于树的高度。

• 若二叉排序树的左、右子树的高度之差的绝对值不超过 1（平衡二叉树），则这样的二叉排序树的平均查找长度为 $O(\log_2 n)$；
• 若二叉排序树是一个只有右（左）孩子的单支树（类似于有序的单链表），则其平均查找长度为 $O(n)$。最坏情况下，即构造二叉排序树的输入序列是有序的，则会形成一个倾斜的单支树，此时二叉排序树的性能显著变差。

即时练习