二叉搜索树：性质、查找与删除

一句话定义

二叉搜索树（Binary Search Tree, BST）在每个节点上维持不变量「左子树所有键 < 根 < 右子树所有键」，使查找、插入、删除都只需走一条根到叶的路径，代价为 O(h)，h 为树高。

为什么重要

BST 第一次示范了「用维护不变量换取操作效率」的完整闭环：一条序性质换来 O(log n) 的查找与插入、有序遍历、范围查询、前驱后继查询。它是 kp-013 平衡树、B+ 树（kp-015）以及 TreeMap 类库的直系祖先；「BST 删除三大情形」更是数据结构面试的经典硬菜。

前置知识

kp-011（二叉树与中序遍历）；比较运算。

核心概念

• 序不变量：对任意节点 x，左子树 keys < key(x) < 右子树 keys（等键需单独约定去重或计数）。
• 核心推论：中序遍历输出严格递增序列——「按序组织」的全部红利由此而来。
• 查找/插入：从根出发，比大小走左或右，直到空位；代价 O(h)。
• 删除三情形：叶子直接删；单孩子让子继位；双子节点用「后继（右子树最小）」或「前驱（左子树最大）」替换键值再删那个替换节点。
• 退化的深渊：按有序序列插入，树退化为链表，h=n，操作全变 O(n)——这是平衡树（kp-013）存在的理由。
• 增强树：节点额外维护子树大小/子树和，可 O(h) 查第 k 小、区间统计。

直观类比

BST 是「每层都能二选一的索引卡」：查「王五」时在每张卡上比一次姓氏序就淘汰一半分支——前提是卡片树摆放规则没被破坏；如果你按顺序一张张往下挂（有序插入），它就退化成一本只能线性翻的册子。

原理与机制

删除双子节点情形的机制：后继 = 右子树中序最小者，它至多有一个右孩子（否则左孩子更小）。用后继的键替换被删节点的键，再删除后继原节点（单孩子情形），序不变量全程保持。范围查询 [lo, hi]：递归时仅当子树可能含目标区间才下探，输出即中序片段，代价 O(h + 输出数)。

查找伪代码:
  cur ← root
  当 cur ≠ 空:
      若 key == cur.key: 返回 cur
      否则若 key < cur.key: cur ← cur.left
      否则: cur ← cur.right
  返回 未找到

图示

删除 5（双子）:
        5                 6
       / \               / \
      3   8    ⇒        3   8
         / \               / \
        6   9             7   9
         \
          7      6 是 5 的后继（右子树最小），先替换值再摘除原位。

实例或案例

• 按名字索引的通讯录：插入乱序建树，中序输出即按名字典序。
• 滑动窗口中位数（增强 BST 记子树大小）：增删 O(log n) + 查第 k 小 O(log n)。
• 语言标准库：C++ std::map/set（通常红黑树，见 kp-013）、Java TreeMap 都是有序映射 ADT 的 BST 系实现；与 kp-009 哈希表形成「有序 vs 无序」的分野。

常见误区

• 删除双子节点时随手拿左孩子顶位：破坏序不变量，后继/前驱替换才是正确姿势。
• 以为 BST「自动平衡」：插入序决定形状，有序插入必然退化 O(n)。
• 中序遍历「等于」排序没问题，但以为因此 BST 查找也是 O(log n)：只有平衡时才成立，要写 O(h)。
• 等键处理不一致：先约定（禁止重复 / 右子树允许相等 / 节点内计数），全库保持同一约定。

自测题

1. 依次插入 5 2 8 1 3 7 画出 BST，再删除 2，画结果。

答案要点：树为 5(2(1,3),8(7,·))；删 2（双子）用后继 3 替换得 5(3(1,·),8(7,·))。

1. 为什么「后继节点至多有一个右孩子」？

答案要点：后继是右子树最小者，若有左孩子则左孩子更小，与「最小」矛盾。

1. 如何在 BST 中 O(h) 求某键的前驱？

答案要点：若有左子树取左子树最大；否则向上回溯到第一个「该节点位于其右子树」的祖先。

与其他知识点的关系

kp-013 用旋转把 h 压到 O(log n)；kp-014 堆是「只保证部分序」的对照物（取最值快、不支持按序遍历）；kp-015 B+ 树是 BST 思想在磁盘扇出上的放大；kp-009 哈希表是无序场景的替代。

延伸阅读

《算法导论》第 12 章全部；《算法（第 4 版）》第 3.2 节（含范围查询与 Hibbard 删除的缺陷讨论）。