3.2 Binary Search Trees：路径查找、有序操作与Hibbard删除

3.2 · Binary Search Trees覆盖 5 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

  • 能解释“3.2 · Binary Search Trees”如何沿根到键的路径实现查找、插入、有序操作、范围查询与 Hibbard 删除
  • 能逐项核对 二叉搜索树、BST查找与插入、BST分析、有序操作、BST删除，并区分作者站内容与本页独立补充
  • 能按“rank(x)=size(left(x))+rank(x.right,key)（当 key>x.key）”手算一个最小输入，逐步检查“每个节点左子树键更小、右子树键更大，size=1+size(left)+size(right)”
  • 能注入“Hibbard 删除后只修复局部链接却没有自底向上重算 size”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“3·2 · Binary Search Trees”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“3·2 · Binary Search Trees”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“3·2 · Binary Search Trees”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：3.2 · Binary Search Trees

  • 1. 二叉搜索树：在本页通过“从根比较键”连接解释、交互状态和练习验收。
  • 2. BST查找与插入：在本页通过“选择左或右子树”连接解释、交互状态和练习验收。
  • 3. BST分析：在本页通过“执行更新或删除”连接解释、交互状态和练习验收。
  • 4. 有序操作：在本页通过“重算子树大小”连接解释、交互状态和练习验收。
  • 5. BST删除：在本页通过“核对中序与 rank”连接解释、交互状态和练习验收。

从“有序数组插入太贵”开始

二叉搜索树（binary search trees）尝试结合linked insertion的灵活性与ordered search的方向性。它不搬移整段array；每次comparison决定向left还是right，只修改一条root-to-null path上的links。

先预测按A、B、C、D顺序插入是否得到balanced tree。不会。每个新key都大于当前所有nodes，只沿right links下降，BST退化为linked list；search与put从logarithmic直觉退成linear。普通BST的性能由shape决定，而shape又由insertion order决定。

官方3.2按 Basic implementation、Analysis、Order-based methods and deletion 展开。所有operation的统一成本参数不是N本身，而是height h；所有ordered operation的统一支点是node的subtree size。

3.2.1 BST invariant与node anatomy

BST不变量是全subtree约束，不只是“left child小、right child大”。若root为10、left child为5，但5的right descendant为12，parent-child两条edge看似合理，整棵树仍不是BST。

Official node保存key、value、left、right、size：

private class Node {
    private Key key;
    private Value val;
    private Node left;
    private Node right;
    private int size;
 
    Node(Key key, Value val, int size) {
        this.key = key;
        this.val = val;
        this.size = size;
    }
}
 
private int size(Node x) {
    return x == null ? 0 : x.size;
}

子树大小（subtree size）必须满足：

size(x)=1+size(x.left)+size(x.right)size(x)=1+size(x.left)+size(x.right)

它让whole-table size constant，并让rank/select跳过整棵subtree。任何put/delete沿return path都必须重算size；只修links不修counts，会让basic get仍正确，却让ordered methods静默错误。

3.2.2 BST search and insertion：同一路径到hit或null

BST查找与插入（BST search and insertion）都从root比较。Query小就进入left，大就进入right，相等命中。Get在null返回absent；put在null创建size 1 node，相等则覆盖value。

private Value get(Node x, Key key) {
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if      (cmp < 0) return get(x.left, key);
    else if (cmp > 0) return get(x.right, key);
    else              return x.val;
}
 
private Node put(Node x, Key key, Value val) {
    if (x == null) return new Node(key, val, 1);
    int cmp = key.compareTo(x.key);
    if      (cmp < 0) x.left = put(x.left, key, val);
    else if (cmp > 0) x.right = put(x.right, key, val);
    else              x.val = val;
    x.size = 1 + size(x.left) + size(x.right);
    return x;
}

Recursive method返回subtree root至关重要：caller必须把结果重新赋给 x.left 或 x.right，因为insert空link、delete或rotation都可能改变child root。Public put仍遵守3.1的null contract：null key拒绝，null value转delete。

Correctness用recursive invariant证明。进入call时x所代表subtree是BST；comparison只递归唯一可能包含key的一侧；recursive result仍是BST且keys范围未跨越x；接回后重算size，整个subtree恢复两类invariant。

3.2.3 BST analysis：随机平均不等于worst guarantee

BST分析（BST analysis）不能只说“binary所以log N”。对N个random distinct keys或random insertion order，官方命题给search hit、insert和miss平均约：

E[CN]∼2ln⁡N≈1.39lg⁡N\mathbb E[C_N]\sim 2\ln N\approx1.39\lg N

但worst height是N减1，所有path operationsTheta(N)。Perfect balanced tree height约floor(lg N)：

⌊lg⁡N⌋≤h≤N−1\lfloor\lg N\rfloor\le h\le N-1

同一key set产生的shape由insertion order决定。Random assumption必须来自真实input model或显式shuffle；按timestamp、自增ID、sorted file导入常会形成坏树。下一节balanced search trees加入结构修复，提供height guarantee。

Recursive implementation额外stack与height同阶；退化tree不仅慢，还可能stack overflow。Iterative get/put可避免call stack，却不能改善comparison path，必须区分implementation safety与data-structure balance。

3.2.4 Order-based methods：沿path保留candidate

有序操作（order-based methods）都只访问可能包含答案的paths/subtrees。

Minimum沿left links到null-left node，maximum沿right。Floor query若小于x.key，只能在left；若大于x.key，先去right找更大但仍不超过query的candidate，right无解才退回x。Ceiling左右对称。

