考研笔记

数据结构 第 7 章 名词库

这一页是复习主入口。 目标是把第 7 章的名词收全，并把每个词的边界和适用范围钉死。

每条最多四行：是（定义）／不是（划掉最常见的误解）／易混（成对的对手）／范围（该结论在什么条件下才成立）。

建设进度：✅ 7.1 查找的基本概念　✅ 7.2 顺序查找和折半查找　✅ 7.3 树形查找　✅ 7.4 B 树和 B+树　✅ 7.5 散列表　（全章完整）

7.1 查找的基本概念

查找

  • 是：在数据集合中寻找满足某种条件的数据元素的过程。
  • 范围：结果只有两种——查找成功、查找失败，两者的代价要分开度量。

查找表

  • 是：用于查找的数据集合，由同一类型的数据元素（或记录）组成。
  • 不是：不是一种存储结构。顺序表、链表、树、散列表都能充当查找表。

静态查找表 / 动态查找表

  • 是：只涉及查找、无须动态修改的是静态查找表；需要动态插入或删除的是动态查找表。
  • 易混：静态适合顺序查找、折半查找、散列查找；动态适合二叉排序树的查找、散列查找。
  • 范围：散列查找是唯一同时出现在两栏的方法。

关键字

  • 是：数据元素中唯一标识该元素的某个数据项的值。
  • 不是：不是「任意一个数据项」；可重复的是次关键字，基于它的查找结果不唯一。

平均查找长度（ASL）

  • 是：， 为查找第 个元素的概率， 为比较次数。
  • 不是： 不一定是 ——「一般认为」等概率，题目给了别的就按题目。
  • 范围：教材称它是衡量查找算法效率的最主要的指标。

查找长度

  • 是：一次查找中需要比较的关键字次数。
  • 不是：不是边数，不是层数减一。树上等于「根到目的结点路径上的结点数」，根为 1。

7.2.1 顺序查找

顺序查找

  • 是：从表的一端开始逐个比较关键字的查找方法，也称线性查找。
  • 范围：本章唯一对存储结构和有序性都不提要求的方法；顺序存储或链式存储皆可。

哨兵

  • 是：放在 ST.elem[0] 的待查值，使循环不必判断数组越界。
  • 不是：不减少比较次数，减少的是边界判断。
  • 范围：算法从后往前扫，返回 0 即查找失败。

有序线性表的顺序查找

  • 是：利用有序性，扫到「当前元素已不小于待查值」即可判失败。
  • 不是：不改善查找成功的 ASL，成功 仍是 。
  • 易混：↔ 折半查找。前者的线性表可以是链式存储，后者只能是顺序存储。

失败结点

  • 是：判定树中虚构的方形叶结点，代表一个查找失败的区间。
  • 范围： 个圆形结点对应 个失败结点；到达失败结点的查找长度等于其父结点所在层数。

7.2.2 折半查找

折半查找

  • 是：也称二分查找，仅适用于有序的顺序表。
  • 范围：两个条件独立且都必需——有序 + 随机存取。

判定树

  • 是：描述折半查找过程的二叉树，圆形结点为记录，方形叶结点为失败区间。
  • 不是：不是完全二叉树；教材的说法是平衡二叉树。
  • 易混：↔ 二叉排序树。判定树在取整规则确定后唯一；BST 的形态取决于插入顺序。
  • 范围：树高 ；。

取整方式

  • 是： 可向下取整也可向上取整，但每次查找的取整方式必须相同。
  • 范围：取整方式不同 → 判定树不同 → 不同。题目不说明时默认向下取整。

7.2.3 分块查找

分块查找

  • 是：也称索引顺序查找，块内无序、块间有序，配一张索引表。
  • 不是：块内不要求有序，因此第二步不能折半。
  • 范围：；均分且两段都顺序查找时为 ， 时最小值 。

索引表

  • 是：每个元素含各块的最大关键字和各块中第一个元素的地址，按关键字有序。
  • 不是：存的不是各块的第一个关键字。
  • 范围：索引表可用顺序或折半查找；折半未命中时应取 low 所指的块。

7.3.1 二叉排序树

二叉排序树（BST）

  • 是：空树，或左子树所有结点 < 根 < 右子树所有结点，且左右子树也是 BST。
  • 不是：只保证「左孩子 < 根 < 右孩子」的树不是 BST。
  • 范围：目的是提高查找、插入和删除的速度，不是排序。

