DS-5 查找

这一部分为什么存在？

“给定关键字，在集合里找到它”是计算机最高频的操作。查找效率用 ASL（平均查找长度） 度量 = 比较次数按概率加权平均。演进链的每一步都在回答上一代留下的“但是”：

1. 无序顺序查找 $O(n)$ → 如果有序呢？→ 折半 $O(\log n)$，但要求有序 + 顺序存储（链表再有序也不行，2024-5）；
2. 有序数组插删要搬元素 $O(n)$ → 能不能既有序又好插删？→ BST（中序有序 + 链接插删）；
3. BST 最坏退化成链 $O(n)$ → 能不能强制平衡？→ AVL（严格平衡）→ 红黑树（弱平衡，旋转更少）；
4. 数据在磁盘上，瓶颈不是比较而是 I/O 次数 → 树要“矮胖”→ B 树（多路，一层一次 I/O）；
5. 范围查询/全量遍历 → B 树中序跨结点不方便 → B+ 树（数据全在叶、叶成链）；
6. 能不能跳过比较直接算地址？→ 散列 $O(1)$，但引出冲突与装填因子问题。

flowchart TD
    A["查找：ASL 度量"] --> B["无序 → 顺序 O(n)"]
    B --> C["有序 + 顺序存储 → 折半 O(log n)<br/>判定树"]
    C --> D["插删贵 → BST<br/>中序有序，高 = O(log n)~O(n)"]
    D --> E["退化 → 平衡化<br/>AVL（|BF|≤1）/ 红黑树"]
    D --> F["磁盘 I/O 瓶颈 → B 树<br/>多路矮胖，结点 = 页"]
    F --> G["范围查询 → B+ 树<br/>数据在叶，叶成链"]
    A --> H["算地址 → 散列<br/>冲突：拉链 / 开放定址<br/>装填因子 α"]

核心概念：

1. 折半查找（必须能手写）

int BinarySearch(int A[], int n, int key) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (A[mid] == key) return mid;
        else if (A[mid] < key) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

判定树视角让一切“比较次数”题变成“树高”题：成功 ≤ 树高、失败 ≤ 树高（失败最多 = 树高）。2013-42 大题：不同查找概率下，顺序表按概率降序排 + 顺序查找（ASL = $\sum i \cdot p_i$）vs 折半（ASL 由判定树层数加权）——概率不均时顺序查找反而可能更优，这是大题的标准陷阱。

2. BST 的查找、插入与删除

• 查找/插入：与根比，小左大右递归，插入总在叶位置。
• 删除三分支：叶直接删；单孩子用孩子顶替；双孩子用中序直接前驱（左子树最大）或中序直接后继（右子树最小）顶替后删那个前驱/后继。
• 2013-6 / 2019-4（AVL 同型）：删除 $v$ 再插回 $v$，$T_1$ 与 $T_3$ 是否相同——不一定：若 $v$ 是叶，删插后必相同；若非叶，删除时结构调整（或 AVL 旋转）使形状改变，插回位置随之不同。

3. AVL 旋转（理解机制 + 会模拟）

插入后从插入点向上找第一个失衡结点（|BF|=2），按失衡方向归类：LL 右单旋、RR 左单旋、LR 先左后右、RL 先右后左。判断口诀：看新结点插入在失衡结点的哪条“路径”上（左左/右右/左右/右左）。最小高度结点数递推 $N_h = N_{h-1} + N_{h-2} + 1$（解释：要最少，两个子树也得最少且高差恰为 1）。

4. B 树：为磁盘而生的“矮胖树”

为什么多路（补充理解）：磁盘按页读写，一次 I/O 代价比一次比较大 5 个数量级，所以让一个结点 = 一个页、每个结点装几百个关键字，$10^8$ 条记录也只需 34 层（34 次 I/O）。核心规则（$m$ 阶）：每个结点最多 $m-1$ 个关键字/$m$ 个孩子；非根结点至少 $\lceil m/2 \rceil - 1$ 个关键字；插入满则以中位关键字为界分裂并向上推；删除借兄弟或合并。B+ 树把数据全部压到叶层并让叶成链，使“范围查询”和全表扫描变为叶链顺序读——这是数据库与文件系统（OS-7 索引）选它的原因（2017-9）。

5. 散列表：ASL 的成功/失败计算模板（必考）

以 2010-41 为模板：$H(key) = (key \times 3) \bmod 7$，线性探测，$\alpha = 0.7$ → 表长 = 7/0.7 = 10。

