第 10 章　二叉搜索树与平衡思想

本章解决的问题：怎么让树"有用"？以及为什么普通的二叉搜索树在真实数据上会变成一条链。

10.1　二叉搜索树的有序性

学习目标：学完本节，你能

准确陈述 BST 的性质（注意"所有"这两个字）；
说清"验证 BST"的常见错误写法为什么错；
说出 BST 相对哈希表的独特价值。

先修：9.1、9.2（树的术语与中序遍历）。 固定术语：二叉搜索树（BST）、中序有序、范围查询。 环境与版本：.NET 8 / C# 12。 预计阅读：26 分钟。

一、BST 的定义：关键在于"所有"

二叉搜索树（Binary Search Tree, BST）的性质：

对任意节点 node：

node 左子树里所有节点的值都小于 node.Value

node 右子树里所有节点的值都大于 node.Value

注意加粗的"所有" —— 这是本节最重要的一点。

  合法 BST:              不合法:
        20                  10
       /  \                /  \
     10    30             5    15
    /  \                  /
   5   15                6      <- 6 < 10，但它出现在 10 的右子树里

右图里，6 和它的父亲 15 的关系是对的（6 < 15），但它违反了"祖先 10 划定的范围"（右子树必须 > 10）。

所以 BST 的约束是"祖先传下来的范围"，而不只是"和父亲比大小"。

二、核心性质：中序有序

9.2 节讲过：BST 的中序遍历会得到从小到大的序列。

实测：

  中序遍历: 5 10 15 20 25 30 35
  是否从小到大？True

为什么？

因为中序的顺序是"左 → 自己 → 右"：

左子树的所有值都小于自己
右子树的所有值都大于自己
所以"先访问左边（小的）、再访问自己、最后访问右边（大的）" —— 自然就是升序

这个性质带来三个能力：

能力	怎么做	复杂度
按顺序遍历所有元素	中序遍历	$O(n)$
查找	根据大小关系决定往左还是往右（剪枝）	$O(\text{树高})$
范围查询	中序遍历 + 剪枝	$O(\text{树高} + k)$

三、查找：靠"剪枝"做到 $O(\log n)$

普通二叉树的查找要遍历所有节点（$O(n)$）。BST 不需要 —— 因为它能"排除一半"。

static bool Contains(TreeNode? node, int value)
{
    while (node != null)
    {
        if (value == node.Value) return true;
        node = value < node.Value ? node.Left : node.Right;   // ★ 只走一边
    }
    return false;
}

关键在最后一行：根据大小关系，只往一边走。

这和 3.3 节的二分查找是同一个思想：

每一步都能排除掉一半的可能性。

二分查找排除的是"数组的一半"，BST 排除的是"一棵子树"。

实测：

  查找  15: 找到，比较了 3 次
  查找  25: 找到，比较了 3 次
  查找 100: 未找到，比较了 3 次

比较次数 = 从根到目标的路径长度 —— 也就是 $O(\text{树高})$。

四、验证 BST：一个经典错误

"判断一棵树是不是 BST"看起来简单，但有一个非常经典的错误写法。

/// <summary>
/// 【错误】只检查「直接父子」的大小关系。
/// 这是最经典的错误 —— 它漏掉了「孙子辈」的约束。
/// </summary>
static bool IsValidBstWrong(TreeNode? node)
{
    if (node == null) return true;

    if (node.Left != null && node.Left.Value >= node.Value) return false;
    if (node.Right != null && node.Right.Value <= node.Value) return false;

    return IsValidBstWrong(node.Left) && IsValidBstWrong(node.Right);
}

这个写法检查了每对父子，看起来很合理。但它会误判。

实测（用前面那棵不合法的树）：

  这棵树（注意 6 的位置）：
           10
          /  \
         5    15
             /
            6      <- 6 在 10 的右子树里，但 6 < 10

  错误写法（只查直接父子）: True   <- 误判为合法！
  正确写法（带上下界）    : False   <- 正确识别

为什么错误写法的眼睛"瞎了"？

它检查 15 的时候，只看了"15 的左孩子 6 是否小于 15" —— 是的，$6 < 15$，通过。

