第七章查找

7.1 查找的基本概念

查找表：同一类型数据元素的集合。

关键字：数据元素中唯一标识该元素的某个数据项。

查找成功/失败：在查找表中找到/未找到给定关键字的记录。

平均查找长度ASL：

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

其中 $P_i$ 是查找第 $i$ 个元素的概率， $C_i$ 是找到第 $i$ 个元素需要比较的次数。

🗣️ 大白话：ASL 就是"平均要比较多少次才能找到"。ASL 越小，查找效率越高。

7.2 线性表的查找

一、顺序查找

思路：从头到尾一个一个比较。

$ASL_{成功} = \frac{n+1}{2}, \quad ASL_{失败} = n+1$

哨兵：将待查找关键字放在表的一端（0号位置），从另一端开始查找，避免每次循环都检查是否越界。

有序表的顺序查找：若表已有序，查找失败时可以提前终止（遇到比目标大的元素即可停止）。

用判定树分析有序表顺序查找：

成功结点有 $n$ 个（圆形结点），失败结点有 $n+1$ 个（方形结点/外部结点）
$ASL_{成功} = \frac{1+2+\cdots+n}{n} = \frac{n+1}{2}$ （与无序表相同）
$ASL_{失败} = \frac{1+2+\cdots+n+n}{n+1} = \frac{n}{2} + \frac{n}{n+1}$ （优于无序表的 $n+1$ ）

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

前提：有序顺序表（必须是顺序存储！链式存储不行！）

int Binary_Search(SeqList L, ElemType key) {
    int low = 0, high = L.length - 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;  // 查找失败
}

java

int binarySearch(int[] arr, int length, int key) {
    int low = 0, high = length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == key) return mid;
        else if (arr[mid] > key) high = mid - 1;
        else low = mid + 1;
    }
    return -1;  // 查找失败
}

时间复杂度： $O(\log_2 n)$

判定树分析：

折半查找的过程可以用一棵判定树来描述
判定树是一棵平衡二叉排序树（注意：不一定是AVL树，但高度差不超过1）
判定树的形态只与 $n$ 有关，与关键字的具体值无关
查找成功的 $ASL \leq \lfloor \log_2 n \rfloor + 1$
$ASL_{成功} = \frac{1}{n} \sum_{i=1}^{n} l_i$ （ $l_i$ 是第 $i$ 个元素在判定树中的层次）
查找失败的ASL：失败结点（叶结点以下的外部结点）在判定树的第 $\lfloor \log_2 n \rfloor + 1$ 或 $\lfloor \log_2 n \rfloor + 2$ 层
判定树中，右子树结点数 ≥ 左子树结点数（因为 $mid = \lfloor (low+high)/2 \rfloor$ 取下整）
失败结点有 $n+1$ 个（代表 $n+1$ 个查找失败的区间）

🗣️ 大白话：折半查找就像猜数字游戏——主持人告诉你"大了"或"小了"，你每次猜中间值，很快就能猜到。

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

思路：将表分成若干块。块间有序（后一块所有元素都大于前一块），块内无序。

索引表：记录每块的最大关键字和起始位置
先在索引表中查找确定在哪一块（可用折半查找），再在块内顺序查找

$ASL = ASL_{索引} + ASL_{块内}$

均匀分块时（ $n$ 个元素分成 $b = \lceil n/s \rceil$ 块，每块 $s$ 个元素）：

索引表顺序查找： $ASL = \frac{b+1}{2} + \frac{s+1}{2}$
当 $s = \sqrt{n}$ 时， $ASL$ 最小，约为 $\sqrt{n}+1$

⚠️ 索引表用折半查找时的特殊规则：折半查找索引表时，若查找失败（key不等于任何索引项），则目标元素在 low 所指的分块中（而非 mid 或 high）。因为折半查找结束时 low > high，low 恰好指向第一个最大关键字 $\geq key$ 的块。

折半查找索引的ASL： $ASL = \lceil\log_2(b+1)\rceil + \frac{s+1}{2}$ （索引折半 + 块内顺序）

7.3 树形查找

一、二叉排序树（BST）

定义：

