二叉排序树

概念

二叉排序树（BST, Binary Search Tree，也称二叉查找树）或者是一棵空树，或者满足：

• 若左子树非空，则左子树上所有结点的值均小于根结点的值；
• 若右子树非空，则右子树上所有结点的值均大于根结点的值；
• 左右子树各自也是二叉排序树。

由此得到它最重要的性质：中序遍历二叉排序树，得到一个递增的有序序列。

一句话理解：BST 是把"折半查找的判定树"变成可动态增删的结构——判定树是静态的，BST 可以插入删除。

原理

查找：天然二分

从根开始，比根小往左走，比根大往右走，相等则命中；走到空指针则查找失败。

/* 递归版查找 */
BSTNode *search(BSTree t, int key) {
    if (!t || t->key == key) return t;
    if (key < t->key) return search(t->lchild, key);
    return search(t->rchild, key);
}

查找长度只与树的高度有关，平均 O(log n)，最坏 O(n)。

插入：一定插成叶子

先查找，若已存在则不插入（BST 通常不允许重复关键字）；若不存在，则在查找失败的最后那个位置新建叶子结点。插入操作永远不改变已有结点的位置，这是 BST 与 AVL 的关键区别。

删除：三种情形

情形	条件	做法
① 叶子	左右子树都空	直接删除，把双亲相应指针置空
② 单支	只有左子树或只有右子树	用该子树顶替被删结点的位置
③ 双支	左右子树都在	用中序直接后继（右子树最左下结点，或左子树最右下结点）的值替换被删结点，再递归删除那个后继结点

情形 ③ 的要点：替换的是值不是结点，被实际删除的是那个后继结点——它必然是叶子或单支，于是化归为情形 ①②。

记忆：删除双支结点 = "找个替身顶上，再把替身删掉"，替身必须比左子树都大、比右子树其余都小，正是中序后继。

查找效率：ASL

平均查找长度（ASL, Average Search Length）= 查找每个关键字所需比较次数的平均值。

• 成功 ASL：${\displaystyle \frac{1}{n}}\sum _{i=1}^n{c}_i$，其中 $c_i$ = 第 i 个结点所在的层数（根为第 1 层）。
• 失败 ASL：把所有空指针画成失败结点（外部结点），${\displaystyle \frac{1}{n+1}}\sum c_j$，其中 $c_j$ = 失败结点层数 − 1（因为比较到空指针为止，不比较空指针本身）。

失败结点个数恒为 n + 1（与二叉链表空指针数 n + 1 是同一件事）。

最坏情况：退化成单链表

若插入序列本身就是有序的（如 1,2,3,4,5），BST 会退化成一条链，树高 = n，查找退化为 O(n) 的顺序查找。

插入 1,2,3,4,5：        插入 3,1,4,2,5：
1                           3
 \                        /   \
  2                      1     4
   \                      \     \
    3                      2     5
     \                    高 3，ASL 小
      4
       \                  高 5，ASL = 3
        5

结论：BST 的性能取决于树形是否平衡，而这取决于输入顺序。这正是下一章**平衡二叉树（AVL）**要解决的问题。

与折半查找判定树的关系

折半查找的判定树是一棵二叉排序树，且是静态的：它不能插入删除，且对 n 个有序元素而言其树形唯一。BST 则是动态的：同样一组关键字，插入顺序不同，树形不同，ASL 也不同。

示例

例：构造 BST 并计算 ASL

依次插入关键字序列 45, 24, 53, 12, 37, 93，画出二叉排序树，求等概率下的成功 ASL 与失败 ASL。

完整推导过程：

第一步，逐个插入：

• 45 → 根
• 24 < 45 → 45 的左孩子
• 53 > 45 → 45 的右孩子
• 12 < 45 → 左；12 < 24 → 24 的左孩子
• 37 < 45 → 左；37 > 24 → 24 的右孩子
• 93 > 45 → 右；93 > 53 → 53 的右孩子

第二步，得出树形：

            45            第 1 层
          /    \
        24      53        第 2 层
       /  \       \
     12    37      93     第 3 层

第三步，算成功 ASL（各结点比较次数 = 其所在层数）：

$$AS{L}_{\mathrm{成}\mathrm{功}}=\frac{1\times 1+2\times 2+3\times 3}{6}=\frac{1+4+9}{6}=\frac{14}{6}\approx 2.33$$

第四步，补全失败结点（外部结点，用 □ 表示），共 n + 1 = 7 个：

• 12 的左右、37 的左右、93 的左右 → 位于第 4 层，各需比较 3 次，共 6 个
• 53 的左子树为空 → 位于第 3 层，需比较 2 次，共 1 个

$$AS{L}_{\mathrm{失}\mathrm{败}}=\frac{3\times 6+2\times 1}{7}=\frac{18+2}{7}=\frac{20}{7}\approx 2.86$$

结论：成功 ASL ≈ 2.33，失败 ASL ≈ 2.86。注意失败 ASL 的分母是 7（n+1） 而不是 6——把失败结点数算错是最常见的失分点。

C 语言：BST 的完整实现

#include <stdio.h>
#include <stdlib.h>

