#查找

#考点定位

• 所属大纲章节：查找的基本概念；顺序查找、折半查找、分块查找；二叉排序树；平衡二叉树；红黑树；B 树及其基本操作、B+ 树的基本概念；散列表；字符串模式匹配（已在串与KMP单独成章）；查找算法的分析及应用
• 常见题型：选择题（ASL 计算、折半判定树、B 树/B+ 树性质与结点数计算、红黑树性质、散列冲突与装填因子）；手推大题（AVL 插入旋转、B 树插入分裂、散列表构造与 ASL）
• 考查频率：极高。散列表与 B 树几乎是每年的必考点，折半判定树与 AVL 旋转是手推题常客

工程直觉迁移：你天天用 std::map、数据库索引、std::unordered_map，底层就是红黑树、B+ 树、散列表——工程直觉告诉你"为什么用它们"；本章要补的是考试特有产物：ASL 的定义式计算口径、折半查找判定树、AVL 四种旋转的手推规范、B 树关键字数上下界的推导、开放定址法下失败 ASL 的数法。这些全是应试细节，工程中从不手算。

前置知识：树与二叉树（二叉树性质、完全二叉树编号）、绪论与复杂度分析。

#零、查找的基本概念与 ASL

• 查找表：由同一类型的数据元素（记录）组成的集合。关键字：数据元素中某个可以唯一标识该记录的数据项；平均查找长度（ASL，Average Search Length）是衡量查找算法效率的指标——一次查找中关键字比较次数的期望值：

$ASL = \sum_{i=1}^{n} P_i \times C_i$

其中 $P_i$ 为查找第 $i$ 个元素的概率（通常取等概率 $P_i = 1/n$），$C_i$ 为找到第 $i$ 个元素所需的比较次数。

• 成功 ASL 与失败 ASL 分开算：查找成功是对"表中有 n 个元素各被查一次"取平均；查找失败是对"所有可能的失败入口各来一次"取平均（顺序/折半查失败入口为 $n+1$ 种，散列表 %$p$ 为 $p$ 种，见各节口径）。408 试题两者都考，口径必须与解析对齐。
• 静态查找表 vs 动态查找表：只查不改（顺序/折半/散列查找）为静态；查找同时伴随插入/删除（BST、AVL、B 树）为动态。动态结构关心"最坏情况下也不退化"——这正是 AVL、红黑树、B 树存在的动机。

#一、顺序查找

#算法步骤

从表的一端（通常从下标小端）逐个比较关键字，相等则成功；扫描完仍无则失败。工程写法是 for + break，考试标准写法用哨兵省掉越界判断：

int SeqSearch(SSTable ST, ElemType key) {
    ST.R[0].key = key;                 // R[0] 为哨兵，不存数据
    for (int i = ST.TableLen; ST.R[i].key != key; i--)
        ;                              // 空循环体，遇 key 必停
    return i;                          // 返回 0 即失败
}

哨兵的作用：循环内不必判断下标越界（$R[0]$ 保证必然命中终止循环），省一半比较分支——这本身就是选择题考点。

#ASL 与复杂度

• 成功：等概率下 $P_i = 1/n$，找到第 $i$ 个元素比较 $n - i + 1$ 次（从后往前扫）或 $i$ 次（从前往后），两种口径求和相同：

$ASL_{成功} = \frac{1}{n}\sum_{i=1}^{n}(n-i+1) = \frac{n+1}{2}$

• 失败：关键字不在表中时须与全部 $n$ 个元素（含哨兵口径下是比较 $n+1$ 次）比较后才失败，故 $ASL_{失败} = n + 1$（王道口径，把与哨兵的那次也算入；若不含哨兵为 $n$，看题目给的算法）。
• 时间 $O(n)$，空间 $O(1)$；对表无任何要求（无序也行、链式也行）。优化：被查概率不等的元素按概率降序排列可降低成功 ASL（哈夫曼思想）。