若左子树非空，则左子树上所有结点值 $<$ 根结点值
若右子树非空，则右子树上所有结点值 $>$ 根结点值
左右子树也分别是二叉排序树

💡 中序遍历BST得到递增有序序列！

查找操作：

BSTNode *BST_Search(BiTree T, ElemType key) {
    while (T != NULL && key != T->data) {
        if (key < T->data) T = T->lchild;
        else T = T->rchild;
    }
    return T;
}

java

BiTNode bstSearch(BiTNode T, int key) {
    while (T != null && key != T.data) {
        if (key < T.data) T = T.lchild;
        else T = T.rchild;
    }
    return T;
}

插入操作：

若树为空，创建新结点
若 key < 根，递归插入左子树
若 key > 根，递归插入右子树

删除操作（三种情况）：

被删结点是叶子结点：直接删除
被删结点只有一棵子树：用子树替代
被删结点有两棵子树：用其中序前驱（左子树最右结点）或中序后继（右子树最左结点）替代，然后删除替代结点

BST的查找效率：

最好情况（平衡BST）： $O(\log_2 n)$
最坏情况（退化为链表）： $O(n)$

⚠️ 2011年真题考点：判断序列是否可能构成BST中的一条查找路径。

关键规则：在BST查找路径上，一旦从某结点 $X$ 进入左子树，之后查找到的所有值都必须 < $X$ ；进入右子树后，所有值都必须 > $X$ 。

例：序列 95, 22, 91, 24, 94, 71 不可能是查找路径——因为从22到91是走右子树（后续值应 >91），但之后出现了24（<91），矛盾！

二、平衡二叉树（AVL树）

定义：任意结点的左右子树高度差（平衡因子）的绝对值不超过1。

$平衡因子 = 左子树高度 - 右子树高度 \in \{-1, 0, 1\}$

四种旋转调整：

失衡类型	旋转操作	说明
LL型	右旋	在左孩子的左子树上插入
RR型	左旋	在右孩子的右子树上插入
LR型	先左旋再右旋	在左孩子的右子树上插入
RL型	先右旋再左旋	在右孩子的左子树上插入

🗣️ 大白话：AVL树就是一棵"始终保持平衡"的BST。每次插入或删除后如果"歪了"（不平衡了），就通过旋转把它"扳正"。

AVL树的删除操作（2026王道新增重点）：

具体步骤：

删除结点（方法同BST删除）
一路向上找到最小不平衡子树，找不到则结束
找最小不平衡子树中**"个头"最高的儿子、孙子**
根据孙子位置执行 LL/RR/LR/RL 旋转调整
不平衡可能向上传导——调整后如果上层不平衡，继续步骤2

⚠️ 插入 vs 删除的关键区别：

插入只需一次调整（旋转）即可恢复平衡

删除可能需要多次调整（不平衡向上传导）——因为旋转可能导致子树变矮，从而使上层祖先也不平衡

AVL树的查找效率： $O(\log_2 n)$ （始终保持平衡）

含有 $n$ 个结点的AVL树的最大高度为 $O(\log_2 n)$ 。

高度为 $h$ 的AVL树的最少结点数 $C_h$ （2012年真题核心，所有非叶结点平衡因子均为1）：

$C_h = C_{h-1} + C_{h-2} + 1, \quad C_1 = 1, C_2 = 2$

$h$	1	2	3	4	5	6	7
$C_h$	1	2	4	7	12	20	33

💡 递推规律类似 Fibonacci 数列。高度为6、所有非叶结点平衡因子为1的AVL树，恰好有20个结点（2012年真题答案）。

三、红黑树（RBT）

红黑树的性质（口诀：左根右，根叶黑，不红红，黑路同）：

每个结点非红即黑
根结点是黑色（"根叶黑"）
叶结点（外部的NULL结点、失败结点）是黑色（"根叶黑"）
不存在两个相邻的红色结点（红结点的父、孩子必须是黑色）（"不红红"）
从任一结点到其任一叶结点的所有简单路径上，黑色结点数目相同（"黑路同"）

结点的黑高 $bh$ ：从某结点出发（不含该结点）到达任一空叶结点的路径上黑结点总数。

