第7章 查找
第7章 查找¶
⚠️ 本章是考研命题的重点。 折半查找要掌握过程、判定树构造、ASL 分析；二叉排序树、平衡二叉树、红黑树要掌握概念、性质和操作。⚠️ B 树和 B+ 树是本章难点 —— B 树要求掌握插入、删除、查找的操作过程，B+ 树仅要求了解基本概念和性质。散列要掌握构造、冲突处理、成功/失败 ASL、性能分析。
b_276_5【知识树】第7章骨架¶
- 基本概念：静态/动态查找表、关键字、ASL
- 线性表查找
- 顺序查找（一般表 / 有序表 + 哨兵）
- 折半查找 + 判定树
- 分块查找（索引顺序查找）
- 树形查找
- 二叉排序树 BST：查找、插入、删除、性能
- 平衡二叉树 AVL：LL/RR/LR/RL 四种旋转
- 红黑树：五条性质、插入调整
- B 树与 B+ 树
- 散列表：散列函数、冲突处理、ASL 与装填因子
b_276_0；PDF 第 276 页 · b_276_27.1 查找的基本概念¶
什么叫查找成功和查找失败？¶
查找是在数据集合中寻找满足某种条件的数据元素的过程。 - 查找成功：集合中找到了满足条件的数据元素 - 查找失败：集合中不存在满足条件的数据元素
⚠️ “失败”不是算法异常，而是查找的一种正常结果；计算 ASL 时，成功查找和失败查找通常要分别统计。
b_276_7；PDF 第 276 页 · b_276_8静态查找表和动态查找表怎么分？¶
- 静态查找表：仅涉及查找，无须动态修改 → 顺序查找、折半查找
- 动态查找表：需要支持插入或删除 → 二叉排序树查找
- ⚠️ 散列查找既可用于静态表，也可用于动态表（取决于实现）
关键字 = 唯一标识元素的数据项的值，⚠️ 基于关键字的查找应返回唯一结果。
b_277_10ASL 的定义式？¶
- Pᵢ：查找第 i 个元素的概率，⚠️ 等概率时 Pᵢ = 1/n
- Cᵢ：找到第 i 个元素所需的关键字比较次数
⚠️ ASL 是衡量查找算法效率的核心指标。
b_277_3；PDF 第 277 页 · b_277_137.2 顺序查找和折半查找¶
哨兵是干什么的？¶
int Search_Seq(SSTable ST, ElemType key) {
ST.elem[0] = key; // 哨兵
for (int i = ST.TableLen; ST.elem[i] != key; --i); // 从后往前找
return i; // 成功返回下标，失败返回 0
}
⚠️ 引入哨兵是为了避免在循环中反复判断数组下标是否越界 —— 查找失败时循环必然在 i = 0 处终止（因为 ST.elem[0] == key），返回 0 表示失败。
💡 效果：省去边界判断，提高效率。
b_277_1；PDF 第 277 页 · b_277_6一般线性表顺序查找的 ASL？¶
定位第 i 个元素需比较 Cᵢ = n − i + 1 次（从表尾向前找）。 - ⚠️ 等概率下 ASL_成功 = (n+1)/2 - ⚠️ ASL_不成功 = n + 1
优化思路：⚠️ 若能预知各记录的查找概率，应按概率由大到小重排，使高频元素靠近查找起点。
优缺点：缺点是 n 较大时 ASL 大、效率低；⚠️ 优点是对存储结构无要求（顺序、链式都行），且不要求有序。⚠️ 链表只能采用顺序查找。
b_278_12有序表的顺序查找为什么失败时更快？ ★1考¶
⚠️ 有序时，一旦发现当前元素关键字大于 key 就可以立即判定失败，无须比到表的另一端。
判定树：圆形结点是表中实际存在的元素；⚠️ 矩形结点是失败结点，n 个元素对应 n + 1 个失败结点。 ⚠️ 到达某失败结点的比较次数 = 其父结点所在的层数。
教材例：n = 6 时 ASL_失败 = 6/2 + 6/7 = 3.86，⚠️ 比一般顺序查找的 n+1 = 7 好一些。
⚠️ 两点区别于折半查找：思想上有本质区别；⚠️ 有序表的顺序查找可用链式存储，折半查找只能顺序存储。
★ 考过 2013
b_278_8折半查找的代码和取整约定？ ★1考¶
int Binary_Search(SSTable L, ElemType key) {
int low = 0, high = L.TableLen - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (L.elem[mid] == key) return mid;
else if (L.elem[mid] > key) high = mid - 1; // 前半部分
else low = mid + 1; // 后半部分
}
return -1;
}
⚠️ 取中间结点时向下取整或向上取整都可以，但每次查找必须采用相同的取整方式。
★ 考过 2016
b_279_3折半查找判定树的三条性质？ ★2考¶
- ⚠️ 查找成功的查找长度 = 从根到目的结点路径上的结点数
- ⚠️ 查找失败的查找长度 = 从根到对应失败结点的父结点路径上的结点数
- 任一结点的值大于其左子树所有结点、小于其右子树所有结点
- ⚠️ n 个元素对应 n 个圆形非叶结点和 n + 1 个方形叶结点
- ⚠️ 判定树是一棵平衡二叉树
★ 考过 2015、2017
b_280_1折半查找的 ASL 和树高？ ★2考¶
- ⚠️ 树高 h = ⌈log₂(n+1)⌉，比较次数最多不超过判定树的高度
- ⚠️ 时间复杂度 O(log₂n)
教材算例（11 个元素）： - ASL_成功 = (1×1 + 2×2 + 3×4 + 4×4)/11 = 3 - ASL_失败 = (3×4 + 4×8)/12 = 11/3
★ 考过 2010、2023
b_280_5折半查找的两个适用条件？ ★1考¶
- ⚠️ 只适用于顺序存储结构，不适用于链式存储 —— 因为需要随机访问任意位置的元素才能快速定位中间元素
- ⚠️ 要求表中元素按关键字有序排列
★ 考过 2024
b_280_10分块查找的组织方式和两个步骤？ ★1考¶
基本思想：把查找表划分为若干子块 —— ⚠️ 块内元素可以无序，但块间必须有序（任意前一块的最大关键字小于后一块中的所有关键字）；建立索引表，每个元素含对应块的最大关键字和该块的起始地址，索引表按最大关键字有序。
两步： - ① 在索引表中确定待查记录所在的块（可顺序查找或折半查找） - ② 在目标块内进行顺序查找
★ 考过 2025
b_280_15分块查找的 ASL 和最优块长？¶
（长度 n 均分为 b 块、每块 s 个记录，索引表和块内都用顺序查找）
⚠️ 当 s = √n 时 ASL 取最小值 √n + 1。
💡 评价：索引表占额外空间、索引查找有开销，但块内查找范围受限，总体效率仍显著优于普通顺序查找。
b_281_47.3 树形查找¶
二叉排序树的定义和中序性质？ ★4考¶
BST 或者是空树，或者满足： - 左子树非空 → 左子树所有结点的关键字均小于根 - 右子树非空 → 右子树所有结点的关键字均大于根 - 左右子树也分别是 BST
⚠️ 核心推论：对 BST 中序遍历可得到一个递增的有序关键字序列。
查找过程：与根比较 → 小于则进左子树，大于则进右子树 → 直到找到或树空。 ⚠️ 递归实现简单，但栈空间开销较大、执行效率较低，所以常用循环实现。
构造 BST 的目的：⚠️ 并非直接输出有序序列，而是利用有序结构支持高效的动态查找、插入和删除。
💡 判断整棵树是否为 BST 的两种稳妥方法：
- 中序 + pre：中序遍历时要求当前关键字严格大于前一个（本书关键字互异约定）
- 递归上下界：根必须落在 (lower, upper)；进左子树把上界改为根值，进右子树把下界改为根值
⚠️ 校订/边界：只检查“左孩子 < 父 < 右孩子”不是充分条件。反例：根 10，左孩子 5，5 的右孩子 12；每条父子边都“看似正确”，但 12 落在 10 的左子树，整树不是 BST。若题目允许重复关键字，还要按题设改成非降并核对重复值放置规则。
★ 考过 2013、2015、2018、2024
b_291_15；PDF 第 291 页 · b_291_17BST 插入的新结点一定在哪？ ★1考¶
⚠️ BST 是动态构建的：查找失败时才执行插入。 - 原树为空 → 新结点作根 - 否则从根比较，小于进左、大于进右 - ⚠️ 新插入的结点一定是叶结点，且恰好是查找失败时所访问的最后一个结点的左孩子或右孩子 - ⚠️ 树中已存在相同关键字则插入失败（返回 0）
构造 BST：从空树开始依次插入，重复关键字被忽略。 教材例：{45, 24, 53, 45, 12, 24} → 第二个 45 和 24 被忽略。
★ 考过 2020
b_292_3BST 删除的三种情况？ ★1考¶
⚠️ 不能把以该结点为根的子树都删掉，必须摘下该结点并重新连接断裂的链，同时保持 BST 性质。 - ① z 是叶结点 → 直接删除 - ② z 只有一棵非空子树 → ⚠️ 把它唯一的子树上移，替代 z 的位置 - ③ z 有左右两棵子树 → ⚠️ 用 z 的直接后继或直接前驱（中序的下一个/上一个）替代 z，再删除那个后继（前驱） - ⚠️ 因为直接后继（前驱）至多只有一棵子树，这样就转化为情形 ① 或 ②
💡 思考题（教材原题）：删除某结点再重新插入，所得 BST 未必与原树相同。
★ 考过 2013
b_293_4BST 的查找效率取决于什么？¶
⚠️ 主要取决于树的高度。 - 左右子树高度差不超过 1（平衡）→ ASL = O(log₂n) - ⚠️ 最坏情况：输入序列有序 → 退化为单支树，高度 n，ASL = (n+1)/2
教材算例（10 个结点）： - 平衡形态 ASL_a = (1 + 2×2 + 3×4 + 4×3)/10 = 2.9 - 单支树 ASL_b = (1+2+…+10)/10 = 5.5
b_294_4；PDF 第 294 页 · b_294_5BST 和折半查找该怎么选？¶
- ⚠️ 二分查找的判定树唯一；相同关键字集合可能生成不同的 BST（形态取决于插入顺序）
- 平均时间性能二者相近
- ⚠️ 维护有序性：BST 插入删除只需修改指针，O(log₂n)；二分查找的对象是有序顺序表，插入删除要移动大量元素，O(n)
💡 结论：静态查找表 → 顺序表 + 二分查找；动态查找表（频繁增删）→ 二叉排序树。
b_294_57.3.2 平衡二叉树¶
平衡因子的取值范围？ ★1考¶
平衡因子 = 结点左子树高度 − 右子树高度。 ⚠️ 平衡二叉树（AVL 树）中所有结点的平衡因子只能取 −1、0 或 1。
形式化定义：空树，或左右子树均为平衡二叉树且左右子树高度差的绝对值不超过 1。
★ 考过 2009
b_294_7；PDF 第 294 页 · b_294_9什么是最小不平衡子树？ ★1考¶
插入后沿查找路径向上检查各祖先结点是否失衡；⚠️ 找到插入路径上离新结点最近、且平衡因子绝对值大于 1 的结点 A —— 以 A 为根的子树即为最小不平衡子树。
⚠️ 每次调整的对象都是最小不平衡子树，且必须在保持 BST 特性的前提下旋转。
★ 考过 2015
b_294_15四种旋转分别怎么做？ ★3考¶
| 类型 | 触发条件 | 平衡因子变化 | 操作 |
|---|---|---|---|
| LL（右单旋转） | 在 A 的左孩子的左子树上插入 | 1 → 2 | B 向右上旋代替 A，A 向右下成为 B 的右孩子，B 的原右子树成为 A 的左子树 |
| RR（左单旋转） | 在 A 的右孩子的右子树上插入 | −1 → −2 | B 向左上旋代替 A，A 向左下成为 B 的左孩子，B 的原左子树成为 A 的右子树 |
| LR（先左后右双旋转） | 在 A 的左孩子的右子树上插入 | 1 → 2 | 先把 B 的右子树根 C 向左上旋取代 B，再把 C 向右上旋取代 A |
| RL（先右后左双旋转） | 在 A 的右孩子的左子树上插入 | −1 → −2 | 先把 B 的左子树根 C 向右上旋取代 B，再把 C 向左上旋取代 A |
⚠️ LR 和 RL 旋转时，新结点插在 C 的左子树还是右子树不影响旋转过程。
💡 记忆法：看"失衡结点 → 孩子 → 孙子"的方向，同向单旋（反方向转一次），异向双旋（先把里面那个转出来）。
💡 3 + 4 重构：画树时统一 LL/RR/LR/RL - 沿失衡高链取 z（最小不平衡子树根）、y（z 的高孩子）、x（y 的高孩子） - 把三个关键字按 BST 顺序排成 a < b < c；把剩余四棵子树按中序顺序排成 T₁ < T₂ < T₃ < T₄ - 重挂为 b 作新根，a/c 作左右孩子；a 接 T₁/T₂，c 接 T₃/T₄ - 最后把 b 接回原 z 的父结点，并自下而上更新高度/平衡因子（若实现存 parent 指针也要同步）
⚠️ 边界：3 + 4 只是四种旋转的统一重挂法；x/y/z 必须来自失衡高链，四棵子树的中序次序不得改变。术语题仍要能识别 LL/RR/LR/RL。
★ 考过 2010、2019、2021
b_295_2构造 AVL 的教材例题（15,3,7,10,9,8）？ ★1考¶
- 插入 7 后失衡：最小不平衡子树根为 15，插入在其左孩子的右子树 → ⚠️ LR 旋转
- 插入 9 后失衡：根为 15，插入在其左孩子的左子树 → ⚠️ LL 旋转
- 插入 8 后失衡：根为 7，插入在其右孩子的左子树 → ⚠️ RL 旋转
💡 做题套路：先定位最小不平衡子树的根 A，再看新结点相对 A 走的是"左左/左右/右右/右左"。
★ 考过 2013
b_296_8AVL 删除和插入的调整有什么不同？¶
删除步骤： - ① 按 BST 方法删除结点 w - ② 从 w 向上回溯，找到第一个不平衡结点 z；设 y 是 z 的较高子树的根，x 是 y 的较高子树的根 - ③ 按 x、y、z 的相对位置分 LL / LR / RR / RL 四种情况调整（与插入相同）
⚠️ 删除的等高补丁：若 y 的两棵子树等高，x 不唯一，则优先选与 y 相对 z 同向的外侧孙子：z 左高就选 x=y.left，z 右高就选 x=y.right，优先归入 LL/RR 单旋。
⚠️ 边界：这条是删除后“y 的两孩子等高”时的确定规则；插入路径通常已唯一确定 x，不要反向套用。
⚠️ 关键区别：插入只需对以 z 为根的子树做一次平衡调整；删除可能需要多次调整 —— 若一次调整使子树高度减 1，则可能还要继续调整 z 的祖先，甚至一路回溯到根。
教材例：删除 32（叶结点）→ 回溯找到第一个不平衡结点 44(z)，y=78，x=50 → RL 情况 → 先右后左双旋。
b_297_2；PDF 第 297 页 · b_297_8高度为 h 的 AVL 树最少有多少结点？ ★1考¶
递推式：nₕ = nₕ₋₂ + nₕ₋₁ + 1，其中 n₀ = 0、n₁ = 1、n₂ = 2。 依次推出：n₃ = 4、n₄ = 7、n₅ = 12、n₆ = 20、n₇ = 33 …
⚠️ 用途：求给定结点数的 AVL 树查找时的最多比较次数（树的最大深度）。 例：含 12 个结点的 AVL 树，因为 n₅ = 12，所以最多比较 5 次。
⚠️ 含 n 个结点的 AVL 树最大深度为 O(log₂n)，平均查找时间复杂度 O(log₂n)。 💡 深度为 h 的 AVL 树最多结点数就是满二叉树的 2^h − 1。
★ 考过 2012
b_297_107.3.3 红黑树¶
红黑树的五条性质？¶
- ① 每个结点或红或黑
- ② ⚠️ 根结点是黑色的
- ③ ⚠️ 叶结点（虚构的外部 NULL 结点）都是黑色的
- ④ ⚠️ 不存在两个相邻的红结点（红结点的父和孩子均为黑）
- ⑤ ⚠️ 从任一结点到任意叶结点的简单路径上，所含黑结点的数量相同
黑高 bh = 从某结点出发（不含该结点）到叶结点路径上的黑结点总数；根的黑高称为红黑树的黑高。 ⚠️ 与折半查找树、B 树类似，引入 n + 1 个外部叶结点（视为黑色）以保证每个内部结点左右子树均非空。
💡 记忆法："红不连红，黑高相同，根叶皆黑"。
b_298_7红黑树的两个高度结论？¶
- 结论 1：⚠️ 从根到叶结点的最长路径不大于最短路径的 2 倍
- 💡 推理：最短路径必然全由黑结点构成（性质⑤）；最长路径必然由黑红交替构成（性质④），此时红结点数最多等于黑结点数
- 结论 2：⚠️ 有 n 个内部结点的红黑树高度 h ≤ 2log₂(n+1)
- 💡 推理：任意一条简单路径上至少一半是黑结点 → 根的黑高至少 h/2 → n ≥ 2^(h/2) − 1
⚠️ 推论：黑高为 h 的红黑树，内部结点数最少 2^h − 1，最多 2^(2h) − 1。
b_298_17；PDF 第 298 页 · b_298_22AVL 树和红黑树该怎么选？¶
- AVL 是"高度平衡"：左右子树高度差 ≤ 1，⚠️ 插入删除时要频繁调整全树拓扑，代价大
- 红黑树是"适度平衡"：⚠️ 允许左右子树高度相差最多 2 倍 → 显著降低调整频率
⚠️ 本书常用选型结论：查找远多于增删 → AVL 更优（查找更快）；增删频繁 → 红黑树更合适（调整开销小）。
💡 教材常举的工程例：红黑树调整频率较低、综合表现均衡；C++ map/set 与 Java TreeMap/TreeSet 的常见实现采用红黑树。具体标准库是否规定内部结构不属于统考作答点。
b_299_0新插入的结点为什么染红？¶
⚠️ 若染黑：该结点所在路径的黑结点数比其他路径多 1，几乎必然违反性质⑤，且调整代价高。 ⚠️ 若染红：所有路径的黑结点数保持不变，仅当出现父子均为红时才违反性质④，局部调整即可高效恢复。
插入调整的三步： - ① 按 BST 规则插入 z 并染红；⚠️ 若父结点为黑，红黑性质未破坏，插入结束 - ② ⚠️ 若 z 为根，则染黑（满足性质②），树的黑高加 1 - ③ 若 z 非根且父结点为红 → 违反性质④；⚠️ 此时爷结点必然存在且为黑，按叔结点 y 的颜色分三种情形处理
💡 情形 1（LR 型）：叔结点是黑色且 z 是父的右孩子 → 先对 z.p 左旋，使 z 上升取代原父位置，转化为情形 2；⚠️ 此操作不改变任何路径的黑结点数（z 与 z.p 均为红），性质⑤不受影响。
b_299_1；PDF 第 299 页 · b_299_2红黑树插入的三种情形怎么分？¶
⚠️ 按叔结点 y 的颜色分（以下设 z.p 是 z.p.p 的左孩子，右孩子情形对称）： - 情形 1（LR 型，先左旋再右旋）：叔结点 y 是黑色，且 z 是父的右孩子 - 先对 z.p 执行左旋，使 z 上升取代原父位置 → 转化为情形 2 - ⚠️ 此操作不改变任何路径的黑结点数（z 与 z.p 均为红），性质⑤不受影响 - 情形 2（LL 型，右单旋）：叔结点 y 是黑色，且 z 是父的左孩子 - 对 z.p.p 执行右旋，⚠️ 并将原父结点染黑、原爷结点染红 → 插入结束 - 情形 3：⚠️ 叔结点 y 是红色（z 是左是右都不影响） - 把 z.p 和 y 染黑，把 z.p.p 染红 - ⚠️ z.p.p 变红后可能与其父再次红红冲突 → 把 z.p.p 视为新的 z 继续向上回溯，每次 z 上移两层 - 终止条件：z 成为根（染黑结束） 或 进入情形 1、2（旋转后结束）
💡 3 + 4 视角只用来画“黑叔 + 红红冲突”的旋转部分：把爷、父、z 按 BST 次序排成 a<b<c，四棵子树保持中序顺序重挂，再按王道规则着色，即可统一理解 LL/RR/LR/RL。
⚠️ 边界：它不是红黑树完整修复算法。红叔必须换色并可能向上溢出，不能硬做 3 + 4；着色条件仍是考试作答主线。
⚠️ 补充陷阱：情形 3 回溯时 z 可能已上移到内部结点，从而拥有子树 —— 所有调整都必须考虑子树的存在。
b_299_7红黑树插入的教材算例（插 5、4、12）？¶
- 插入 5：⚠️ 情形 3 —— 把父结点 3 与叔结点 10 染黑、爷结点 7 染红；7 是根 → 重新染黑，树的黑高加 1
- 插入 4：⚠️ 情形 1 的对称情形（RL 型） —— 先对以 5 为根的子树右旋，转为情形 2 的对称（RR 型），交换 3 和 4 的颜色，再对以 4 为根的子树左旋
- 插入 12：⚠️ 父结点为黑，无须调整，直接结束
💡 做题顺序：先看父是不是黑（是就结束）→ 再看叔的颜色（红走情形 3，黑走旋转）。
b_300_6红黑树删除为什么会出现"双黑结点"？¶
⚠️ 插入易破坏性质④（无连续红结点）；删除更易破坏性质⑤ —— 被删结点为黑时，经过它的所有路径黑高减 1。
归约：有两个非空子树的结点不能直接删，用中序后继（右子树最小结点）替代 —— ⚠️ 该后继至多只有一个右孩子 → 最终只剩两种情形：有一个孩子、无孩子。 - 有一个孩子 → ⚠️ 该子树只有一个结点且必然是红色（否则破坏性质⑤） - 无孩子且是红色 → 直接删，无须调整 - 无孩子且是黑色 → ⚠️ 把替换它的结点 x 视为带"额外一重黑色"的双黑结点，任务转化为把双黑结点恢复为普通结点
b_301_10；PDF 第 301 页 · b_301_14红黑树删除的四种情形？（了解即可）¶
⚠️ 教材原话：本节难度较大、考查概率较低，可按自身情况决定是否学习。
按 x 的兄弟 w 及 w 的孩子颜色分（设 x 是左孩子，右孩子对称）： - 情形 1：w 是红色 → 交换 w 与父结点颜色，对 x.p 左旋 → ⚠️ 转为情形 2、3 或 4 - 情形 2（RR 型，左单旋）：w 黑，w 的右孩子红 → 交换 w 与 x.p 颜色，把 w 的右孩子染黑，对 x.p 左旋 → x 变单重黑，结束 - 情形 3（RL 型，先右旋再左旋）：w 黑，w 的左孩子红、右孩子黑 → 交换 w 与其左孩子颜色，对 w 右旋 → 转为情形 2 - 情形 4：w 黑，w 的两个孩子都黑 → ⚠️ 从 x 和 w 各去掉一重黑色（x 变普通黑、w 变红），把 x.p 额外着一层黑 → x 上升一层继续循环
💡 红侄删除的 3 + 4 视角：兄弟 w 为黑且至少有一个红侄子时，可把“父、兄弟、选定的红侄”作为三结点重挂；若内外侄都红，优先取外侧侄子，可直接归入单旋情形。 ⚠️ 边界：若兄弟及两侄均黑，必须执行情形 4 的双黑上传，3 + 4 无法替代；所有旋转后仍必须按原情形完成着色。
⚠️ 只有情形 4 可能重复执行，每次 x 上升一层，至多 O(log₂n) 次；情形 1、2、3 各执行常数次着色和至多 3 次旋转后即终止。 ⚠️ 若由情形 1 进入情形 4，因原 x.p 是红色，把新 x 变黑即终止。
b_302_4；PDF 第 302 页 · b_302_57.4 B 树和 B+ 树¶
m 阶 B 树的五条定义？ ★2考¶
- ⚠️ 每个结点至多 m 棵子树，即至多 m − 1 个关键字
- ⚠️ 根结点若不是叶结点，则至少 2 棵子树，即至少 1 个关键字
- ⚠️ 除根外，所有非叶结点至少 ⌈m/2⌉ 棵子树，即至少 ⌈m/2⌉ − 1 个关键字
- 结点结构：n | P₀ | K₁ | P₁ | K₂ | … | Kₙ | Pₙ —— K₁ < K₂ < … < Kₙ，Pᵢ₋₁ 所指子树全小于 Kᵢ，Pᵢ 所指子树全大于 Kᵢ
- ⚠️ 所有叶结点都在同一层，且不实际存储数据（可视为查找失败的外部结点，作用类似折半查找判定树中的失败结点）
⚠️ 术语分歧（务必注意）：多数教材把 B 树的叶结点定义为失败结点，本书采用此定义；但统考真题把 B 树的叶结点定义为最底层终端结点。
★ 考过 2009、2025
b_317_3B 树关键字数与子树数的关系？（5 阶实例） ★4考¶
- ⚠️ 任意结点的子树个数 = 其关键字个数 + 1
- 根至少 1 个关键字 → 至少 2 棵子树
- 5 阶时：除根外非叶结点至少 ⌈5/2⌉ = 3 棵子树（至少 2 个关键字），至多 5 棵子树（至多 4 个关键字）
- 结点内关键字从左到右严格递增；⚠️ 下层子树的关键字落在上层关键字划分出的区间内（如关键字 5、11 划出 (−∞,5)、(5,11)、(11,+∞)）
★ 考过 2013、2014、2018、2021
b_317_9B 树查找为什么要分两步？¶
- ① 在 B 树中定位目标结点 —— ⚠️ 这一步在磁盘上进行
- ② 在结点内查找关键字 —— ⚠️ 这一步在内存中进行（结点读入内存后用顺序或折半查找）
⚠️ 所以磁盘上的查找次数（结点所在层次数）才是决定查找效率的关键因素。
查找失败的标志：⚠️ 查找到叶结点（外部结点）说明树中不存在该关键字。
b_318_1B 树高度的上下界怎么推？¶
（⚠️ 本书的高度不包括最底层外部叶结点那一层） - 最小高度（每结点关键字数最大）： n ≤ (m−1)(1 + m + m² + … + m^(h−1)) = m^h − 1 → ⚠️ h ≥ log_m(n+1) - 最大高度（每结点关键字数最小）： 第 1 层 ≥1 个结点，第 2 层 ≥2，第 3 层 ≥2⌈m/2⌉ …，第 h+1 层 ≥2(⌈m/2⌉)^(h−1) ⚠️ 外部叶结点数恒为 n + 1 → n + 1 ≥ 2(⌈m/2⌉)^(h−1) → ⚠️ h ≤ log_⌈m/2⌉((n+1)/2) + 1
教材算例：3 阶 B 树含 8 个关键字 → 2 ≤ h ≤ 3.17 → 实际 2 ≤ h ≤ 3。
b_318_3；PDF 第 318 页 · b_318_5B 树插入的定位与分裂规则？ ★1考¶
- ① 定位：⚠️ 查找必然落到外部叶结点（查找失败），但实际插入位置是它的父结点，即最底层终端结点
- ② 插入与分裂：⚠️ 每个非根结点的关键字数必须在 [⌈m/2⌉−1, m−1] 内
- 插入后 ≤ m−1 → 直接插入
- 插入后 = m → 必须分裂
分裂方法：⚠️ 从第 ⌈m/2⌉ 个关键字处分成左右两部分 —— 左半留原结点，右半移入新结点，⚠️ 中间那个关键字（是关键字不是结点）被提升插入父结点；父结点若也超限则递归分裂，⚠️ 一直传到根被分裂时 B 树高度加 1。
教材例（m=3）：结点已有 2 个关键字，插入 60 后有 3 个 → 分裂，中间关键字 52 上提，原结点与新结点各留 1 个。
★ 考过 2020
b_318_11B 树删除的三种情况？ ★2考¶
⚠️ 被删关键字不在终端结点时：用其前驱（左子树最右下）或后继（右子树最左下）k′ 替代，再去删 k′ —— k′ 必在终端结点，转化为下面三种情况。 教材例：4 阶 B 树删 80，用前驱 78 替代，再在终端结点删 78。
- ① 直接删除：删除前该结点关键字数 ≥ ⌈m/2⌉ → 直接删
- ② 兄弟够借：该结点关键字数 = ⌈m/2⌉−1，且相邻兄弟 ≥ ⌈m/2⌉ → ⚠️ 父子换位法
- 教材例：删 65 → 把父结点的 71 下移替代 65，再把右兄弟的最小关键字 74 上移到父结点原 71 的位置
- ③ 兄弟不够借：该结点和左右兄弟都是 ⌈m/2⌉−1 → ⚠️ 把该结点、一个兄弟、父结点中分隔它们的关键字合并为一个新结点
★ 考过 2012、2022
b_319_5合并后父结点关键字减少会怎样？ ★1考¶
⚠️ 合并过程中父结点的关键字个数会减 1： - 若父是根且关键字数减到 0 → ⚠️ 直接删除根结点，合并后的新结点成为根（树高减 1） - 若父不是根且关键字数减到 ⌈m/2⌉−2 → ⚠️ 对父结点执行借位或合并，并可能向上递归，直到整棵树重新满足 B 树性质
★ 考过 2023
b_320_1B+ 树的五条定义？ ★1考¶
- 每个分支结点最多 m 棵子树
- 非叶根结点至少 2 棵子树；其余分支结点至少 ⌈m/2⌉ 棵子树
- ⚠️ 每个分支结点的关键字个数 = 其子树个数（B 树是子树数 = 关键字数 + 1）
- ⚠️ 所有关键字及其记录指针都存储在叶结点中；叶结点内关键字升序排列，⚠️ 相邻叶结点用指针按关键字顺序链接，支持高效顺序查找
- ⚠️ 分支结点（索引的索引）只含引导查找的关键字（通常是子结点关键字的最大值）和指针
★ 考过 2017
b_320_5B 树和 B+ 树的四点差异？ ★1考¶
| B 树 | B+ 树 | |
|---|---|---|
| 子树数 | n 个关键字 → n+1 棵子树 | ⚠️ n 个关键字 → n 棵子树 |
| 关键字数范围 | ⌈m/2⌉−1 ≤ n ≤ m−1（根 1 ≤ n ≤ m−1） | ⚠️ ⌈m/2⌉ ≤ n ≤ m（非叶根 2 ≤ n ≤ m） |
| 关键字存储 | ⚠️ 只出现一次，各结点关键字互不重复 | ⚠️ 全部存在叶结点，非叶结点中的是副本（最大值），会重复出现 |
| 结点功能 | 各结点都存数据 | ⚠️ 叶结点存完整数据，非叶结点仅起索引作用 |
💡 B+ 树为什么适合数据库：非叶结点结构更紧凑 → 一个磁盘块能容纳更多关键字 → 减少磁盘 I/O 次数；⚠️ 叶结点链表还支持范围查询。
★ 考过 2016
b_320_13B+ 树的两个头指针和两种查找方式？¶
⚠️ B+ 树通常有两个头指针：一个指向根结点，另一个指向关键字最小的叶结点。 → 支持两种查找：从最小关键字开始的顺序查找、从根结点开始的多路查找。
⚠️ 查找过程的关键差异：即使在非叶结点遇到与给定关键字相等的值也不终止，必须继续向下走到叶结点 → 无论成功与否，每次查找都对应一条从根到某叶结点的完整路径。
💡 这也是 B+ 树查找长度稳定的原因（B 树可能在中途命中提前结束）。
b_320_197.5 散列表¶
冲突和同义词是什么？¶
散列函数：H(key) = Addr，把关键字映射到存储地址（数组下标、索引或内存地址）。 - ⚠️ 冲突：两个或以上不同关键字映射到同一地址 - ⚠️ 同义词：这些发生冲突的不同关键字
⚠️ 冲突总是不可避免的 → 一方面设计好的散列函数减少冲突，另一方面必须设计有效的冲突处理方法。 💡 理想情况下散列表查找的时间复杂度为 O(1)，与表中元素个数无关。
b_329_12构造散列函数的三点要求？¶
- ⚠️ 定义域必须包含全部关键字，值域范围取决于散列表大小
- 计算出的地址应尽可能均匀分布在整个地址空间
- 函数应尽量简单，能在较短时间内算出
b_330_3；PDF 第 330 页 · b_330_18四种散列函数的适用场景？¶
- 直接定址法：H(key) = key 或 a·key + b —— ⚠️ 计算最简单且不会产生冲突；适用于关键字分布基本连续，⚠️ 分布稀疏时浪费空间
- 除留余数法（⚠️ 最简单最常用）：H(key) = key % p，⚠️ p 取不超过 m 且尽可能接近 m 的质数
- 数字分析法：⚠️ 选取数码分布较均匀的数位组合成地址；适用于关键字集合已知且固定，⚠️ 集合变化就要重构函数
- 平方取中法：取关键字平方值的中间几位；⚠️ 平方运算与关键字每一位都有关，地址分布较均匀；适用于各位取值分布不均或位数较少的情形
⚠️ 不能笼统地说某种方法最优，要根据关键字集合的特性选择。
b_330_6开放定址法的通式和四种增量？ ★1考¶
⚠️ 开放定址法 = 散列表中所有空闲地址都可用于存放任意关键字（无论是否同义）。
- 线性探测法：dᵢ = 1, 2, …, m−1 —— 探测到表尾就回绕到表首；⚠️ 只要表未满必能找到空位
- 平方探测法（二次探测法）：dᵢ = 1², −1², 2², −2², …, k², −k²（k ≤ m/2）；⚠️ 散列表长度 m 必须是形如 4k+3 的素数
- 双散列法：dᵢ = i·H₂(key) → Hᵢ = (H(key) + i·H₂(key)) % m，⚠️ 需要两个散列函数
- 伪随机序列法：dᵢ 由伪随机数生成器产生
★ 考过 2025
b_331_5；PDF 第 331 页 · b_331_9什么是堆积（聚集）现象？ ★1考¶
⚠️ 线性探测法的固有缺陷：原本映射到地址 i 的同义词被存入 i+1，本应存入 i+1 的元素被迫占用 i+2，以此类推 → 大量元素在相邻地址上堆积，显著降低查找效率。
⚠️ 平方探测法能有效避免堆积，是一种较好的冲突处理方法；⚠️ 缺点是无法探测散列表中的所有位置，但至少能覆盖一半的地址空间。
★ 考过 2014
b_331_6开放定址法为什么不能直接删除元素？ ★1考¶
⚠️ 直接物理删除可能截断其他同义词的查找路径，导致查找失败。
正确做法：对被删元素所在位置设置一个删除标记，实现逻辑删除。 ⚠️ 副作用：经过多次删除后，散列表看似已满，但实际上有许多位置未被利用。
★ 考过 2023
b_331_15拉链法的组织方式和适用场景？¶
⚠️ 把散列到同一地址的所有同义词组织成一个链表 —— 散列地址为 i 的同义词链表，其头指针存放在散列表的第 i 个单元中。
⚠️ 拉链法特别适用于需要频繁执行插入和删除操作的场景（不存在开放定址法的删除难题）。
教材例：{19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79}，H(key) = key % 13。
b_331_18；PDF 第 331 页 · b_331_19散列查找的两个步骤？ ★4考¶
初始化 Addr = H(key)： - ① 检查 Addr 处是否有记录：无记录 → 查找失败；有记录则比较，相等 → 成功，否则转 ② - ② 按冲突处理方法计算下一个探测地址，更新 Addr，返回 ①
教材算例（线性探测，表长 16，H(key) = key % 13）： - 查 84：H(84)=6，L[6]≠84 → H₁=(6+1)%16=7，L[7]≠84 → H₂=8，L[8]=84 成功 - 查 38：H(38)=12，L[12]≠38 → H₁=13，L[13] 为空 → 查找失败
⚠️ 注意查找失败的判据是"探测到空单元"，不是"探测完整张表"。
★ 考过 2010、2018、2019、2024
b_332_0散列表 ASL 怎么算？（教材算例）¶
教材例各关键字的比较次数：14→1, 01→2, 68→1, 27→4, 55→3, 19→1, 20→1, 84→3, 79→9, 23→1, 11→1, 10→3
⚠️ 重要结论：对同一关键字集合和相同散列函数，不同的冲突处理方法会生成不同的散列表，从而 ASL 不同（本例线性探测的结果就与拉链法不同）。 ⚠️ 尽管散列表建立了直接映射，但由于冲突的存在，查找仍需比较 → ASL 仍是衡量效率的核心指标。
b_332_14；PDF 第 332 页 · b_332_16影响散列表查找效率的三个因素？ ★2考¶
- 散列函数
- 冲突处理方法
- 装填因子 α
⚠️ ASL 主要依赖于装填因子 α，而不直接依赖于 n 或 m。 α 越大表越满、冲突可能性越高；α 越小冲突越少。
★ 考过 2011、2022
b_332_19【原书试题精选与答案方法】第7章¶
有序表和无序表做顺序查找时，三种情况下的 ASL 为什么不总相同？（7.2 综合应用题 01）¶
分“失败、唯一命中、多重命中”讨论：
- 查找失败：有序表遇到第一个大于目标值的元素即可停止；无序表必须扫到表尾，二者不同。
- 唯一命中：命中第 \(i\) 个位置都比较 \(i\) 次，等概率时二者相同。
- 找出全部相等元素：有序表的相同值连续，找到第一个后可连续收集；无序表仍须扫描全表，二者不同。
⚠️ “表有序”并不会自动降低成功查找的 ASL；只有它能提供提前失败或连续收集重复值时才体现优势。
b_288_4；PDF 第 288 页 · b_288_5；PDF 第 288 页 · b_288_6；PDF 第 288 页 · b_288_7折半查找判定树怎样同时解决查找路径、成功/失败 ASL 和最多比较次数？（7.2 综合应用题 02；2010、2023 统考真题）¶
先按题目固定的 mid 取整规则递归取中点，画出圆形成功结点；再在每个空子树位置补一个方形失败结点。
- Q02：查 275 依次比较 509、154、275；查 684 依次比较 509、677、897、765。
- 成功 ASL 按圆形结点层次加权：本题为 \(45/14\)。
- 失败 ASL 按失败区间等概率加权，但比较只算到方形结点的父结点：本题为 \(59/15\)。
- 最多比较次数等于判定树高度，长度 16 时为 5，长度 600 时为 10。
⚠️ 方形失败结点是虚构结点，本身不增加关键字比较次数。
b_287_3；PDF 第 287 页 · b_287_4；PDF 第 287 页 · b_287_5；PDF 第 287 页 · b_287_15；PDF 第 287 页 · b_287_16；PDF 第 288 页 · b_288_8；PDF 第 288 页 · b_288_11；PDF 第 288 页 · b_288_12；PDF 第 288 页 · b_288_14；PDF 第 288 页 · b_288_15“先每隔 8 个顺序定位，再在块内折半”怎样计算 ASL？（7.2 综合应用题 03）¶
这是一个固定块长为 8 的两级查找：先比较 \(A[7],A[15],\dots\) 确定块；若目标不等于已比较过的块尾元素，再在该块前面的 7 个元素中折半。
- 第 \(i\) 块要先做 \(i\) 次索引顺序比较。
- 每块 8 个目标位置中，块尾元素已在第一阶段命中，不再做块内比较；其余 7 个位置的折半比较次数总和为 \(1+2\times2+3\times4=17\)，所以平均附加量是 \(17/8\)。
- 等概率下教材化简为
💡 两级查找一律按“定位块的代价 + 块内查找的代价”计算，不能只算其中一级。
b_288_16；PDF 第 288 页 · b_288_17；PDF 第 288 页 · b_288_18；PDF 第 289 页 · b_289_0折半查找的递归写法怎样处理成功、失败和递归栈？（7.2 综合应用题 04）¶
递归区间为 [low,high]：
low>high：查找失败，按题目约定返回 0。key>elem[mid]：递归右半[mid+1,high]。key<elem[mid]：递归左半[low,mid-1]。- 相等：返回
mid。
每次规模减半，时间 \(O(\log n)\)；递归工作栈深度同为 \(O(\log n)\)。若改成循环写法，额外空间可降为 \(O(1)\)。
b_289_1；PDF 第 289 页 · b_289_2；PDF 第 289 页 · b_289_3；PDF 第 289 页 · b_289_4；PDF 第 289 页 · b_289_5为什么折半查找的 O(logn) 不代表每一次都比顺序查找比较少？（7.2 普通选择题 06）¶
复杂度描述的是规模增大后的总体增长趋势，不能替代某一次具体查找的比较次数。
- 例如在 1000 个元素的有序表中查第一个元素，顺序查找只比较 1 次，折半查找却要先从中部不断缩小区间，比较次数接近 \(\log_2 1000\)。
- 因此只能说折半查找在一般情况或大部分位置更快，不能说对每个目标都必然更快。
- 若各元素查找概率不等，还要按概率加权比较 ASL，不能只比较两种算法的渐近量级。
b_285_9；PDF 第 285 页 · b_285_10不等概率顺序查找怎样通过“与前驱交换”逐渐自组织？（7.2 综合应用题 05）¶
从表头顺序扫描；若找到目标且它不是首元，就与直接前驱交换，使高频结点逐步向表头移动。
- 顺序表：交换相邻两个记录并返回新下标。
- 链表：必须保存目标、前驱及前驱的前驱，改链前先保留旧链接。
- 单次查找最坏 \(O(n)\)，额外空间 \(O(1)\)。
⚠️ 这是“每命中一次只前移一位”，不是一次性按频度整体排序。
b_289_6；PDF 第 289 页 · b_289_7；PDF 第 289 页 · b_289_8；PDF 第 289 页 · b_289_9；PDF 第 290 页 · b_290_0行列都递增的矩阵怎样在 O(n) 时间内查找目标值？（7.2 综合应用题 06）¶
从右上角开始：当前值大于目标就左移一列；小于目标就下移一行；相等则成功。每一步都能排除一整行或一整列。
- 最多左移 \(n-1\) 次、下移 \(n-1\) 次，比较不超过 \(2n\) 次。
- 时间 \(O(n)\)，空间 \(O(1)\)。
💡 右上角同时具有“向左变小、向下变大”两种单调方向；左下角也可对称处理。
b_290_1；PDF 第 290 页 · b_290_2；PDF 第 290 页 · b_290_3；PDF 第 290 页 · b_290_4；PDF 第 290 页 · b_290_5；PDF 第 290 页 · b_290_6查找概率不等时，为什么顺序查找或 BST 可能优于折半查找？（2013 统考真题）¶
折半查找优化的是均匀概率下的树高，概率不等时应让高概率元素获得更短路径。
- 顺序存储：按概率降序排成
do, while, for, repeat（同概率者次序可互换），顺序查找 ASL 为 \(2.1\)。 - 链式存储：同样按概率降序做单链表，顺序查找 ASL 仍为 \(2.1\)。
- 也可用二叉链表构造概率友好的 BST，教材给出的 ASL 为 \(2.0\)。
⚠️ 折半查找的前提是按关键字有序；不能为照顾概率任意重排后仍声称使用折半查找。
b_290_7；PDF 第 290 页 · b_290_8；PDF 第 290 页 · b_290_9；PDF 第 290 页 · b_290_10；PDF 第 290 页 · b_290_12怎样判断一串关键字能否成为折半查找的比较序列？（2015 统考真题）¶
把每次比较后的可行区间同步收窄：目标小于当前关键字就更新上界，大于则更新下界；后续关键字必须始终落在当前区间内。
另一种等价方法是画出路径，检查它能否嵌入一棵二叉排序树。教材选项 A 在路径约束上发生矛盾，因此不能构成比较序列。
💡 通法不是只看相邻两数，而是维护“截至当前仍可能出现的上下界”。
b_287_7；PDF 第 287 页 · b_287_8；PDF 第 287 页 · b_287_9；PDF 第 287 页 · b_287_10跳跃式顺序查找中，目标越靠前为什么比较越少？（2016 统考真题）¶
题中伪代码按固定步长跳着扫描升序数组，本质仍是顺序排除候选位置；目标越早落入前面的探查点或区间，完成的比较轮次越少。
⚠️ 不要因为代码里有“跳跃”就自动套 \(O(\log n)\)。只有每轮把候选规模按比例缩小，才具有对数级特征；固定步长通常仍是线性级。
b_287_11；PDF 第 287 页 · b_287_12一棵树能否作为折半查找判定树，为什么还要检查 mid 取整方向？（2017 统考真题）¶
折半查找判定树不仅是平衡 BST，还受同一套 mid 取整规则约束。
- 若始终向下取整，偶数个元素时左子树比右子树少 1 个或二者相等。
- 若始终向上取整，偶数个元素时左子树比右子树多 1 个或二者相等。
- 一棵候选树若某处体现向上取整、另一处又体现向下取整，就不可能由同一算法生成。
b_287_13；PDF 第 287 页 · b_287_14哪些结构不适合直接折半查找？（2024 统考真题）¶
折半查找要求同时满足：有序，且能按下标 \(O(1)\) 随机定位中点。
- 数组或顺序表适合。
- 链表、静态链表即使有序，也需沿链寻找中点；反复定位会失去折半优势，因此不适合直接使用。
⚠️ “逻辑上有序”只是一个条件，“物理上支持随机存取”同样不可少。
b_287_17；PDF 第 287 页 · b_287_18；PDF 第 288 页 · b_288_0顺序索引、块内也顺序查找时，最优块长为什么是 √n？（2025 统考真题）¶
设每块含 \(s\) 个元素，块数 \(k=n/s\)。等概率时
由均值不等式，\(n/s=s\) 时最小，所以 \(s=\sqrt n\)。本题 \(n=400\)，最优块长为 20。
⚠️ 该结论依赖“索引顺序查找 + 块内顺序查找 + 均匀分块”。若两级使用折半查找，结论要重新推导。
b_288_1；PDF 第 288 页 · b_288_2已知 BST 的先序或插入序列，怎样还原树并计算 ASL？（7.3 综合应用题 01、02）¶
- 先序序列还原：首元素是根；利用 BST 的中序序列必为递增序列，先序 + 中序可唯一重建。
- 插入序列建树：从空树开始逐个比较并落到空孩子位置。
- 成功 ASL：按真实结点层次加权；失败 ASL：补全空孩子对应的失败区间，比较次数算到其父结点。
教材 Q01 得成功 ASL \(2.9\)、失败 ASL \(39/11\)；Q02 成功 ASL \(3.2\)。
b_313_3；PDF 第 313 页 · b_313_5；PDF 第 313 页 · b_313_6；PDF 第 313 页 · b_313_7；PDF 第 313 页 · b_313_8；PDF 第 313 页 · b_313_9；PDF 第 313 页 · b_313_10；PDF 第 313 页 · b_313_11；PDF 第 313 页 · b_313_13n 个不同关键字能构造多少种 BST 形态，为什么会出现 Catalan 数？（7.3 普通选择题 09）¶
不同关键字的升序序列固定了 BST 的中序序列；每一种树形再配合其先序序列，就能唯一确定一棵 BST。因此，BST 形态数等于 n 个结点的二叉树形态数：
本题 \(n=5\)，所以 \(C_5=42\)。
⚠️ 题目问的是不同树形，不是插入序列数；多个不同插入序列可能生成同一棵 BST。
b_308_2；PDF 第 308 页 · b_308_3AVL 插入手算怎样统一处理 LL、RR、LR、RL？（7.3 综合应用题 03；2010、2013、2021 统考真题）¶
从新结点向根回溯，找到第一个平衡因子绝对值变为 2 的结点 z，再看插入路径的两步方向：
- LL：对 z 右旋；RR：对 z 左旋。
- LR：先对左孩子左旋，再对 z 右旋。
- RL：先对右孩子右旋，再对 z 左旋。
教材综合题依次出现 LL、RR、RL、RL；2010 插入 48 后为 RL，调整后 37 的孩子是 24、53；2013 顺序插入 1～7 后平衡因子为 0 的分支结点有 3 个；2021 插入 23 后 RL 调整，根为 25。
⚠️ 旋转后仍要保持 BST 的中序次序不变。
b_310_3；PDF 第 310 页 · b_310_4；PDF 第 310 页 · b_310_6；PDF 第 311 页 · b_311_4；PDF 第 311 页 · b_311_5；PDF 第 312 页 · b_312_9；PDF 第 312 页 · b_312_10；PDF 第 313 页 · b_313_14；PDF 第 313 页 · b_313_16；PDF 第 313 页 · b_313_18；PDF 第 314 页 · b_314_1；PDF 第 314 页 · b_314_3固定高度的 AVL 有多少种树形，怎样按左右子树高度递推？（7.3 普通选择题 13）¶
设 \(A_h\) 为高度恰为 h 的 AVL 树形数。根的左右子树高度只能是 \((h-1,h-1)\)、\((h-1,h-2)\)、\((h-2,h-1)\)，因此
按题目层高口径，\(A_1=1\)、\(A_2=3\)，所以
💡 先枚举允许的“左右高度对”，再乘法组合左右子树形态；不要把 AVL 误当完全二叉树只画一种。
b_308_7；PDF 第 308 页 · b_308_8；PDF 第 308 页 · b_308_11；PDF 第 308 页 · b_308_12；PDF 第 308 页 · b_308_13关键字递增插入 AVL 时，怎样利用满树边界判断何时增高？（7.3 普通选择题 15）¶
按题目“单根高度为 0”的口径，递增插入到 \(2^{h+1}-1\) 个关键字时，教材给出的 AVL 恰为高度 h 的满树；再插入 1 个关键字，树高增为 \(h+1\)。
本题先插入 1～1023：\(1023=2^{10}-1\)，树高为 9；再插入 1024，树高变为 10。
⚠️ 先确认高度是“边数”还是“层数”。同一棵树若按层数计高，数值会多 1。
b_308_16；PDF 第 308 页 · b_308_17等概率关键字的“最佳 BST”怎样构造？（7.3 综合应用题 04）¶
先将关键字升序排列，再仿照折半查找判定树：尽量取中间关键字为根，使左右子树结点数接近，从而让树高和等概率 ASL 尽量小。
⚠️ 这是等概率下的教材构造法；若概率不同，应按加权路径长度优化，不能只追求完全平衡。
b_314_4；PDF 第 314 页 · b_314_5；PDF 第 314 页 · b_314_6怎样用一次中序遍历判断二叉树是否为 BST？（7.3 综合应用题 05）¶
BST 的中序序列应严格递增。递归中序遍历时用 predt 保存前一个访问值：若发现 predt>=current->data，立即判否；否则更新 predt 并继续右子树。
- 时间 \(O(n)\)。
- 递归栈空间 \(O(h)\)。
- ⚠️ 初值应是真正的负无穷或额外的“尚无前驱”标志，不能让某个普通常量误伤合法关键字。
b_314_7；PDF 第 314 页 · b_314_8；PDF 第 314 页 · b_314_9；PDF 第 314 页 · b_314_10怎样求指定结点在 BST 中的层次？（7.3 综合应用题 06）¶
沿 BST 查找路径向下：每与一个结点比较并下降一层，层次计数加 1；找到目标时返回计数。
- 平均时间取决于树高，随机 BST 通常为 \(O(\log n)\)；最坏退化链时为 \(O(n)\)。
- 若树中可能有重复关键字，只比较 data 未必能唯一定位“指定结点”，应按题设约定处理。
b_314_11；PDF 第 314 页 · b_314_12；PDF 第 314 页 · b_314_13；PDF 第 315 页 · b_315_0选择题中怎样快速判断一棵树是否满足 AVL 定义？（2009 统考真题）¶
从叶结点向上标出每个非叶结点的左右子树高度，计算平衡因子；任一结点的绝对值超过 1 即排除。2009 题只有选项 B 的所有结点都满足该条件。
⚠️ 不能只检查根结点；AVL 要求任意结点都平衡。
b_310_1；PDF 第 310 页 · b_310_2怎样在一次后序遍历中判断整棵二叉树是否为 AVL？（7.3 综合应用题 07）¶
后序递归让每棵子树同时返回“高度 h”和“是否平衡 balance”：
- 空树返回高度 0、平衡真。
- 当前高度为
max(hl,hr)+1。 - 只有左右子树都平衡且 \(|h_l-h_r|<2\)，当前树才平衡。
时间 \(O(n)\)、递归栈 \(O(h)\)。
b_315_1；PDF 第 315 页 · b_315_2；PDF 第 315 页 · b_315_3；PDF 第 315 页 · b_315_5BST 的最小、最大关键字为什么不需要逐个比较？（7.3 综合应用题 08）¶
由 BST 性质，最小关键字在最左下结点，最大关键字在最右下结点。分别沿 lchild 或 rchild 走到空即可。
时间 \(O(h)\)、空间 \(O(1)\)；最值结点不一定是叶结点，但最小结点必无左孩子，最大结点必无右孩子。
b_315_6；PDF 第 315 页 · b_315_7；PDF 第 315 页 · b_315_8怎样从大到小输出 BST 中所有不小于 k 的关键字？（7.3 综合应用题 09）¶
采用逆中序“右—根—左”，并利用阈值剪枝：
- 先访问右子树。
- 仅当当前值 \(\ge k\) 时输出；若当前值小于 k，其左子树更小，可整棵剪掉。
- 再访问仍可能含合格值的左子树。
教材给出逆中序主线；实现时补上阈值判断和剪枝，避免把所有结点无条件输出。
b_316_0；PDF 第 316 页 · b_316_1；PDF 第 316 页 · b_316_2；PDF 第 316 页 · b_316_3带子树结点数 count 的 BST 怎样在平均 O(logn) 内找第 k 小？（7.3 综合应用题 10）¶
设左子树大小为 \(L\)：
- \(k=L+1\)：当前结点就是第 k 小。
- \(k\le L\)：递归左子树，k 不变。
- \(k>L+1\)：递归右子树，改查第 \(k-L-1\) 小。
先检查 \(1\le k\le t->count\)。时间等于一条根到结点路径，随机 BST 平均 \(O(\log n)\)；若树退化则最坏 \(O(n)\)。
b_316_4；PDF 第 316 页 · b_316_5；PDF 第 316 页 · b_316_6；PDF 第 316 页 · b_316_7；PDF 第 316 页 · b_316_8；PDF 第 316 页 · b_316_10；PDF 第 316 页 · b_316_11BST 查找路径和插入序列题怎样用“动态上下界”排除？（2011、2020 统考真题）¶
沿某条 BST 查找路径时维护合法区间 (low,high)：向左后更新 high=current，向右后更新 low=current；后续关键字必须始终落在区间内。
判断一个输入序列能否生成指定 BST 时也一样：逐个按 BST 插入规则模拟；只要某元素落点与目标树不符即可排除。
⚠️ 只检查“左小右大”的相邻关系不够，必须服从所有祖先共同限定的区间。
b_310_7；PDF 第 310 页 · b_310_8；PDF 第 310 页 · b_310_9；PDF 第 312 页 · b_312_6；PDF 第 312 页 · b_312_7；PDF 第 312 页 · b_312_8高度为 h 的 AVL 最少结点数怎样递推？（2012 统考真题）¶
最少结点 AVL 的两棵子树高度应为 \(h-1\) 与 \(h-2\)：
按本书层高口径取 \(N_1=1,N_2=2\)。递推得高度 6、所有非叶结点平衡因子均为 1 时共有 20 个结点。
💡 本质是“在仍平衡的前提下让两边尽可能少”，因此取允许的最大高度差 1。
b_310_11；PDF 第 310 页 · b_310_12；PDF 第 310 页 · b_310_13；PDF 第 311 页 · b_311_0；PDF 第 311 页 · b_311_1删除结点再插回，BST 与 AVL 为什么都不保证恢复原树？（2013、2019 统考真题）¶
- BST：删叶结点再按原规则插回可恢复；删非叶结点时常由前驱/后继替代，原结点再插回成为叶结点，形态通常改变。
- AVL：删除和重新插入都可能触发旋转；删叶也可能改变，删非叶也可能因后续旋转恰好恢复，所以只能讨论“可能”，不能下绝对结论。
⚠️ 看到“必然相同、必然不同”先找反例；AVL 比普通 BST 多一层旋转影响。
b_311_2；PDF 第 311 页 · b_311_3；PDF 第 311 页 · b_311_11；PDF 第 311 页 · b_311_12；PDF 第 311 页 · b_311_13；PDF 第 312 页 · b_312_1；PDF 第 312 页 · b_312_2；PDF 第 312 页 · b_312_4中序得到降序的“AVL”题，为什么必须按统考题设口径作答？（2015 统考真题）¶
多数教材把 AVL 定义为高度平衡的 BST，中序应升序；但本题命题口径把“平衡二叉树”只按高度平衡理解，因此允许中序降序。
按题设可推出：最大元素没有左子树，但未必是叶结点；最后插入结点经旋转后也未必仍是叶结点。教材答案据此选 D。
⚠️ 考试遇到材料内部约定与常规定义冲突时，先明确“本题按题设/教材口径”，不要擅自改题。
b_311_7；PDF 第 311 页 · b_311_8BST 图中的未知关键字和整棵子树范围怎样推？（2018、2024 统考真题）¶
把每个祖先带来的上下界同时保留：左子树继承上界，右子树继承下界；越往下区间只会继续收窄。
- 2018：先写出图的中序序列，再由递增性比较未知关键字。
- 2024：子树 T 同时受多个祖先限制，教材综合得到其中任意 \(x\) 满足 \(k_3<x<k_2\)。
💡 一棵子树不是只和直接父结点比，还必须满足所有祖先的范围约束。
b_311_9；PDF 第 311 页 · b_311_10；PDF 第 313 页 · b_313_0；PDF 第 313 页 · b_313_1红黑树选择题中，哪些绝对化表述最容易出错？（7.3 普通选择题 16～18）¶
- AVL 高度更严格，通常查询效率优于同规模红黑树；红黑树的优势主要是增删调整较少，不能把方向说反。
- 两者查找、插入、删除的渐近复杂度都是 \(O(\log n)\)；但按本书删除流程，红黑树删除的旋转次数可能超过 2 次。
- 红黑树从任一结点到最远叶与最近叶的路径长度之比不超过 2，这是“适度平衡”，不是 AVL 的高度差不超过 1。
- 若所有内部结点都是黑色，为满足各路径黑高相同，树必须是满二叉树；但以红结点为根截下的子树不满足“根为黑色”，不能直接称为红黑树。
⚠️ 做性质判断时，逐条回到“根叶黑、红不相邻、各路黑高相同”，少凭“看起来平衡”下结论。
b_308_18；PDF 第 308 页 · b_308_19；PDF 第 308 页 · b_308_20；PDF 第 308 页 · b_308_21；PDF 第 309 页 · b_309_0；PDF 第 309 页 · b_309_1；PDF 第 309 页 · b_309_2m 阶 B 树定义题怎样逐项核对而不被某张具体图误导？（2009 统考真题）¶
逐项核对四条数量边界：结点关键字数比子树数少 1；根若非终端至少 2 棵子树；除根外非终端至少 \(\lceil m/2\rceil\) 棵子树；所有外部失败结点在同层。
⚠️ 某棵具体 B 树可能同时满足 4 阶、5 阶、6 阶的上下界，不能因为“图中最大分支数是 4”就断言它一定是 4 阶。2009 题中“叶结点彼此必须用指针连接”描述的是 B+ 树特征，不是 B 树定义。
b_325_11；PDF 第 325 页 · b_325_12B 树的最少/最多关键字或结点数，怎样按层建立上下界？（2013、2014、2018、2021 统考真题）¶
先分清题目问“关键字数”还是“含关键字的结点数”，再按每层最少/最多分支递推。
- 2013：高度 2 的 5 阶 B 树，根至少 1 个关键字、第二层至少 2 个结点且各至少 2 个关键字，最少共 5 个。
- 2014：15 个关键字要让结点数最多，就让每结点尽量只含 1 个关键字，最多 15 个结点。
- 2018：高度 5 的 3 阶 B 树最少形如满二叉分支，关键字最少为 \(2^5-1=31\)。
- 2021：3 阶树第 2 层 4 个关键字，为使结点最多，应把它们分散到尽可能多的结点，再让下一层满分支；教材答案为 11 个结点。
b_326_2；PDF 第 326 页 · b_326_4；PDF 第 326 页 · b_326_6；PDF 第 326 页 · b_326_7；PDF 第 326 页 · b_326_12；PDF 第 326 页 · b_326_13；PDF 第 327 页 · b_327_0；PDF 第 327 页 · b_327_13 阶/4 阶 B 树连续插入时，分裂和上提怎样逐层传播？（7.4 综合应用题 01、02；2020 统考真题）¶
先把关键字插到最底层终端结点并保持结点内有序；若插入后关键字数达到 m，就从第 \(\lceil m/2\rceil\) 个关键字处分裂，中间关键字上提父结点；父结点溢出则继续向上分裂。
- 综合 Q01：3 阶树每结点最多 2 个关键字，插 50、60、70 时分别触发分裂，最终 52 上升为新根。
- 综合 Q02：插 25 触发一次分裂；插 45 时叶结点和父结点连续分裂。
- 2020：4 阶树插入给定序列后，根含 6、9。
⚠️ 只有分裂一路传到根并使根分裂，树高才增加 1。
b_326_14；PDF 第 326 页 · b_326_15；PDF 第 328 页 · b_328_0；PDF 第 328 页 · b_328_1；PDF 第 328 页 · b_328_3；PDF 第 328 页 · b_328_5；PDF 第 328 页 · b_328_7；PDF 第 328 页 · b_328_10；PDF 第 328 页 · b_328_12B 树删除时，什么时候直接删、向兄弟借、与兄弟合并？（7.4 综合应用题 02；2012、2022 统考真题）¶
先把非终端结点中的删除转化为删除前驱或后继；再看删后是否低于最少关键字数。
- 兄弟够借：父分隔关键字下移到待调整结点，兄弟的边界关键字上移到父结点，必要时还要随关键字转移对应子树。
- 兄弟不够借：把当前结点、父分隔关键字和一个兄弟合并；父若下溢继续向上调整。
- 2012 删除 78 属于左兄弟够借；2022 删除 260 可选前驱或后继并产生多种合法结果，只有根序列
<60,90,110,350>不可能。 - 综合 Q02 删除 80 会引发多层合并，但本题调整后根仍有关键字，树高并未下降。一般只有合并使根的关键字数降为 0、原根被删除时，树高才下降 1。
⚠️ 判断合法结果必须同时检查各结点关键字上下界和关键字区间，不能只看根。
b_325_13；PDF 第 326 页 · b_326_0；PDF 第 327 页 · b_327_3；PDF 第 327 页 · b_327_4；PDF 第 327 页 · b_327_5；PDF 第 329 页 · b_329_0；PDF 第 329 页 · b_329_2；PDF 第 329 页 · b_329_3；PDF 第 329 页 · b_329_5B+ 树与 B 树的差异怎样直接判断应用题？（2016、2017 统考真题）¶
B+ 树的全部记录信息都在叶结点，非叶结点只作索引；叶结点按关键字顺序链接，所以既能从根多路查找，也能顺序/范围扫描。
- 2016：能顺序查找、所有关键字信息集中在叶结点，是 B+ 树区别于 B 树的特征。
- 2017：数据库索引、文件索引适合 B+ 树，因为非叶层更紧凑、磁盘 I/O 代价低，查找路径也更稳定。
b_326_8；PDF 第 326 页 · b_326_9；PDF 第 326 页 · b_326_10；PDF 第 326 页 · b_326_11B 树的插入、删除、查找是否一定到“叶结点”？（2023 统考真题）¶
按本书答案与统考术语作答：
- 插入可能把分裂一路传到根，故可能增高。
- 删除最终会转化到最底层终端结点处理，教材据此认为会导致叶结点变化。
- 查找成功可在内部结点提前结束，不总要到底层。
- 新关键字最初插在底层，但分裂时可能上提，不保证最终仍在叶结点。
⚠️ 本题把最底层终端结点称为“叶结点”，与本书正文常把外部失败结点称叶结点的口径不同；考场以题设为准。
b_327_6；PDF 第 327 页 · b_327_7；PDF 第 327 页 · b_327_8；PDF 第 327 页 · b_327_97 个关键字能形成多少种不同 4 阶 B 树，怎样按树高与根关键字数分类？（2025 统考真题）¶
按树高分类，再按根含 1、2、3 个关键字分配剩余关键字：
- 两层：根含 1 个时分配
(3,3)共 1 种；根含 2 个时三子结点分配(3,1,1)或(2,2,1)，计排列共 6 种；根含 3 个时四子结点各 1 个，共 1 种。 - 三层：只有根和第 2 层两个结点都各含 1 个关键字、底层四结点各 1 个的最小结构，共 1 种。
总数 \(1+6+1+1=9\)。
b_327_10；PDF 第 327 页 · b_327_11用 B 树做磁盘索引时，阶数和索引页数怎样由页块大小反推？（7.4 综合应用题 03）¶
设 m 阶 B 树结点最多有 \(m-1\) 个关键字与记录地址、m 个子树指针，另有关键字计数域。按题中每项 5B、计数 2B：
得 \(m\le267\)，取 267 阶。
20000000 条记录、每页 20 条，共 1000000 个数据页；每索引结点可容纳 133～266 个索引项，因此索引部分约需 3760～7519 个页块。
⚠️ 计算时要按题设区分 B 树与 B+ 树：B 树索引项可分布在各层，B+ 树完整记录索引集中在叶层。
b_329_6；PDF 第 329 页 · b_329_7；PDF 第 329 页 · b_329_8；PDF 第 329 页 · b_329_9；PDF 第 329 页 · b_329_10高度为 h 的 B 树插入一次，最坏读写和新结点数怎样计算？（7.4 普通选择题 11）¶
按题设“根未读入内存，读过的结点一直留在内存”计算最坏情况：查找插入位置需沿根到最底层读 h 个结点；若分裂逐层传到根，每层分裂要写回 2 个结点，根分裂后形成新根还要再写 1 次。
- 最多新产生 \(h+1\) 个结点。
- 最多写磁盘 \(2h+1\) 次，读磁盘 h 次，总读写次数为 \(3h+1\)。
- 只有分裂传到根并使根分裂时树高才增加；某个普通结点分裂不代表树高必增。
b_325_5；PDF 第 325 页 · b_325_6提高散列表效率要同时看哪三个因素？（2011、2022 统考真题）¶
散列表 ASL 主要受三者影响：散列函数是否均匀、冲突处理方法、装填因子 \(\alpha=n/m\)。
- \(\alpha\) 越大，表越满，冲突概率通常越高。
- 合适的冲突策略可减轻聚集。
- ASL 不直接由“表中已有记录数 n”或“表长 m”单独决定；同一 \(\alpha\) 下仍会因函数和策略不同而变化。
b_337_23；PDF 第 337 页 · b_337_24；PDF 第 338 页 · b_338_0；PDF 第 338 页 · b_338_12；PDF 第 338 页 · b_338_13堆积为什么增大 ASL？线性探测与二次探测的覆盖能力有何不同？（2014、2025 统考真题）¶
线性探测的探查序列连续，非同义词的探查路径也会互相交织，形成长的连续占用区，即堆积；它会直接增大平均查找长度。
- 线性探测会遍历整张表，所以只要表未满，一定能找到空位。
- 二次探测跳跃探查，可减轻堆积，但可能只覆盖部分地址；即使表未满也不保证找到空位。
- 两种方法处理的冲突都可能来自同义词或非同义词，不能用“一定”限定。
b_336_13；PDF 第 336 页 · b_336_14；PDF 第 338 页 · b_338_1；PDF 第 338 页 · b_338_2；PDF 第 338 页 · b_338_19；PDF 第 338 页 · b_338_20；PDF 第 339 页 · b_339_0线性探测散列表的查找成功 ASL 怎样逐元素计算？（2018 统考真题）¶
先按插入顺序构造表；每个关键字的成功查找长度就是从其初始散列地址开始，直到命中它所经历的关键字比较次数。
本题 22、43、15 的比较次数分别为 1、2、3，因此
⚠️ 不能直接用“最终下标 − 初始下标”，因为探查可能回绕；应按真实探查序列计数。
b_338_3；PDF 第 338 页 · b_338_4；PDF 第 338 页 · b_338_5；PDF 第 338 页 · b_338_6线性探测的失败 ASL 为什么按散列函数值域平均，而不是按表长平均？（2019 统考真题）¶
失败查找先由 \(H(key)\) 产生初始地址，再沿探查序列直到遇到真正空位。题中 \(H(key)=key\%7\)，初始地址只有 0～6 七种，即使表长为 11，也只应对这 7 种等可能起点平均。
各起点失败比较次数为 9、8、7、6、5、4、3，所以
⚠️ “分母看散列函数可能产生多少个初始地址”，不是机械写表长。
b_338_7；PDF 第 338 页 · b_338_8；PDF 第 338 页 · b_338_9；PDF 第 338 页 · b_338_10；PDF 第 338 页 · b_338_11开放定址法删除为什么要留墓碑标记？拉链法为什么可物理删除？（7.5 综合应用题 01；2023 统考真题）¶
开放定址中，某位置可能位于其他关键字的探查路径上；若改成真正空位，后续查找会提前停止。因此只能标为“已删除”，查找遇到墓碑仍要继续。
拉链法的同义词都在独立链表中，删除某结点只需断链，不会截断其他散列地址的查找路径，所以可物理删除。
2023 题删除 25 后，失败查找仍跨过删除标记，教材算得失败 ASL 为 1.8。
b_338_14；PDF 第 338 页 · b_338_15；PDF 第 338 页 · b_338_16；PDF 第 338 页 · b_338_17；PDF 第 338 页 · b_338_18；PDF 第 339 页 · b_339_1；PDF 第 339 页 · b_339_2；PDF 第 339 页 · b_339_3怎样判断一个表达式能否作为“好散列函数”？（7.5 综合应用题 02）¶
至少检查三点：返回值始终落在 [0,n-1]、同一 key 每次结果确定、地址分布尽量均匀。
key/n可能越界，不能直接用。- 常数 1 虽能映射到表内，但所有关键字冲突，不是好函数。
- 含每次变化的
random(n)，同一 key 地址不确定，无法正常查找。 key % p(n)且 p 为不大于 n 的最大素数，是教材认可的好方法。
b_339_4；PDF 第 339 页 · b_339_5同一组关键字用线性探测和链地址法时，成功/失败 ASL 为什么不同？（7.5 综合应用题 03）¶
两种方法的初始散列地址相同，但冲突后的组织方式不同，所以比较路径不同。
- 线性探测：成功 ASL 按每个关键字真实探查次数平均，本题 \(21/8\)；失败从 0～10 各起点探测到空位，本题 \(47/11\)。
- 链地址：成功按链内关键字比较次数平均，本题 \(13/8\)；失败口径若把空指针也算一次，本题 \(19/11\)。
⚠️ 失败 ASL 有“比较到空结点也计一次”和“只计关键字比较”两种口径，必须服从题目或教材说明。
b_339_6；PDF 第 339 页 · b_339_8；PDF 第 339 页 · b_339_9；PDF 第 339 页 · b_339_16；PDF 第 339 页 · b_339_18；PDF 第 340 页 · b_340_0；PDF 第 340 页 · b_340_1；PDF 第 340 页 · b_340_3；PDF 第 340 页 · b_340_5；PDF 第 340 页 · b_340_6；PDF 第 340 页 · b_340_8给定装填因子并用链地址法时，怎样确定表长、模数和 ASL？（7.5 综合应用题 04）¶
先由 \(\alpha=n/N\) 求表长 \(N\)，再取不大于 N 的最大素数 P 作为除留余数法模数。题中 \(n=11,\alpha=0.73\)，得 \(N\approx15,P=13\)，故 \(H(key)=key\%13\)。
构造 13 条同义词链后，成功 ASL 按各关键字在链内的比较次数加权；失败若题目明确“只计与关键字比较”，则空链贡献 0。本题成功 ASL \(18/11\)，失败 ASL \(11/13\)。
b_340_9；PDF 第 340 页 · b_340_10；PDF 第 340 页 · b_340_11；PDF 第 340 页 · b_340_13；PDF 第 341 页 · b_341_0；PDF 第 341 页 · b_341_1已知线性探测的 ASL 上限，怎样反推装填因子和最小表长？（7.5 普通选择题 06、07）¶
若题目直接给出线性探测成功查找的教材公式
先由 ASL 上限解出 \(\alpha\)，再用 \(\alpha=n/m\) 反推表长。200 个元素且 ASL 不超过 1.5 时，\(alpha\le1/2\)，故 \(m\ge400\)。
若 K 个关键字全为同义词并依次线性探测，最少探测次数为
⚠️ 公式题按题给模型计算；若题目给出具体关键字序列，则必须实际构表逐项数比较次数。
b_336_17；PDF 第 336 页 · b_336_18；PDF 第 337 页 · b_337_0；PDF 第 337 页 · b_337_1；PDF 第 337 页 · b_337_2；PDF 第 337 页 · b_337_3链地址法查找路径为什么一定全是同义词，而线性探测不一定？（7.5 普通选择题 12、13）¶
- 链地址法把同一初始散列地址的关键字放入同一链表，因此在某条链上成功查找时，经过的关键字一定互为同义词。
- 线性探测会把冲突元素向后搬移，其他初址的探查序列又可能经过这些位置，所以途中比较的关键字不一定都是同义词。
- 若 \(H(key)=key\bmod17\)，函数值域是 0～16，对应 17 条链和下标 0～16 的链首指针数组。
⚠️ “同义词冲突”与“堆积”不是同一概念；线性探测尤其容易让不同初址的探查路径交织。
b_337_11；PDF 第 337 页 · b_337_12；PDF 第 337 页 · b_337_13；PDF 第 337 页 · b_337_14双散列探测怎样从固定步长生成整条查找路径？（7.5 综合应用题 05）¶
先算 \(H_0(key)\)，再由第二函数得到该关键字固定的步长；发生冲突后反复累加同一步长并模表长，直到空位或命中。
本题 27 的初址为 1，步长由 REV(28)%11+1 得到，依次探测 1、7、0，最终放入 0。按每个关键字的真实比较次数，成功 ASL 为 \(11/8\)。
⚠️ 双散列不是每次重新生成一个无关步长；对同一 key 的探查序列必须可重现。
b_341_2；PDF 第 341 页 · b_341_3；PDF 第 341 页 · b_341_4；PDF 第 341 页 · b_341_5；PDF 第 341 页 · b_341_6线性探测综合题怎样从装填因子反推表长并计算两种 ASL？（2010 统考真题）¶
7 个关键字、装填因子 0.7，先得表长 \(m=10\)；再按 \(H(key)=3key\bmod7\) 算初址，用模 10 的线性探测找空位。
- 成功 ASL：按 7 个表中关键字各自比较次数平均，教材为 \(12/7\)。
- 失败 ASL：初始地址只可能是 0～6，按这 7 个起点探测到空位的次数平均，教材为 \(18/7\)。
⚠️ 散列函数的模数 7 决定失败 ASL 的等可能起点，散列表长度 10 决定线性探测如何回绕，两者不能混用。
b_341_7；PDF 第 341 页 · b_341_8；PDF 第 341 页 · b_341_10；PDF 第 341 页 · b_341_12；PDF 第 341 页 · b_341_14；PDF 第 341 页 · b_341_16平方探测综合题怎样构表、给出比较序列并确认失败地址？（2024 统考真题）¶
严格按 \(H_k=(H_0+k^2)\%11\)，取 \(k=1,2,3,\dots\) 的正平方序列：
- 构表后装填因子为 \(7/11\)。
- 查 14：依次比较 3、18、14。
- 查 8：从初址 2 出发，依次探测 2、3、6、0、7；地址 7 为空，故在 7 确认失败。
⚠️ 本题明确只用 \(+k^2\)，不要擅自加入教材另一种常见的 \(\pm k^2\) 序列。
b_341_17；PDF 第 342 页 · b_342_0；PDF 第 342 页 · b_342_1；PDF 第 342 页 · b_342_2；PDF 第 342 页 · b_342_3【原书归纳总结与思维拓展】第7章¶
各类查找题的 ASL 能否统一成一套“概率 × 比较次数”框架？¶
可以。成功时对已有元素求
失败时对由已有元素划分出的失败区间或可能初址求
真正的难点不是公式，而是确定样本空间：折半失败看 \(n+1\) 个失败区间；开放定址失败看散列函数可能产生的初始地址；链地址还要先确认空指针是否计一次。
b_342_4；PDF 第 342 页 · b_342_5；PDF 第 342 页 · b_342_6；PDF 第 342 页 · b_342_7；PDF 第 342 页 · b_342_8；PDF 第 342 页 · b_342_10手算查找题时，怎样按“结构—路径—次数—平均”四步避免乱套公式？¶
- 结构：先构造判定树、BST/B 树或散列表。
- 路径：逐个标出成功路径及每个失败入口。
- 次数：在图上写每个元素/区间的真实比较次数。
- 平均：最后才按题给概率求加权平均。
⚠️ 不同结构的失败样本空间不同。先画结构再数次数，通常比直接背 ASL 公式更可靠。
b_342_5；PDF 第 342 页 · b_342_8AVL 手算能否用零壹“3+4 重构”辅助？边界在哪里？¶
可以把失衡路径上的三个关键结点按中序排成小、中、大，并把四棵有序子树按中序接回，用来快速复核旋转后的形态；但考试主答案仍按王道写清 LL/RR/LR/RL 类型、最小不平衡子树和旋转方向。
⚠️ “3+4”只是画图/验图工具：不能替代题目要求的旋转过程，也不能忽略结点平衡因子更新；遇到删除可能连续向上调整时，更不能只重构一次就停止。
b_313_14；PDF 第 313 页 · b_313_16；PDF 第 314 页 · b_314_1；PDF 第 314 页 · b_314_3散列题中有哪些“题设口径优先”的高风险点？¶
- 散列失败 ASL 有“空位置也算一次”和“只算关键字比较”两种口径；按题目明示。
- 平方探测有
+k²与±k²两种序列；按题给公式，不自行补项。 - 失败 ASL 的等可能起点由散列函数值域决定，不一定等于散列表的全部下标。
b_340_7；PDF 第 340 页 · b_340_8；PDF 第 342 页 · b_342_3；PDF 第 342 页 · b_342_10“超过一半的元素”为什么能用成对抵消做到 O(n)？（思维拓展）¶
若某数出现次数超过一半，每次删除两个不同的数后，它在剩余序列中仍占多数。扫描时维护候选与计数：相同加一，不同减一，计数归零就换候选；最后再扫描一次验证候选是否确实超过一半。
时间 \(O(n)\)、空间 \(O(1)\)。这与第2章主元素题同一方法；本章思维拓展从“查找”角度再次解释了抵消不变量。
b_342_11；PDF 第 342 页 · b_342_12；PDF 第 342 页 · b_342_13；PDF 第 342 页 · b_342_14；PDF 第 342 页 · b_342_15【易混点】第7章成对概念对照¶
| 概念 A | 概念 B | 一句话切分 |
|---|---|---|
| 静态查找表 | 动态查找表 | 顺序/折半 vs BST；散列两者皆可 |
| 一般表顺序查找 | 有序表顺序查找 | 失败要比 n+1 次 vs 失败可提前返回，n/2 + n/(n+1) |
| 有序表顺序查找 | 折半查找 | ⚠️ 可用链式存储 vs ⚠️ 只能顺序存储 |
| 折半查找判定树 | BST | 唯一 vs 形态取决于插入顺序 |
| 折半查找 | BST | 静态表更优 vs 动态表更优（增删只改指针） |
| ASL 成功 | ASL 失败 | 算到目的结点 vs 算到失败结点的父结点 |
| 分块查找 s = √n | 索引顺序表 | ASL 最小值 √n + 1 |
| 平衡因子 | 黑高 | 左减右高度差，取 −1/0/1 vs 到叶结点路径上的黑结点数 |
| AVL 插入调整 | AVL 删除调整 | 只调一次 vs ⚠️ 可能一路回溯到根 |
| LL/RR | LR/RL | 同向单旋 vs 异向双旋 |
| AVL | 红黑树 | 高度平衡、查找快 vs 适度平衡、增删调整少 |
| B 树叶结点（本书） | B 树叶结点（统考） | ⚠️ 失败结点 vs ⚠️ 最底层终端结点 |
| B 树 n 关键字 | B+ 树 n 关键字 | n+1 棵子树 vs n 棵子树 |
| B 树关键字数范围 | B+ 树关键字数范围 | ⌈m/2⌉−1 ~ m−1 vs ⌈m/2⌉ ~ m |
| B 树查找 | B+ 树查找 | 中途可命中提前结束 vs 必须走到叶结点 |
| 兄弟够借 | 兄弟不够借 | 父子换位法 vs 与兄弟和父关键字合并 |
| 开放定址法 | 拉链法 | ⚠️ 不能物理删除，只能逻辑删除 vs 适合频繁增删 |
| 线性探测 | 平方探测 | 会堆积 vs 避免堆积且至少覆盖一半地址，但未必覆盖全部 |
【必背数字】第7章¶
| 数字 | 含义 |
|---|---|
| (n+1)/2 / n+1 | 顺序查找 ASL 成功 / 失败 |
| n/2 + n/(n+1) | 有序表顺序查找 ASL 失败 |
| ⌈log₂(n+1)⌉ / O(log₂n) | 折半查找判定树高度 / 时间复杂度 |
| n 个圆形结点 + n+1 个方形失败结点 | 折半查找判定树的构成 |
| 3 / 11/3 | 教材 11 元素折半查找的 ASL 成功 / 失败 |
| √n + 1 | 分块查找 s = √n 时的最小 ASL |
| −1、0、1 | AVL 的平衡因子取值 |
| nₕ = nₕ₋₂ + nₕ₋₁ + 1 | AVL 最少结点递推；n₅ = 12 |
| 2log₂(n+1) | 红黑树高度上界 |
| 2^h − 1 ~ 2^(2h) − 1 | 黑高为 h 的红黑树内部结点数范围 |
| m−1 / ⌈m/2⌉−1 | B 树结点关键字数上限 / 下限 |
| log_m(n+1) ≤ h ≤ log_⌈m/2⌉((n+1)/2) + 1 | B 树高度范围 |
| n + 1 | B 树含 n 个关键字时的外部叶结点数 |
| 第 ⌈m/2⌉ 个关键字 | B 树分裂时上提的位置 |
| 4k + 3 的素数 | 平方探测法对表长的要求 |
| α = n/m | 装填因子；ASL 主要依赖它 |
| 2.5 | 教材线性探测算例的 ASL |
【口诀速记】第7章¶
| 维度 | 口诀 | 解释 |
|---|---|---|
| ASL 两头算 | 成功算到目标，失败算到失败结点的父 | 顺序表、折半、BST 的判定树都适用 |
| 折半三前提 | 有序 + 顺序存储 + 取整一致 | 链表不能折半；向上/向下取整全程只能选一种 |
| 分块查找 | s = √n 时最省，ASL = √n + 1 | 块内可无序，块间必须有序 |
| AVL 旋转 | 同向单旋，异向双旋 | LL/RR 单旋；LR/RL 双旋 |
| AVL 定位 | 先找最小不平衡子树的根 A | 再看新结点相对 A 走左左/左右/右右/右左 |
| AVL 最少结点 | nₕ = nₕ₋₂ + nₕ₋₁ + 1 | n₁=1、n₂=2、n₃=4、n₄=7、n₅=12 |
| 红黑树五性质 | 红不连红，黑高相同，根叶皆黑 | 高度上界 2log₂(n+1) |
| B 树两个界 | ⌈m/2⌉−1 到 m−1 | 动手前先把这两个数算出来 |
| B 树增删 | 超上限中间上提，低下限先借后并 | 分裂取第 ⌈m/2⌉ 个关键字；兄弟 ≥⌈m/2⌉ 才够借 |
| B vs B+ | B 树子树多一个，B+ 关键字全在叶 | n 个关键字：B 树 n+1 棵子树，B+ 树 n 棵 |
| 散列删除 | 开放定址只能逻辑删除 | 物理删除会截断同义词的查找路径 |
b_276_3；PDF 第 276 页 · b_276_4【解题路线】第7章：查找题怎么下手¶
- ① 算 ASL 一律先画判定树（顺序表 / 折半 / BST 都有判定树）：⚠️ 成功算到目标结点的路径结点数；失败算到失败结点的父结点
- ② 折半查找题 → ⚠️ 先确认表是否有序、是否顺序存储；取整方式全程保持一致；判定树是平衡二叉树，高度 ⌈log₂(n+1)⌉
- ③ AVL 调整 → ⚠️ 先定位最小不平衡子树的根 A，再看新结点相对 A 走的是 左左 / 左右 / 右右 / 右左 → LL / LR / RR / RL
- ④ B 树题 → ⚠️ 动手前先算出 ⌈m/2⌉−1（下限）和 m−1（上限）两个数：
- 插入超上限 → 从第 ⌈m/2⌉ 个关键字处分裂，中间那个上提
- 删除低于下限 → 先看兄弟够不够借（≥⌈m/2⌉ 就父子换位），不够借就合并
- ⑤ 散列题 → 先按冲突处理方法把表构造出来，再分别算两个 ASL：⚠️ 成功按各元素的比较次数平均，失败按各初始地址探测到空单元的次数平均
⚠️ 三个易失分点：开放定址法只能逻辑删除；平方探测法要求表长是 4k+3 的素数；B 树的"叶结点"在本书和统考真题中定义不同。
b_276_5；PDF 第 276 页 · b_276_6