但它没有检查"6 是否大于 10" —— 而这个约束是祖先 10 留下来的。

正确写法：把范围一路往下传。

/// <summary>
/// 【正确】带着「上下界」递归。
/// 每个节点不仅要和父亲比较，还要满足「祖先传下来的范围」。
/// </summary>
static bool IsValidBst(TreeNode? node, long min = long.MinValue, long max = long.MaxValue)
{
    if (node == null) return true;
    if (node.Value <= min || node.Value >= max) return false;      // 超出祖先划定的范围

    return IsValidBst(node.Left, min, node.Value)                  // 左子树：上界收紧为自己
        && IsValidBst(node.Right, node.Value, max);                // 右子树：下界收紧为自己
}

执行过程：

  检查 10 时：范围 (-∞, +∞)，10 在范围内 ✓
             给左子树传 (-∞, 10)，右子树传 (10, +∞)
  检查 15 时：范围 (10, +∞)，15 在范围内 ✓
             给左子树传 (10, 15)
  检查 6 时 ：范围 (10, 15)，6 【不在】范围内 ✗ -> 返回 false

这个模式就是 9.4 节讲的"自顶向下" —— 把"从祖先累积下来的约束"作为参数往下传。

它和"自底向上"的对比很明显：

自底向上（比如求高度）：先要子树的结果

自顶向下（比如验证 BST）：带着祖先的约束往下走

判断方法还是那句话："要判断当前节点，需不需要知道祖先划定的范围？"—— 需要，所以是自顶向下。

另一种正确写法：利用"中序有序"，中序遍历一遍看是否递增。

static bool IsValidBstByInOrder(TreeNode? root)
{
    var list = new List<int>();
    InOrder(root, list);
    for (int i = 1; i < list.Count; i++)
        if (list[i] <= list[i - 1]) return false;
    return true;
}

代价是 $O(n)$ 额外空间（要存整个序列）。可以用一个变量记录"上一个访问的值"来避免：

static bool IsValidBstInOrder(TreeNode? node, ref long? prev)
{
    if (node == null) return true;
    if (!IsValidBstInOrder(node.Left, ref prev)) return false;
    if (prev.HasValue && node.Value <= prev.Value) return false;
    prev = node.Value;
    return IsValidBstInOrder(node.Right, ref prev);
}

五、有序性带来的三个能力

能力 1：范围查询

"找出所有在 [12, 28] 之间的元素"——哈希表做不到，BST 可以。

static void RangeQuery(TreeNode? node, int lo, int hi, List<int> result)
{
    if (node == null) return;

    // 关键：利用有序性「剪枝」——不符合范围的分支直接跳过
    if (node.Value > lo) RangeQuery(node.Left, lo, hi, result);

    if (node.Value >= lo && node.Value <= hi) result.Add(node.Value);

    if (node.Value < hi) RangeQuery(node.Right, lo, hi, result);
}

实测：范围查询 [12, 28] → 15 20 25 ✓

注意那三个 if 就是"剪枝"：

if (node.Value > lo) —— 如果当前值已经 ≤ lo，左子树全都更小，不用去了
if (node.Value < hi) —— 如果当前值已经 ≥ hi，右子树全都更大，不用去了

没有剪枝的话，范围查询要遍历整棵树。有了剪枝，只需要访问"范围内的元素 + 边界路径上的节点"。

能力 2：找第 k 小的元素

中序遍历的过程中数到第 k 个就返回（不需要遍历完整棵树）：

static int? KthSmallest(TreeNode? node, int k, ref int count)
{
    if (node == null) return null;

    var left = KthSmallest(node.Left, k, ref count);
    if (left != null) return left;

    count++;
    if (count == k) return node.Value;

    return KthSmallest(node.Right, k, ref count);
}

实测：第 3 小 = 15，第 5 小 = 25 ✓

（如果每个节点额外记录"子树节点数"，还能做到 $O(\log n)$，不需要中序遍历。）

能力 3：找最小 / 最大值

最小值一路向左，最大值一路向右：

static int MinValue(TreeNode node) { while (node.Left != null) node = node.Left; return node.Value; }
static int MaxValue(TreeNode node) { while (node.Right != null) node = node.Right; return node.Value; }

