首页/数据结构/第 7 章 查找
408 计算机学科专业基础 数据结构 第 7 章

查找
折半、平衡树、B 树与散列

选择题 3–4 道,常有综合题(散列表、B 树插入)。必会:折半查找判定树、AVL 旋转、B 树关键字个数与分裂、散列表 ASL。

查找的核心矛盾:想查得快,就得让数据有序;想改得快,有序又难以维持。折半查找、平衡树、B 树、散列表,是在这对矛盾之间给出的四种不同答案。

7 个考点模块 4 个交互模拟器 2 张图
71814 7 14 8 11 30 H(key)
00
复习策略

考频地图

★★★★★ 高频 选择 + 综合
考点考频常见问法
顺序、折半、分块★★★★☆“折半查找判定树”“最多比较几次”“ASL”
二叉排序树★★★★☆“删除结点后的树”“查找路径是否可能”
平衡二叉树★★★★★“插入后进行了哪种旋转”“高度为 h 至少几个结点”
红黑树★★★☆☆“性质判断”“黑高”
B 树 / B+ 树★★★★★“最少 / 最多关键字数”“插入后分裂”“B+ 树特点”
散列表★★★★★“ASL 成功 / 失败”“装填因子”
一句话:查找效率用平均查找长度 ASL 衡量。折半查找 O(log n) 但要求顺序存储且有序;BST/AVL/红黑树/B 树是“动态”的有序结构;散列表的 ASL 只取决于装填因子 α 而与 n 无关。
01
7.1 · 必考

顺序、折半与分块查找

★★★★☆ 高频 选择 + 计算
方法ASL 成功ASL 失败要求
顺序查找(无序)(n + 1)/2n + 1(带哨兵)无,顺序 / 链式都可
顺序查找(有序表)(n + 1)/2n/2 + n/(n + 1)有序后可提前判定失败
折半查找≈ log₂(n + 1) − 1—顺序存储 + 有序
分块查找索引 ASL + 块内 ASL—块内无序、块间有序

折半查找与判定树

折半查找的过程可以画成一棵判定树:每个结点是一次比较,左子树是“比它小”时的后续比较。判定树是平衡的二叉排序树,n 个元素时树高 ⌈log₂(n + 1)⌉,这就是最多比较次数。

分块查找:n 个元素分成 b 块,每块 s 个,块间有序(索引表记每块最大值)、块内无序。索引和块内都用顺序查找时 ASL = (b + 1)/2 + (s + 1)/2,取 s = √n 时最小,为 √n + 1。例:n = 10000 时 s = 100,ASL = 101。

  • 折半查找只适用于顺序存储(链表无法随机定位 mid)。
  • mid = ⌊(low + high)/2⌋ 时判定树中左子树结点数 ≤ 右子树结点数(相差不超过 1);若题目用 ⌈ ⌉ 则相反——判断“可能的判定树”时看这一点。
  • 折半查找成功时比较次数不超过树高,失败时比较次数为 ⌈log₂(n + 1)⌉ 或少 1。
02
7.2 · 高频

二叉排序树

★★★★☆ 高频 选择题

左子树所有结点 < 根 < 右子树所有结点,中序遍历得到递增序列。查找沿一条路径往下走,比较次数 ≤ 树高。

删除的结点 z做法
是叶子直接删除
只有一棵子树让子树替代 z 的位置
左右子树都有用 z 的中序后继(右子树最左结点)或中序前驱替代 z,再删除那个后继(它最多只有一棵右子树,转化为前两种情况)

BST 的形态取决于插入顺序:按有序序列插入会退化成单支树,ASL 变为 (n + 1)/2、查找 O(n)。这正是需要“平衡”的原因。判断“查找路径是否可能”:路径上的每个结点都要满足——在它之后出现的所有结点都落在它划定的范围内。

03
7.3 · 必考

平衡二叉树 AVL

★★★★★ 必考 选择题

任一结点的左右子树高度差(平衡因子 = 左高 − 右高)只能是 −1、0、1。插入后若出现不平衡,找到离插入点最近的不平衡结点 A(最小不平衡子树的根),根据新结点插在 A 的哪个孩子的哪棵子树上,做四种旋转之一:

LL 型:右单旋转 ABC bf = 2 BCA B 上提为根,A 成为 B 的右孩子;B 原来的右子树改挂到 A 的左边 LR 型:先左旋再右旋 ABC CBA 新结点插在 A 的左孩子的右子树上:C 上提为根,B、A 分别成为左右孩子
图 7-1 LL(插在左孩子的左子树)右旋一次;RR 对称地左旋一次;LR(插在左孩子的右子树)先对 B 左旋再对 A 右旋;RL 对称。
高为 h 的 AVL 树最少结点数:N(h) = N(h − 1) + N(h − 2) + 1,N(0) = 0,N(1) = 1 N:1, 2, 4, 7, 12, 20, 33, …(h = 1, 2, 3, 4, 5, 6, 7) → n 个结点的 AVL 树高度 O(log n),查找、插入、删除都是 O(log n)
  • 旋转的对象是最小不平衡子树,不一定是根。
  • 插入只需在最小不平衡子树处调整一次;删除可能需要沿路径一直调整到根。
  • 判断类型看的是“新结点相对于 A”的位置:在 A 左孩子的右子树上就是 LR,与新结点在那棵子树的左边还是右边无关。
04
7.4 · 中频

红黑树

★★★☆☆ 中频 选择题

AVL 要求严格平衡,插入删除时旋转较多。红黑树放宽要求,只保证“大致平衡”,在频繁增删时总体更快(C++ map、Java TreeMap 用它)。

  1. 每个结点是红色或黑色;根是黑色。
  2. 叶结点(外部结点、NULL)都是黑色。
  3. 不存在两个相邻的红结点(红结点的孩子和父亲都是黑色)。
  4. 从任一结点到它的每个叶结点的路径上,黑结点数相同(称为该结点的黑高)。
推论:从根到叶子的最长路径 ≤ 2 × 最短路径(最短全黑,最长红黑相间) n 个内部结点的红黑树高度 h ≤ 2 log₂(n + 1) → 查找、插入、删除 O(log n) 新插入结点着红色(不破坏性质 4);若父结点也是红色:叔叔红 → 变色并上移;叔叔黑 → 旋转 + 变色
对比AVL红黑树
平衡要求严格(高度差 ≤ 1)宽松(最长 ≤ 2 倍最短)
查找略快(树更矮)略慢
插入删除旋转可能较多旋转次数少(插入最多 2 次,删除最多 3 次)
05
7.5 · 必考

B 树与 B+ 树

★★★★★ 必考 选择 + 综合

磁盘上的数据按块读写,一次读一个结点代价很高,所以希望树又矮又胖:每个结点放很多关键字。这就是 B 树(多路平衡查找树)。

一、m 阶 B 树的性质

结点子树数关键字数
根结点(非叶)2 ~ m1 ~ m − 1
其他非叶结点⌈m/2⌉ ~ m⌈m/2⌉ − 1 ~ m − 1
所有叶结点—在同一层(失败结点在最下面一层)
n 个关键字、高为 h(不含失败结点层)的 m 阶 B 树: log_m(n + 1) ≤ h ≤ log_⌈m/2⌉((n + 1)/2) + 1 例:高为 2 的 5 阶 B 树至少几个关键字?根至少 1 个(2 棵子树),每个子结点至少 ⌈5/2⌉ − 1 = 2 个 → 1 + 2×2 = 5

二、插入与删除

插入:先查找到最底层的非叶结点插入;若关键字数超过 m − 1,从中间第 ⌈m/2⌉ 个关键字处分裂,中间关键字上移到父结点(可能引起父结点继续分裂,直到根,树高 + 1)。
删除:删非底层结点的关键字时用前驱或后继替代,转化为删底层结点。删后关键字数 < ⌈m/2⌉ − 1 时:兄弟够借(多于下限)就“借”(通过父结点转一个过来);兄弟不够借就与兄弟及父结点中的分隔关键字合并(可能引起父结点合并,直到根,树高 − 1)。

三、B+ 树