红黑树的重要性质：

性质1：从根到叶的最长路径不大于最短路径的 2倍
- 最短路径：全黑，长度 = $bh$
- 最长路径：黑红交替，长度 = $2 \times bh$
性质2：有 $n$ 个内部结点的红黑树，高度 $h \leq 2\log_2(n+1)$
查找效率 = $O(\log_2 n)$ ，与AVL同数量级

红黑树的插入操作：

新结点非根染红色（若染黑必然破坏"黑路同"，而染红只可能破坏"不红红"，更容易修复）
新结点是根则染黑色
调整策略：看叔叔（父的兄弟）的脸色——

情况	叔叔颜色	操作
黑叔/NULL (LL型)	叔叔是黑色/NULL	右旋 + 变色（P变黑，G变红）
黑叔/NULL (RR型)	叔叔是黑色/NULL	左旋 + 变色（P变黑，G变红）
黑叔/NULL (LR/RL)	叔叔是黑色/NULL	双旋（先转为LL/RR，再处理）
红叔	叔叔是红色	染色 + 变新（叔、父染黑，爷染红，爷变为新的当前结点继续调整）

💡 黑叔旋转口诀：LL右旋"父换爷"、RR左旋"父换爷"、LR双旋"儿换爷"、RL双旋"儿换爷"，换后染色。

⚠️ 秒杀模型：看到叔叔是红色 -> 变色继续往上看；看到叔叔是黑色 -> 旋转变色完工！

⚠️ 红黑树删除的核心考点：删除操作时间复杂度 = $O(\log_2 n)$ ，处理方式与BST删除相同，之后调整颜色。

红黑树的删除操作（⭐ 2022考纲正式收录后，删除调整已可命题）：

第一步：按BST规则定位并删除（与BST删除完全相同）

叶子结点 → 直接删除
仅有一个孩子 → 孩子替代
有两个孩子 → 用中序后继（右子树最小）替换关键字，转为删除后继结点

🗣️ 大白话：红黑树删除分两步——先像普通BST一样把结点拿掉，然后调整颜色和结构来修复被破坏的红黑性质。

第二步：根据被删结点与替代结点的颜色决定是否调整

被删/替代结点实际颜色	处理方式	原因
删红色叶子	✅ 直接删除，无需任何调整	不影响黑高，不破坏任何性质
删黑色，替代结点红色	✅ 将替代结点染黑即可	补偿该路径上丢失的一个黑结点
删黑色，替代结点黑色/NULL	❌ 产生"双重黑色"问题，需复杂调整	该路径黑高减1，违反性质5（黑路同）

"双重黑色"调整框架（看兄弟脸色，与插入"看叔叔脸色"对偶）：

设 $x$ 为替代结点（双重黑色）， $s$ 为 $x$ 的兄弟， $p$ 为父结点：

Case	兄弟 $s$ 颜色	兄弟孩子情况	操作	效果
1	红	—	$s$ 变黑、 $p$ 变红，朝 $x$ 方向旋转	转为 Case 2/3/4
2	黑	两个孩子均黑	$s$ 变红，双重黑上移到 $p$	若 $p$ 原为红 → $p$ 变黑完工；否则继续调整
3	黑	近侄红、远侄黑	近侄变黑、 $s$ 变红，朝 $s$ 方向旋转	转为 Case 4
4	黑	远侄红	$s$ 取 $p$ 色、 $p$ 变黑、远侄变黑，朝 $x$ 旋转	✅ 调整完成！

💡 删除记忆口诀："红兄先旋→黑兄看侄→远红一旋收工！"

Case 1 红兄：旋转降级为 Case 2~4

Case 2 黑兄双黑侄：染色上传（类似插入的"红叔变色上传"）

Case 3 近侄红：旋转调整为 Case 4

Case 4 远侄红：终结操作——一次旋转+染色即可解决

⚠️ 考试中红黑树删除的考法：

判断"删除某结点后红黑树是否仍满足全部5条性质"（选择题）

判断删除操作最多旋转几次（答：最多3次，远少于AVL可能的 $O(\log n)$ 次）