中序遍历有序

  • 是：对 BST 中序遍历可得递增有序序列，且这是充要判据。
  • 不是：不能由中序序列唯一确定一棵 BST——所有 BST 的中序序列都是那一列排好序的数。

BST 的插入

  • 是：新结点一定是叶结点，且是查找失败路径上最后一个结点的孩子。
  • 不是：关键字重复时插入失败返回 0，不是插到某一侧。
  • 范围：算法签名是 BST_Insert(BiTree &T, KeyType k)，& 是引用。

BST 的删除（三种情况）

  • 是：① 叶结点直接删；② 只有一棵子树则子树顶替；③ 两棵子树则用直接后继或直接前驱顶替，转化为 ① 或 ②。
  • 范围：后继是右子树中最小的结点，必然无左孩子，所以一定能化归。
  • 易混：删除后再插入同一关键字，得到的树一般与原来不同（2013 思考题）。

单支树

  • 是：输入序列有序时 BST 退化成的形态，树高为 。
  • 范围：此时 ，与顺序查找相同。

7.3.2 平衡二叉树

平衡二叉树（AVL 树）

  • 是：任意结点的左、右子树高度差的绝对值不超过 1 的二叉排序树。
  • 不是：只满足高度条件、不满足 BST 序的树不是 AVL 树。

平衡因子

  • 是：结点左子树高度减右子树高度，取值只能是 −1、0、1。
  • 不是：不是右减左。LL 时由 ，RR 时由 。

最小不平衡子树

  • 是：以插入路径上离插入结点最近的平衡因子绝对值大于 1 的结点为根的子树。
  • 不是：不是从根往下找的第一个失衡结点。
  • 范围：每次调整的对象都是最小不平衡子树。

LL / RR / LR / RL

  • 是：按插入位置相对于 的两步路径命名。LL = 右单旋，RR = 左单旋，LR = 先左后右，RL = 先右后左。
  • 范围：单旋 上位，双旋 上位。 LR / RL 时新结点挂在 的哪一侧不影响旋转过程。

AVL 的删除

  • 是：先按 BST 删，再从 上溯找第一个失衡结点 ， 取 高度最高的孩子， 取 高度最高的孩子。
  • 易混：↔ 插入。插入只调一棵最小不平衡子树；删除可能一路回溯到根。

递推

  • 是：深度为 的平衡二叉树含有的最少结点数，。
  • 范围：。用于「 个结点最多比较几次」。深度为 的最多结点数是 。

7.3.3 红黑树

红黑树

  • 是：满足五条红黑性质的二叉排序树。
  • 不是：不是平衡二叉树——它是适度平衡，左右子树高度可相差近 2 倍。
  • 范围：C++ map/set、Java TreeMap/TreeSet 的底层实现。

五条红黑性质

  • 是：① 每个结点非红即黑；② 根是黑的；③ 叶结点（虚构的外部 NULL 结点）都是黑的；④ 不存在两个相邻的红结点；⑤ 对每个结点，到任意叶结点的简单路径上黑结点数量相同。
  • 范围：④ 和 ⑤ 才是有内容的——插入破坏 ④，删除破坏 ⑤。

黑高（bh）

  • 是：从某结点出发（不含该结点）到达一个叶结点的任意简单路径上的黑结点总数。
  • 不是：不含结点自身；外部 NULL 结点的黑高为 0，但它自己算一个黑结点。
  • 范围：根结点的黑高称为红黑树的黑高；黑高为 时内部结点数在 。

适度平衡

  • 是：「任意一个结点左右子树的高度相差不超过 2 倍」。
  • 范围：由此得 ；比 AVL 松，所以调整频率低。

叔结点

  • 是： 的父结点的兄弟结点 ，插入调整按它的颜色分三种情况。
  • 范围：叔红 → 变色上爬（情况 3）；叔黑 → 旋转一次就完（情况 1/2）。

双黑结点

  • 是：删除黑色终端结点后，用来替换它的结点 被视为「还有额外一重黑色」。
  • 范围：删除操作的任务就是把双黑结点恢复为普通结点；教材把这一小节标 *，考查概率较低。

7.4.1 B 树

B 树

  • 是：所有结点的平衡因子均等于 0 的 路平衡查找树，也写作「B-树」。
  • 不是：这里的「-」是连接词，不能读作「减」。
  • 范围：动机是减少磁盘存取次数——在磁盘上查找的次数即结点的层次数。

阶

  • 是： 是子树数的上限，关键字数上限是 。
  • 不是： 不是关键字个数。
  • 范围：孩子个数 关键字个数 （关键字是隔板，子树是格子）。

