考研笔记

数据结构第 7 章：查找总览

本章是考研命题的重点（教材复习提示原话）。四块用户点名的重点——二叉排序树、红黑树、B 树 / B+树、散列表——全部在这一章。

大纲原文与教材的复习提示

【考纲内容】（一）查找的基本概念（二）顺序查找法（三）分块查找法（四）折半查找法（五）树形查找：二叉搜索树、平衡二叉树、红黑树（六）B 树及其基本操作、B+树的基本概念（七）散列（Hash）表（八）查找算法的分析及应用

教材【复习提示】给了逐项的深度要求，这是本章最省时间的一段话：

内容要求的深度
折半查找掌握过程、构造判定树、分析 ASL
二叉排序树、二叉平衡树、红黑树了解概念、性质和相关操作
B 树本章难点；考研大纲要求掌握插入、删除和查找的操作过程
B+树仅要求了解基本概念和性质
散列查找掌握构造、冲突处理方法（各种方法的处理过程）、成功与不成功的 ASL、特征和性能分析

照这张表分配时间：B 树和散列表要动手练，红黑树只要「了解」，B+树只背差异表。

页面导航

节页一句话
7.1查找的基本概念ASL 是全章唯一的尺子
7.2.1 + 7.2.3顺序查找与分块查找唯一不挑存储结构的方法；分块 = 顺序 + 一层索引
7.2.2折半查找判定树：把查找变成数结点
7.3.1二叉排序树后面三节的共同祖先
7.3.2平衡二叉树插入调一次，删除可能回溯到根
7.3.3红黑树按叔结点颜色分三种情况
7.4.1B 树及其基本操作分裂长高、合并变矮，都只在根
7.4.2B+树的基本概念子树 = 关键字，一切差异由此派生
7.5.1 + 7.5.2散列表的基本概念与散列函数不靠比较定位；
7.5.3处理冲突的方法开放定址 vs 拉链，堆积的归因；双散列遍历全表的互素条件
7.5.4散列查找及性能分析三个分母：、、
—📖 第 7 章名词库61 条名词 + 45 行范围限定清单

全章的三条线

① ASL 是唯一的尺子

方法在变，量法不变。每一节都要给出两个 ，而且两者的分母不同。

flowchart LR
    A["7.1 定义 ASL"] --> B["7.2 顺序 / 折半 / 分块"]
    A --> C["7.3 BST / AVL / 红黑树"]
    A --> D["7.4 B 树 / B+树"]
    A --> E["7.5 散列表"]
    B --> F["判定树上数结点"]
    C --> F
    D --> G["数磁盘存取次数<br/>= 层次数"]
    E --> H["数探测次数<br/>分母是值域 p"]

    classDef root fill:#ffcdd2,stroke:#b71c1c,stroke-width:3px
    classDef norm fill:#e3f2fd,stroke:#1565c0
    classDef end2 fill:#c8e6c9,stroke:#1b5e20
    class A root
    class B,C,D,E norm
    class F,G,H end2

② 「虚构 个失败结点」出现了三次

出处叫法数量
7.2.2 折半查找方形叶结点 / 失败结点
7.3.3 红黑树外部叶结点 / NULL 结点
7.4.1 B 树不带信息的叶结点 / 失败结点

三处的作用完全一样：把「查找失败」变成一个可以指到的位置，从而让「查找长度」这个量对失败也有定义。B 树的最大高度公式正是靠这一条把层数和关键字数接起来的。

③ 树形查找的谱系：都是 BST 加约束

flowchart TD
    BST["7.3.1 二叉排序树<br/>无约束，可退化成单支树"]
    BST -->|"加：高度差 ≤ 1"| AVL["7.3.2 平衡二叉树<br/>高度平衡"]
    BST -->|"加：五条红黑性质"| RB["7.3.3 红黑树<br/>适度平衡"]
    BST -->|"加：多路 + 同层叶结点"| B["7.4.1 B 树<br/>为磁盘而设"]
    B -->|"数据下沉到叶 + 叶间链表"| BP["7.4.2 B+树<br/>为数据库而设"]
    AVL -.->|"放宽约束<br/>降低调整频率"| RB

    classDef base fill:#ffcdd2,stroke:#b71c1c,stroke-width:3px
    classDef norm fill:#e3f2fd,stroke:#1565c0
    class BST base
    class AVL,RB,B,BP norm