结合性质5（黑路同）判断"删除后某路径黑高是否变化"

不会要求写出完整代码，但需理解调整框架

红黑树 vs AVL树：

对比项	AVL树	红黑树
发明年份	1962	1972
平衡标准	严格（ $\\|BF\\| \leq 1$ ）	宽松（黑路同 + 不红红）
查找	$O(\log n)$ ，略优	$O(\log n)$
插入	$O(\log n)$ ，可能旋转	$O(\log n)$ ，旋转更少
删除	$O(\log n)$ ，可能多次旋转	$O(\log n)$ ，最多3次旋转
适用场景	以查为主，少插入删除	频繁插入、删除，实用性更强
实际应用	——	Java TreeMap、C++ map/set、Linux进程调度

7.4 B树和B+树

一、B树（多路平衡查找树）

$m$ 阶B树的定义：

每个结点最多有 $m$ 棵子树（最多 $m-1$ 个关键字）
根结点至少有2棵子树（至少1个关键字），除非是叶子
非根非叶结点至少有 $\lceil m/2 \rceil$ 棵子树（至少 $\lceil m/2 \rceil - 1$ 个关键字）
所有叶结点都出现在同一层
结点内关键字有序排列

🗣️ 大白话：B树就是一棵"矮胖"的查找树。普通二叉树每个结点只存一个值，B树每个结点可以存很多值，所以树的高度大大降低。高度低意味着查找时磁盘I/O次数少——这就是数据库索引用B树的原因。

🔗 【跨学科联动·OS/计组】 B 树和 B+ 树是 408 跨学科考点的"桥梁"：

OS·文件系统索引：Unix/Linux 的 inode 索引结构（直接索引→一级间接→二级间接→三级间接）本质思想与 B 树类似——通过多级索引减少磁盘 I/O

OS·磁盘调度：B 树节点大小通常设计为一个磁盘块/页面的大小（如 4KB），每次读一个结点恰好对应一次磁盘 I/O。因此 B 树高度 = 查找所需的磁盘 I/O 次数

计组·Cache 原理：B 树的设计理念与 Cache 类似——利用局部性原理，将频繁访问的数据（索引）集中存放以减少慢速存储的访问次数

实际应用：MySQL InnoDB 引擎使用 B+ 树做聚簇索引，叶结点链表支持高效范围查询

B树的插入：

找到应插入的叶子结点
如果关键字个数未满，直接插入
如果满了（达到 $m-1$ $m - 1$ 个），执行分裂：
- 取中间关键字上提到父结点
- 左右两半各形成一个新结点

B树的删除（分三种情况）：

情况1：直接删除 —— 被删关键字在终端结点中，且该结点关键字个数 $> \lceil m/2\rceil - 1$ ，直接删除。

情况2：兄弟够借 —— 被删关键字所在结点删后关键字不够（ $= \lceil m/2\rceil - 1$ ），但左/右兄弟结点关键字数 $\geq \lceil m/2\rceil$ 。处理方法：

父结点中对应关键字下移到被删结点
兄弟结点中最大（左兄弟）或最小（右兄弟）关键字上移到父结点

💡 2012年真题：3阶B树删除78，左兄弟有2个关键字 $\geq \lceil 3/2\rceil = 2$ ，属"兄弟够借"。左兄弟最大关键字上移到父结点，父结点对应关键字下移。

情况3：兄弟不够借 —— 左右兄弟关键字数都 $= \lceil m/2\rceil - 1$ 。处理方法：

将被删结点、父结点中对应关键字、兄弟结点三者合并为一个结点
合并后若父结点关键字不够，继续向上合并（合并可能向上传播直到根结点）

非终端结点中的删除：用该关键字的直接前驱（左子树中最右下的关键字）或直接后继（右子树中最左下的关键字）替换，转化为终端结点的删除。

补充：B树高度范围的推导（⭐常考计算）

$n$ 个关键字的 $m$ 阶B树，高度 $h$ 的范围：

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

下界推导（树最"胖"时高度最小）：

