10.2　查找、插入、删除

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

实现 BST 的三种基本操作；
说清删除操作为什么要分三种情况，以及"中序后继"为什么能保持 BST 性质；
说出三种操作的共同点 —— 它们都依赖于树高。

先修：10.1（BST 的性质）。 固定术语：中序后继、树高。 环境与版本：.NET 8 / C# 12。 预计阅读：28 分钟。

一、一个共同的结构

BST 的三种操作，本质上都是"沿着一条路径从根走到某个位置"：

操作	路径终点
查找	找到目标节点，或走到 `null`（不存在）
插入	走到 `null`，在那里新建节点
删除	找到目标节点，然后调整指针

所以三种操作的代价都正比于"路径长度"，也就是树高。

这个共同点很重要：它意味着只要树高是 $O(\log n)$，三种操作就都是 $O(\log n)$。

反过来说：如果树退化，三种操作一起退化。

二、查找

static TreeNode? Search(TreeNode? node, int value, ref long comparisons)
{
    while (node != null)
    {
        comparisons++;
        if (value == node.Value) return node;
        node = value < node.Value ? node.Left : node.Right;   // ★ 只走一边
    }
    return null;
}

实测（树是 20 为根、10/30 为第二层、5/15/25/35 为第三层）：

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

比较次数 = 从根到目标的路径长度 + 1。

注意"未找到"也是 3 次 —— 因为走到 null 就知道了。

递归版和迭代版都可以。迭代版更好 —— 没有函数调用开销、不会栈溢出。

三、插入

static TreeNode? Insert(TreeNode? node, int value)
{
    if (node == null) return new TreeNode(value);       // 找到空位，新建节点

    if (value < node.Value) node.Left = Insert(node.Left, value);
    else if (value > node.Value) node.Right = Insert(node.Right, value);
    // value == node.Value：重复值，忽略

    return node;
}

插入 = "查找 + 在失败的地方挂上新节点"。

实测：

  插入前:   5 10 15 20 25 30 35
  插入 12 后: 5 10 12 15 20 25 30 35
    （12 比 10 大、比 15 小 —— 它落到了 15 的左孩子位置）

  再插入一次 12: 5 10 12 15 20 25 30 35
    （重复值被忽略，元素个数不变）

关于重复值的三种处理策略：

策略	做法
忽略（本节采用）	`value == node.Value` 时直接返回
计数	节点里加一个 `Count` 字段
允许重复	约定"相等的放到右边"（或左边），但这会破坏某些性质

无论选哪种，都要在文档里写清楚。 否则调用者会困惑"我插入了一个已存在的值，为什么 Count 没变？"

四、删除：三种情况

删除是 BST 里最复杂的操作，因为删掉一个节点后，要保证"BST 的性质仍然成立"。

分三种情况：

情况	处理
叶子节点	直接删掉，父节点的对应指针置空
只有一个孩子	用孩子"顶替"自己的位置
有两个孩子	用中序后继（右子树最小值）替代自己

static TreeNode MinNode(TreeNode node)
{
    while (node.Left != null) node = node.Left;      // 一路向左 = 最小值
    return node;
}

static TreeNode? Delete(TreeNode? node, int value)
{
    if (node == null) return null;                       // 没找到

    if (value < node.Value)
    {
        node.Left = Delete(node.Left, value);
    }
    else if (value > node.Value)
    {
        node.Right = Delete(node.Right, value);
    }
    else
    {
        // 找到要删的节点，分三种情况
        if (node.Left == null) return node.Right;        // 情况 1 & 2：没有左孩子
        if (node.Right == null) return node.Left;        // 情况 2：没有右孩子

        // 情况 3：两个孩子都有 —— 用「中序后继」替代
        var successor = MinNode(node.Right);
        node.Value = successor.Value;
        node.Right = Delete(node.Right, successor.Value);   // 再去右子树删掉后继
    }
    return node;
}

注意前两个 if 已经把"叶子"和"只有一个孩子"都覆盖了：

叶子节点：Left == null 成立，返回 node.Right（也是 null）—— 相当于删掉了自己

只有右孩子：Left == null 成立，返回 node.Right —— 孩子顶替上来

只有左孩子：第一个 if 不成立，第二个成立，返回 node.Left —— 孩子顶替上来

代码很简洁，但理解上要清楚它覆盖了哪些情况。