B 树的结点约束

  • 是：根（非叶）子树 、关键字 ；其他非叶结点子树 、关键字 。
  • 范围：所有叶结点在同一层且不带信息。

终端结点 / 叶结点

  • 是：教材把叶结点定义为不带信息的失败结点；408 真题把叶结点定义为最底层的终端结点。
  • 范围：这是教材脚注明确指出的口径分歧，读题时按语境切换。

B 树的高度

  • 是：。
  • 范围：高度不包括最后那层不带信息的叶结点（有些书包含）。

结点分裂

  • 是：插入后关键字超过 时，从中间位置 分为两半，中间关键字上升到父结点。
  • 不是：中间关键字不留在原结点。
  • 范围：可能连锁传到根，这是 B 树唯一的长高方式。

兄弟够借 / 兄弟不够借

  • 是：删除前本结点关键字数 时，看相邻兄弟—— 则借（父子换位法），否则合并。
  • 范围：判据取的是删除前的关键字个数；够借要调三个结点（本结点、兄弟、双亲）。

合并

  • 是：本结点 + 双亲的分隔关键字 + 兄弟并成一个结点，双亲关键字数减 1。
  • 范围：双亲若因此不足需逐层上溯；根空则删根，这是 B 树唯一的变矮方式。

7.4.2 B+树

B+树

  • 是：应数据库所需而出现的一种 B 树的变形树。
  • 范围：大纲只要求了解基本概念和性质，不考操作过程。

子树与关键字相等

  • 是：B+树中结点的子树个数与关键字个数相等。
  • 易混：↔ B 树的「子树 = 关键字 + 1」。这是两者最根本的差异，其余差异都由它派生。

分支结点

  • 是：可视为索引的索引，仅包含各个子结点中关键字的最大值及指向子结点的指针。
  • 不是：不含记录的存储地址——这样一个磁盘块能装更多关键字，I/O 更少。
  • 范围：关键字是叶结点关键字的副本，必然重复出现。

叶结点链表

  • 是：所有叶结点包含全部关键字，按大小排列并相互链接成线性链表。
  • 范围：支持顺序查找 / 范围扫描；B+树有两个头指针（根、最小关键字叶结点），对应两种查找运算。

B+树的查找终点

  • 是：无论成功与否都必须走到叶结点（因为分支结点只是索引）。
  • 易混：↔ B 树可能在任意一层查找成功。

7.5 散列表

散列函数

  • 是：把关键字映射成对应地址的函数，。
  • 范围：定义域必须包含全部关键字，值域依赖散列表的大小。

冲突 / 同义词

  • 是：不同关键字映射到同一地址称冲突，这些关键字互为同义词。
  • 不是：同义词看的是 相等，与最终存放位置无关。
  • 范围：冲突总是不可避免的，所以必须设计处理冲突的方法。

散列表

  • 是：根据关键字而直接进行访问的数据结构，建立了关键字与存储地址的直接映射。
  • 范围：理想情况下查找为 ，与表中元素个数无关。

直接定址法

  • 是： 或 。
  • 范围：不会产生冲突；关键字分布不连续时浪费空间。

除留余数法

  • 是：， 取不大于 但最接近或等于 的质数。
  • 易混：↔ 表长 。 用于散列， 用于探测取模，两者常不相等。

数字分析法 / 平方取中法

  • 是：前者选取数码分布较均匀的若干位；后者取关键字平方值的中间几位。
  • 范围：数字分析法适用于关键字集合已知；平方取中法的地址与关键字每一位都有关。

开放定址法

  • 是：，空闲地址既向同义词开放又向非同义词开放。
  • 范围：不能物理删除元素（会截断同义词的查找路径），只能做逻辑删除。

线性探测法

  • 是：，冲突时顺序查看下一个单元，探测到表尾则回绕到表首 0。
  • 范围：会造成堆积。

堆积

  • 是：大量元素在相邻的散列地址上聚集，大大降低查找效率。
  • 不是：不是由同义词冲突引起。
  • 易混：由非同义词之间发生冲突引起（2014）。

平方探测法（二次探测法）

  • 是：，。
  • 不是：增量不是 一路加，是正负交替。
  • 范围： 必须是可表示成 的素数；能避免堆积，但只能探测到一半单元。

双散列法

  • 是：，用两个散列函数。
  • 范围：， 是冲突次数，初始为 0。