B 树(3 阶) 3060 1020 4050 7080 每个关键字只出现一次,可以在任意层找到 B+ 树 4080 103040 507080 叶子链表 非叶结点只作索引(关键字是子树最大值), 所有关键字都在叶子上,叶子串成链表
图 7-2 B 树与 B+ 树。数据库索引普遍使用 B+ 树。
对比m 阶 B 树m 阶 B+ 树
n 个关键字的结点有几棵子树n + 1n
关键字数范围(非根)⌈m/2⌉ − 1 ~ m − 1⌈m/2⌉ ~ m
关键字出现位置每个只出现一次,可在任意层叶结点包含全部关键字;非叶结点中的关键字在叶子中重复出现
查找可能在非叶结点就结束一定走到叶结点(每次查找路径长度相同)
范围查询需中序遍历叶子链表顺序扫描,支持顺序查找
06
7.6 · 必考

散列表

★★★★★ 必考 选择 + 综合

直接用散列函数 H(key) 算出存储地址,理想情况下 O(1) 查找。两个问题:怎么设计散列函数,冲突(不同关键字算出同一地址)了怎么办。

散列函数做法说明
除留余数法H(key) = key % p最常用;p 取不大于表长的最大质数
直接定址法H(key) = a·key + b不会冲突,但关键字分布不连续时浪费空间
数字分析法 / 平方取中法取关键字中分布均匀的若干位—
冲突处理探测序列 dᵢ特点
线性探测0, 1, 2, 3, …容易产生“聚集”(堆积):同义词和非同义词争抢地址
平方探测0, 1², −1², 2², −2², …减少聚集;表长须为 4k + 3 形式的质数才能探测到所有单元
双散列i × H₂(key)—
链地址法(拉链法)同义词存在同一链表中不会聚集;可以真正删除;适合经常增删
  • 装填因子 α = 表中记录数 n / 表长 m。ASL 只取决于 α,α 越大冲突越多。
  • 开放定址法删除元素时不能直接清空(会截断探测链),只能做删除标记(逻辑删除)。
  • 算 ASL 失败时,分母是散列函数可能的取值个数(如 % 7 则为 7),不一定是表长。
  • “聚集”是线性探测的现象,链地址法不会产生聚集。
07
实战

真题与自测

★★★★★ 收口 选择 + 综合

一、真题问法

问法 1(2010 真题):“将关键字序列 (7, 8, 30, 11, 18, 9, 14) 散列到下标从 0 开始、装填因子为 0.7 的散列表中,H(key) = (key×3) MOD 7,线性探测。画出散列表,求等概率下查找成功和不成功的 ASL。”→ 表长 10;ASL 成功 12/7,不成功 18/7(散列表模拟器的默认数据就是这道题)。

问法 2:“高度为 2 的 5 阶 B 树中关键字个数至少是?”→ 5。

问法 3:“在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为 A,并已知 A 的左孩子的平衡因子为 0、右孩子的平衡因子为 1,则应作什么型调整?”→ A 的右孩子平衡因子为 1 说明新结点插在 A 的右孩子的左子树上:RL 型。

二、折叠自测

1. 有序表 n = 11,折半查找成功的 ASL?

判定树各层 1、2、4、4 个结点:(1 + 4 + 12 + 16)/11 = 3。

2. 高度为 6 的平衡二叉树最少有多少个结点?

20。

3. m 阶 B 树中非根非叶结点最少有几个关键字?

⌈m/2⌉ − 1。

4. B+ 树为什么适合做数据库索引?

非叶结点只存索引,一个结点能放更多关键字,树更矮、磁盘读取次数少;叶子链表支持高效的范围查询和顺序扫描。

5. 散列表的查找效率取决于什么?

散列函数、冲突处理方法和装填因子 α;在给定方法下,ASL 只是 α 的函数,与 n 无关。

三、考前速览

4 句话

折半:顺序存储 + 有序,最多比较 ⌈log₂(n+1)⌉ 次。
AVL 最少结点 N(h) = N(h−1) + N(h−2) + 1。
B 树非根结点关键字 ⌈m/2⌉−1 ~ m−1。
散列 ASL 只取决于 α。

3 个易错

① 旋转针对最小不平衡子树。
② B+ 树 n 个关键字 n 棵子树。
③ 开放定址法不能直接删除。