#二、折半查找（二分查找）

#前提与算法步骤

前提：① 关键字有序；② 顺序存储（需随机存取定位 mid）。链表存储不能折半查找——这是判断题/选择题高频陷阱。

以升序表为例，设 mid = ⌊(low + high) / 2⌋（向下取整）：

1. 初始 low = 1, high = n；
2. 若 low > high，失败结束；
3. 取 mid，比较 ST.R[mid] 与 key：相等则成功；key < R[mid] 则 high = mid - 1；key > R[mid] 则 low = mid + 1；回到 2。

int BinSearch(SSTable ST, ElemType key) {
    int low = 1, high = ST.TableLen, mid;
    while (low <= high) {
        mid = (low + high) / 2;        // C 语言整除即向下取整
        if (ST.R[mid].key == key) return mid;
        else if (ST.R[mid].key > key) high = mid - 1;
        else low = mid + 1;
    }
    return 0;                          // 失败
}

#判定树：一切折半查找问题的通用解法

把每次 mid 作为树根、两次递归搜索区间作为左右子树，得到唯一的判定树（也叫二叉判定树/比较树）。它满足：

• 形态唯一确定：由 mid 取法唯一决定（向下取整时，每个结点的左子树结点数等于右子树或比右子树多 1，即判定树是"偏左平衡"的）；它不是一般意义上的满二叉树，但与同高度的满二叉树编号 1..n 对应，可套完全二叉树的高度公式。
• n 个元素的成功查找对应 n 个内部结点；失败对应 n + 1 个外部结点（方形失败结点）——n 个内部结点的二叉树恰有 $n+1$ 个空链域，每个空链域挂一个失败结点（完全二叉树编号性质 $2i$、$2i+1$ 越界即失败入口）。
• 成功比较次数 = 该元素所在层数（根为第 1 层）；失败比较次数 = 失败结点的双亲结点所在层数（走到空位前最后一次和双亲比较过）。
• 判定树高度 $h = \lceil \log_2(n+1) \rceil$，故成功查找最多比较 $h$ 次，$ASL_{成功} \approx \log_2(n+1) - 1 < \lceil \log_2(n+1) \rceil$，时间复杂度 $O(\log_2 n)$。

以有序表 {7, 10, 13, 16, 19, 29, 32, 33, 37, 41, 43}（n = 11，经典 2012 真题序列）为例，其判定树：

（结构说明：第 4 层的 10、19、33、43 分别是第 3 层结点 7、16、32、41 的右孩子——因为 mid 向下取整，右子区间更短，判定树呈"左满右缺"形态，高 $h = \lceil \log_2 12 \rceil = 4$。）验证查找 16：mid 序列 29 → 13 → 16，共比较 3 次；查找 7：mid 序列 29 → 13 → 7，共比较 3 次；查找失败的情形落到 12 个外部结点之一，比较次数为其双亲所在层（最多 4，最少 3）。

手推判定树的快速方法：不画树也能数比较次数——按算法在区间 [low, high] 上迭代到命中/失败，逐步记录 mid；考试建议直接模拟算法而不是凭树感。

#ASL 推导（n 较大时）

判定树近似平衡，$n = 2^h - 1$（满）时第 $k$ 层有 $2^{k-1}$ 个结点：

$ASL_{成功} = \frac{1}{n}\sum_{k=1}^{h} k \cdot 2^{k-1} = \frac{n+1}{n}\log_2(n+1) - 1 \approx \log_2(n+1) - 1$

（推导要点：$\sum_{k=1}^{h} k\cdot 2^{k-1} = (h-1)\cdot 2^h + 1$，再用 $2^h = n + 1$ 代入。）一般 $n$ 下 $ASL_{成功}$ 严格小于 $\lceil\log_2(n+1)\rceil$，可按"≈ 对数级"做选择估算。

#三、分块查找（索引顺序查找）

#结构定义