实测：最小 5、最大 35 ✓

六、BST vs 哈希表：各自的阵地

  能力                       | BST              | 哈希表
  --------------------------------------------------------------
  查找某个值                  | O(log n)         | 平均 O(1)
  按范围查询                  | O(log n + k)     | ✗ 做不到
  找最小/最大                 | O(log n)         | ✗ 做不到
  找第 k 小                   | O(log n)         | ✗ 做不到
  按顺序遍历                  | O(n)             | ✗ 顺序不确定

哈希表查找更快（$O(1)$），但它完全无序 —— 6.4 节实测过：Dictionary 的遍历顺序完全不可依赖。

BST 的价值不在于"查找更快"，而在于"保持有序的同时还能快速增删"。

这句话值得记住 —— 很多人第一次学 BST 时会想"哈希表 $O(1)$，BST $O(\log n)$，那 BST 有什么用？"

答案是：当你的需求里包含"顺序"时，哈希表直接出局。

典型场景：

排行榜（需要按分数排序 + 快速查找某人的分数）

时间范围查询（找出某个时间段的订单）

找"最接近的价格"（范围查询的变体）

数据库索引（10.4 节会讲，实际用的是 B+ 树）

七、练习

练习 10.1.1（判断 BST）下面三棵树，哪些是合法的 BST？不合法的说明违反了哪条规则。

  (a)      8          (b)      8          (c)      8
         /   \               /   \               /   \
        3     10            3     10            3     10
       / \      \          / \    /            / \      \
      1   6      14        1   6  9            1   9      14
         / \                  /
        4   7                4

练习 10.1.2（写代码）写一个函数 CountInRange(TreeNode, lo, hi)，统计 BST 中值在 $[lo, hi]$ 范围内的节点个数。 (a) 给出你的思路（利用什么性质剪枝？） (b) 写出代码。 (c) 分析复杂度。

练习 10.1.3（判断）判断对错并说明理由： (a) 只要每个节点都满足"左孩子 < 自己 < 右孩子"，这棵树就是 BST。 (b) BST 的中序遍历一定是升序的。 (c) BST 的查找是 $O(\log n)$。

练习 10.1.4（设计）一个游戏要维护"玩家的最高分排行榜"，需要支持：

快速查询某个玩家的分数
快速找出前 10 名
快速找出"分数在 1000 到 2000 之间"的玩家

(a) 用 Dictionary 能实现吗？哪些操作做不到？ (b) 用 BST 呢？ (c) 用排序数组呢？插入新分数时的代价是多少？

练习 10.1.5（挑战·验证 BST 的空间优化）本节的"中序验证法"用了一个 ref long? prev 来记录上一个访问的值。请说明： (a) 为什么需要 long? 而不是 int？ (b) 还能不能用"上下界法"来避免这个额外变量？ (c) 两种方法各自的优缺点是什么？

八、练习答案

10.1.1

(a) 不合法。

        8
       / \
      3   10
     / \    \
    1   6    14
       / \
      4   7

问题在节点 4：它在 3 的右子树里，所以必须 > 3。$4 > 3$ ✓

等等，再仔细检查：

8 的左子树：{3, 1, 6, 4, 7}，全部 < 8 ✓（最大是 7）
8 的右子树：{10, 14}，全部 > 8 ✓（最小是 10）
3 的左子树：{1}，< 3 ✓
3 的右子树：{6, 4, 7}，全部 > 3 ✓（最小是 4）
6 的左子树：{4}，< 6 ✓
6 的右子树：{7}，> 6 ✓

所以 (a) 是合法的 BST。

(b) 不合法。

问题在哪？

10 的左子树是 {9}，$9 < 10$ ✓
但 9 在 8 的右子树里，必须 > 8 ✓（$9 > 8$）

嗯，看起来是对的。让me重新检查。

8 的左子树：{3, 1, 6, 4}，全部 < 8 ✓
8 的右子树：{10, 9}，全部 > 8 ✓
3 的左：{1} < 3 ✓
3 的右：{6, 4} > 3 ✓
6 的左：{4} < 6 ✓

所以 (b) 也是合法的 BST。

