首页/考点精讲/数据结构 · 查找
考点精讲数据结构大纲 · 查找

查找
比较了几次?—— ASL 就是全章的度量衡

选择 3–4 道,应用题常考散列表构造与 ASL、折半查找判定树、AVL/红黑树插入、B 树插入删除。

全章按“数据怎么组织”分成三类:线性表上查(顺序、折半、分块)、树上查(BST → AVL / 红黑树 → B/B+ 树)、算地址直接查(散列)。比较它们,只看一个指标:平均查找长度 ASL。

11 个大纲条目 5 类 ASL 计算 2 处仅做理解
00
先看范围

大纲对照

★★★★★ 必考选择 + 应用
  1. 一查找的基本概念→ 01
  2. 二顺序查找法→ 01
  3. 三分块查找法→ 01
  4. 四折半查找法→ 01
  5. 五树形查找二叉搜索树、平衡二叉树、红黑树→ 02–04
  6. 六B 树及其基本操作、B+ 树的基本概念→ 05
  7. 七散列(Hash)表→ 06
  8. 八字符串模式匹配→ 07
  9. 九查找算法的分析及应用→ 各节 ASL + 08
本页标为“仅做理解”的内容

红黑树的删除调整 · 插值查找 / 斐波那契查找。

ASL = Σ(查找每个元素的概率 × 比较次数)。顺序 O(n),折半与平衡树 O(log n),散列理想 O(1)。散列表的 ASL 只取决于装填因子 α,与元素个数 n 无关。
01
大纲 一 ~ 四

基本概念、顺序、折半与分块查找

★★★★★选择 + 计算

一、基本概念

  • 静态查找只查不改(顺序、折半、分块);动态查找查找过程中还要插入删除(BST、AVL、B 树、散列)。
  • ASL 成功:等概率时 = 所有元素比较次数之和 / n。ASL 失败:= 所有“失败位置”比较次数之和 / 失败位置数。

二、顺序查找

无序表(带哨兵):ASL成功 = (n + 1)/2 ASL失败 = n + 1 有序表:查找失败可以提前停(遇到比 key 大的就停) ASL失败 = (1 + 2 + … + n + n)/(n + 1) = n/2 + n/(n + 1)

三、折半查找(二分)

只能用于有序的顺序表(要能随机访问中间元素,链表不行)。每次和中间元素比,一次排除一半。把所有可能的比较过程画出来就是一棵判定树——一棵平衡的二叉搜索树。
在 11 个有序元素中找 21:每比较一次,搜索范围(实线格子)缩小一半,3 次就找到了。灰色虚线格子是已经排除的部分。
猜数字游戏:“我想了一个 1~100 的数”,每次猜中间值,对方说“大了 / 小了”,最多 7 次一定猜中(⌈log₂101⌉ = 7)。查纸质字典时先翻到中间、再往前或往后翻,也是这个思路。
动手试一试:输入有序表和关键字,逐步看 low / mid / high
mid = ⌊(low + high) / 2⌋ 判定树:n 个圆形结点(成功),n + 1 个方形结点(失败) 高度 h = ⌈log2(n + 1)⌉ = 查找最多比较次数(成功和失败都不超过 h) 用 ⌊ ⌋ 取 mid 时,每个结点的右子树结点数 − 左子树结点数 = 0 或 1

11 个元素的有序表折半查找,求 ASL 成功与 ASL 失败。

判定树各层结点数:1、2、4、4。
ASL 成功 = (1×1 + 2×2 + 4×3 + 4×4) / 11 = 33 / 11 = 3。
失败结点共 12 个:第 3 层有 4 个空位(比较 3 次),第 4 层下有 8 个(比较 4 次)。ASL 失败 = (4×3 + 8×4) / 12 = 11/3。
上面 11 个元素的判定树(圆形 = 成功结点,下方小方块 = 12 个失败结点)。找 21 走的就是橙色路径 56 → 19 → 21,比较 3 次。
层数 1、2、3、4 的结点分别有 1、2、4、4 个,正好对应 ASL 成功 = 33 / 11 = 3 里的各项。
  • 失败时的比较次数 = 失败结点的父结点所在层数(方形结点本身不比较)。
  • “哪个不可能是折半查找的比较序列”:检查序列能否构成判定树上的一条路径——每一步之后的数必须都落在同一侧区间里。

四、分块查找(索引顺序查找)