分块查找 = 顺序查找 + 折半/顺序查找的组合，要求"块间有序、块内无序"：

• 把表均分为 b 块，每块 s 个元素（$n = b \times s$ 或最后一块不满）；
• 前一块的最大关键字 < 后一块中所有关键字（块间有序），块内不要求有序；
• 另建索引表，按块序存放每块的最大关键字和块起始地址，索引表有序。

#查找步骤与 ASL

1. 在索引表中确定目标块（索引有序，可顺序或折半查找）；
2. 在块内顺序查找（块内无序，只能顺序）。

$ASL = L_I(\text{索引查找}) + L_S(\text{块内查找})$

• 索引表也用顺序查找：$ASL = \dfrac{b+1}{2} + \dfrac{s+1}{2}$。固定 $n = b s$ 时对 s 求导取极值，$s = \sqrt{n}$（此时 $b = \sqrt{n}$）最优，$ASL = \sqrt{n} + 1$。
• 索引表用折半查找：$ASL \approx \lceil \log_2(b+1) \rceil + \dfrac{s+1}{2}$。

例（模拟题）：$n = 630$，每块 $s = 21$（$b = 30$），块间块内均顺序查找：$ASL = \dfrac{31}{2} + \dfrac{22}{2} = 15.5 + 11 = 26.5$。

#四、二叉排序树（BST）

#定义与核心性质

二叉排序树或为空树，或满足：左子树上所有结点的关键字均小于根的关键字，右子树上所有结点的关键字均大于根，且左右子树各又是一棵二叉排序树。注意是"所有后代"与根比较，不是只和双亲比较——给序列判断能否构成某 BST、或判断某树是否 BST 时，必须逐子树验证。

核心性质：中序遍历 BST 得到递增有序序列。这是"由两个遍历序列重建 BST""判断二叉树是否 BST""BST 中求第 k 小"等题的统一入口。

#查找与插入

• 查找：从根出发，小则左、大则右，空则失败；比较次数 = 目标结点所在层数（失败时为路径长度 + 1）。
• 插入：走查找路径到空位置，作为新叶结点插入——BST 的插入必然插在叶子位置，不会插到中间。由同一组关键字按不同次序插入会得到不同的 BST（选择题常考反例：{2,1,3} 与 {1,2,3} 两种插入序形态不同）；但中序序列相同。

#删除（三种情形，408 经典）

设被删结点为 p，其双亲为 f：

1. p 是叶子：直接删除。
2. p 只有一棵子树：用其左/右孩子替代 p（子树整体上移）。
3. p 有两棵子树：用 p 的中序前驱（p 左子树中最右下结点，即左子树最大）或中序后继（p 右子树中最左下结点，即右子树最小）的关键字替换 p，再删除那个前驱/后继结点（它必无右孩子/无左孩子，回到情形 2 或 1）。两种替换都保持 BST 性质，考试看题目指定用哪种。

#ASL 分析

BST 的查找性能取决于树形：n 个相同结点、不同插入次序会得到不同 ASL。

• 最好（形态平衡）：$ASL \sim \log_2 n$，与折半查找同量级；
• 最坏（按有序序列插入，退化成单支树/链）：$ASL_{成功} = \dfrac{n+1}{2}$，查找退化为顺序查找，$O(n)$。

选择题给 n 个关键字的插入序问"最少/最多比较次数"时，按"最优是平衡判定树形、最坏是链形"两个极端算。

#五、平衡二叉树（AVL）

#定义

平衡二叉树（AVL 树）：任意结点的左右子树高度差的绝对值不超过 1 的二叉排序树。平衡因子 BF（Balance Factor）= 左子树高 − 右子高，AVL 中每个结点 $BF \in \{-1, 0, 1\}$。AVL = BST + 平衡条件，其查找效率稳定在 $O(\log_2 n)$（n 个结点的 AVL 高度 $h$ 满足 $h < 1.44\log_2(n+2)$，考试一般只需知道"$\log_2 n$ 量级、绝不退化到 n"）。

