课程 · #6 / 11

二叉搜索树

顺序进去，对数时间出来

Binary search tree · path-walking search

size0

height0

compares0

init

value

动手试试：插入若干键；search 会高亮出比较路径。然后点 break it：插入已排序的值会让这棵树坍缩成一条链表——高度从 log n 一下蹿到 n。

为什么它重要

BST 把数组的快速查找与链表的灵活插入结合到了一起。它是集合、映射和数据库的根基。理解 BST 是理解平衡树和高效搜索的关键。

核心思想

还记得猜数字游戏吗？"是更大还是更小？"每个回答都排除掉一半的可能。

BST 就是这个游戏的树形版本。 每个节点都遵循同一条规则：左孩子更小，右孩子更大。

要找一个值：

从根开始
若该值 < 当前节点，往左走；若该值 > 当前节点，往右走。
重复，直到找到或走到空。

每一步都排除掉半棵树——这就是 O(log n)……前提是树是平衡的。如果你插入已排序的数据，就会得到一条链表和 O(n)。这正是平衡树存在的原因。

要点回顾

左子树 < 节点 < 右子树（BST 性质）
搜索、插入、删除都是 O(h)，其中 h 是高度
平衡树：h = O(log n)。不平衡：h = O(n)
中序遍历给出有序序列

BST 不变式

对 BST 的每一个操作都必须保住一条规则。把它陈述一次，你就能通过检查这条规则在操作前后是否成立，来证明每个算法的正确性：

BST 不变式: 对每个节点 n：n.left 子树中的每个键都严格小于 n.key，而 n.right 子树中的每个键都严格大于 n.key。
推论——中序遍历给出有序顺序: 递归访问 left，然后访问 self，再递归访问 right。对 left 的递归调用返回的键全都小于 self.key；对 right 的调用返回的键全都更大。所以拼接起来就是有序的。
"保住"在实践中意味着什么: 每次插入/删除结束后，不变式必须在各处仍然成立。插入很容易——你只在叶子处添加，所以规则本就成立。删除才是难啃的情形；见下文。

再深入一些

删除 —— 三种情形逐一走一遍

正是这个操作让工程师们转而求助于 AVL 树或红黑树。在保住不变式的同时移除一个节点，需要小心处理。

情形 1 —— 叶子。 直接把它从父节点上摘下来。不变式被自然保住，因为没有别的节点依赖于它。

    5                5
   / \              / \
  3   8     →      3
     /
    6           (delete 6 from right of 3)

等等，那个例子是从 8 的左边移除 6——重点是，叶子可以白拿。

情形 2 —— 一个孩子。 把那个孩子接上来，填进被删节点的位置。被删节点的父节点现在指向该孩子；该孩子的子树本就满足不变式，所以在新位置上依然满足。

      5                5
     / \              / \
    3   8     →      3   6
        /
       6           (delete 8: it had only a left child, 6)

情形 3 —— 两个孩子。 你不能随便提拔哪一个孩子——两边都有各自的子树，你总得设法把它们合并。诀窍是：找到中序后继——右子树中最小的键（等价地，right 最左边的叶子）。把它的值拷贝进被删节点，然后从右子树中删除那个后继（递归调用，但后继本身至多有一个孩子，所以递归会触底到情形 1 或情形 2）。

      5                6
     / \              / \
    3   8     →      3   8
       / \              / \
      6   9            7   9
       \
        7              (delete 5: successor is 6;
                       copy 6 up, then delete the
                       original 6 — case 2 with right
                       child 7)

为什么用后继而不用前驱？ 两者都行——前驱是左子树中最大的键。大多数实现要么交替使用，要么固定选一种并保持一致。不变式之所以被保住，是因为后继严格大于左子树中的一切（所以提拔后它依然更大），又严格小于右子树中的其余一切（所以右子树依然有效）。

没有平衡时这一切为何崩塌

演示里的 break it 按钮插入的是已经排好序的值。每个新节点都落到最右的位置——树变成了一条链表，高度爬到 n，搜索退化为 O(n)。这正是平衡树那一课的动机所在：那里的算法在每次插入和删除后都会重新平衡，于是无论输入以什么顺序到来，高度都保持在 O(log n)。

数学细节

时间复杂度（高度为 h）: Search: O(h); Insert: O(h); Delete: O(h); Min/Max: O(h)
高度界: Balanced: h = O(log n); Unbalanced: h = O(n)

实现

BST 搜索

fn search(node: Option<&Box<BstNode>>, key: i32)
    -> bool
{
    match node {
        None => false,
        Some(n) => {
            if key < n.data {
                search(n.left.as_ref(), key)
            } else if key > n.data {
                search(n.right.as_ref(), key)
            } else {
                true  // Found!
            }
        }
    }
}

删除的几种情形

叶子：直接移除
一个孩子：用该孩子替换
两个孩子：用后继替换

练习

三道建立在 BST 不变式之上的题目：

验证 BST —— 中等 · 为什么局部检查还不够；(min, max) 区间套路
BST 中的最近公共祖先 —— 简单 · 利用 BST 顺序的 O(h) 行走——无需任何辅助结构
BST 中第 K 小的元素 —— 中等 · 用显式栈做迭代式中序遍历；每一个有序下标游标背后的模板

→ 浏览全部练习题

🌲 二叉搜索树