像字典的“部首目录”:块内无序,块间有序(前一块的最大值 < 后一块的最小值)。先在索引表里找到在哪一块(可顺序也可折半),再到块里顺序找。
n 个元素分成 b 块,每块 s 个;索引和块内都顺序查找: ASL = (b + 1)/2 + (s + 1)/2 s = √n 时最小:ASL = √n + 1 例:n = 10000 → 每块 100 个,ASL = 101
找 38:在索引表里发现 22 < 38 ≤ 48 → 在第 2 块;再到第 2 块里从头顺序找,第 4 个就是 38。块内是乱序的,但第 2 块里每个数都比第 1 块大、比第 3 块小。

插值查找、斐波那契查找

折半查找的变种:插值查找按 key 的大小比例估计 mid,适合分布均匀的数据;斐波那契查找用斐波那契数分割区间。大纲未列。

02
大纲 五 · 1

二叉搜索树(BST)

★★★★☆选择 + 算法
左子树都比根小,右子树都比根大(每棵子树都满足)。查找就像“猜数字”:比根小往左,比根大往右。中序遍历得到递增序列——这是判断 BST 的核心依据。

插入与删除

  • 插入:查找失败的位置就是插入位置,新结点一定是叶子。
  • 删除三种情况:
    1. 叶子 → 直接删。
    2. 只有一棵子树 → 让子树顶替它的位置。
    3. 有两棵子树 → 用它的中序直接后继(右子树最小,即右子树最左下)或直接前驱顶替,再删掉那个后继/前驱(它最多一个孩子,转为情况 1 或 2)。
  • 删除一个结点再插回去,树不一定恢复原样(删的是叶子才会恢复)。
  • 同一组关键字插入顺序不同,BST 形态不同;有序插入会退化成单链表,查找 O(n)——所以需要平衡。

依次插入 45 24 53 45 12 24 90(重复的不插),求 ASL 成功。

得到:45 为根;24、53 为第 2 层;12、90 为第 3 层。ASL = (1 + 2×2 + 3×2) / 5 = 11/5。
删除有两个孩子的 30:找它的中序后继——右子树中最左下的 35(绿色),把 35 搬到 30 的位置,再删掉原来的 35(它是叶子,直接删)。中序序列仍然有序:20 35 40 50 60 70 80。
03
大纲 五 · 2

平衡二叉树(AVL)

★★★★★选择 + 应用
在 BST 上加一条规矩:每个结点的左右子树高度差(平衡因子)只能是 −1、0、1。插入后一旦有结点失衡,就在离插入点最近的失衡结点(最小不平衡子树的根)处“转一下”。
类型新结点插在失衡结点 A 的…调整
LL左孩子的左子树A 的左孩子 B 右旋上来当根
RR右孩子的右子树A 的右孩子 B 左旋上来当根
LR左孩子的右子树先左旋再右旋:让 A 的左孩子的右孩子 C 两次上升成为根
RL右孩子的左子树先右旋再左旋:C 两次上升成为根
上排:新插入的结点 C(橙色)让 A 的平衡因子变成 ±2;下排:调整后的样子。不管哪种,结果都是三个结点里大小居中的那个当根,较小的在左、较大的在右。(实际题目中 A、B、C 下面还会挂着子树,按 BST 大小关系重新接上即可。)
口诀:LL、RR 转一次,“中间那个”上去;LR、RL 转两次,“孙子”上去当根。调整后的子树高度恢复为插入前,所以不会影响更上面的祖先。

依次插入 16 3 7 11 9 26 18 14 15 构造 AVL 树,求最终根结点。

插 7:16→3→7 是 LR,7 上升为根 → 7(3, 16)。
插 11、9:9 插在 11 的左边,16 失衡(LL)→ 11 右旋上来 → 7(3, 11(9, 16))。
插 26:7 失衡(RR,26 在 7 的右孩子 11 的右子树)→ 11 左旋为根 → 11(7(3, 9), 16(26))。
插 18:16 失衡(RL)→ 18 上升 → 11(7(3,9), 18(16, 26))。
插 14、15:14 挂在 16 左;15 挂在 14 右 → 16 失衡(LR)→ 15 上升 → 18 的左子树变为 15(14, 16)。
最终根为 11。
每张图是一次旋转之后的样子:绿色是旋转后“上位”的新子树根,橙色是触发旋转的新结点。插 11、14 时没有失衡,图中省略。
动手试一试:改插入序列,逐个看 AVL 的旋转
高度为 h 的 AVL 树最少结点数:n(h) = n(h−1) + n(h−2) + 1 n(1)=1, n(2)=2, n(3)=4, n(4)=7, n(5)=12, n(6)=20 … → n 个结点的 AVL 树高度 O(log n),查找、插入、删除都是 O(log n)
  • 判断失衡类型看的是“新结点相对于失衡结点”的位置,而不是相对于它父亲。
  • AVL 删除后可能需要从下往上多次旋转(插入最多调整一次)。
  • 问“含 n 个结点的 AVL 树最大高度”:反查上面那串数。如 12 个结点最高为 5。