#四种失衡的判定（考试的动作分解）

插入后从插入点向上找第一个 BF 变成 ±2 的祖先结点 A（最小不平衡子树的根），设 A、A 的孩子 B、A 的孙子 C 沿插入路径排列，按"插入点在 A 的哪侧孩子的哪侧子树"分类：

判定口诀：两字母看"插入点相对最小不平衡根的路径"（第一个字母是孩子方向，第二个是孙子方向），同字母（LL/RR）单旋一次，异字母（LR/RL）双旋两步。注意调整的只是最小不平衡子树——旋转后该子树高度恢复到插入前，上方祖先的 BF 自动复原，一次插入至多一次旋转调整。

#右单旋与左单旋的完整操作

• 右单旋（LL 型）：A 的左孩子 B 上升为新根，B 的原右子树 $\beta$ 挂到 A 的左下（$\beta$ 中所有关键字介于 A、B 之间，故可作 A 的左子树），A 连同其右子树整体成为 B 的右孩子：

• 左单旋（RR 型）完全对称：A 的右孩子 B 上升，B 的原左子树挂到 A 的右下，A 成为 B 的左孩子。
• 旋转的统一本质：三个方向的子树按关键字大小重挂（BST 中序序不变），BF 重算——单旋后新根 B 与 A 的 BF 均为 0（LL/RR 型插入）。

#LR / RL 两步旋转详解（以 LR 为例）

例：向 AVL 依次插入 {50, 30, 70, 20, 40, 35}（模拟题，分步演示，另配单步交互动画，见交互演示页 AVL 树旋转）：

更正并细化上例的关键判定：自插入点向上，40: BF=1 正常；30: 左高 1、右高 2，BF = −1 正常；50: 左子树（30 一侧）高 3、右子树（70）高 1，BF = +2 失衡——最小不平衡子树以 50 为根，插入点 35 在 50 的左孩子（30）的右子树（40）里 → LR 型，两步旋转：

RL 型对称：先对右孩子右旋、再对根左旋。记忆锚点：LR/RL 双旋后孙结点 C 成为新根，三个结点关键字排序后 C 恰居中（例中 30 < 35? 不，例中 30、40、50 排序 40 居中，新根正是 40）——双旋结果 = "把 A、B、C 三结点中关键字居中者提为子树根，另外两个按大小挂左右，四棵子树按区间归位"。这个"中者提根"速算法可用来 10 秒复核答案。

#插入与删除的完整步骤

插入：① 按 BST 规则插入为叶；② 自插入点向上重算 BF，找到最小不平衡子树；③ 按 LL/RR/LR/RL 调整。一次插入至多一次旋转（含双旋的两步）即恢复全树平衡。

删除：① 按 BST 三情形删除；② 自删除点向上重算 BF 并调整。与插入不同：调整会使子树高度降低，可能引发上方祖先连锁失衡，需要一路向上多次旋转。这是"插入至多一次旋转、删除可能多次"选择题的标准答案。

#最少结点数递推（高频计算题）

高度为 $h$ 的 AVL 的最少结点数 $N_h$：要高度为 h 且结点最少，根的一侧子树高 $h-1$、另一侧高 $h-2$，两侧都取最少：

$N_h = N_{h-1} + N_{h-2} + 1,\quad N_1 = 1,\ N_2 = 2$

（约定空树高度 0。若题目按"n 个结点的 AVL 最大高度"提问，等价于找使 $N_h \le n$ 的最大 h。）对应形态是斐波那契树（各层只保最瘦分支），由递推亦可得 $N_h = F_{h+2} - 1$（$F$ 为斐波那契数列，$F_1=F_2=1$）。

#六、红黑树

#五大性质（定义）

红黑树是满足以下五条的二叉排序树（结点带颜色域）：