实测：三种情况

情况 1：删除叶子节点（删掉 5）

    删除前:       20              删除后:       20
      ├─ 10                        ├─ 10
      │  ├─ 5     <- 叶子           │  └─ 15
      │  └─ 15                     └─ 30
      └─ 30                           ├─ 25
         ├─ 25                        └─ 35
         └─ 35

    中序: 10 15 20 25 30 35        仍是合法 BST: True

情况 2：删除只有一个孩子的节点（删掉 5，它有一个右孩子 7）

    删除前:       20              删除后:       20
      ├─ 10                        ├─ 10
      │  ├─ 5                      │  ├─ 7      <- 7 顶替了 5 的位置
      │  │  └─ 7                   │  └─ 15
      │  └─ 15                     └─ 30
      └─ 30                           ├─ 25
         ├─ 25                        └─ 35
         └─ 35

    中序: 7 10 15 20 25 30 35      仍是合法 BST: True

情况 3：删除有两个孩子的节点（删掉 30）

    删除前:       20              删除后:       20
      ├─ 10                        ├─ 10
      │  ├─ 7                      │  ├─ 7
      │  └─ 15                     │  └─ 15
      │     └─ 12                  │     └─ 12
      └─ 30        <- 有两个孩子     └─ 35      <- 35（中序后继）顶上来了
         ├─ 25                        └─ 25    <- 25 变成了 35 的左孩子
         └─ 35

    中序: 7 10 12 15 20 25 35      仍是合法 BST: True

三种情况处理完，中序序列都保持升序，BST 性质都成立 ✓

为什么用"中序后继"？

中序后继 = 右子树里的最小值 = 所有比当前节点大的元素中最小的那个。

用它替代当前节点后：

左子树的所有值 都小于当前值，而当前值 < 后继 → 左子树仍然全部小于后继 ✓
右子树里剩下的值 都大于后继（因为后继是右子树的最小值）✓

BST 性质得以保持。

也可以用"中序前驱"（左子树最大值） —— 对称的做法，效果一样。

两者选一个就行，但要在整个实现里保持一致。

五、三种操作的复杂度

  操作           | 平均         | 最坏         | 说明
  ----------------------------------------------------------------------
  查找           | O(log n)     | O(n)         | 从根往下走，比较次数 = 树高
  插入           | O(log n)     | O(n)         | 先查找位置，再挂上去
  删除           | O(log n)     | O(n)         | 查找 + 调整指针

$n = 1{,}000{,}000$ 时：

平均情况：树高约 $\log_2(10^6) \approx 20$ → 约 20 次比较
最坏情况：树退化成链，树高 $10^6$ → 100 万次比较

差了 5 万倍。

注意"平均"和"最坏"这一列 —— 它们都依赖于"树高"。

所以整节的结论可以浓缩成一句话：

BST 的所有操作都是 $O(\text{树高})$。平衡时树高是 $O(\log n)$，退化时是 $O(n)$。

下一节就来看看"退化"是怎么发生的。

六、练习

练习 10.2.1（手写推演）从空树开始，依次插入 50, 30, 70, 20, 40, 60, 80： (a) 画出最终的树。 (b) 写出中序遍历的结果。 (c) 删除 30，画出结果树。

练习 10.2.2（代码阅读）下面这段删除代码有什么问题？

else
{
    // 情况 3：有两个孩子
    var successor = MinNode(node.Right);
    node.Value = successor.Value;
    // 忘了写这一行：node.Right = Delete(node.Right, successor.Value);
}
return node;

练习 10.2.3（判断）判断对错并说明理由： (a) BST 的插入一定比查找慢，因为它还要新建节点。 (b) 删除有两个孩子的节点时，用"中序前驱"替代也可以。 (c) BST 的操作复杂度是 $O(\log n)$。

练习 10.2.4（工程判断）一个系统用 BST 存储 100 万个订单（按订单号）。 (a) 如果订单号是"自增 ID"，插入顺序会是什么样？树会变成什么形状？ (b) 如果订单号是随机的 UUID，树会是什么形状？ (c) 这个差异会导致什么后果？

练习 10.2.5（挑战·删除的另一种实现）本节用的是"用后继的值覆盖当前节点，然后删除后继"（值复制法）。另一种做法是"节点替换"：直接调整指针，把后继节点整个搬过来。 (a) 两种做法在功能上有什么区别？ (b) 如果树节点里存的是"指向外部对象的引用"，哪种做法更好？为什么？

