考频地图
| 考点 | 考频 | 常见问法 |
|---|---|---|
| 顺序、折半、分块 | ★★★★☆ | “折半查找判定树”“最多比较几次”“ASL” |
| 二叉排序树 | ★★★★☆ | “删除结点后的树”“查找路径是否可能” |
| 平衡二叉树 | ★★★★★ | “插入后进行了哪种旋转”“高度为 h 至少几个结点” |
| 红黑树 | ★★★☆☆ | “性质判断”“黑高” |
| B 树 / B+ 树 | ★★★★★ | “最少 / 最多关键字数”“插入后分裂”“B+ 树特点” |
| 散列表 | ★★★★★ | “ASL 成功 / 失败”“装填因子” |
顺序、折半与分块查找
| 方法 | ASL 成功 | ASL 失败 | 要求 |
|---|---|---|---|
| 顺序查找(无序) | (n + 1)/2 | n + 1(带哨兵) | 无,顺序 / 链式都可 |
| 顺序查找(有序表) | (n + 1)/2 | n/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。
二叉排序树
左子树所有结点 < 根 < 右子树所有结点,中序遍历得到递增序列。查找沿一条路径往下走,比较次数 ≤ 树高。
| 删除的结点 z | 做法 |
|---|---|
| 是叶子 | 直接删除 |
| 只有一棵子树 | 让子树替代 z 的位置 |
| 左右子树都有 | 用 z 的中序后继(右子树最左结点)或中序前驱替代 z,再删除那个后继(它最多只有一棵右子树,转化为前两种情况) |
BST 的形态取决于插入顺序:按有序序列插入会退化成单支树,ASL 变为 (n + 1)/2、查找 O(n)。这正是需要“平衡”的原因。判断“查找路径是否可能”:路径上的每个结点都要满足——在它之后出现的所有结点都落在它划定的范围内。
平衡二叉树 AVL
任一结点的左右子树高度差(平衡因子 = 左高 − 右高)只能是 −1、0、1。插入后若出现不平衡,找到离插入点最近的不平衡结点 A(最小不平衡子树的根),根据新结点插在 A 的哪个孩子的哪棵子树上,做四种旋转之一:
- 旋转的对象是最小不平衡子树,不一定是根。
- 插入只需在最小不平衡子树处调整一次;删除可能需要沿路径一直调整到根。
- 判断类型看的是“新结点相对于 A”的位置:在 A 左孩子的右子树上就是 LR,与新结点在那棵子树的左边还是右边无关。
红黑树
AVL 要求严格平衡,插入删除时旋转较多。红黑树放宽要求,只保证“大致平衡”,在频繁增删时总体更快(C++ map、Java TreeMap 用它)。
- 每个结点是红色或黑色;根是黑色。
- 叶结点(外部结点、NULL)都是黑色。
- 不存在两个相邻的红结点(红结点的孩子和父亲都是黑色)。
- 从任一结点到它的每个叶结点的路径上,黑结点数相同(称为该结点的黑高)。
| 对比 | AVL | 红黑树 |
|---|---|---|
| 平衡要求 | 严格(高度差 ≤ 1) | 宽松(最长 ≤ 2 倍最短) |
| 查找 | 略快(树更矮) | 略慢 |
| 插入删除 | 旋转可能较多 | 旋转次数少(插入最多 2 次,删除最多 3 次) |
B 树与 B+ 树
磁盘上的数据按块读写,一次读一个结点代价很高,所以希望树又矮又胖:每个结点放很多关键字。这就是 B 树(多路平衡查找树)。
一、m 阶 B 树的性质
| 结点 | 子树数 | 关键字数 |
|---|---|---|
| 根结点(非叶) | 2 ~ m | 1 ~ m − 1 |
| 其他非叶结点 | ⌈m/2⌉ ~ m | ⌈m/2⌉ − 1 ~ m − 1 |
| 所有叶结点 | — | 在同一层(失败结点在最下面一层) |
二、插入与删除
插入:先查找到最底层的非叶结点插入;若关键字数超过 m − 1,从中间第 ⌈m/2⌉ 个关键字处分裂,中间关键字上移到父结点(可能引起父结点继续分裂,直到根,树高 + 1)。
删除:删非底层结点的关键字时用前驱或后继替代,转化为删底层结点。删后关键字数 < ⌈m/2⌉ − 1 时:兄弟够借(多于下限)就“借”(通过父结点转一个过来);兄弟不够借就与兄弟及父结点中的分隔关键字合并(可能引起父结点合并,直到根,树高 − 1)。
三、B+ 树
| 对比 | m 阶 B 树 | m 阶 B+ 树 |
|---|---|---|
| n 个关键字的结点有几棵子树 | n + 1 | n |
| 关键字数范围(非根) | ⌈m/2⌉ − 1 ~ m − 1 | ⌈m/2⌉ ~ m |
| 关键字出现位置 | 每个只出现一次,可在任意层 | 叶结点包含全部关键字;非叶结点中的关键字在叶子中重复出现 |
| 查找 | 可能在非叶结点就结束 | 一定走到叶结点(每次查找路径长度相同) |
| 范围查询 | 需中序遍历 | 叶子链表顺序扫描,支持顺序查找 |
散列表
直接用散列函数 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),不一定是表长。
- “聚集”是线性探测的现象,链地址法不会产生聚集。
真题与自测
一、真题问法
问法 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 无关。
三、考前速览
折半:顺序存储 + 有序,最多比较 ⌈log₂(n+1)⌉ 次。
AVL 最少结点 N(h) = N(h−1) + N(h−2) + 1。
B 树非根结点关键字 ⌈m/2⌉−1 ~ m−1。
散列 ASL 只取决于 α。
① 旋转针对最小不平衡子树。
② B+ 树 n 个关键字 n 棵子树。
③ 开放定址法不能直接删除。