• 成功 ASL = 每个已插入关键字的“插入时探测次数”的平均；
• 失败 ASL = 对每个可能的散列地址（mod 7 共 7 个），从该地址起顺序扫到第一个空位的比较次数的平均（分母是散列函数值域个数，不是表长！）；
• 删除陷阱：开放定址下删除只能置“已删除”标记，不能直接清空，否则截断后续探测链（2023-9）。
• 变体：2024-42 大题用平方探测 $H_k = (H_0 + k^2) \bmod 11$（减堆积），逻辑同上。

B 树 vs B+ 树（本模块第一易混对）：为什么易混——都是多路平衡树、名字只差个加号。本质区别——B 树非叶也存数据（查到即可停，不必到叶，2023-7 III 错误项），B+ 树非叶纯索引、数据全在叶且叶成链。判别线索：题目出现“范围查询/顺序遍历/数据库索引”→ B+ 树；出现“结点关键字即数据、查到非叶就停”→ B 树。

AVL vs 红黑树：AVL 平衡更严（高差 ≤1）→ 查找略快、旋转更多；红黑树约束更弱（最长路径 ≤ 2×最短）→ 插删旋转少，工程上（C++ map、Java TreeMap、epoll）用红黑。408 只要求识别红黑树性质（根黑、红结点孩子必黑、任意路径黑高相同），插入删除细节只识别思想。

散列 vs 树系：散列用“放弃有序性”换 $O(1)$；树系用“维护有序”换对数保证与范围操作。

形态一：折半与判定树：2010-9、2015-7、2017-8、2023-8、2024-5（链表不能折半）、2013-42（概率加权大题）。

形态二：BST：2011-7（路径合法性）、2018-6、2020-5、2024-7、2013-6（删插同一性）。

形态三：AVL：2009-4、2010-4、2012-4（$N_h$ 递推 33）、2013-3、2015-4、2019-4、2021-6。

形态四：B/B+ 树：2009-8（定义）、2013-10、2014-9、2016-10、2017-9、2018-8、2020-10（插入分裂）、2021-9、2022-8（删除调整）、2023-7。

形态五：散列：2010-41（大题模板）、2011-9、2014-8（堆积）、2018-9、2019-8（失败 ASL）、2022-9、2023-9（删除标记）、2024-42（平方探测大题）。

做题触发词：看到“最多比较次数”→ 判定树高；看到“中序”+“有序”→ BST 系；看到“阶/高度/最少关键字”→ B 树上下界公式；看到“mod/探测/装填因子”→ 散列模拟；看到“删除”+“开放定址”→ 置标记不清空。

来源：真题markdown/2009-2024统考真题.md 对应题号。

• 向前依赖：DS-1（顺序存储 vs 链式决定折半可行性）、DS-3（BST/AVL/B 树都是“树 + 约束”；判定树概念）。
• 向后引出：
  • 排序是折半与 BST 的前提 → DS-6（“为什么排序有用”在本章找到答案）；
  • 散列思想 → Cache 组相联的地址映射、TLB（CO-3/X-1，同构的“算 + 查”）；B+ 树 → OS 文件索引（OS-7）、数据库索引（X-8）；
  • 代码题衔接：折半查找必须能手写；BST 判定（2022-41）是树类代码题的常客——DS-7。

1. 查找快慢用什么度量？（ASL，比较次数的概率加权）
2. 折半查找的两个前提是什么？为什么有序链表也不行？
3. 折半的比较次数为什么可以用判定树高度回答？
4. 有序数组插删贵，怎么救？（BST：链接 + 中序有序）
5. BST 最坏会变成什么？怎么强制平衡？（链；AVL 旋转四种）
6. AVL 高 $h$ 的最少结点数怎么递推？为什么这样构造最省？
7. 磁盘查找的瓶颈是比较次数吗？B 树为什么又矮又胖？（I/O；结点=页）
8. B 树的阶、高度、关键字数上下界怎么算？插入满了怎么办？
9. B+ 树和 B 树三点不同？为什么数据库选 B+？（叶链 → 范围查询）
10. 散列为什么能 O(1)？代价是什么？（放弃有序；冲突）
11. 成功 ASL 和失败 ASL 各怎么数？失败 ASL 的分母是谁？
12. 开放定址的表为什么不能直接清空删除？（探测链截断，置标记）
13. 查找结构的演进如何贯穿“内存 vs 外存”这条暗线？（接 CO-3 存储层次）