七、练习答案

10.2.1

依次插入 50, 30, 70, 20, 40, 60, 80：

(a) 最终的树：

              50
            /    \
          30      70
         /  \    /  \
       20   40  60   80

(b) 中序遍历：20 30 40 50 60 70 80

(c) 删除 30：

30 有两个孩子（20 和 40），所以要用中序后继 —— 右子树 {40} 的最小值是 40。

用 40 替代 30，然后删除原来的 40（它是叶子）：

              50
            /    \
          40      70
         /       /  \
       20      60    80

中序：20 40 50 60 70 80 ✓

验证 BST 性质：40 的左子树 {20} 都 < 40 ✓；右子树为空 ✓；40 在 50 的左子树里，$40 < 50$ ✓

10.2.2

问题：没有真正删除后继节点。

var successor = MinNode(node.Right);
node.Value = successor.Value;      // 把后继的值复制过来了
// 缺少：node.Right = Delete(node.Right, successor.Value);

后果：树里会同时存在两个值为 successor.Value 的节点 —— 一个是原来那个节点（值被覆盖了），一个是真正的后继节点。

具体表现：

Count 数量不对（删了一个却还是原来的数量）
中序遍历会出现两个相同的值
后续的查找/删除可能出现意外行为

修复：必须把原后继节点从右子树里删掉。

这也解释了为什么叫"值复制法" —— 新节点的值覆盖了旧节点，然后删掉提供值的那个节点。

本质上是"用后继的值替换掉被删节点的值，再删除后继"。

10.2.3

(a) 错，两者是同一个量级。

插入 = 查找路径 + 一次新建节点。新建节点是 $O(1)$，所以插入和查找同阶。

不过实际上插入通常稍慢一点 —— 因为它要修改指针、可能触发内存分配。但复杂度量级完全相同。
(b) 对。 中序前驱（左子树最大值）和后继是对称的，效果一样：
- 前驱是"所有比当前值小的元素中最大的" → 用它替代后，左子树剩下的都 < 前驱 ✓
- 右子树的所有值都 > 当前值 > ... 等等，右子树所有值都大于当前值，也大于前驱 ✓
两者都能保持 BST 性质，选一个即可。

但实现里要保持一致 —— 混用会让代码难以理解（而且某些自平衡树的实现精度依赖于一致性）。
(c) 错（又是这个点）。 准确说是 $O(\text{树高})$：
- 平衡时：$O(\log n)$
- 退化时：$O(n)$
说"BST 是 $O(\log n)$"是漏掉了前提。

10.2.4

(a) 自增 ID 的插入顺序是"严格递增"的。

结果：树会退化成一条"右斜链"。

  依次插入 1, 2, 3, 4, 5, ...：

  1
   \
    2
     \
      3
       \
        4
         \
          5
          ...

因为每个新值都比已有的所有值大，所以每次都往右走到底 —— 树的形状就是一条链。

(b) 随机 UUID 的插入顺序是随机的。

结果：树会相当平衡，高度约 $O(\log n)$。

具体来说：随机插入的 BST，期望高度约为 $2.99 \log_2 n$（这是已知的理论结果），仍然是 $O(\log n)$。

(c) 后果：差距是 5 万倍。

以 100 万个订单为例：

键类型	树高	单次查找比较次数
自增 ID	1,000,000	1,000,000 次
随机 UUID	约 60	60 次

这个例子的可怕之处在于：

"自增 ID"是数据库里最常见的键类型，而它恰好是让 BST 退化的最坏输入。

这不是"运气不好"，而是"默认行为" —— 你的数据天然就是有序的。

这就是为什么不能直接使用普通 BST —— 必须用自平衡的树（10.4 节），它在插入时会自动调整形状，不管数据是什么顺序，高度都保持 $O(\log n)$。

10.2.5

(a) 功能上的区别：

	值复制法（本节）	节点替换法
节点对象	被删节点的对象保留（值被覆盖）	被删节点的对象被摘除
后继节点	被删除	被搬走（对象保留）
指向节点的外部引用	失效（值变了）	保持有效
实现复杂度	简单	复杂（要处理父指针或返回新节点）

(b) 如果节点里存的是"指向外部对象的引用"，节点替换法更好。