1. 每个结点或是红色，或是黑色；
2. 根结点是黑色；
3. 每个叶结点（外部结点/NULL 指针）是黑色（此"叶结点"指失败结点，不是含关键字的数据结点）；
4. 红结点的两个孩子都是黑色（即不存在两个相邻的红结点——红父必黑子，"黑红交替"）；
5. 对每个结点，从该结点到其所有后代叶结点的简单路径上，黑色结点数目相同（此数目称为该结点的黑高 bh，全树的黑高即根的黑高）。

由性质 4、5 的联合推论（考试会问"为什么"）：

• 从根到叶的最短路径是纯黑路径（长 = 黑高）；最长路径是红黑相间路径，长度至多 $2 \times$ 黑高。故最长路径不超过最短路径的 2 倍；
• 由此，$n$ 个内部结点的红黑树高度 $h \le 2\log_2(n+1)$（对比 AVL 的 $1.44\log_2(n+2)$，红黑树是"近似平衡"：放宽平衡换更少的旋转次数）。红黑树查找效率低于同规模的 AVL，但插入删除的旋转开销更小——这正是工程（std::map）选红黑树的原因。

#旋转

与 AVL 的左旋、右旋完全相同的操作（只动指针不碰颜色），复习上节 AVL 旋转即可。

#插入调整（三种情形，408 考点）

插入步骤：先按 BST 插入，新结点 z 着红色（着红色只可能违反性质 2/4；若着黑必然违反性质 5，代价更大——这句原理是选择题点）。随后按插入点向上的父子关系分情形调整（设父 P、叔 U、祖 G）：

关键结论：

• 情形 2 只变色不旋转、可能连续上溯；情形 3 最多两次旋转（LR/RL 双旋）即终止。故红黑树一次插入：旋转至多 2 次，但变色可至多 $O(\log_2 n)$ 次（沿树高上溯）；
• 变色口径速记："父叔双红 → 变色上移；父红叔黑 → 旋转终结"；
• 分步示例（向合法红黑树插入序列过程中的若干中间状态）已配单步交互动画，见交互演示之"红黑树插入"小节（依次触发 RR 旋转、父红叔红变色、LL 旋转，每步注明黑高一致性校验结果）。

删除的调整涉及更多子情形，历年 408 未考过完整删除过程（大纲表述为"红黑树"性质与基本操作，插入为主），掌握定义、性质推论与插入三情形即可；如需完整删除规则，以"用中序后继替换后转化为删除红/黑结点讨论"为主线，此处不展开（保守口径）。

#七、B 树与 B+ 树

#B 树（多路平衡查找树）的定义

一棵 m 阶 B 树（或为空树）满足：

1. 每个结点至多 m 棵子树（即至多 $m-1$ 个关键字）；
2. 除根外每个非叶（分支）结点至少 $\lceil m/2 \rceil$ 棵子树（即至少 $\lceil m/2 \rceil - 1$ 个关键字）；若根不是叶结点，至少 2 棵子树（1 个关键字）；
3. 所有叶结点在同一层（叶结点即查找失败的外部结点，不带信息——这就是 B 树"多路平衡"的含义：绝对平衡）；
4. 结点结构：含 $n\ (\lceil m/2\rceil - 1 \le n \le m-1)$ 个关键字 $K_1 < K_2 < \cdots < K_n$ 与 $n+1$ 个指针 $P_0 \cdots P_n$，子树 $P_{i-1}$ 中所有关键字 $< K_i$，子树 $P_i$ 中所有关键字 $> K_i$（关键字之间夹子树，与 BST"小左大右"是同一条规则的多元推广）。

为什么下界是 $\lceil m/2 \rceil - 1$：这是分裂操作反向设计的产物——结点满（$m-1$ 个关键字）再插入会溢出到 $m$ 个，取第 $\lceil m/2 \rceil$ 个上移后左右各剩 $\lceil m/2 \rceil - 1$ 个；为让每个结点都"恰好可由一次分裂产生"，就规定下界为 $\lceil m/2 \rceil - 1$。这是理解而非死记的关键。

