# 第六章 查找 · 速览 > Arietids Learn · 个人课程复习笔记 > 在线阅读：https://learn.arietids.net/courses/data-structures/chapter-06-quick/ ## 查找基本概念与静态查找 ### 概念 - 静态查找表：数据相对稳定、鲜有变化；最便利存储为顺序存储。动态查找表：频繁插入删除，一般用链式存储。 - 静态查找细分：顺序、折半、插值、分块。 ### 顺序查找 - 哨兵法：把待查值 x 存入 0 号哨兵位，从 n 下标向前扫到 0；返回下标 m>0 成功、m=0 失败。好处：省去每步越界判断，以一个空间换时间。 - 性能：失败比较 $n+1$ 次；等概率成功平均 $(n+1)/2$ 次；时间复杂度 $O(n)$（无序表亦适用）。 ### 折半（二分）查找 - 前提：顺序存储且有序。每次比中间元素，小走前半、大走后半，区间空则失败。 - 代码约定：下标从 1 起，low=1、high=size，成功返回 mid、失败返回 0。 - 性能：成功最少 1 次，最坏成功/失败比较次数均为 $\log_2 n$ 量级（具体次数需取整，最坏成功比较常写作 $\lfloor\log_2 n\rfloor+1$）；时间复杂度 $O(\log_2 n)$。 ### 插值查找 - 思想：按值与端点距离估算位置 $mid = low + (high-low)\cdot\dfrac{x-a[low]}{a[high]-a[low]}$。 - 条件：数据有序且分布均匀；理想时间复杂度 $O(1)$。分母 $a[high]=a[low]$ 时无法计算需中止。 - 注意：位置计算很复杂、一次计算比多次数据访问更耗时时，该方法不占优势。 ### 分块查找 - 定义：大表分若干块，块内可无序、块间必须有序；建索引表存各块最大关键字（升序）。 - 查找：先在索引表（折半或顺序）定位块，再块内顺序查找。适合数据量大、动态变化（增删只需调整所在块）。 - 性能：慢于折半，但远快于顺序查找。 ## 二叉查找树（BST） ### 定义 - 对每个结点：其左子树上**所有**结点都比它小、右子树上**所有**结点都比它大（假设无相等元素）。 - 易错：仅"左孩子小、右孩子大"不够，须整棵子树与祖先满足大小关系。 ### 查找 - 小往左、大往右、相等命中、到空失败（递归/非递归均可）。 - 性能：比较次数最多为树高，故复杂度＝树高；不平衡时退化为单链表 $O(N)$，故非对数级别。等概率形态假设下平均约 $1.38\log n$。 ### 插入 - 小于根入左子树、大于根入右子树、相等则不插入重复键，递归到空位新建结点；递归函数形参为指针的非常量引用 `BinaryNode*&`（引用不能省，用于关联父子）。 - 性能：本质是查找，复杂度＝树高。 ### 删除（保持仍为 BST） - 情况1（叶子）：直接删，父子链置空。 - 情况2（唯一孩子）：用该孩子顶替。 - 情况3（两个孩子）：取替身——左子树最大结点（左孩一路向右）或右子树最小结点（右孩一路向左），用替身值替换待删值，再转为删除替身（替身最多一个孩子，归约为情况1/2）。 - 性能：叶/单孩子删除＝树高量级；双孩子需找替身再下删，最多树高两倍。 ### 问题引出 - BST 三种操作复杂度均为树高；退化为单支树时高＝结点数，三操作皆 $O(n)$，故需平衡操作。 ## 平衡二叉树（AVL） ### 定义 - 平衡因子 BF＝左子树高−右子树高；AVL 要求每结点 $BF\in\{-1,0,1\}$，目标是限制树高、查找接近 $O(\log n)$。 - 平衡 ≠ 最矮，但已接近最矮。结点比普通 BST 多一个 height 字段。 - 查找：与 BST 完全相同（小左、大右、相等命中）。 ### 插入失衡与旋转 - 新结点 BF=0，自下而上传导：来自左子树父 BF+1、来自右子树父 BF−1。父 BF 变 0 则子树高不变、传导停止；变非 0 继续向上，直到出现 ±2、变 0 或到根。 - 冲突结点：向上传导中第一个 BF 超出 $\{-1,0,1\}$ 的结点；在其附近调整至平衡。 - 四种失衡类型（按冲突结点→子→孙方向判定）： | 类型 | 插入方向 | 处理 | |---|---|---| | LL | 左孩子的左子树 | 右单旋（口诀：右旋插到右子之左） | | RR | 右孩子的右子树 | 左单旋（左旋插入左子之右） | | LR | 左孩子的右子树 | 先对左孩 RR 左旋，再对冲突结点 LL 右旋 | | RL | 右孩子的左子树 | 先对右孩 LL 右旋，再对冲突结点 RR 左旋 | - 单旋：LL 取左孩为新根、原根挂为右孩、左孩原右子树改挂原根左侧；RR 对称。旋转后冲突结点与新根 BF 均归 0。LR/RL 双旋后位于顶部的是"孙子结点"。 - 旋转代码要点：先更新原根 height，再用更新后的原根 height 算新根 height。 - 插入总结：递归插入子树，若子树高未变即完成；否则按 X 与各键值选单/双旋（以原结点为根），旋转后高度＝插入前，操作结束（插入最多调整一处）。 ### 删除 - 先按 BST 删除，再沿到根路径向上回溯调整；删除不"幸运"——子树调整后高度不保证不变，可能连串调整。递归删除函数返回布尔值：true＝子树高不变停止，false＝继续向上。 - 删除发生在 P 左子树（左矮一层）的五种情况： | 情况 | P 原 BF | 处理 | 是否继续向上 | |---|---|---|---| | 1 | 0 | 不调整（BF 变 −1） | 高度不变，停 | | 2 | +1 | 不调整（BF 变 0） | 高度变矮，继续 | | 3 | −1→−2，右孩左子树矮 | RR 旋转 | 高度变矮，继续 | | 4 | −1→−2，右孩右子树矮 | RL 旋转 | 高度变矮，继续 | | 5 | −1→−2，右孩左右等高 | RR 或 RL（RR 简单） | 高度不变，停 | - 易错：旋转修复局部失衡后子树仍可能变矮，必须继续向上检查直到某结点高度不变或到根。 - adjust(t, subTree)：subTree=1 删在右子树、0 删在左子树；返回 true 高度不变可停、false 继续。 - 局限：平衡要求高（高度差≤1），插入删除易打破、引发调整，删除调整可能连串。 ## 外部查找与 B 树 ### 外部查找背景 - 数据量大、存外存无法全入内存；建索引文件（关键字+数据地址，按关键字序存）加速。外存以文件为单位、以数据块为单位与内存交换，整块读入缓冲区。 - 设计外存算法重点：减少磁盘访问次数。磁带顺序存取；磁盘顺序＋随机存取（术语：磁道/扇区/柱面）。外部查找索引结构：B 树、B+ 树。 ### B 树定义（m 阶） - 增加分叉降低树高（M 叉查找树最佳高度 $\log_M N$），把磁盘访问降到小常数。B 树是平衡的 M 叉查找树。 - m 阶 B 树为空或满足：①根或是叶、或至少 2 个至多 m 个儿子；②除根与叶外每结点儿子数 $\lceil m/2\rceil\le s\le m$；③有 s 个儿子的非叶结点含 $n=s-1$ 个关键字（子树数＝关键字数+1），结点形如 $(n,A_0,(K_1,R_1),A_1,\ldots,(K_n,R_n),A_n)$；④所有叶子在同一层、不带信息（空、指针为空）。 - 关键字 $K_1<\cdots - 查找：从根逐层下行，结点内按关键字区间选子树指针；每下一层即一次磁盘 IO，必须到达对应位置或落到空叶 F 才判成败。 ### 插入 - 总在最底层非叶结点；查找定位后按序插入。结点关键字数 ≤ m−1 即结束；已等于 m−1（插入后超员）须分裂。 - 分裂：超员结点一分为二（前半、后半），居中关键字上移到父结点（父增一关键字一子树）；父若超员递归分裂、沿路径向上传播。复杂度约 2×树高。 - 易错：5 阶 B 树每结点最多 m−1=4 个关键字，插第 5 个才分裂；上移的是排序后居中的关键字；目标结点未满则不分裂。 ### 删除 - 删内部关键字：用替身（右子树最左＝后继，或左子树最右＝前驱）覆盖，转为删最底层替身。 - 删最底层后：仍满足下限即结束；低于下限按**先借后合并**——左/右兄弟有富余则经父结点中转借（父分隔关键字下移、兄弟端点关键字上移）；左右兄弟都为下限则合并（父分隔关键字下移并入合并结点，父关键字数减一）。 - 合并致父减一，失衡可逐层向上传播；传到根且根被掏空则整树高度减一（最坏）。 ### M 的选择 - 一个磁盘块作一结点（块容量 max 字节、每键 key 字节）：$(M-1)\times key$ + M 个分支地址 + $(M-1)$ 个记录地址 $< max$，由此定 M。 ## B+ 树 ### 定义 - 动机：B 树可随机查找但按序遍历全部记录是灾难；B+ 树兼顾随机查找与顺序访问（索引顺序文件）。 - M 阶 B+ 树性质：①数据记录只存于叶子，非叶结点至多 $M-1$ 个键引导查找（键 i＝子树 i+1 的最小值）；②根或是叶、或有 2~M 个儿子；③除根外非叶结点儿子数 $\lceil M/2\rceil$~$M$（防退化）；④所有叶在同一层、每叶有 $\lceil L/2\rceil$~$L$ 个数据项；⑤所有叶连成单链表。 - 查找：从根按区间下行至叶子；必须到达叶子才能判成败（数据地址只在叶子）。 ### L 与 M 的选择 - 块 8192 字节、键 32 字节、分支 4 字节：非叶结点需 $36M-32\le 8192$，得 $M=228$。每记录 256 字节则一块存 $8192/256=32$ 条，$L=32$，每叶 16~32 条。通常 $L$ 远小于 $M$。 ### 插入与删除 - 插入：定位叶子。叶不满直接插；叶满则分裂为两个半满叶并更新父；父满则继续分裂，最坏分裂到根（故根允许仅两孩子）。 - 删除：叶元素降至最小值以下时——邻居有富余则领养（借），邻居也最少则合并（父失一子），向上过滤到根；根只剩一子则删根、其子为新根（唯一使 B+ 树变矮的情况）。 ### 性能与比较 - $N$ 记录最坏 $2N/L$ 个叶、深度 $\log_{\lceil M/2\rceil}(2N/L)$；一般 3~4 层即够。查找至多约 5 次读磁盘，插删多一次写，分裂/归并至多再加 4 次写（罕见、可均摊忽略）。 - B 树 vs B+ 树：B 树关键字与地址可分布在任何结点，查找可停于任一层、时间 ≤ 树高；B+ 树全部在叶子，查找必到叶、时间一定＝树高。两者插删最差均为树高的 2 倍。 - B+ 便于按序遍历：头指针指首叶，各叶尾指针链向右邻叶成单链表，顺链即可顺序遍历。 ## 哈希查找 ### 基本概念 - 散列法：不按大小比较，直接由关键字 KEY 经函数算出存储位置；理想/平均情况下查找可达 $O(1)$，最坏情况会受冲突和装填因子影响而退化；不支持有序操作。 - 直接以关键字作下标在大值域/字符串关键字时不可行：需用散列函数把大数映射为小下标，把字符串解释为整数。 ### 哈希函数 - 哈希函数 $H$ 以关键字算存储位置，值域 $0\sim m-1$（m 为表规模）；选择标准：计算快、地址均匀（冲突少）。 - 五种常用哈希函数： | 方法 | 形式/做法 | 要点 | |---|---|---| | 直接地址法 | $H(key)=key$ 或 $a\cdot key+b$ | 线性变换压缩表空间 | | 除留余数法 | $H(key)=key\bmod p$（+c） | p 为 ≤m 的素数；最常用，避免浪费单元 | | 数字分析法 | 取数字分布均匀的位组成地址 | 丢弃各关键字恒同的位 | | 平方取中法 | 关键字平方取中间各位 | 适合各位均匀但值域大；中间位与每位相关 | | 折叠法 | 按定长分组相加、舍进位 | 适合关键字很长 | - 除留余数法选素数 p 的理由：若 key 全奇、p 偶则结果全奇浪费一半；若 key 全为 5 的倍数、p=95 则只占 1/5 单元。 ### 冲突与解决 - 冲突（碰撞）：哈希函数一般多对一，两个以上关键字映射到同一单元即冲突。 - 闭散列表：用表内空余单元，含线性探测、二次探测、再次散列。开散列表：冲突结点链到表外线性表（链地址法）。 #### 闭散列（线性探测） - 线性探测：冲突时探测下一单元直到空。迟删除：删除只做标记不真清空（否则清空单元会中断后续探测链使元素查不到）。 - 状态：0 空 empty、1 活动 active、2 已删 deleted。insert 找 state≠1 的单元（空或迟删都可重用）；remove 沿链遇 state=0 即止，找到只置 2；find 遇 0 返回 NULL，state=2 单元跳过不中断链。 #### 二次探测 - 地址序列为 $(k+1^2)\bmod m, (k+2^2)\bmod m, (k+3^2)\bmod m,\ldots$（m 为表长）。定理：表长为素数且至少一半为空时新元素总能插入、且不会探测同一单元两次；可不用昂贵乘除实现。 #### 再次散列（双散列） - 用两个散列函数：hash1 算起始地址、hash2 算步长；第 i 次冲突增量 $f(i)=i\times hash2(x)$。建议 $hash2(x)=R-(x\bmod R)$（R 为小于表长的素数）。探测序列 $hash1(x), (hash1+hash2)\bmod M, (hash1+2hash2)\bmod M,\ldots$。 #### 开散列（链地址法） - 同一散列地址的元素链成一条单链表（同义链）；数组每元素是指向对应链首的指针，采用不带头结点单链表。 - insert 头插法（$O(1)$）；析构须释放数组及各链全部结点；remove 因不带头结点需对首结点特殊处理；find 沿对应链顺序比较。 #### 易错（闭散列线性探测计数） - 探测到表尾须回绕到 0；比较次数含初始地址那一次在内的每次位置检查。 ## 本章小结 - 静态查找（少增删，顺序存储）：无序用顺序查找 $O(n)$，有序用折半查找 $O(\log_2 n)$。 - 动态查找（频繁增删）：用 BST，平衡时 $O(\log_2 n)$；AVL 通过平衡约束控制树高。 - 外存：B 树/B+ 树为大文件建索引。B 树关键字分布在非叶结点、每关键字仅出现一次、叶为空；B+ 树所有关键字及地址都在叶子、规模更小且支持按序遍历，建索引更常用。 - 哈希：摆脱关键字比较，靠函数直接映射地址；理想一对一难找，通常有冲突，常用解决法为线性探测、二次探测、链地址法。