04
大纲 五 · 3

红黑树

★★★☆☆选择
AVL 太“较真”,插删时经常要转。红黑树放宽要求:不追求左右一样高,只保证最长路径不超过最短路径的两倍,换来更少的旋转。
五条性质(“左根右,根叶黑,不红红,黑路同”): ① 是一棵 BST(左 < 根 < 右) ② 每个结点非红即黑;根是黑的 ③ 叶结点(外部的 NULL 结点)都是黑的 ④ 不存在两个相邻的红结点(红结点的孩子和父亲都是黑的) ⑤ 任一结点到其所有叶结点的路径上,黑结点数相同(黑高 bh) 推论:n 个内部结点的红黑树高度 h ≤ 2·log2(n + 1) 根的黑高为 h 的红黑树至少有 2^h − 1 个内部结点

插入:新结点一律染红

  1. 按 BST 插入,新结点为红色(染红不会破坏“黑路同”)。若是根,染黑结束。
  2. 父亲是黑的 → 结束。
  3. 父亲是红的(出现红红),看叔叔:
    • 叔叔是黑的:按 LL/RR/LR/RL 旋转(同 AVL),然后旋转后的新根染黑、它的两个孩子染红。结束。
    • 叔叔是红的:父亲和叔叔染黑,爷爷染红,然后把爷爷当成新插入的结点继续向上检查。
依次插入 10、20、30、15(红色圆 = 红结点,深色圆 = 黑结点)。两种处理:叔叔黑 → 旋转(前两张),叔叔红 → 变色并向上(后两张)。最后每条从根到空指针的路径上都有 2 个黑结点。
对比AVL红黑树
平衡程度严格(高度差 ≤ 1)宽松(最长 ≤ 2 倍最短)
查找略快O(log n)
插入/删除旋转多少(插入最多 2 次旋转)
适合查多改少频繁插删(如 C++ map、Java TreeMap)

红黑树的删除

删除黑结点会破坏“黑路同”,需要按兄弟的颜色和兄弟孩子的颜色分 4 类情况处理(“双黑”调整)。教材标注为了解,大纲考查重在性质与插入。

05
大纲 六

B 树与 B+ 树

★★★★★选择 + 应用
数据在磁盘上时,每访问一个结点就是一次磁盘 I/O。所以要让树又矮又胖:一个结点放很多关键字、有很多孩子。m 阶 B 树就是“多路平衡查找树”,每个结点最多 m 个孩子。

一、m 阶 B 树的规定

每个结点:关键字数 ≤ m − 1,孩子数 ≤ m(孩子数 = 关键字数 + 1) 根结点: 若不是叶子,至少 2 个孩子(至少 1 个关键字) 其他非叶结点:至少 ⌈m/2⌉ 个孩子,即至少 ⌈m/2⌉ − 1 个关键字 所有叶结点(失败结点)在同一层 → 绝对平衡 n 个关键字的 B 树有 n + 1 个叶结点(失败结点) 高度 h(不含失败结点层): log_m(n + 1) ≤ h ≤ log_⌈m/2⌉((n + 1)/2) + 1

3 阶 B 树,高度为 3(不含叶子层),最少、最多有几个关键字?

最多:每结点 2 个关键字、3 个孩子 → 结点数 1 + 3 + 9 = 13 → 26 个。
最少:根 1 个关键字、2 个孩子;其余每结点 ⌈3/2⌉ − 1 = 1 个关键字、2 个孩子 → 结点 1 + 2 + 4 = 7 → 7 个。

二、插入:满了就“分裂”

  1. 插入位置一定在最底层的非叶结点(终端结点)。
  2. 插入后关键字数 ≤ m − 1 → 结束。
  3. 否则(达到 m 个)从中间位置 ⌈m/2⌉ 处分裂:左边留在原结点,右边成为新结点,中间关键字上升到父结点。父结点也满了就继续分裂;根分裂会让树长高 1 层。