高度计算（含叶/失败层，选择题口径）：$n$ 个关键字的 m 阶 B 树高度 $h$ 满足

$\log_m(n+1) \le h \le \log_{\lceil m/2 \rceil}\left(\frac{n+1}{2}\right) + 1$

推导：最矮 = 每结点塞满 $m$ 棵子树，第 $l$ 层最多 $m^{l-1}$ 个结点，n 个关键字对应 $n+1$ 个失败结点（最底层），故 $m^{h-1} \ge$ …（逐层计数可得下界）；最高 = 每结点只保下界 $\lceil m/2\rceil$ 棵子树，同理放大。考试更常考的是"给定阶与高度，求最多/最少关键字数"：直接按"满配 $m-1$ 个/最瘦 $\lceil m/2\rceil - 1$ 个"逐层累乘。

#B 树的插入（分裂）

插入总发生在最底层非叶（终端）结点（先按 B 树路径下行定位，插入后仍保持所有叶同层）：

1. 定位终端结点，插入关键字后保持结点内有序；
2. 若结点关键字数达到 $m$（上溢出），取第 $\lceil m/2 \rceil$ 个关键字上移插入双亲，左右各 $\lceil m/2 \rceil - 1$ 个关键字分裂成两个结点；
3. 上移可能使双亲也溢出，连锁向上分裂；根分裂时新建根（上移关键字独居新根），树高加 1——B 树长高是"根向上裂开"，不是叶向下长。

例（模拟题）：5 阶 B 树某终端结点含 {8, 20, 32, 45}（4 = $m-1$ 个，已满），插入 51：{8, 20, 32, 45, 51} 溢出，第 $\lceil 5/2 \rceil = 3$ 个即 32 上移，原结点分裂为 {8, 20} 与 {45, 51}。完整的插入-分裂单步动画（3 阶，$t=2$，含连锁分裂与根分裂）见交互演示之"B 树插入与分裂"小节。

#B 树的删除

先定位：若被删关键字在非终端结点，用其中序前驱（左子树最右）或中序后继（右子树最左，必在终端层）替换后删除副本——归约为终端结点删除。终端结点删除后：

#B+ 树的定义与 B 树差异

一棵 m 阶 B+ 树满足：每个分支结点至多 m 棵子树；除根外至少 $\lceil m/2 \rceil$ 棵子树，根至少 2 棵；n 棵子树的结点含 n 个关键字（注意：与 B 树"n 棵子树 n−1 个关键字"相反）；所有叶结点包含全部关键字及指向记录的指针，且叶结点按关键字大小用链表串联（支持高效顺序/范围查找）；非叶结点仅作索引——结点中每个关键字 $K_i$ 等于其相应子树（第 $i$ 棵）中最大关键字，故关键字会在叶结点重复出现。

记忆锚点：B 树"关键字夹子树、命中即停"；B+ 树"关键字挂子树头、必走到叶"。

#八、散列表（Hash 表）

#基本概念

散列函数 Hash(key)：把关键字映射为存储地址的函数，理想情况下查找不需比较、$O(1)$ 定位。冲突：不同关键字映射到同一地址；映射到同一地址的关键字互称同义词。冲突不可避免（关键字空间大于地址空间），只能选好函数减少冲突 + 好策略处理冲突。散列表：按散列函数与冲突处理方式建立的表，装填因子：

$\alpha = \frac{表中记录数\ n}{散列表长度\ m}$

散列表的 ASL 是 α 的函数，与表长本身无关（α 越小冲突越少、ASL 越小，但空间浪费越大）——选择题口径："ASL 与表中已有记录个数和散列函数有关（通过 α），与记录的具体取值无关"。

#常用散列函数

#冲突处理一：开放定址法

地址序列 $H_i = (H(key) + d_i) \bmod m$，$d_i$ 为增量序列，探测"下一个空位"：