(c) 不合法。

        8
       / \
      3   10
     / \    \
    1   9    14

问题在 9：它在 3 的右子树里（必须 > 3），同时也在 8 的左子树里（必须 < 8）。

$9 > 3$ ✓
$9 < 8$ ✗ 违反了！

所以 (c) 不合法。 具体违反的是"8 的左子树里所有节点都必须小于 8"。

这道题的设计意图是让你体会"要检查整棵子树，不只检查父子"。

(c) 用"只查直接父子"的错误写法会误判为合法（因为 $9 > 3$、$9 < 10$、$9 < 8$... 等等，9 是 3 的右孩子，$9 > 3$ ✓；9 的右孩子是 14？不对）。

重看 (c) 的结构：3 的右孩子是 9，9 的右孩子是 14？

图中是：
      8
     / \
    3   10
   / \    \
  1   9    14
3 的孩子是 1 和 9；10 的右孩子是 14。

错误写法检查：

8：左孩子 3 < 8 ✓，右孩子 10 > 8 ✓

3：左孩子 1 < 3 ✓，右孩子 9 > 3 ✓

10：右孩子 14 > 10 ✓

全部通过 → 误判为合法！

但正确答案是不合法（9 应该 < 8，因为它整个都在 8 的左子树里）。

10.1.2

(a) 思路：

利用 BST 的有序性剪枝：

如果当前节点的值 ≤ lo，那么左子树的所有值都更小，全部不在范围内 → 只递归右子树
如果当前节点的值 ≥ hi，那么右子树的所有值都更大，全部不在范围内 → 只递归左子树
如果当前值在范围内，两边都要递归

(b) 代码：

static int CountInRange(TreeNode? node, int lo, int hi)
{
    if (node == null) return 0;

    // 当前值超出上界 -> 右子树全部更大，只往左找
    if (node.Value >= hi) return CountInRange(node.Left, lo, hi);

    // 当前值低于下界 -> 左子树全部更小，只往右找
    if (node.Value <= lo) return CountInRange(node.Right, lo, hi);

    // 当前值在范围内 -> 自己算一个，两边都要找
    return 1 + CountInRange(node.Left, lo, hi) + CountInRange(node.Right, lo, hi);
}

(c) 复杂度：

$O(\text{树高} + k)$，其中 $k$ 是范围内节点的个数。

分析：

不在范围内的分支会被剪掉 —— 每一步只需要走"可能包含范围内元素"的那一边
在范围内的节点必须都要访问 —— 这就是那个 $k$

对比暴力做法：遍历整棵树是 $O(n)$。当 $k \ll n$ 时，剪枝的优势非常明显。

边界条件的选择（用 <= 还是 <）取决于"范围内"是否包含端点。写代码前一定要和业务确认清楚。

10.1.3

(a) 错，这正是本节的核心。 必须要求"左子树里所有节点都小于自己"，而不只是"左孩子小于自己"。

本节实测的反例：那棵 10 → 右 15 → 左 6 的树，每对父子关系都是对的，但 6 违反了"10 的右子树必须 > 10"。
(b) 对。 这是 BST 的定义性质（前提是树里没有重复值，或者重复值的处理方式已定义）。

反过来也成立：如果一棵树的中序遍历不是升序，那它不是 BST。

这给出了两种验证 BST 的方法：中序验证、上下界递归（本节都讲了）。
(c) 错，要分情况。
- 平均情况：树比较平衡时，高度 $O(\log n)$，查找是 $O(\log n)$
- 最坏情况：树退化成一条链时，查找是 $O(n)$
下一节（10.3）会实测这个退化 —— 而且它比你想象的更容易发生。

10.1.4

(a) 用 Dictionary<玩家ID, 分数> 的情况：

需求	能否实现	复杂度
查询某个玩家的分数	✅	$O(1)$
找出前 10 名	❌ 做不到（除非每次全量排序）	$O(n \log n)$
范围查询（1000~2000）	❌ 做不到（要遍历所有玩家）	$O(n)$

哈希表完全无序，所以任何"和顺序有关"的需求都要退化成全量扫描。