每个结点最多 $m-1$ 个关键字， $h$ 层最多 $(1 + m + m^2 + \cdots + m^{h-1}) \times (m-1) = m^h - 1$ 个关键字
故 $n \leq m^h - 1$ ，即 $h \geq \log_m(n+1)$

上界推导（树最"瘦"时高度最大）：

根结点至少 1 个关键字、2 棵子树
非根非叶结点至少 $\lceil m/2 \rceil$ 棵子树
第 $h+1$ 层为叶结点层（失败结点层），至少有 $2 \times \lceil m/2 \rceil^{h-1}$ 个结点
叶结点数 = $n+1$ （ $n$ 个关键字对应 $n+1$ 个查找失败区间）
故 $n+1 \geq 2 \times \lceil m/2 \rceil^{h-1}$ ，即 $h \leq \log_{\lceil m/2 \rceil}\frac{n+1}{2} + 1$

📝 例题：3阶B树存储20个关键字，高度范围？

下界： $h \geq \log_3 21 = \lceil 2.77 \rceil = 3$
上界： $h \leq \log_2 \frac{21}{2} + 1 = \lceil 3.39 \rceil + 1 = 5$
答： $3 \leq h \leq 5$

二、B+树

B+树与B树的区别：

特点	B树	B+树
关键字与子树数目	$n$ 个关键字， $n+1$ 棵子树	$n$ 个关键字， $n$ 棵子树
关键字分布	非叶结点和叶结点都包含数据	数据只在叶结点中
叶结点	不含信息	包含全部关键字且按顺序链接
查找过程	可能在任意结点停止	必须到叶结点才能找到数据
叶结点链表	无	叶结点通过指针链成有序链表

🗣️ B+树的优势：叶结点形成有序链表，支持高效的范围查询。这就是为什么MySQL的InnoDB引擎用B+树做索引。

7.5 散列表（Hash表）

一、基本概念

散列函数： $H(key)$ 把关键字映射到存储地址。

散列表：根据散列函数建立的查找表。

冲突：两个不同关键字映射到同一个地址： $H(key_1) = H(key_2)$ ， $key_1 \neq key_2$

同义词：发生冲突的两个关键字互称同义词。

二、散列函数的构造方法

散列函数的设计原则（4条）：

定义域必须包含全部可能的关键字，值域不超过散列表地址范围
散列函数计算出的地址应尽可能均匀地分布在整个地址空间
散列函数应尽量简单，在较短时间内计算出结果
尽量减少冲突（冲突不可能完全避免，但好的散列函数能使冲突尽量少）

方法	公式	特点
除留余数法	$H(key) = key \% p$ （ $p$ 取不大于表长的最大质数）	最常用； $p$ 取质数能减少冲突
直接定址法	$H(key) = a \times key + b$	不会冲突，但要求关键字分布基本连续，否则空间浪费
数字分析法	取关键字某些分布均匀的位	适合关键字位数多且事先知道分布
平方取中法	取 $key^2$ 的中间几位	适用范围广，不需要知道关键字分布

三、处理冲突的方法

1. 开放定址法

发生冲突时，在散列表中寻找下一个空闲地址。

$H_i = (H(key) + d_i) \% m$

$d_i$ 的取值方法	名称	探查序列
$d_i = 0, 1, 2, \ldots$	线性探测法	顺序往后找
$d_i = 0, 1^2, -1^2, 2^2, -2^2, \ldots$	平方探测法	左右跳着找
$d_i$ 由另一个散列函数决定	双散列法	用第二个函数决定步长
伪随机数	伪随机序列法	—

⚠️ 线性探测法会导致"聚集"（堆积/Clustering）：

初级聚集（Primary Clustering）：线性探测中，冲突的元素和非同义词都聚集在一起。例如地址2已满，关键字映射到地址2的和映射到地址3的都堆在一起，导致"滚雪球"效应。

二级聚集（Secondary Clustering）：平方探测法中，同义词的探测序列相同，仍会发生一定程度的聚集。

双散列法可以有效减少聚集现象。

⚠️ 开放定址法中的删除问题：

开放定址法中不能直接物理删除元素！因为删除后留下的空位会使后续查找误认为"查找失败"而提前终止。