3 阶 B 树(每个结点最多 2 个关键字)依次插入 10、20、30、40、50。结点一旦装了 m = 3 个关键字就从中间劈开,中间那个“升”到父结点;所有叶子始终在同一层。
动手试一试:任选阶数和插入序列,看分裂过程

三、删除:不够了就“借”或“合并”

  • 删的不在终端结点 → 用直接前驱或后继(一定在终端结点)替换,转为删终端结点。
  • 删后关键字数 ≥ ⌈m/2⌉ − 1 → 结束。
  • 不够了:兄弟够借(兄弟关键字数 > ⌈m/2⌉ − 1)→ 父结点中间的关键字下来,兄弟的一个关键字上去(“父下兄上”);兄弟不够借 → 与兄弟及父结点中间的那个关键字合并,父结点少一个关键字,可能继续向上合并;根被合并空了,树矮 1 层。

四、B+ 树(只要求基本概念)

对比B 树B+ 树
关键字与孩子n 个关键字 n + 1 棵子树n 个关键字 n 棵子树
数据(记录指针)放哪所有结点都可能放只在叶子;非叶结点只做索引
关键字是否重复出现不重复非叶结点中的关键字在叶子中都会再出现
查找可能在非叶结点就结束一定走到叶子(路径长度相同)
顺序查找不支持叶子用指针链起来,支持顺序 / 范围查找
一棵 B+ 树:根有 3 个关键字、3 个孩子(每个关键字是对应子树的最大值);所有关键字都在叶子里出现一次,叶子用指针(蓝色箭头)从左到右串起来。查“20~50 之间的所有记录”:先找到 20 所在的叶子,再顺着链表往右读即可。
数据库(如 MySQL)给“学号”建索引,底层就是 B+ 树:千万条记录,树高通常只有 3~4 层,查一个学号只需读 3~4 次磁盘;按学号范围查询时直接沿叶子链表扫描。
B+ 树非叶结点不存数据,一个磁盘块能放更多索引 → 树更矮 → I/O 更少。这就是数据库索引、文件系统偏爱 B+ 树的原因。
06
大纲 七

散列(Hash)表

★★★★★选择 + 应用
不比较,直接“算”出位置:地址 = H(key)。问题是两个不同的 key 可能算出同一个地址(冲突),所以要两样东西:一个好的散列函数 + 一个处理冲突的办法。

一、散列函数

  • 除留余数法(最常用):H(key) = key % p,p 取不大于表长 m 的最大质数。
  • 直接定址法 H(key) = a·key + b(不冲突,但可能浪费空间)、数字分析法、平方取中法。

二、处理冲突

方法做法注意
线性探测H, H+1, H+2, …(mod 表长)容易产生聚集(堆积),大大增加 ASL
平方探测H, H+1², H−1², H+2², H−2², …表长需为 4k + 3 的质数才能探遍;减少聚集
双散列H + i·H₂(key)第二个散列函数决定步长
拉链法同一地址的元素串成一条链表没有聚集;可直接删除;α 可以大于 1
  • 开放定址法中不能物理删除元素(会截断探测序列),只能做删除标记。
  • 散列表的 ASL 取决于装填因子 α = n / m,而不是 n;α 越大冲突越多。
  • “聚集”是因为线性探测让不同地址的同义词串在一起;它影响的是 ASL,不影响能否找到。

关键字 19 14 23 01 68 20 84 27 55 11 10 79,H(key) = key % 13,表长 16(地址 0–15),线性探测。求 ASL 成功与失败。

地址012345678910111213
关键字140168275519208479231110
比较次数121431139113
ASL 成功 = (1+2+1+4+3+1+1+3+9+1+1+3) / 12 = 30 / 12 = 2.5。
ASL 失败:H 只能算出 0–12 这 13 个起点。从地址 0 出发比较 1 次(遇到空);从 1 出发要比到 13 号空位,共 13 次;从 2 出发 12 次……从 12 出发 2 次。合计 1 + (13 + 12 + … + 2) = 91 → 91 / 13 = 7。
注意:失败的分母是散列函数可能的取值个数(这里是 13,不是表长 16);“与空位置比较算不算一次”按教材约定算一次,题目另有说明时从之。
线性探测(上题)
拉链法(同一组关键字)
79 的散列地址是 1,但 1~8 号位置被别人(包括地址不是 1 的 68、19、20……)一路占满,线性探测要比较 9 次——这就是聚集。拉链法中同义词各自挂在自己的链上,79 是链上第 4 个,比较 4 次。
拉链法 ASL 成功 = (6×1 + 4×2 + 1×3 + 1×4) / 12 = 21/12 = 1.75,比线性探测的 2.5 小。
快递驿站按手机尾号放包裹:尾号就是散列函数,同一个尾号的包裹放在同一格(拉链法);如果规定一格只能放一个,满了就往下一格放,就是线性探测——取件时可能要往后翻好几格。
动手试一试:换散列函数、表长和冲突处理方法,看 ASL 的变化
07
大纲 八