四者的插入删除全都以 BST 的插入删除为第一步，再补一段调整。 记住这一句，7.3 和 7.4 的四套操作就只剩「调整那一段」需要单独记。

计算模板总表

结构成功不成功分母
一般顺序查找—
有序线性表顺序查找失败结点
折半查找判定树上数到父结点成功 ／失败
分块查找，最优 ——
BST（最坏）同判定树成功 ／失败
散列表比较次数探测到空位次数成功 ／失败
结构高度公式
折半判定树
AVL 最少结点；
红黑树；黑高 时结点数
B 树
散列表， 只依赖

高频边界（按易错程度排序）

第一组 · 分母（本章最高频失分点）

  • 成功除 ，失败不除 ——判定树类除 ，散列表除值域大小 。
  • 装填因子 ，分母是表长，第三个分母。
  • 散列表一道题里 、、 同时出现。

第二组 · 查找长度怎么数

  • 数结点不数边，根为 1。
  • 判定树上成功数到自己，失败数到父亲。
  • 散列表空位本身算一次比较。

第三组 · 存储结构与有序性

  • 顺序查找：两者都不要求；有序线性表的顺序查找可以是链式。
  • 折半查找：有序 + 随机存取，两个条件独立且都必需。
  • 分块查找：块间有序、块内无序，第二步不能折半。

第四组 · 插入与删除的不对称

  • AVL：插入最多调一次，删除可能一路回溯到根。
  • 红黑树：插入破坏性质 ④，删除破坏性质 ⑤。
  • B 树：分裂只让树长高，合并只让树变矮，都只发生在根。
  • BST：删除后再插入同一关键字，树一般会变。

第五组 · 定义里的一个词

  • BST：左子树「所有结点」小于根，不只是左孩子。
  • 平衡因子：左减右。
  • 黑高：「不含该结点」。
  • 阶： 是子树数。
  • B+树：子树数等于关键字数。
  • 同义词： 相等，与存放位置无关。

第六组 · 教材与真题的口径分歧

  • B 树的「叶结点」：教材 = 失败结点；408 真题 = 最底层的终端结点（教材脚注明说）。
  • B+树分支结点存最大值（王道口径），工程实现常存最小值。
  • 红黑树的删除教材标 * 且注明「考查概率较低」。

复习顺序

  1. 7.1 — 把 ASL 的定义和「查找长度数结点」钉死。这一步不牢，后面全错。
  2. 7.2.2 — 判定树。学会圆形/方形两套数法，本章后面反复用。
  3. 7.2.1 + 7.2.3 — 顺序与分块，重点是三个方法的条件对照。
  4. 7.3.1 — BST 的定义、三种删除、与折半的四点对比。
  5. 7.3.2 — 手上练四种旋转，练到不用想。
  6. 7.3.3 — 五条性质 + 插入三种情况。删除先跳过，教材自己标了 *。
  7. 7.4.1 — 本章难点，必须动手画：插入分裂、删除的借与并各画三遍。
  8. 7.4.2 — 只背五点差异表。
  9. 7.5.1 + 7.5.2 — 四种散列函数，重点分清 与 。
  10. 7.5.3 — 四种探测 + 拉链，动手填两张表。
  11. 7.5.4 — 两个 ASL，重点是分母。
  12. 名词库 — 考前扫 45 行范围限定清单。

只有 5 小时的话：7.1 的 ASL 定义 → 7.2.2 判定树 → 7.4.1 B 树手算 → 7.5.3 + 7.5.4 散列表填表算 ASL → 名词库清单。这五块占本章分值的绝大部分。

链接

反向链接