解决方案：使用逻辑删除（设置删除标记），查找时遇到删除标记继续探测，插入时遇到删除标记可以覆盖。

缺点：多次删除后，表中会积累大量"已删除"标记，降低查找效率，需定期重建散列表。

2. 拉链法（链地址法）

将所有同义词存储在同一个链表中。散列表的每个位置是一个链表的头指针。

🗣️ 大白话：拉链法就像多个抽屉——算出来放第5个抽屉，但第5个抽屉已经有东西了？没关系，在这个抽屉里排成一排就行了。

🔗 【跨学科联动·OS/计组】 散列（Hash）思想在 408 其他学科中的体现：

OS·页表：虚拟地址到物理地址的映射本质是一种散列——通过页号直接计算页表项地址

OS·快表（TLB）：TLB 就是页表的"散列缓存"，利用相联存储器实现快速查找

计组·Cache 映射：直接映射 $\text{Cache行号} = \text{主存块号} \% \text{Cache总行数}$ 本质就是散列函数

计网·校验码：CRC 校验、MD5/SHA 等哈希函数用于数据完整性检验

四、散列查找的性能分析

装填因子： $\alpha = \frac{表中记录数}{散列表长度}$

$\alpha$ 越大，冲突越多，查找效率越低。

ASL 与装填因子 $\alpha$ 有关，与表中记录数 $n$ 无直接关系（这是散列表与其他查找表的重要区别）。

⚠️ 2011年真题考点：提高散列表查找效率的正确措施是——

✅ 设计冲突少的散列函数

✅ 处理冲突时避免产生聚集（堆积）

❌ 增大装填因子（ $\alpha$ 增大会增加冲突，降低效率！）

方法	$ASL_{成功}$	特点
线性探测法	约 $\frac{1}{2}(1 + \frac{1}{1-\alpha})$	$\alpha < 1$ 时有效
平方探测法	约 $-\frac{1}{\alpha}\ln(1-\alpha)$	性能优于线性探测
拉链法	约 $1 + \frac{\alpha}{2}$	性能最好， $\alpha$ 可大于1

📝 真题剖析

【2010年408真题】 将关键字序列 (7, 8, 30, 11, 18, 9, 14) 散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为 $H(key) = (key \times 3) \% 7$ ，处理冲突采用线性探测法，要求装填（载）因子为0.7。

（1）请画出散列表；（2）分别计算等概率情况下查找成功和不成功的的 ASL。

解：

表长 $m = n / \alpha = 7 / 0.7 = 10$ ，即散列表下标 0~9。

依次计算各关键字的散列地址并插入：

关键字key	H(key) = (key×3)%7	实际存储位置	比较次数
7	(21)%7 = 0	0	1
8	(24)%7 = 3	3	1
30	(90)%7 = 6	6	1
11	(33)%7 = 5	5	1
18	(54)%7 = 5 → 冲突，探测6→冲突，探测7	7	3
9	(27)%7 = 6 → 冲突，探测7→冲突，探测8	8	3
14	(42)%7 = 0 → 冲突，探测1	1	2

散列表：

下标	0	1	2	3	4	5	6	7	8	9
关键字	7	14		8		11	30	18	9

$ASL_{成功} = \frac{1+2+1+1+3+3+1}{7} = \frac{12}{7} \approx 1.71$

$ASL_{失败}$ ：计算每个散列地址（0~6）查找失败需要的比较次数（从该地址开始探测直到遇到空位置），然后取平均。

散列地址 $H$	探测序列	到空位置的比较次数
0	0(7) → 1(14) → 2(空)	3
1	1(14) → 2(空)	2
2	2(空)	1
3	3(8) → 4(空)	2
4	4(空)	1
5	5(11) → 6(30) → 7(18) → 8(9) → 9(空)	5
6	6(30) → 7(18) → 8(9) → 9(空)	4

$ASL_{失败} = \frac{3+2+1+2+1+5+4}{7} = \frac{18}{7} \approx 2.57$

⚠️ 注意： $ASL_{失败}$ 的分母是散列函数值域的大小（即 $p$ 的值 = 7，对应地址0~~6），而不是表长10。因为任何关键字通过 $H(key) = (key \times 3) \% 7$ 只会映射到 0~~6。