原因：假设 BST 的每个节点还存了一个"指向订单对象"的引用：

public class BstNode
{
    public int Key;
    public Order Order;      // 指向外部的订单对象
    public BstNode? Left;
    public BstNode? Right;
}

如果外部代码持有某个节点的引用（比如迭代器、或者一个"当前选中项"的指针），那么：

值复制法：被删节点的对象还在，但它的 Key 和 Order 被改成了后继的值 —— 持有这个引用的代码会突然发现它指向了另一个订单！这是静默的数据错乱。
节点替换法：被删节点的对象被摘除（外部引用变成"指向一个已脱离树的节点"），而后继节点的对象保持完整（只是换了位置）。语义更清晰。

实际的库实现（比如 C++ 的 std::map、Java 的 TreeMap）用的大多是"节点替换法"，原因正是这个 —— 标准库要考虑"外部持有节点引用"的情况（迭代器就是个典型）。

而教学实现常用值复制法，因为它简单。知道这个区别，能帮你看懂不同实现的文档。

八、常见错误

误区	纠正
删除时忘记"再删掉后继"	会导致树里出现两个相同的值。`Count` 不对、中序遍历有重复。
认为"插入比查找慢一个量级"	两者是同一量级（都是 $O(\text{树高})$），只是插入多一次 `new`。
说"BST 是 $O(\log n)$"	漏了前提。只有平衡的 BST 才是，退化时是 $O(n)$。
用自增 ID 当 BST 的键	自增 ID 会让 BST 退化成链（因为插入顺序天然有序）。这是 10.3 节的主题。
混用中序前驱和后继	两者都对，但实现里要保持一致。

九、本节总结

三种操作有共同的骨架：从根出发沿一条路径走。代价都正比于树高。
查找：根据大小关系只走一边（剪枝）。实测 3 次比较命中。
插入：查找路径 + 在失败位置挂新节点。重复值的处理策略要事先定义。
删除分三种情况：叶子（直接删）、一个孩子（孩子顶替）、两个孩子（中序后继替代）。
前两个 if 已经把"叶子"和"一个孩子"都覆盖了 —— 代码简洁但理解要清楚。
中序后继能保持 BST 性质：它是"比当前值大的元素中最小的那个"，替代后左右两边都满足约束。
复杂度都是 $O(\text{树高})$：$n = 10^6$ 时，平衡树约 20 次比较，退化链约 100 万次 —— 差 5 万倍。
自增 ID 是让 BST 退化的最坏输入，而它恰恰是最常见的键类型。

下一节衔接：本节末尾已经预告了 —— "插入顺序"决定了树的形状。而且最糟糕的是，最常见的键类型（自增 ID）恰好就是最坏输入。下一节用实测把这件事量化出来，并对比 BST 和有序数组、哈希表在退化前后的表现。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "10.2",
  "title": "查找、插入、删除",
  "covered": [
    "三种操作共同的「沿路径走」骨架与树高依赖",
    "查找的剪枝实现与实测（3 次比较命中）",
    "插入的实现与重复值三种处理策略",
    "删除的三种情况与代码覆盖关系分析",
    "三种情况的完整实测（都保持合法 BST）",
    "中序后继能保持 BST 性质的论证",
    "复杂度表与 n=10^6 时 20 次 vs 100 万次的对比",
    "自增 ID vs 随机 UUID 的树形差异与后果",
    "值复制法 vs 节点替换法的语义差异"
  ],
  "unresolved": [
    "退化问题的量化实测留到 10.3",
    "自平衡机制留到 10.4",
    "迭代器与外部引用的完整讨论超出本书范围"
  ],
  "canonical_terms": {
    "中序后继": "中序遍历中的下一个节点，即右子树的最小值",
    "树高": "从根到最远叶子的边数，决定所有操作的代价"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 10.1 的 BST 性质与 9.4 的递归套路",
    "读者理解 C# 的引用类型与 null 传播"
  ],
  "word_count_actual": 3120,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch10/Sec102/",
    "三种删除情况、插入、查找均为实测且保持了 BST 合法性",
    "练习 10.2.1 的插入与删除推演已手工验算",
    "术语写法与 glossary.md 一致"
  ],
  "next": "10.3 退化问题：为什么需要平衡"
}

10.2　查找、插入、删除