private Node floor(Node x, Key key) {
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp == 0) return x;
    if (cmp < 0) return floor(x.left, key);
    Node candidate = floor(x.right, key);
    return candidate != null ? candidate : x;
}

Rank与select利用left size t：

rank(x.key)=size(x.left)rank(x.key)=size(x.left)

Select(k)若 k<t 去left；若 k==t 返回x；若 k>t 去right并把local rank改为 k-t-1。Rank(query)向right时必须累加 1+size(left)，因为这些keys都严格小于query。

Inverse certificate是：

rank(select(i))=i,select(rank(k))=k for present krank(select(i))=i, \qquad select(rank(k))=k\ \text{for present }k

Stale subtree size最容易被这组checks捕获。Floor/ceiling还需测below-min、above-max和exact cases；无candidate时官方public API抛NoSuchElementException。

3.2.5 BST deletion：零/一子节点与Hibbard两子节点

BST删除（BST deletion）对零或一child直接返回non-null child。DeleteMin沿left到 x.left==null，返回x.right替代x，因为right中的所有keys仍落在parent允许范围。

两children时使用Hibbard deletion：

private Node delete(Node x, Key key) {
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if      (cmp < 0) x.left  = delete(x.left, key);
    else if (cmp > 0) x.right = delete(x.right, key);
    else {
        if (x.right == null) return x.left;
        if (x.left  == null) return x.right;
        Node old = x;
        x = min(old.right);
        x.right = deleteMin(old.right);
        x.left = old.left;
    }
    x.size = 1 + size(x.left) + size(x.right);
    return x;
}

Successor是right subtree minimum，没有left child；移除它后，其right child接到原位置。Successor key大于old left所有keys、又不大于old right其余keys，因此接回两侧保持order。Size必须从successor新root开始重算，并由ancestor return path继续向上。

Hibbard deletion总选successor而不随机在successor/predecessor间对称选择，长期random delete/insert会让tree产生偏斜；它正确但不提供balance guarantee。Deletion tests要覆盖leaf、only-left、only-right、two-child、root、missing与重复delete。

3.2.6 Inorder与range search：order自然流出

Inorder traversal先left、再node、再right，由BST invariant直接得到ascending keys。Range [lo,hi] 可prune：若lo小于x.key才需探left；若x在range就enqueue；若hi大于x.key才需探right。

private void keys(Node x, Queue<Key> out, Key lo, Key hi) {
    if (x == null) return;
    int cmpLo = lo.compareTo(x.key);
    int cmpHi = hi.compareTo(x.key);
    if (cmpLo < 0) keys(x.left, out, lo, hi);
    if (cmpLo <= 0 && cmpHi >= 0) out.enqueue(x.key);
    if (cmpHi > 0) keys(x.right, out, lo, hi);
}

Search、insert、min/max、floor/ceiling、rank/select、delete与range count worst case都与height成正比；range enumeration还至少与输出size成正比。Whole keys traversal是Theta(N)，不应宣称仅Theta(h)。

Certification至少包含三项：global min/max bounds验证isBST；recursive size equation；rank/select consistency。再与reference ordered map随机执行put/get/delete/range sequences，可同时捕捉association、order与metadata errors。

统一验收：把一条path和整棵tree同时核查

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“3.2 · Binary Search Trees”的两个最小情境间切换，再逐项选择正式概念。预测“rank(x)=size(left(x))+rank(x.right,key)（当 key>x.key）”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

3.2 · Binary Search Trees：对象、操作与不变量

沿根到键的路径实现查找、插入、有序操作、范围查询与 Hibbard 删除

选择最小情境

切换正式概念

输入合同操作证书algs4-3.2 · 先给前提，再执行，再验收当前概念：1/6
路径查找
在键 [S,E,X,A,R,C,H] 构成的 BST 中查找 R
当前观察
binary search trees：每次比较只排除一侧子树，轨迹可由根到 R 重放
rank(x)=size(left(x))+rank(x.right,key)（当 key>x.key）

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

  • 二叉搜索树：在实验 1 中指出对应状态，并写出一个通过条件。
  • BST查找与插入：在实验 2 中指出对应状态，并写出一个通过条件。
  • BST分析：在实验 3 中指出对应状态，并写出一个通过条件。
  • 有序操作：在实验 1 中指出对应状态，并写出一个通过条件。
  • BST删除：在实验 2 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“rank(x)=size(left(x))+rank(x.right,key)（当 key>x.key）”不是孤立结论？

问题 3：故障恢复。 怎样证明“Hibbard 删除后只修复局部链接却没有自底向上重算 size”已经修复？

本章回顾

  1. BST要求每个node左subtree全小、右subtree全大，并维护subtree size。
  2. Get与put沿同一comparison path，miss null link正是new node位置。
  3. 普通BST operation成本与height成正比；random average log N，worst linear。
  4. Floor/ceiling在单path上保留candidate，rank/select借left size跳过subtree。
  5. Hibbard deletion以right minimum successor替换two-child target并deleteMin旧右树。
  6. Inorder自然输出ascending keys，range traversal可按lo/hi剪枝。
  7. isBST、size consistency、rank/select inverse与reference map共同组成可靠验收。

资料与写作方式声明

本章以Algorithms, Fourth Edition的合法公开试读核定可见范围，并以目录限定未公开部分，并结合正文列出的技术资料独立重写；不宣称复现原书正文，也不沿用原作表述。

原作版权归作者与出版社所有；本站原创教学结构与表述仅供学习交流。

讨论

评论区加载中…