返回：0300 数据结构总目录 · 上一章：0306 Chap6 图 · 下一章：0308 Chap8 高级搜索树

1、学习目标

二叉搜索树把“有序向量的二分思想”和“二叉树的链接结构”结合起来。它的核心不变式是：左子树关键码小，右子树关键码大，中序遍历有序。

模块 要掌握的内容
BST 性质 顺序性、中序单调性
操作 查找、插入、删除
复杂度 与树高 h 成正比
退化 极端情况下退化成链
平衡 等价 BST、旋转、AVL

2、资料范围

PDF 课件 内容
07.BST.A.introduction.pdf BST 概述
07.BST.B.algorithms_implementation.pdf 查找、插入、删除
07.BST.C.balance_equivalence.pdf 平衡与等价 BST
07.BST.D.AVL.pdf AVL 树

3、BST 不变式

对任一节点 x：

1
左子树所有关键码 <= x.key <= 右子树所有关键码

如果不允许重复关键码，则改成严格小于和严格大于。

重要结论：

1
BST 的中序遍历序列是有序序列。

这个结论是判断 BST、输出有序结果和实现范围查询的基础。

4、查找

查找过程类似二分：

1
2
3
4
5
6
7
Node* search(Node* x, int key) {
    while (x && x->key != key) {
        if (key < x->key) x = x->left;
        else x = x->right;
    }
    return x;
}

复杂度是 O(h)，其中 h 是树高。

树形 高度 查找复杂度
平衡 O(log n) O(log n)
退化成链 O(n) O(n)

5、插入

插入时先查找失败位置，再把新节点接到最后访问节点的左或右孩子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Node* insert(Node*& root, int key) {
    if (!root) return root = new Node(key);
    Node* x = root;
    Node* p = nullptr;
    while (x) {
        p = x;
        if (key < x->key) x = x->left;
        else if (x->key < key) x = x->right;
        else return x;
    }
    Node* node = new Node(key);
    node->parent = p;
    if (key < p->key) p->left = node;
    else p->right = node;
    return node;
}

插入会改变从新节点到根路径上的高度，AVL 等平衡树会在这条路径上检查并修复失衡。

6、删除

删除分三种情况：

情况 处理
叶子 直接删除
只有一个孩子 用孩子替代该节点
有两个孩子 找中序后继或前驱，交换数据后删除后继/前驱

双分支删除常用中序后继：

1
后继 = 右子树中一路向左的最小节点

后继节点一定没有左孩子，因此交换后会转化为前两种简单删除。

7、等价 BST 与旋转

两棵 BST 若保存相同关键码集合，中序序列相同，就可视为等价 BST。旋转是在保持中序序列不变的前提下改变树形。

右旋：

1
2
3
4
5
    y              x
   / \            / \
  x   C   ->     A   y
 / \                / \
A   B              B   C

左旋对称。

旋转是 AVL、伸展树、红黑树等平衡搜索树的基本操作。

8、AVL 树

AVL 树要求任一节点左右子树高度差不超过 1。

平衡因子：

1
bf(x) = height(left) - height(right)

合法范围：

1
-1, 0, 1

插入后可能出现四种失衡：

类型 形态 修复
LL 左孩子的左侧变高 右旋
RR 右孩子的右侧变高 左旋
LR 左孩子的右侧变高 先左旋，再右旋
RL 右孩子的左侧变高 先右旋，再左旋

AVL 查找、插入、删除均为 O(log n)。插入通常只需修复最低失衡祖先；删除可能导致多个祖先继续失衡，需要一路向上检查。

9、复杂度汇总

结构 查找 插入 删除
普通 BST 平均 O(log n) O(log n) O(log n)
普通 BST 最坏 O(n) O(n) O(n)
AVL O(log n) O(log n) O(log n)

10、易错点

易错点 修正
认为 BST 一定快 普通 BST 可能退化
删除双分支节点直接删 应先找前驱/后继转化
旋转后忘记维护父子指针 父指针、孩子指针、高度都要更新
AVL 删除只修一次 删除可能向上连续失衡
混淆 BST 与堆 BST 关心中序有序，堆关心父子优先级

11、复盘清单

检查项 状态
能证明 BST 中序有序 待复盘
能手写 BST 查找、插入、删除 待复盘
能画出左旋和右旋 待复盘
能区分 LL/RR/LR/RL 四种失衡 待复盘
能解释 AVL 为什么保持 O(log n) 待复盘