删除必须"打标记"：开放定址法下物理删除元素会截断后续同义词的探测路径（后来者探测到空位误判"不存在"），只能做删除标记（懒惰删除）；副作用是标记多了使表看似变满。链地址法无此问题，可直接删除。

#冲突处理二：链地址法（拉链法）

同一地址的所有同义词链成单链表，表头指针数组大小 m。删除直接摘链；无堆积，ASL 更小；适合删除频繁、关键字数动态变化的场景。代价：指针空间。

#ASL 计算（手推大题核心口径）

成功 ASL：逐个关键字数"从初始地址探测到自身位置的比较次数"，求平均（等概率 $1/n$）。

失败 ASL：从散列函数每个可能初值（%$p$ 即 $p$ 个地址）出发，数探测到空位置为止的比较次数（含与空位置"比较"的那次——王道口径：数到空格即停，空格本身算一次比较；但也有教材不计，以题目示例口径为准），对 $p$（或 m，视题目函数）取平均。线性探测法下失败链常很长（要滑过所有连续占用格）。

完整例题（模拟题）：关键字 {14, 36, 42, 37, 15, 40}，$H(key) = key \bmod 11$，线性探测法，表长 11：

$ASL_{成功} = \dfrac{1+2+1+2+3+1}{6} = \dfrac{10}{6}$。

失败：从地址 0..10 出发滑到空位（含空位计 1 次）逐格点数：

合计 27 次，$ASL_{失败} = \dfrac{27}{11}$。

（复核地址 9：探测序列 9（占，42）→ 10（空），共 2 次。同一道题若改用链地址法：成功 = 各链上位置深度平均；失败 = 各桶链长平均——链地址法失败比较次数不含空格，口径与开放定址不同，注意区分。）

#例题

例 1（模拟题）：长度为 11 的有序表折半查找，等概率下成功查找的最大比较次数与失败的最小比较次数分别是（ ）

A. 4、3 B. 4、4 C. 3、3 D. 3、4

解答：选 A。判定树高 $h = \lceil \log_2(11+1) \rceil = 4$，成功最大比较 4 次（最底层元素）；失败结点挂满后最深失败比较 = 双亲层 = 4、最浅 = 3（失败结点的双亲在第 3 层）。错因提醒：失败比较次数数的是双亲所在层，不是失败结点自己所在层（那样会多 1）。

例 2（模拟题）：依次把关键字 {50, 30, 70, 20, 40, 35} 插入初始为空的 AVL 树，画出最终形态并指出调整类型。

解答：插到 35 时 50 失衡（BF = +2），插入点位于 50 左孩子的右子树 → LR 型两步旋转（对 30 左旋、再对 50 右旋），最终树为 40(30(20,35), 50(-,70))。详见上节分步表。错因提醒：最小不平衡子树的判定要自插入点向上找第一个失衡祖先，不要直接拿根说事；本例中 30、40 的 BF 都合法，失衡者是 50。

例 3（模拟题）：5 阶 B 树中，非根的终端结点关键字个数最少与最多分别是多少？某终端结点已含 {8, 20, 32, 45}，再插入 51 会发生什么？

解答：最少 $\lceil 5/2 \rceil - 1 = 2$，最多 $5 - 1 = 4$。插入 51 后达 5 个关键字溢出，第 $\lceil 5/2 \rceil = 3$ 个关键字 32 上移到双亲，原结点分裂为 {8, 20} 与 {45, 51}（若双亲因此溢出则连锁分裂）。错因提醒：上移的是第 $\lceil m/2 \rceil$ 个，别数成中间偏左/偏右的其它位置。

#常见坑