字符串模式匹配(KMP)

★★★☆☆选择
在主串 S 里找模式串 P。朴素算法失配后主串指针回退,最坏 O(mn)。KMP 的想法:失配时,已经比对成功的那一段里藏着信息——主串指针不回退,只让模式串跳到合适的位置继续比。跳到哪由 next 数组决定,最坏 O(m + n)。
求 next(位序从 1 开始,next[1] = 0): ① 对 P 的每个前缀求“最长相等前后缀长度”,得到部分匹配值 PM ② next[j] = PM[j − 1] + 1 (j ≥ 2) 例:P = a b a a b c 前缀 a ab aba abaa abaab abaabc PM 0 0 1 1 2 0 next 0 1 1 2 2 3 nextval 0 1 0 2 1 3
P = abaabc。比到第 6 位 c ≠ a 失配;前面已匹配的 “abaab” 最长相等前后缀是 “ab”(长 2),所以直接让 P 的第 3 位对准 S 的第 6 位继续比,主串指针不回退。接下来 a、a、b、c 全部匹配,在 S 的第 4 位找到 P。
动手试一试:输入模式串,看 next / nextval 与匹配过程
  • 含义:在 P 的第 j 位失配时,让 P 的第 next[j] 位对准主串当前字符继续比;next[j] = 0 表示主串指针后移一位、P 从头比。
  • nextval 优化:若 P[j] == P[next[j]],跳过去必然再次失配,于是 nextval[j] = nextval[next[j]];否则 nextval[j] = next[j]。
  • 有的教材下标从 0 开始,next 整体减 1(next[0] = −1)。做题先看题目给的约定。
  • 更详细的推导和练习见 DS 04 串。
08
大纲 九 · 分析及应用

自测与考前速览

★★★★★自测
方法要求平均时间适用
顺序查找无O(n)小表、链表
折半查找有序 + 顺序存储O(log n)静态有序表
分块查找块间有序O(√n)动态变化不大的表
AVL / 红黑树BSTO(log n)内存中的动态表
B / B+ 树多路平衡O(log n),I/O 少磁盘中的索引
散列表散列函数理想 O(1)按关键字精确查找;不支持范围查找
1. 折半查找 n = 1000 时,最多比较几次?

⌈log2(1001)⌉ = 10 次。

2. 为什么折半查找不能用在链表上?

需要随机访问中间元素,链表只能顺序访问。

3. 5 阶 B 树中,非根非叶结点的关键字个数范围?

⌈5/2⌉ − 1 = 2 到 4。

4. 高度为 5 的 AVL 树最少有多少个结点?

12。

5. 红黑树插入新结点为什么染红?

染红不改变任何路径上的黑结点数(不破坏“黑路同”),最多只会出现“红红”冲突,修正代价更小。

6. 散列表的 ASL 与什么有关?

装填因子 α、散列函数、冲突处理方法;与表中元素个数 n 本身无直接关系。

7. 开放定址法为什么不能直接删除元素?

直接删除会把探测序列截断,导致后面的同义词查不到;只能做逻辑删除标记。

五句话

折半判定树高 ⌈log2(n+1)⌉,失败看父结点层数。
BST 删双子树结点用中序前驱/后继顶替。
AVL:LL/RR 转一次,LR/RL 孙子上位。
B 树满 m 分裂、少于 ⌈m/2⌉−1 借或并。
散列 ASL 看 α,失败分母是 H 的取值数。

五个易错

① B+ 树 n 个关键字 n 棵子树。
② B 树叶结点 = 失败结点,n + 1 个。
③ 红黑树插入看叔叔:黑转、红变色上推。
④ 线性探测会聚集,拉链法不会。
⑤ KMP 的 next 下标约定先看清。