typedef struct BSTNode {
    int key;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

/* 插入：成功返回根（可能变化） */
BSTree insert(BSTree t, int key) {
    if (!t) {
        BSTree s = (BSTree)malloc(sizeof(BSTNode));
        s->key = key; s->lchild = s->rchild = NULL;
        return s;
    }
    if (key < t->key)      t->lchild = insert(t->lchild, key);
    else if (key > t->key) t->rchild = insert(t->rchild, key);
    return t;                       /* 关键字已存在：不插入 */
}

BSTNode *search(BSTree t, int key) {
    while (t && t->key != key)
        t = (key < t->key) ? t->lchild : t->rchild;
    return t;
}

int deleteNode(BSTree *t, int key) {
    if (!*t) return 0;
    if (key < (*t)->key)      return deleteNode(&(*t)->lchild, key);
    if (key > (*t)->key)      return deleteNode(&(*t)->rchild, key);

    /* 找到待删结点 */
    if ((*t)->lchild && (*t)->rchild) {        /* 情形③：双支 */
        BSTNode *p = (*t)->rchild, *parent = *t;
        while (p->lchild) { parent = p; p = p->lchild; }   /* 找中序后继 */
        (*t)->key = p->key;                    /* 用后继的值顶替 */
        return deleteNode(&parent->lchild == p ? &parent->lchild
                                               : &parent->rchild, p->key);
    } else {                                   /* 情形①②：叶子或单支 */
        BSTNode *child = (*t)->lchild ? (*t)->lchild : (*t)->rchild;
        free(*t);
        *t = child;
        return 1;
    }
}

void inOrder(BSTree t) {
    if (!t) return;
    inOrder(t->lchild);
    printf("%d ", t->key);
    inOrder(t->rchild);
}

int main(void) {
    BSTree t = NULL;
    int a[] = {45, 24, 53, 12, 37, 93};
    for (int i = 0; i < 6; i++) t = insert(t, a[i]);
    inOrder(t);  printf("\n");        /* 12 24 37 45 53 93 —— 递增，验证 BST 性质 */

    deleteNode(&t, 24);               /* 删除双支结点：用后继 37 顶替 */
    inOrder(t);  printf("\n");        /* 12 37 45 53 93 */

    deleteNode(&t, 45);               /* 删除根：用后继 53 顶替 */
    inOrder(t);  printf("\n");        /* 12 37 53 93 */

    printf("search 93: %s\n", search(t, 93) ? "found" : "not found");
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

Python 对照

class BST:
    def __init__(self): self.root = None

    def insert(self, k):
        def _ins(t):
            if not t: return {'key': k, 'l': None, 'r': None}
            if k < t['key']: t['l'] = _ins(t['l'])
            elif k > t['key']: t['r'] = _ins(t['r'])
            return t
        self.root = _ins(self.root)

    def search(self, k):
        t = self.root
        while t and t['key'] != k:
            t = t['l'] if k < t['key'] else t['r']
        return t

    def inorder(self, t=None):
        if t is None: t = self.root
        return [] if not t else self.inorder(t['l']) + [t['key']] + self.inorder(t['r'])

    def asl_success(self, t=None, depth=1):
        """返回 (结点数, 比较次数总和)"""
        if t is None: t = self.root
        if not t: return 0, 0
        ln, lc = self.asl_success(t['l'], depth + 1)
        rn, rc = self.asl_success(t['r'], depth + 1)
        return ln + rn + 1, lc + rc + depth

tree = BST()
for x in [45, 24, 53, 12, 37, 93]:
    tree.insert(x)
print(tree.inorder())                       # [12, 24, 37, 45, 53, 93]
n, total = tree.asl_success()
print(n, total, round(total / n, 2))        # 6 14 2.33

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

考点

考点

1. 必背结论

• BST 的中序序列递增，这是判定一棵树是否为 BST 的最快方法。
• 插入与删除都基于查找，时间复杂度 O(h)，h 为树高；平衡时 O(log n)，退化时 O(n)。
• 删除双支结点时用中序直接后继（或前驱）的值顶替，再删掉那个后继结点。
• n 个结点的 BST，查找失败的外部结点恰为 n + 1 个。

2. ASL 计算套路

• 成功 ASL 分母 = n，分子 = 各结点层数之和（根算第 1 层）。
• 失败 ASL 分母 = n + 1，分子 = 各失败结点（层数 − 1）之和。
• 画失败结点时不要漏掉"根没有左子树"这类靠上的空位。

3. 易错点

• "左子树所有结点小于根" ≠ "左孩子小于根"，必须是整棵左子树。判定题常在此设陷阱：只比较孩子与根是不够的，还要看子树的最右/最左结点。
• 删除操作的三种情形不要混淆：单支结点是用子树顶替，不是把孩子的值上移。
• 插入顺序不同 → 树形不同 → ASL 不同。题目问"最优/最差 ASL"时，最优对应平衡的树形。
• BST 的查找不要求关键字有序存储（那是折半查找的前提），它靠树形本身维持有序性。
• 同一个关键字集合，BST 的中序序列是唯一的（就是有序序列），与插入顺序无关。

小结

• BST 是"能动态增删的折半查找判定树"，核心性质是中序序列递增。
• 查找、插入、删除都是 O(h)；删除的难点在双支结点的"替身"处理。
• ASL 计算是本章的固定题型：成功看层数、失败看外部结点（n+1 个）。
• 树形随输入顺序退化是 BST 的致命弱点，答案就在下一章的平衡二叉树。

下一篇：平衡二叉树（AVL）