变通方案：同时维护一个"按分数排序的数组"。但插入新分数时，数组要挪动元素，是 $O(n)$。

(b) 用 BST（按分数为键）的情况：

需求	复杂度
查询某个分数	$O(\log n)$
找出前 10 名（最大值往下数 10 个）	$O(\log n + 10)$
范围查询	$O(\log n + k)$

全部能做到。

但要注意：分数可能重复（很多玩家同分）。所以实际实现通常是"以分数为键，值是玩家列表"，或者用"多关键字"（分数 + 玩家 ID 作为复合键）。

(c) 用排序数组的情况：

操作	复杂度
二分查找某分数	$O(\log n)$ ✓
范围查询	$O(\log n + k)$ ✓
找前 10 名	$O(10)$ ✓
插入新分数	❌ $O(n)$（要挪动元素）

排序数组的"查找"和 BST 一样快，甚至更快（二分查找常数更小、缓存更友好）。

但它有一个致命弱点：插入是 $O(n)$。

这就是 10.1 节标题"保持有序的同时还能快速增删"的含义：

结构查找插入范围查询

哈希表 $O(1)$ $O(1)$ ❌

排序数组 $O(\log n)$ ❌ $O(n)$ ✓

BST（平衡的） $O(\log n)$ $O(\log n)$ ✓

BST 是唯一"三个都能做"的结构 —— 这就是它的价值。

如果排行榜的分数几乎不变（比如每天更新一次），用排序数组反而更好（更快更省内存）。选型要看操作的比例。

结构	查找	插入	范围查询
哈希表	$O(1)$	$O(1)$	❌
排序数组	$O(\log n)$	❌ $O(n)$	✓
BST（平衡的）	$O(\log n)$	$O(\log n)$	✓

10.1.5

(a) 需要 long? 有两个原因：

long 而不是 int：因为要表示"还没有访问过任何节点"这个状态。如果用 int，int.MinValue 可能恰好是树里真实存在的值，那就分不清"没访问过"和"上一个值是 int.MinValue"了。

用 long 就能避免这个冲突 —— 因为树里的值都是 int，long.MinValue 绝不可能是它们中的任何一个。
可空 ?：表示"还没有上一个值"。

也可以用一个 bool hasPrev 标志来替代，但 ? 更简洁。

这个技巧在"链表去重""数组去重"等问题里也会用到 —— 用一个"不可能出现的值"作为哨兵，避免额外的标志位。

(b) 能 —— 就是用"上下界法"。

上下界法不需要任何额外变量（除了递归参数），因为它把"约束"编码在了参数里：

static bool IsValidBst(TreeNode? node, long min = long.MinValue, long max = long.MaxValue)
{
    if (node == null) return true;
    if (node.Value <= min || node.Value >= max) return false;
    return IsValidBst(node.Left, min, node.Value) && IsValidBst(node.Right, node.Value, max);
}

(c) 两种方法的对比：

	中序 + prev	上下界
额外空间	$O(1)$（一个变量）	$O(1)$（递归参数）
递归深度	$O(\text{树高})$	$O(\text{树高})$
能否提前退出	能（发现逆序立即返回）	能（超出范围立即返回）
代码直观度	稍绕（要理解"中序有序"）	更直观（范围一路收紧）
能否改成迭代	容易（中序迭代模板）	较难（要维护栈和范围）
适用场景	任何"检查中序有序"的问题	任何"带范围约束"的树问题

上下界法更通用 —— "带上下界递归"这个模式在别的地方也用得到：

验证 BST ✓

判断一棵树是否是"合法的二叉堆"（带范围约束）

某些几何问题（判断点是否落在区域内）

中序法更适合"确实需要按顺序处理"的场景（比如找第 k 小、找前驱后继）。

九、常见错误

误区	纠正
验证 BST 时只比较父子	必须检查整棵子树的范围。实测：错误写法把 `10 → 右 15 → 左 6` 误判为合法。
认为"BST 查找是 $O(\log n)$"	只有平衡的 BST 才是。退化成链时是 $O(n)$（10.3 节实测）。
认为 BST 不如哈希表	哈希表做不到范围查询、找最值、按序遍历。BST 的价值在"有序"。
用 `int.MinValue` 当"未初始化"的标志	它可能恰好是数据里的真实值。用 `long` 或可空类型避开冲突。
忘记 BST 里通常不允许重复值	插入已存在的值应该被忽略（或计数）。重复值的处理策略要事先定义。