1. 折半查找必须"有序 + 顺序存储"，链表不能折半；折半判定树不是满二叉树但可套完全二叉树高度公式；失败结点 n + 1 个、失败比较次数 = 双亲所在层。
2. 分块查找 ASL 是两段之和；索引折半时失败也要按折半口径算，别把 $\sqrt n + 1$ 当万能公式（那是"块间块内均顺序 + $s=\sqrt n$ 最优分块"的专属结论）。
3. BST 删除双子结点时，替换者是左子树最大（中序前驱）或右子树最小（中序后继），别拿"直接前驱/后继遍历序的邻居"混淆；同一组关键字不同插入序 → 不同 BST、相同中序序。
4. AVL：①失衡判定对象是最小不平衡子树的根；②插入至多一次旋转、删除可能连锁多次；③ LR/RL 双旋后孙结点当根（可用"中者提根"速检）。
5. 红黑树：①"叶结点全黑"的叶指外部 NULL 结点；②红结点孩子必黑 ⇔ 无相邻红结点，但黑结点孩子可黑；③插入新结点是红色；④问"最长路径与最短路径关系"答"不超过 2 倍"，绝对化的"恰好 2 倍"是错项。
6. B 树：根结点不受 $\lceil m/2 \rceil - 1$ 下界约束（根至少 1 个关键字 2 棵子树）；B 树所有叶同层；B 树 n 棵子树 n−1 个关键字、B+ 树 n 棵子树 n 个关键字——两处最易互串。
7. B+ 树任何查找必到叶结点；非叶关键字 = 相应子树最大关键字（王道口径）并在叶中重复。
8. 散列：①开放定址法删除只能打标记；②失败 ASL 的分母是 p（或 m）、不是 n，且数到空位是否计一次比较以题目口径为准；③链地址法失败比较不含空格；④平方探测表长取 4j + 3 型素数保证全覆盖；⑤ ASL 是 α 的函数、与表长无关。

#自测

1. 长度为 100 的有序表折半查找，判定树高度多少？失败结点多少个？失败时最多比较几次？
2. 某分块查找表共 1024 个元素、等分 32 块，块间用折半查找、块内顺序查找，写出 ASL（用对数式表达即可）。
3. 高度为 5 的 AVL 树最少多少个结点？30 个结点的 AVL 树最大高度是多少？
4. 5 阶 B 树（根为终端结点的退化情形除外）中，第 2 层某结点的关键字数范围是多少？整树高度（含失败层）为 3 时全树最多多少个关键字？
5. 关键字序列 {1, 2, 3, 4, 5} 依次插入空 BST 与空 AVL，最终两树的高度分别是多少？

答案与简析

1. $h = \lceil \log_2 101 \rceil = 7$；失败结点 101 个；失败最多比较 7 次（失败结点双亲在第 7 层）。
2. 每块 $s = 1024/32 = 32$，$ASL = \lceil \log_2(32+1) \rceil + \dfrac{s+1}{2} = \lceil \log_2 33 \rceil + \dfrac{33}{2} = 6 + 16.5 = 22.5$。
3. $N_5 = 12$（递推 1, 2, 4, 7, 12）；$N_6 = 20 \le 30 < N_7 = 33$，故最大高度 6。
4. 第 2 层结点（根的孩子）：关键字数 $[\lceil 5/2 \rceil - 1, 4] = [2, 4]$。高度 3 = 两层分支结点 + 失败层：根最多 4 个关键字 5 棵子树，5 个孩子各最多 4 个 → 最多 $4 + 5 \times 4 = 24$ 个。
5. BST：{1,2,3,4,5} 递增插入成右单链，高 5；AVL 插入 3 后 1 失衡（RR 型左旋）得 2(1,3)，插入 4 得 2(1,3(-,4))，插入 5 后 3 失衡 RR 左旋得 2(1,4(3,5))，高度 3。

下一步：完成手推型练习——AVL 四种旋转各推一遍、B 树分裂/合并各推一遍、散列两种冲突处理各算一次成功与失败 ASL，然后进入03-查找与排序-章节测的第 1-12 题限时训练。错题记入测验/00-错题本。