【2024年408应用题】 散列函数 $H(key) = (key \times 3) \% 11$ ，表长 $m=11$ ，采用平方探测法（二次探测法）处理冲突， $H_k = (H_0 + k^2) \% m$ （ $k=1,2,3,\ldots$ ），依次插入一组关键字并计算 ASL。

平方探测法要点：

探测序列： $H_0, H_0+1^2, H_0+2^2, H_0+3^2, \ldots$ （均对 $m$ 取余）
注意：标准平方探测是 $d_i = 0, 1, -1, 4, -4, 9, -9, \ldots$ （正负交替），但真题中可能只取正平方（需看题意）
表长 $m$ 必须是 $4k+3$ 形式的素数才能保证探测到所有位置

⚠️ 手动建表步骤：

算 $H_0 = H(key)$

若位置空，插入；若冲突，依次尝试 $(H_0 + 1) \% m$ , $(H_0 + 4) \% m$ , $(H_0 + 9) \% m, \ldots$

记录每个关键字的比较次数

$ASL_{成功}$ = 所有关键字比较次数之和 / 关键字个数

【2023年408真题】 对含 600 个元素的有序表进行折半查找，最多需要比较多少次？

$\text{最多比较次数} = \lfloor \log_2 n \rfloor + 1 = \lfloor \log_2 600 \rfloor + 1 = 9 + 1 = 10$

💡 公式记忆：折半查找判定树的高度 $h = \lfloor \log_2 n \rfloor + 1$ ，最多比较次数就等于树高。等价于 $\lceil \log_2(n+1) \rceil$ 。

【2025年408真题】 分块查找中， $n$ 个元素等分为若干块，使 ASL 最小的最优块大小？

$\text{最优块大小} = \sqrt{n}$

设共 $b$ 块，每块 $s$ 个元素，则 $b = n/s$
顺序查找索引 + 顺序查找块内： $ASL = \frac{b+1}{2} + \frac{s+1}{2} = \frac{n/s+1}{2} + \frac{s+1}{2}$
由均值不等式， $s = \sqrt{n}$ 时 $ASL$ 取最小值 $\approx \sqrt{n} + 1$

例： $n=400$ ，最优分 $\sqrt{400}=20$ 块，每块 20 个元素。

【B树高频考点汇总】（2023、2025年多次出题）：

考点	结论	年份
B树插入	插入只在叶结点（最底层非叶结点）进行	2023
B树插入可能增加高度	根结点分裂 → 高度+1	2023
B树删除	删除可能导致非叶结点变化（替换+合并）	2023
4阶B树7个关键字	可能的树形态不止一种（取决于插入顺序）	2025
$m$ 阶B树最少关键字	根: $1$ ; 非根非叶: $\lceil m/2 \rceil - 1$	常考
B树高度计算	$n$ 个关键字的 $m$ 阶B树高度 $h$ : $\log_m(n+1) \leq h \leq \log_{\lceil m/2 \rceil}\frac{n+1}{2} + 1$	常考

【散列表ASL计算中的"逻辑删除"陷阱】（2023年考点）：

散列表中执行逻辑删除后，被删位置标记为"已删除"，查找时仍需越过该位置继续探测。因此：

删除元素后， $ASL_{成功}$ （针对剩余元素）可能不变或不减
$ASL_{失败}$ 不受影响（因为失败查找必须到空位停止，已删标记不是空位）

📌 第七章总结

核心知识点	考研要求
ASL的概念及计算	高频考点
顺序查找	了解即可
折半查找及判定树	重中之重，选择题和大题都常考
分块查找	理解概念
二叉排序树（BST）的查找、插入、删除	必须掌握
平衡二叉树（AVL）的旋转调整	高频考点
红黑树的性质	近年新考点，需掌握
B树的定义、插入（分裂）	重点
B+树与B树的区别	高频选择题
散列表的构造（除留余数法）	必须掌握
线性探测法解决冲突	大题常考
拉链法	需要掌握
散列表的ASL计算	重中之重

第七章 查找