拉链法（链接法）

  • 是：把所有同义词存在一个线性链表中，链表头指针存在散列表的第 个单元。
  • 范围：不会堆积；适用于经常进行插入和删除的情况；表长 值域大小即可。

逻辑删除

  • 是：开放定址法下删除元素时只做删除标记。
  • 范围：副作用是多次删除后表面上很满、实际有许多位置未利用（2023）。

装填因子

  • 是：表中记录数散列表长度。
  • 范围：平均查找长度依赖于 ，而不直接依赖于 或 。

查找效率的三个因素

  • 是：散列函数、处理冲突的方法、装填因子。
  • 范围：同一组关键字 + 同一散列函数，不同的冲突处理方法得到不同的表和不同的 ASL。

散列表的两个 ASL

  • 是：成功 各关键字比较次数；不成功 各起点探测到空位的次数。
  • 不是：不成功的分母不是表长 ，也不是 ，是散列函数的值域大小 。
  • 范围：空位本身算一次比较；查找失败的判据是遇到空位，不是探遍全表。

高频范围限定清单

每一条都是「说法 → 它在什么条件下才成立 / 为什么错」。考前扫这一张表。

常见说法范围限定
「查找长度是走过的边数」错。是路径上的结点数，根为 1
「不成功的 ASL 除以 」错。除以失败结点数，一般是 ；散列表是值域大小
「散列查找只适合静态查找表」错。静态和动态都适合，是唯一横跨两栏的
「顺序查找只能用于顺序表」错。顺序或链式皆可，对有序性也无要求
「有序线性表的顺序查找更快」只有「不成功」更快，「成功」完全一样
「哨兵能减少比较次数」错。减少的是边界判断
「折半查找可用于有序链表」错。要随机存取
「取整方式不影响结果」错。判定树形状变，ASL 变。但每次必须相同
「判定树是完全二叉树」教材说的是平衡二叉树，不要替换
「分块查找块内有序」错。块内无序、块间有序，第二步不能折半
「分块查找 ASL 最小值是 」错。是
「左孩子<根<右孩子就是 BST」错。要求整棵左子树都小于根
「已知中序序列可确定一棵 BST」错。所有 BST 的中序序列都相同
「BST 插入重复关键字会插到右子树」错。插入失败返回 0
「BST 删除后再插入，树不变」错。一般会变（2013 思考题）
「平衡因子 = 右减左」错。左减右
「AVL 删除最多旋转一次」错。可能一路回溯到根。插入才是最多一次
「LR 旋转后 成为根」错。双旋是 上位
「深度为 的 AVL 最少 个结点」错。，
「红黑树是平衡二叉树」错。是适度平衡，高度可相差近 2 倍
「黑高包含结点自身」错。定义是「不含该结点」
「不存在两个相邻的黑结点」错。是不存在两个相邻的红结点
「新插入的红黑树结点着黑色」错。着红色
「红黑树树高 」错。
「查找多就用红黑树」反了。查找多、增删少用 AVL
「 阶 B 树每结点有 个关键字」错。至多 棵子树、 个关键字
「B 树的叶结点是最底层终端结点」教材：失败结点；408 真题：最底层终端结点。看语境
「B 树分裂时中间关键字留在原结点」错。上升到父结点
「B 树根至少 棵子树」错。根至少 2 棵
「B 树可以从中间层长高」错。只能从根长高，所以叶结点永远同层
「B+树关键字数 = 子树数 − 1」错。相等。这是与 B 树最根本的差异
「B+树非叶结点存记录地址」错。仅起索引作用
「B+树可在分支结点查找成功」错。必须走到叶结点。B 树才可能任意层成功
「B+树分支结点存子树最小关键字」王道口径是最大值
「同义词是存储位置相同的关键字」错。是散列函数值相同
「堆积由同义词冲突引起」错。由非同义词之间冲突引起（2014）
「平方探测能探测所有单元」错。至少能探测一半
「平方探测表长可任意」错。 须为 型素数
「开放定址法可直接删除元素」错。会截断查找路径，须逻辑删除（2023）
「拉链法会引起聚集」错。拉链法不会堆积
「除留余数法的 就是表长 」错。 且为质数，两者常不等
「装填因子 可避免冲突」错。冲突与 无必然关系
「ASL 依赖于记录数 」错。依赖于 ，不直接依赖 或
「散列查找不需要比较关键字」错。定位后必须比较
「查找失败要探遍全表」错。撞到第一个空位就失败，且空位计一次比较

链接

反向链接