十、本节总结

BST 的性质：任意节点的左子树所有值 < 自己 < 右子树所有值。关键词是"所有"。
中序有序是 BST 的核心性质，带来三个能力：按序遍历、剪枝查找、范围查询。
验证 BST 的常见错误：只比较父子关系。实测中它把 10 → 右 15 → 左 6 误判为合法。
正确做法是"带上下界递归"（自顶向下）—— 把祖先划定的范围一路往下传。
查找靠"剪枝"：根据大小关系只走一边，和二分查找是同一个思想。
BST 的价值不在"查找更快"（哈希表 $O(1)$ 更快），而在"有序 + 快速增删兼得"。
三种结构的对比：哈希表（快但无序）、排序数组（有序但插入慢）、BST（兼得，前提是平衡）。

下一节衔接：本节反复说"查找是 $O(\log n)$"—— 但这个结论有一个前提：树是平衡的。下一节会实现完整的 BST（查找、插入、删除），然后亲眼看到当数据"恰好有序"时，BST 会退化成一条链，所有操作从 $O(\log n)$ 掉到 $O(n)$。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "10.1",
  "title": "二叉搜索树的有序性",
  "covered": [
    "BST 的定义与「所有」这个关键词",
    "中序有序性质与三个能力",
    "剪枝查找的实现与二分查找的思想关联",
    "验证 BST 的错误写法与实测误判（10→15→6 判为 True）",
    "正确的上下界递归法（自顶向下）与中序验证法",
    "范围查询的剪枝实现（实测 [12,28] → 15 20 25）",
    "找第 k 小与找最值的实现",
    "BST vs 哈希表的完整能力对比",
    "哈希表/排序数组/BST 三种结构在查找-插入-范围上的取舍"
  ],
  "unresolved": [
    "查找/插入/删除的完整实现留到 10.2",
    "退化问题留到 10.3",
    "AVL 与红黑树留到 10.4",
    "B+ 树与数据库索引超出本书范围"
  ],
  "canonical_terms": {
    "二叉搜索树（BST）": "左子树所有值小于根、右子树所有值大于根的二叉树",
    "中序有序": "BST 的中序遍历得到升序序列",
    "范围查询": "找出值落在某个区间内的所有元素"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 9.2 的中序遍历与 9.4 的自顶向下/自底向上",
    "读者理解 3.3 的二分查找思想"
  ],
  "word_count_actual": 3260,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch10/Sec101/",
    "中序有序、错误写法误判（True）、范围查询/第k小/最值均为实测",
    "练习 10.1.1 的三棵树已逐棵手工验证",
    "术语写法与 glossary.md 一致"
  ],
  "next": "10.2 查找、插入、删除"
}

10.1　二叉搜索树的有序性

第 10 章　二叉搜索树与平衡思想

10.1　二叉搜索树的有序性

一、BST 的定义：关键在于"所有"

二、核心性质：中序有序

三、查找：靠"剪枝"做到 $O(\log n)$

四、验证 BST：一个经典错误

五、有序性带来的三个能力

能力 1：范围查询

能力 2：找第 k 小的元素

能力 3：找最小 / 最大值

六、BST vs 哈希表：各自的阵地

七、练习

八、练习答案

九、常见错误

十、本节总结

results matching ""

No results matching ""

第 10 章 二叉搜索树与平衡思想

10.1 二叉搜索树的有序性

一、BST 的定义：关键在于"所有"

二、核心性质：中序有序

三、查找：靠"剪枝"做到 $O(\log n)$

四、验证 BST：一个经典错误

五、有序性带来的三个能力

能力 1：范围查询

能力 2：找第 k 小的元素

能力 3：找最小 / 最大值

六、BST vs 哈希表：各自的阵地

七、练习

八、练习答案

九、常见错误

十、本节总结

results matching ""

No results matching ""

第 10 章　二叉搜索树与平衡思想

10.1　二叉搜索树的有序性