第7章查找自学版¶

章节定位：查找体系章

这一章把线性查找、树形查找、多路平衡查找和散列表放到一条统一效率主线下。
建议先掌握 ASL 和判定树，再进入 BST、AVL、红黑树、B树/B+树和 Hash 表的代码专题。

1. 本章定位¶

第 7 章是整本数据结构里“最容易被学生学成一堆零散题型”的一章。

它表面上讲的是“怎么找元素”，但真正的主线其实是：

不同查找结构的组织方式不同。
组织方式不同，决定了比较次数不同。
比较次数不同，决定了查找效率、插入删除代价和适用场景都不同。

如果把这一章只看成“顺序查找、折半查找、二叉排序树、AVL、B 树、Hash 表”的清单，就很容易越学越碎。更稳的学法是始终盯住一个总问题：

为了更快地找到目标元素，我们到底提前做了哪些结构化准备？

2. 学习目标¶

学完第 7 章后，建议至少达到下面这些目标：

能解释“静态查找”和“动态查找”的区别。
能理解平均查找长度 ASL 为什么是这一章的核心效率指标。
能写出顺序查找、折半查找的真实 C 代码，并知道各自适用条件。
能看懂并实现二叉排序树的查找、插入、删除。
能理解 AVL 树为什么要旋转，以及四类失衡如何调整。
能分清 B 树与 B+ 树的层次结构、用途和高频考点。
能理解散列函数、冲突、开放定址法、拉链法以及基本性能分析。

3. 前置知识¶

在继续往下看之前，最好已经比较稳地掌握：

本书第2章正文 中的顺序表、链表。
本书第5章正文 中的二叉树、遍历、树高。
时间复杂度的基本分析方法。

这一章和前面章节的衔接关系很强：

顺序查找、折半查找，本质上是在顺序表上做文章。
二叉排序树、AVL、红黑树，本质上是在二叉树结构上做文章。
散列表虽然不再按“比较树形”组织，但仍然是在用空间换时间。

4. 本章结构总览¶

第 7 章可以按下面的逻辑顺序理解：

先明确“查找到底在优化什么”。
再看线性结构中的查找：顺序查找、折半查找、分块查找。
再看树形结构中的查找：二叉排序树、AVL、红黑树。
再看外存查找结构：B 树、B+ 树。
最后看散列结构：Hash 表。

你可以把这一章理解成三条路线：

继续比较关键字：顺序查找、折半查找、BST、AVL、B 树。
通过更好的组织方式减少比较次数：有序、平衡、多路。
尽量绕开大量比较：散列。

5. 7.1 查找的基本概念¶

5.1 什么叫查找¶

查找就是：在一个数据集合中，寻找满足条件的元素。

结果只有两种：

查找成功：找到了目标元素。
查找失败：集合里没有它。

这一章最重要的不是“能不能找到”，而是：

为了找到它，我们平均要比较多少次。

5.2 静态查找和动态查找¶

这两个词非常高频：

静态查找
只关心“查找”
表中元素基本不变
适合折半查找这类依赖有序结构的方法
动态查找
不只要查找，还要频繁插入、删除
结构必须能在更新后继续保持较好的查找性能
典型代表是二叉排序树、AVL、红黑树

通俗地说：

静态查找像“已经排好座位表的考场名单”
动态查找像“不断有人加入、退出的通讯录”

5.3 平均查找长度 ASL¶

ASL 是 Average Search Length，也就是平均查找长度。

它表示：

在等概率或给定概率条件下，查找过程中平均需要进行多少次关键字比较。

这一章很多题最后其实都在考：

查找成功时的 ASL
查找失败时的 ASL
不同结构的 ASL 为什么不同

真正要抓住的不是公式本身，而是：

结构越接近“直接定位”，ASL 越小。
结构越失衡、越混乱，ASL 越大。

6. 7.2 线性结构中的查找¶

6.1 顺序查找¶

顺序查找是最朴素的方法：

从头开始
一个一个比较
找到就停，找不到就走到末尾

它的优点是：

实现最简单
对表是否有序没有要求

缺点也很明显：

最坏情况下要把整个表看完
查找效率不高

当前真实代码入口：

第7章普通代码版 中的 SeqSearch

6.2 折半查找¶

折半查找的核心不是“分成两半”这句话，而是：

每比较一次，就能排除掉一大半不可能的区间。

它必须建立在一个关键前提上：

表必须有序
并且通常用顺序存储实现

如果表是无序的，折半查找就没有意义。

当前真实代码入口：

第7章普通代码版 中的 BinarySearchIter
第7章普通代码版 中的 BinarySearchRecursive

6.3 分块查找¶

分块查找处在顺序查找和折半查找之间。

它的思想是：

先把表分成若干块
块内可以不完全有序
但块与块之间按最大关键字或范围建立索引

于是查找时分两步：

先查索引表，确定目标可能在哪个块
再到块内顺序查找

这是一种典型的“局部有序 + 局部顺查”的折中结构。

当前真实代码入口：

第7章普通代码版 中的 BlockSearch

7. 7.3 树形查找¶

7.1 二叉排序树 BST¶

BST 的核心性质是：

左子树所有关键字小于根
右子树所有关键字大于根
左右子树本身也分别是 BST

查找时其实就在不断做决策：

比当前结点小，往左走
比当前结点大，往右走
相等，查找成功

当前真实代码入口：

第7章普通代码版 中的 BSTSearch
第7章普通代码版 中的 BSTInsert
第7章普通代码版 中的 BSTDelete

7.2 为什么 BST 会退化¶

BST 的问题在于：

它虽然有序，但不一定平衡。

比如把 1, 2, 3, 4, 5 依次插入空 BST，就会退化成一条链。

这时查找效率会从理想情况下的对数级，恶化到接近顺序查找。

7.3 平衡二叉树 AVL¶

AVL 的目标很直接：

不要让 BST 长歪。

它要求每个结点左右子树高度差的绝对值不超过 1。

一旦插入后失衡，就通过旋转把它拉回来。

最该掌握的是四种失衡：

LL
RR
LR
RL

当前真实代码入口：

第7章普通代码版 中的 AVLInsert
第7章普通代码版 中的 RotateLeft
第7章普通代码版 中的 RotateRight

7.4 红黑树¶

红黑树也是自平衡二叉查找树，但它不是像 AVL 那样追求“严格高度平衡”，而是追求“适度平衡”。

直觉上可以这样理解：

AVL 更严格，所以查找往往更稳
红黑树调整代价通常更温和，所以工程上更常用

这一章后面我们会重点把它当作“概念和对比点”来讲，而不是一上来就把实现复杂度拉满。

8. 7.4 B 树和 B+ 树¶

这一部分的难点不是定义本身，而是：

为什么要多路查找
为什么磁盘块 / 页这个背景会重要
为什么数据库索引更偏爱 B+ 树

先抓住一个直觉：

二叉树每层分叉少，高度容易变高
多路平衡树每层能放更多关键字和更多分支
这样访问外存时层数更少，I/O 更少

这一部分后续会继续补：

B 树结点结构和性质
插入 / 删除过程
B+ 树和 B 树的高频区别

9. 7.5 散列（Hash）表¶

9.1 散列思想¶

散列的核心不是“继续一层层比较”，而是：

希望通过一个函数，直接把关键字映射到可能存放的位置。

理想状态下：

算出地址
一次命中

但现实里会发生冲突：

不同关键字映射到同一地址
这就需要冲突处理方法

9.2 两类高频冲突处理方法¶

这一章最常见的是：

开放定址法
典型是线性探测
拉链法
同义词挂到同一个链表里

当前真实代码入口：

第7章普通代码版 中的 HashOpenInsert
第7章普通代码版 中的 HashOpenSearch
第7章普通代码版 中的 ChainHashInsert
第7章普通代码版 中的 ChainHashSearch

10. 第7章代码阅读入口¶

这一章第一版代码目前已经先落了最应该优先掌握的几块：

顺序查找
折半查找
分块查找
二叉排序树
AVL 树插入与查找
Hash 表的开放定址法与拉链法

建议阅读顺序：

先看 SeqSearch 和 BinarySearchIter
再看 BSTInsert、BSTSearch、BSTDelete
再看 AVLInsert 和旋转函数
最后看 HashOpenInsert、ChainHashInsert

对应代码文件：

第7章普通代码版

14. 当前边界说明¶

这一版是“第 7 章启动版”，不是终版。

目前先把最适合直接代码落地、也最适合先学的部分起起来了。

还没有做厚的部分主要是：

红黑树代码专项
B 树 / B+ 树完整代码专项
原书试题区整理
题型索引、刷题路径、自学检查清单

这些会在后续轮次继续补上。

14. 7.2 重点展开¶

14.1 顺序查找再讲透一点¶

顺序查找最容易被低估，因为它看起来太“朴素”了。

但恰恰因为朴素，它经常被拿来做对照：

和折半查找比，能看出“有序”到底值多少钱。
和 BST 比，能看出“结构化组织”到底带来了什么收益。
和 Hash 比，能看出“直接定址”为什么会快很多。

顺序查找的本质是：

不利用任何额外结构
不利用有序性
只依赖“从前往后逐个比较”

所以它的优点和缺点都非常纯粹：

优点是简单、稳定、适配性强
缺点是比较次数基本靠运气，最坏情况很差

如果目标刚好在第一个位置，那只比较 1 次。如果目标在最后一个位置，或者根本不在表里，就要比较很多次。

14.2 顺序查找的 ASL 怎么理解¶

顺序查找成功时的平均查找长度，在等概率情况下，本质上就是：

第 1 个元素要比 1 次
第 2 个元素要比 2 次
第 3 个元素要比 3 次
依此类推

如果表长为 n，而且每个元素被查到的概率相同，那么成功时：

ASL = (1 + 2 + ... + n) / n = (n + 1) / 2

这条结论要真正理解，不要只背：

因为顺序查找没有“提前排除大段区间”的能力，所以平均位置基本就在中间附近。

查找失败时，如果要确认“确实没有”，通常要把表扫完，因此失败代价往往接近 n。

14.3 顺序查找：原书思路版伪代码¶

SeqSearch(A, n, key)
    for i = 0 to n - 1
        if A[i] == key
            return i
    return -1

这个伪代码特别值得学生注意的一点是：

它没有任何“跳跃式推进”，所以时间复杂度天然是线性的。

14.4 顺序查找：对应真实代码¶

当前真实代码是：

第7章普通代码版（约第51行）

对应函数：

SeqSearch

它和伪代码的关系非常直接：

先判空和判长度是否合法
再从 0 走到 length - 1
一旦命中就立即返回
否则最后返回 -1

这一段代码很适合学生第一次练“从伪代码翻译成真代码”。

14.5 折半查找再讲透一点¶

折半查找最重要的不是公式，而是“每一步都在排除不可能区间”。

它能快起来的原因只有一个：

你已经为它付出了“表必须有序”的前提成本。

所以折半查找不是白赚的，它是拿“维护有序”换来的查找效率。

查找时每一步都围绕中点 mid 展开：

若 A[mid] == key，查找成功
若 A[mid] < key，说明目标只能在右半边
若 A[mid] > key，说明目标只能在左半边

于是每次比较之后，待查区间几乎减半。

14.6 折半查找的判定树怎么理解¶

判定树是这一节最容易“学会做题但没学会原理”的点。

更形象的理解方式是：

每个被比较到的中点，就是判定树里的一个结点
往左走，表示“目标更小”
往右走，表示“目标更大”
某个元素所在层数越浅，平均比较次数越少

所以判定树不是额外画着玩的图，而是：

折半查找比较过程的树形展开图。

后面一切关于：

成功 ASL
失败 ASL
某个元素要比较几次
哪些元素更早被找到

都可以回到判定树上看。

14.7 折半查找：原书思路版伪代码¶

BinarySearch(A, low, high, key)
    while low <= high
        mid = (low + high) / 2
        if A[mid] == key
            return mid
        else if A[mid] < key
            low = mid + 1
        else
            high = mid - 1
    return -1

学生最容易错的不是“大思路”，而是边界：

为什么循环条件是 low <= high
为什么更新右边界时是 mid - 1
为什么更新左边界时是 mid + 1

14.8 折半查找：对应真实代码¶

当前真实代码包括两版：

非递归版：
第7章普通代码版（约第68行）
递归版：
第7章普通代码版（约第95行）

对应函数：

BinarySearchIter
BinarySearchRecursive

建议阅读顺序：

先看非递归版，先把 low、high、mid 的移动看懂
再看递归版，理解“缩区间”如何交给函数调用来完成

14.9 折半查找为什么不能随便用¶

折半查找虽然快，但有明显前提：

表必须按关键字有序
一般要求顺序存储，方便直接取中间位置

这就是为什么：

静态查找表很适合折半查找
若插入、删除很多，有序顺序表维护代价会变高
这时就需要 BST、AVL 这类动态查找结构来接手

所以你要把它看成“静态有序表上的强力工具”，而不是所有查找问题的默认解。

14.10 分块查找再讲透一点¶

分块查找很像一种折中策略。

它不要求整个表都严格有序，但也不愿意完全像顺序查找那样从头扫到底。

于是它采用“两级定位”：

一级定位：通过索引块先缩小范围
二级定位：在块内顺序查找

它的适合场景可以这样理解：

整体完全有序，最适合折半查找
完全无序，只能顺序查找
局部能组织出一定规律时，分块查找是一个很自然的中间方案

14.11 分块查找：原书思路版伪代码¶

BlockSearch(A, Index, block_count, key)
    先在索引表中找到 key 所属的块
    再在该块内顺序查找 key
    若找到则返回位置
    否则返回 -1

分块查找最容易漏掉的点不是块内顺查，而是：

索引项通常保存什么
为什么常常用“块最大关键字”来做索引
为什么块内未必需要完全有序

14.12 分块查找：对应真实代码¶

当前真实代码位置：

第7章普通代码版（约第117行）

对应函数：

BlockSearch

这一版代码已经把思路拆成了两层：

先在索引数组里定位目标块
再在目标块范围内顺序扫描

如果学生能把这段代码看懂，后面理解“索引结构不是一步查到底，而是先粗定位、再细定位”会轻松很多。

14.13 7.2 三种查找方法怎么放在一起比较¶

可以把这三种方法放在同一张脑图里：

顺序查找
对结构要求最低
比较次数通常最多
折半查找
对有序性要求最高
查找效率最好
分块查找
要求介于两者之间
性能也介于两者之间

所以这不是三种互不相关的方法，而是三种“利用结构信息程度不同”的查找方案。

14.14 7.2 高频易错点¶

这一节最容易错的地方主要有：

以为“有序链表”也适合折半查找
不对
因为链表不能像顺序表那样低代价地直接取中间位置
折半查找边界写错
特别是 low <= high
以及 mid + 1、mid - 1
把分块查找误以为“块内也必须折半”
不一定
块内常常就是顺序查找
把 ASL 只当公式背
真正该理解的是“为什么平均比较次数会那样分布”

15. 7.2 进一步展开¶

15.1 折半查找判定树例题怎么做¶

很多学生一看到“判定树”就想先背结论，其实更稳的方法是先把过程还原出来。

假设有一个有序表：

[5, 8, 12, 19, 23, 31, 45, 57, 68, 72]

如果做折半查找，第一次比较的中点是：

low = 0
high = 9
mid = 4
所以第一次比较的是 23

于是判定树的根就不是凭空来的，而是：

根结点对应第一次被比较的元素
左子树对应“小于 23 的那半边”
右子树对应“大于 23 的那半边”

然后递归地对左右区间继续取中点，就能把整棵判定树画出来。

所以做判定树题时，固定步骤是：

先写当前区间
再找中点元素
再把左右区间继续拆
最后把比较层数和结点层次对应起来

15.2 折半查找成功 ASL 的例题直觉¶

判定树一旦画出来，成功 ASL 的本质就变得很直观：

某个元素如果在根，比较 1 次
某个元素如果在第 2 层，比较 2 次
某个元素如果在第 3 层，比较 3 次
依此类推

所以成功 ASL 其实就是：

把所有成功结点所在层数按概率加权平均。

等概率情况下，可以理解成：

把每个成功结点的比较次数加起来
再除以元素个数

这和树、图里那种“只记结构定义”不一样，这里一定要把“层数 = 比较次数”这个映射记牢。

15.3 折半查找失败 ASL 为什么常常更绕¶

失败 ASL 更难，是因为：

查找失败时，落到的不是“成功结点”
而是判定树中那些“空位置”或“失败结点”

更直观地说：

成功查找是在找“表里真实存在的元素”
失败查找是在确认“这个值不在表里”

所以做失败 ASL 时，看的不是元素本身，而是：

最后会落入哪一个失败区间
到那个失败位置之前一共比较了几次

这一类题最容易错的地方，就是把失败 ASL 也按成功结点层数去算。

15.4 一个最典型的折半查找比较次数题¶

还是看这个有序表：

[5, 8, 12, 19, 23, 31, 45, 57, 68, 72]

如果查找 68：

先比 23
因为 68 > 23，去右半边
再比右半边的中点
再继续缩区间

你真正应该做的不是直接口算，而是把路径写出来：

23 -> 57 -> 68

于是比较次数就是 3

所以做这类题时，最稳的方式永远是：

不要直接猜
把每一步中点写出来
用路径长度判断比较次数

15.5 顺序查找和折半查找的 ASL 对比怎么看¶

这一类题经常考比较，不一定让你完整算数值。

你至少要能说清下面几点：

顺序查找成功 ASL 一般是线性级别的平均位置
折半查找成功 ASL 一般明显更小
原因不是“折半查找更神奇”，而是它吃到了“有序”的结构红利

所以如果题目问：

“为什么折半查找效率更高？”

更完整的回答应该是：

因为每次比较后能排除半个区间
而不是只排除一个元素
但前提是顺序表有序，且能直接访问中间位置

15.6 为什么有序链表不适合折半查找¶

这道题非常经典。

很多学生觉得：

既然有序
那就应该能折半

但真正的卡点在于“取中间位置”的代价。

顺序表里：

取 A[mid] 很快
因为可以直接按下标访问

链表里：

你想找中间结点
往往还得从头一个一个走过去

于是折半查找最核心的优势就被抵消了。

所以结论不是“有序就一定能高效折半”，而是：

还要看存储结构是否支持快速定位中间元素。

15.7 分块查找例题的固定做法¶

分块查找题最容易在两个地方出错：

不会先确定块
确定块之后又忘了块内怎么找

固定做法可以直接记成两步：

先查索引表，判断目标属于哪个块
再在这个块内部顺序查找

如果题目给出的是每块最大关键字，那么判断规则通常是：

找第一个满足 key <= max_key 的块
这个块就是目标可能落入的块

之后再到块内顺序找。

15.8 7.2 高频题统一抓法¶

这一节高频题基本都可以归到下面几类：

顺序查找的成功 / 失败 ASL
折半查找的比较次数
折半查找判定树
折半查找成功 / 失败 ASL
分块查找的过程题
“哪种结构适合哪种查找方法”的判断题

看到题目后，先判断它属于哪一类，再选固定思路，会比“现场瞎想”稳很多。

15.9 7.2 当前最容易丢分的点¶

到目前为止，7.2 最容易丢分的点主要是：

折半查找边界写错
把判定树画错成普通二叉排序树
不会区分成功 ASL 和失败 ASL
以为有序链表也天然适合折半查找
分块查找时不会先看索引、直接进块内乱找

15.10 本节小结¶

到这里，7.2 已经进一步补到了“能做题”的层次：

有判定树题的固定思路
有成功 / 失败 ASL 的直觉区别
有折半查找比较次数的路径化理解
有“有序链表为什么不适合折半”的高频判断点
有分块查找题的固定做法

这意味着下一步最自然的推进是：

开始做厚 7.3：BST、AVL、红黑树
或者继续把 7.2 做成“原书题型整理版”

16. 7.3 重点展开¶

16.1 BST 不是“另一种二叉树”，而是“带查找规则的二叉树”¶

学生在这一节最常见的误区，是把 BST 只当作“长得像二叉树的结构”。

其实 BST 最核心的不是形状，而是查找规则：

左边都更小
右边都更大
每向下一层，都会排除掉一整片不可能的范围

所以 BST 和普通二叉树最大的区别不是“有没有左右孩子”，而是：

它把关键字大小关系编码进了树结构里。

这也是为什么：

中序遍历 BST 会得到递增序列
查找时不需要遍历整棵树
插入时也不是随便挂，而是必须沿着大小关系找到位置

16.2 BST 查找：原书思路版伪代码¶

BSTSearch(T, key)
    while T != NULL
        if key == T->key
            return T
        else if key < T->key
            T = T->lchild
        else
            T = T->rchild
    return NULL

这一段最该抓的，不是循环长什么样，而是每一步都在做区间裁剪：

当前结点就是一个“分界点”
小了只能去左边
大了只能去右边

16.3 BST 查找：对应真实代码¶

当前真实代码位置：

第7章普通代码版（约第166行）

对应函数：

BSTSearch

这段代码特别适合学生训练“伪代码翻译成真代码”的感觉，因为它几乎就是把书上的逻辑一层层展开：

用 current 指针从根开始走
每次先判断是否相等
再根据大小关系决定向左还是向右
指针走到 NULL 时，说明查找失败

16.4 BST 插入：本质上是在找“应该落在哪里”¶

BST 插入不是“把新结点塞进树里”这么简单，它其实分两步：

先按查找路径一路走下去
走到空位置时，把新结点挂在那里

所以 BST 插入和 BST 查找的关系非常紧：

查找成功：说明元素已存在
查找失败：失败停止的位置，就是插入位置

16.5 BST 插入：原书思路版伪代码¶

BSTInsert(T, key)
    if T == NULL
        创建新结点并返回
    if key < T->key
        T->lchild = BSTInsert(T->lchild, key)
    else if key > T->key
        T->rchild = BSTInsert(T->rchild, key)
    return T

学生这里最容易忽略的是：

返回值为什么还是树根
为什么递归插入后还要把子树重新接回去

这其实是在保证“下层子树改完后，上层指针也能连对”。

16.6 BST 删除为什么最容易出错¶

BST 删除比查找、插入都难，因为它不仅要删掉目标结点，还要保证删完之后仍然满足 BST 性质。

最稳的理解方式是分三类：

叶子结点
直接删
只有一个孩子的结点
让孩子顶上来
有两个孩子的结点
不能直接乱删
通常找右子树最小结点或左子树最大结点来替代

真正麻烦的就是第三类。

16.7 BST 删除：对应真实代码¶

当前真实代码位置：

第7章普通代码版（约第217行）

对应函数：

BSTDelete

配套辅助函数：

第7章普通代码版（约第202行）

对应函数：

BSTFindMin

这两段代码建议配套看，因为“删除双孩子结点”时，核心就在于：

先在右子树中找到后继
用后继值覆盖当前结点
再去右子树里删掉那个后继结点

这样做不是绕，而是在最小代价下维持 BST 的有序性。

16.8 AVL 为什么比 BST 更稳¶

BST 最大的问题是可能退化。

AVL 就是在 BST 的基础上加了一条更严格的约束：

任意结点左右子树高度差绝对值不超过 1

于是 AVL 的思路可以概括成一句话：

先像 BST 那样插
再检查有没有失衡
如果失衡，就旋转回来

所以 AVL 不是“另一套全新查找方法”，而是“给 BST 加了自动纠偏机制”。

16.9 AVL 的四种失衡类型怎么理解¶

四种失衡不要死背名字，最稳的方法是看“失衡发生在左还是右、内侧还是外侧”。

LL
左孩子的左子树更高
右旋
RR
右孩子的右子树更高
左旋
LR
左孩子的右子树更高
先左旋再右旋
RL
右孩子的左子树更高
先右旋再左旋

更形象地说：

外侧高，用一次单旋
内侧高，用一次双旋

16.10 AVL 旋转：对应真实代码¶

当前真实代码位置：

第7章普通代码版（约第332行）
第7章普通代码版（约第352行）

对应函数：

RotateRight
RotateLeft

学生看旋转代码时最容易晕，是因为同时在改很多指针。

建议盯住两个问题：

谁变成新的子树根
中间那棵“被夹着的子树”最后挂回哪里

只要这两个问题清楚，旋转就不会只剩下死记硬背。

16.11 AVL 插入：原书思想和真实代码怎么对上¶

AVL 插入的完整逻辑是：

先按 BST 递归插入
回溯时更新当前结点高度
计算平衡因子
判断属于 LL / RR / LR / RL 哪一类
选择对应旋转

当前真实代码位置：

第7章普通代码版（约第372行）

对应函数：

AVLInsert

这一段代码非常值得后面做逐行拆解，因为它不是单纯在“插入”，而是在“插入 + 回溯更新 + 修复失衡”。

16.12 红黑树先抓概念，不先硬啃实现¶

第 7 章里红黑树最适合先掌握的是“为什么会有它”，而不是一开始就陷进复杂调整细节。

先抓住这层对比关系：

BST
有序
但可能退化
AVL
更严格平衡
查找性能很稳
更新时调整代价更高
红黑树
平衡没 AVL 那么严格
但动态更新通常更适合工程实现

所以红黑树在这一章的第一目标，是：

会和 BST、AVL 做比较
会判断它的工程定位
会做高频选择题和判断题

16.13 BST、AVL、红黑树怎么放在一起比较¶

这一节最值得学生建立的，不是三个零碎定义，而是一张对照表：

BST
优点：结构简单，查找 / 插入 / 删除思路直接
缺点：可能退化
AVL
优点：高度更稳，查找效率通常更好
缺点：插入删除时旋转维护更频繁
红黑树
优点：适度平衡，工程应用广
缺点：性质和调整规则更复杂

只要这张关系图清楚，后面的高频题就不会碎掉。

16.14 7.3 高频易错点¶

这一节目前最容易错的地方主要有：

把 BST 当普通二叉树来做
忘记 BST 中序遍历一定有序
BST 删除双孩子结点时不会找替代结点
AVL 只记旋转名字，不知道为什么要这样转
把 AVL 和红黑树的定位混在一起

17. 7.3 进一步展开¶

17.1 BST 高频题：中序遍历为什么总是有序¶

这几乎是 BST 最核心、也最常考的性质。

原因不是“老师规定了它有序”，而是 BST 的定义天然保证了：

左子树都更小
根在中间
右子树都更大

而中序遍历的顺序正好是：

左
根
右

所以中序一展开，得到的就是一个递增序列。

这条性质特别重要，因为它会反复用在：

判断一棵树是不是 BST
判断删除、插入后是否仍满足 BST 性质
通过中序结果反推关键字大小规律

17.2 BST 高频题：由插入序列构造 BST 时该怎么想¶

这种题最容易误以为要“整体规划”树形，其实不用。

固定思路只有一句话：

按给定顺序，一个一个插。

每插入一个元素时：

从根开始比较
小了往左
大了往右
走到空位置时挂上去

这类题真正的难点不是“规则不懂”，而是：

手工模拟时容易漏走一步
会把后插入元素放到不符合 BST 性质的位置

所以建议做题时一定把路径写出来，而不是靠脑补。

17.3 BST 高频题：删除结点后树形为什么可能变化很大¶

删除 BST 结点时，最容易让学生觉得“删一个点怎么树会变这么多”的，是双孩子结点删除。

关键原因在于：

不能直接把这个结点物理删掉就完事
必须找一个能合法顶替它的位置
通常用右子树最小结点或左子树最大结点

所以这类题的判断核心不是“删掉谁”，而是：

删完后中序序列仍然必须保持有序。

只要抓住这句话，很多删除题就不会乱。

17.4 AVL 高频题：为什么插入后只调整最小不平衡子树¶

这是特别经典的判断点。

很多学生会以为插入后整棵树可能都要一路大改，其实不是。

更稳的结论是：

从插入点往上回溯
第一个平衡因子绝对值大于 1 的结点
就是最小不平衡子树的根
只要把这棵最小不平衡子树调整好，整棵树就能恢复平衡

这条结论非常重要，因为它解释了：

为什么 AVL 调整是局部的
为什么题目里总让你找“最小不平衡子树”
为什么不是从根开始乱转

17.5 AVL 典型例题：LL 和 RR 怎么快速判断¶

看名字不如看“插入路径”。

如果插入路径是：

根 -> 左 -> 左
就是 LL
做一次右旋
根 -> 右 -> 右
就是 RR
做一次左旋

真正该记住的是：

外侧高，单旋
左左失衡右旋
右右失衡左旋

不要把它们背成死词，而要和插入路径绑定起来。

17.6 AVL 典型例题：LR 和 RL 为什么一定是双旋¶

这类题最容易错在“看起来偏左就想右旋，看起来偏右就想左旋”。

但 LR 和 RL 的麻烦就在于：

失衡方向和插入方向拧着
直接单旋会破坏 BST 的大小关系

所以：

LR
先对左孩子左旋
再对当前根右旋
RL
先对右孩子右旋
再对当前根左旋

一句更容易记的话是：

内侧高，先把它转成外侧高
再做单旋收尾

17.7 AVL 插入调整题的固定做法¶

看到 AVL 插入题，不要直接猜旋转。

固定流程建议写成四步：

先按 BST 规则完成插入
从插入结点一路向上检查平衡因子
找到最小不平衡子树
根据插入路径判断是 LL / RR / LR / RL

如果题目让你写最终树形，也不要跳步，最好把：

插入前局部子树
失衡后局部子树
旋转后局部子树

分别画出来。

17.8 红黑树高频题：先抓五条性质¶

红黑树后面最容易出选择题和判断题，所以第一步先把性质抓稳：

每个结点非红即黑
根结点是黑色
叶结点（外部空结点）是黑色
红结点不能有红孩子
从任一结点到其每个叶结点的所有路径上，黑结点数相同

这五条里最容易出错的是后两条，因为它们直接决定：

为什么不会出现连续红结点
为什么红黑树虽然不严格平衡，但也不会太歪

17.9 红黑树和 AVL 的高频比较题¶

这类题常常不是让你实现，而是让你判断哪句话对、哪句话错。

最稳的比较框架是：

AVL
平衡更严格
查找性能通常更稳
更新时调整更频繁
红黑树
平衡相对宽松
插入删除时通常更适合工程实现
实际应用范围很广

如果题目在问“谁查找更优、谁工程更常用”，不要只背一个名字，要带上“为什么”。

17.10 7.3 高频选择题统一抓法¶

这一节高频题大致可以归成下面几类：

BST 性质题
BST 插入序列与树形题
BST 删除题
AVL 平衡因子与旋转题
AVL 插入调整题
红黑树性质判断题
红黑树与 AVL 比较题

看到题目后，先给它分型，再决定是：

画树
写中序
看插入路径
看平衡因子
对照红黑树五条性质

这样会比直接上手判断稳得多。

17.11 7.3 当前最容易丢分的点¶

到目前为止，这一节最容易丢分的点主要有：

只会背 BST 性质，不会用中序判断
BST 删除双孩子结点时不知道找谁替代
AVL 旋转名字记住了，但不会通过插入路径判断
看到 LR / RL 题时还是想直接单旋
红黑树把“黑高相等”和“树高相等”混为一谈
把红黑树的工程优势说成“查找一定比 AVL 快”

17.12 本节小结¶

到这里，7.3 已经进一步补到了“能做高频题”的层次：

有 BST 高频题抓法
有 AVL 插入调整的固定思路
有红黑树五条性质的判断框架
有 AVL 和红黑树的比较框架
有树形查找题的统一分型思路

下一步最自然的推进是：

开始补 7.4：B 树、B+ 树
或者回头把 7.3 做成“原书题型整理版”

18. 7.4 重点展开¶

18.1 为什么学到这里会突然出现 B 树¶

很多学生学到这一节会有一个自然疑问：

前面不是已经有 BST、AVL、红黑树了吗
为什么还要再来一个 B 树

答案在于应用场景变了。

前面的 BST、AVL、红黑树，更像是在“内存里做查找”。

而 B 树这一类结构，重点是：

当数据量很大、需要频繁访问外存时，怎么减少磁盘 I/O 次数。

更直观地说：

二叉树每个结点能放的信息比较少
树的高度容易上去
树一高，每次查找就要访问更多层
如果每层访问都伴随一次磁盘页读取，代价就会很大

所以 B 树的目标不是“比 AVL 更帅”，而是：

让树变矮，让每一层装更多关键字和更多分支。

18.2 B 树的核心直觉：不是二叉，而是多路平衡¶

看 B 树时，一定先把“二叉”的思维放开。

B 树的核心不是每个结点最多两个孩子，而是：

一个结点里可以存多个关键字
一个结点也可以连出多个分支
所有叶子结点都在同一层

所以 B 树最该抓的不是某个死定义，而是这三个直觉：

结点更胖
树更矮
查找层数更少

18.3 B 树查找时到底在做什么¶

B 树查找其实也是“不断缩小范围”，只不过这里不是每到一个结点只比较一次，而是：

先在当前结点内部找关键字应该落在哪个区间
再沿对应分支往下一层走

也就是说，一个 B 树结点本身就像一个“小的有序表”。

所以查找过程可以理解成：

先在当前页内定位
再决定往哪棵子树继续走

这和 BST 的“一个结点只放一个关键字”非常不同。

18.4 B 树最常考的性质应该怎么抓¶

这一节最容易把人绕晕的是“阶”“关键字个数”“孩子个数”“最少多少、最多多少”。

稳一点的学法不是一口气背一堆数字，而是先抓住这些关系：

一个结点里有 k 个关键字
通常就会有 k + 1 棵子树
根结点和非根结点的下界规则不同
所有叶子结点在同一层，所以 B 树是平衡的

做题时最关键的不是背每句定义，而是会从：

一个结点最少能有几个关键字
一个结点最多能有几个关键字
每层最少能扩出多少个结点

一步步往下推。

18.5 B 树为什么适合外存索引¶

这一点一定要和“页 / 块”联系起来理解。

磁盘访问慢，不怕一页里多比较几次，怕的是：

树太高
每走一层都要多做一次 I/O

所以 B 树的设计方向是：

让一个结点尽量装下更多关键字
让一个磁盘页尽量对应一个结点
这样每次读进来一页，就能在这一页里完成更多判断

因此 B 树的优势不是“比较次数一定最少”，而是：

总 I/O 次数更少。

18.6 B 树插入为什么会有“分裂”¶

这一节的第一个高频动作就是结点分裂。

原因很自然：

新关键字总要插到某个叶子或某个目标结点里
如果这个结点还没满，直接插进去就行
如果已经满了，就放不下了
这时就必须分裂

分裂时最应该形成的画面是：

中间关键字上移
左边关键字留在左结点
右边关键字留在右结点
父结点接收上移关键字

如果父结点也满了，分裂可能继续向上传。

所以 B 树插入题最常考的不是“会不会背规则”，而是：

分裂时谁上移
分裂后谁留左边、谁留右边
分裂是否继续向上传播

18.7 B 树删除为什么更绕¶

删除比插入更容易让学生头疼，因为删除后不仅可能“空出位置”，还可能破坏结点的下界要求。

删除时常见的几个动作是：

借关键字
合并结点
调整父结点

理解的关键不是一次记完所有分支，而是先抓这条主线：

删除后当前结点关键字太少了
先看兄弟结点能不能借
借不到，就和兄弟及父结点中的关键字合并
如果父结点又因此出问题，再继续向上调

所以 B 树删除题的本质是：

在“删完还合法”这件事上不断补平衡。

18.8 B+ 树和 B 树最该怎么区分¶

这一组题几乎必考。

最稳的比较方式是先抓三点：

B+ 树的非叶结点主要起索引作用
B+ 树的叶结点包含全部关键字对应的信息
B+ 树叶结点常按关键字顺序链接起来

而 B 树则是：

非叶结点也可能直接存记录信息
查找成功时不一定走到叶子
更像“整棵树都在存有效数据”

所以这组题不要只记一句“B+ 树更适合数据库”，而要知道为什么：

顺序访问更方便
范围查询更自然
非叶层更纯粹地用于索引

18.9 B 树和 B+ 树的高频考法¶

这一节高频题通常集中在下面几类：

性质判断题
给定阶数，求关键字 / 孩子数上下界
给定关键字总数，求树高范围
插入分裂过程题
删除借位 / 合并过程题
B 树和 B+ 树差异题
数据库 / 文件索引适用场景题

所以这部分做题时要先判断：

它是在考结构性质
还是在考操作过程
还是在考和 B+ 树的对比

18.10 7.4 当前最容易丢分的点¶

这一节现在最容易丢分的地方主要有：

还在用二叉树思维看 B 树
搞混“关键字个数”和“孩子个数”
不会区分根结点和非根结点的下界
插入时不知道谁上移
删除时不知道先借还是先合并
把 B 树和 B+ 树的记录存储位置混在一起
只会背“B+ 树更适合数据库”，但说不出原因

19. 7.5 重点展开¶

19.1 Hash 表为什么和前面的查找思路完全不一样¶

前面的顺序查找、折半查找、BST、AVL、B 树，本质上都还在做一件事：

通过比较关键字
一步一步缩小范围
最后找到目标

而 Hash 表的思路明显更“激进”：

不想老老实实比较很多次
想直接根据关键字算出它大概该放在哪

所以它的核心问题不再是“怎么比较更快”，而是：

怎么把关键字映射到地址，并尽量减少冲突。

这就是为什么这一节和前面几节的气质完全不同。

19.2 散列函数到底在做什么¶

散列函数的作用，可以直接理解成“给关键字安排一个初始座位”。

比如：

输入关键字 84
通过某个函数算出地址
比如得到 6
那我们就先尝试把它放到第 6 个位置

理想情况下：

每个关键字都映射到不同位置
查找时一步到位

但现实通常没这么理想，因为可用位置有限，而关键字空间很大。

所以散列函数真正做的是：

给出一个“首选位置”
不是绝对保证不冲突

19.3 什么叫冲突，为什么冲突不可避免¶

冲突就是：

两个不同的关键字
通过散列函数
映射到了同一个地址

比如：

19 % 13 = 6
84 % 13 = 6

那它们都想占第 6 号位置，就冲突了。

这一点一定要接受：

冲突不是程序写错了，而是 Hash 表天生要处理的正常现象。

真正要比较优劣的，不是“有没有冲突”，而是：

冲突多不多
冲突后怎么处理
处理后平均查找长度大不大

19.4 开放定址法怎么理解¶

开放定址法可以想得非常形象：

你本来想坐 6 号座位
发现 6 号已经有人了
那就继续找下一个可用座位

所以它的核心不是“换一张表”，而是：

冲突后，继续在表内找别的位置。

这也是为什么书上会写成：

初始地址 H(key)
冲突后再产生 H1
再冲突就继续 H2

本质上就是一条“探测路径”。

19.5 线性探测为什么容易产生堆积¶

线性探测是最常见的开放定址法：

冲突了就看下一个位置
还冲突就继续往后看
到表尾就绕回表头

它好理解，但有一个经典问题：堆积。

更形象地说：

某几个关键字本来冲突
被迫顺着排到后面
后来的关键字又撞上这串连续区域
结果这片区域越来越挤

于是查找、插入时都容易在这片区域里反复比较。

所以线性探测最典型的副作用就是：

一旦某一段开始拥挤，后面会越来越挤。

19.6 拉链法怎么理解¶

拉链法可以理解成：

同一个地址不是只允许放一个元素
而是允许这个地址下面挂一条链表

于是：

映射到同一个地址的元素
都挂在同一个桶下面

它的好处是：

冲突不需要在表里继续探测
插入删除通常更自然

但也有代价：

会引入链表指针
如果某个桶太长，查找效率也会下降

19.7 开放定址法和拉链法怎么比较¶

这一组题特别常见。

更稳的比较方法是：

开放定址法
所有元素都还在同一张顺序表里
查找路径靠探测产生
删除时处理更麻烦，常涉及“逻辑删除”
拉链法
每个地址对应一个链表桶
冲突元素挂到同义词链上
插入删除通常更自然

所以如果题目强调：

频繁插入删除
冲突较多

那往往要优先想到拉链法更合适。

19.8 Hash 表查找成功和失败时在看什么¶

这一节的 ASL 题特别容易把人绕住。

更稳的理解方式是：

查找成功时
看目标关键字最终要比较几次才能找到
查找失败时
看为了确认“表里没有它”，要探测或遍历到什么程度

开放定址法里：

成功查找，看目标元素所在探测路径长度
失败查找，通常要一直探测到“真正空位置”才敢停

拉链法里：

成功查找，看桶中找到该元素前比较了几次
失败查找，看桶中元素全比完后仍没找到

所以成功和失败 ASL 的思路并不一样，不能混着算。

19.9 为什么开放定址法删除时不能随便物理删除¶

这是 Hash 表里特别高频、也特别容易错的一点。

如果在线性探测中直接把某个位置清空，可能会出问题：

后面某个元素其实是因为冲突才被探测到这里
你把前面那个位置直接清成“空”
后续查找时一旦探测到这个空位，就会误以为查找失败

所以开放定址法里删除常常不是直接物理清空，而是：

打删除标记
告诉系统“这里原来占过，但现在删掉了”

这样后续查找时才不会把探测路径截断。

19.10 7.5 和代码怎么对上¶

当前第 7 章首稿代码已经把这一节最核心的两类实现落下来了。

开放定址法：

第7章普通代码版（约第478行）
第7章普通代码版（约第506行）

对应函数：

HashOpenInsert
HashOpenSearch

拉链法：

第7章普通代码版（约第577行）
第7章普通代码版（约第597行）

对应函数：

ChainHashInsert
ChainHashSearch

再配合演示主函数：

第7章普通代码版（约第660行）

学生现在已经可以把“书上讲的冲突处理”直接和真实运行结果对起来看。

19.11 7.5 高频题统一抓法¶

这一节高频题大致可以归到下面几类：

给定散列函数，构造 Hash 表
给定冲突处理方法，写出插入过程
判断某元素查找成功时要比较几次
判断某元素查找失败时要比较几次
比较开放定址法和拉链法
分析堆积现象
删除操作为什么不能直接物理删除

看到题之后，先问自己：

它考的是“建表”
还是“查找路径”
还是“方法比较”

这一步会让解题速度快很多。

19.12 7.5 当前最容易丢分的点¶

这一节当前最容易丢分的地方主要有：

以为散列函数能完全避免冲突
不会区分“初始地址”和“冲突后的探测地址”
把开放定址法和拉链法的查找过程混在一起
线性探测时漏掉回绕到表头
删除时直接物理清空位置
成功 ASL 和失败 ASL 混着算
只会背“堆积”，但说不清它为什么会发生

20. 第7章题型索引¶

20.1 基本概念与效率指标类¶

这一类题主要围绕：

查找、查找成功、查找失败
静态查找与动态查找
平均查找长度 ASL
不同查找结构的适用场景

这类题看起来概念多，但本质上都在考：

你是否真的理解“结构”和“效率”之间的关系
你是否知道某种结构为什么适合某种场景

20.2 顺序查找、折半查找、分块查找类¶

这一类题主要包括：

顺序查找成功 / 失败 ASL
折半查找过程题
折半查找判定树
折半查找成功 / 失败 ASL
分块查找定位过程
为什么有序链表不适合折半查找

这类题的核心是：

能不能把“比较次数”具体地走出来
能不能把“有序”和“顺序存储”的条件分清

20.3 二叉排序树类¶

这一类题主要包括：

由插入序列构造 BST
BST 查找过程
BST 删除结点
BST 中序遍历性质
BST 与折半查找的比较

这类题的统一抓手是：

大小关系
中序有序
删除后仍要保持 BST 性质

20.4 AVL 和红黑树类¶

这一类题主要包括：

平衡因子判断
LL / RR / LR / RL 旋转题
最小不平衡子树
红黑树五条性质
AVL 和红黑树比较题

这类题最重要的是：

不要只背旋转名称
要看插入路径和失衡位置
要把“严格平衡”和“适度平衡”区分开

20.5 B 树和 B+ 树类¶

这一类题主要包括：

结点关键字数与孩子数关系
树高与关键字总数关系
插入分裂过程
删除借位 / 合并过程
B 树与 B+ 树差异
外存索引适用场景

这类题最该抓的是：

多路平衡
页 / 块与 I/O
分裂、借位、合并的主线

20.6 Hash 表类¶

这一类题主要包括：

散列函数构造表
冲突处理过程
线性探测查找路径
拉链法桶链长度
成功 / 失败 ASL
堆积现象
逻辑删除

这类题最该抓的是：

初始地址
冲突后的处理路径
成功和失败查找的区别

21. 刷题路径¶

21.1 基础训练：先把线性查找部分做稳¶

基础训练建议先刷：

顺序查找
折半查找
分块查找

目标不是求快，而是：

把 ASL 真正理解
把判定树看明白
把“有序 + 顺序存储”这个前提吃透

21.2 进阶训练：专刷 BST¶

进阶训练建议聚焦 BST 相关题：

插入序列构树
查找路径
删除结点
中序性质

这一部分的目标是：

让学生真正熟悉“大小关系编码进树结构”这件事
把 BST 和普通二叉树彻底区分开

21.3 强化训练：专刷 AVL 和红黑树¶

强化训练建议集中刷：

AVL 旋转题
最小不平衡子树题
红黑树性质判断题
AVL / 红黑树比较题

这一部分不要急着碰太多复杂实现题，先把：

失衡识别
旋转方向
红黑树性质

练稳。

21.4 第四轮：专刷 B 树和 B+ 树¶

第四轮建议刷：

性质题
树高题
插入分裂题
删除调整题
B 树 / B+ 树比较题

这一部分最重要的是：

不要死背
要画局部过程图
把“为什么适合外存”说清楚

21.5 第五轮：专刷 Hash 表¶

第五轮建议集中刷：

建表题
线性探测题
拉链法题
成功 / 失败 ASL
逻辑删除和堆积现象

这一部分建议做到：

路径能手推出来
不把开放定址法和拉链法混掉

21.6 第六轮：整章综合回刷¶

最后一轮建议把整章混着刷：

先判断题型
再调用对应方法

这一部分的目标不是“第一次会做”，而是：

看见题就知道它属于哪类
知道该调用哪条思路

22. 自学检查清单¶

22.1 概念层¶

学完第 7 章后，至少应该能不用看书直接说清：

静态查找和动态查找的区别
ASL 的含义
顺序查找、折半查找、分块查找的适用条件
BST、AVL、红黑树、B 树、B+ 树、Hash 表各自解决什么问题

22.2 线性查找层¶

你至少应该能做到：

手推顺序查找比较次数
手推折半查找过程
看懂并画出折半查找判定树
分清折半查找成功 / 失败 ASL
解释为什么有序链表不适合折半查找

22.3 树形查找层¶

你至少应该能做到：

根据插入序列构造 BST
判断 BST 删除操作是否正确
根据插入路径判断 AVL 失衡类型
说清 AVL 为什么只调整最小不平衡子树
说清红黑树和 AVL 的差异

22.4 B 树与 B+ 树层¶

你至少应该能做到：

说清多路平衡树出现的原因
说清 B 树为什么适合外存
判断 B 树结点关键字数与孩子数关系
看懂一次插入分裂和删除合并
分清 B 树和 B+ 树的记录存储差异

22.5 Hash 表层¶

你至少应该能做到：

根据散列函数构造表
手推线性探测过程
手推拉链法建表过程
分析堆积现象
解释为什么开放定址法删除常用逻辑删除
分清成功查找和失败查找的 ASL

22.6 代码层¶

你至少应该能做到：

看懂 第7章普通代码版 中的顺序查找、折半查找、分块查找
看懂 第7章普通代码版 中的 BST 查找、插入、删除
看懂 第7章普通代码版 中的 AVL 插入和旋转
看懂 第7章普通代码版 中的开放定址法和拉链法实现
卡住时能切到 第7章逐行注释版代码

22.7 阶段总结¶

到这里，第 7 章已经不只是“启动版”了，而是已经进入了“章节成品化中段”：

主线讲义已经搭起来
代码首稿已经完成
逐行注释版已经补上
题型索引、刷题路径、自学检查也已经补上

这意味着后面继续推进原书试题整理和详细解答时，已经有很稳的底座可用。

23. 原书试题区整理版¶

23.1 这一版整理的作用¶

这一部分不是把原书题目机械抄一遍，而是把原书试题按“考法”重新归类。

这样整理的目的有两个：

学生一看到题，先能判断题型，不会把整章题目看成一团
后面做逐题详细解答时，可以直接沿着这个分类继续展开

当前这一版主要先做三件事：

把原书第 7 章试题按知识块重新归类
每类题都给出“它在考什么”
给出对应的做题思路和易错点

23.2 基本概念与效率指标题¶

这一类题通常围绕：

静态查找和动态查找
平均查找长度 ASL
各种查找结构的适用场景
哪种结构更适合查找、插入、删除

这类题表面看像概念选择题，实际上在考：

你有没有把“结构”和“效率”对应起来
你是否真的理解某种查找方式依赖什么前提

做题思路：

先判断题目问的是“定义”还是“适用条件”
再判断它问的是“查找效率”还是“维护代价”
最后再选最匹配的结构

易错点：

把“查找快”误解成“所有操作都快”
把“结构更复杂”误解成“一定更优”

23.3 顺序查找、折半查找、分块查找题¶

这一类题通常围绕：

顺序查找成功 / 失败 ASL
折半查找过程
折半查找判定树
折半查找比较次数
分块查找过程
为什么有序链表不适合折半查找

这类题最常考的不是大定义，而是：

你能不能手推查找过程
你是否真的理解折半查找的前提
你会不会把判定树和 BST 搞混

做题思路：

顺序查找题：盯比较次数
折半查找题：盯 low / high / mid
判定树题：盯每次被比较的中点
分块查找题：先看索引，再进块内

易错点：

折半查找边界写错
成功 ASL 和失败 ASL 混着算
误以为有序链表也适合折半查找

23.4 二叉排序树题¶

这一类题通常围绕：

根据关键字序列构造 BST
BST 的查找路径
BST 删除结点
BST 和折半查找的比较
BST 的中序遍历性质

这类题最核心的考点只有两条：

大小关系是否始终成立
中序遍历是否保持递增

做题思路：

构树题：按插入顺序一个一个插
删除题：先判断删的是叶子、单孩子还是双孩子
比较题：分清 BST 适合动态查找，折半查找更适合静态有序表

易错点：

插入时跳步
删除双孩子结点时不知道找后继 / 前驱
把 BST 当普通二叉树来做

23.5 AVL 和红黑树题¶

这一类题通常围绕：

AVL 平衡因子
LL / RR / LR / RL 旋转
最小不平衡子树
红黑树性质判断
红黑树和 AVL 的比较

这类题真正考的是：

你会不会看插入路径
你能不能根据失衡位置判断旋转方式
你是否知道红黑树的工程定位

做题思路：

AVL 题先画插入路径
再找最小不平衡子树
再判断外侧高还是内侧高
红黑树题优先对照五条性质逐条排除

易错点：

LR / RL 题时想当然地单旋
把红黑树的“黑高相等”理解成“树高相等”
误以为红黑树查找一定比 AVL 更快

23.6 B 树和 B+ 树题¶

这一类题通常围绕：

结点关键字数、孩子数和阶数关系
树高与关键字总数关系
B 树插入分裂
B 树删除借位 / 合并
B 树与 B+ 树差异
文件索引 / 数据库索引适用场景

这类题最难的地方不是定义本身，而是：

规则多
过程长
容易把“根结点特例”和“普通结点规则”混掉

做题思路：

性质题：先写上下界关系
过程题：先画局部，不要一口气画全树
比较题：先判断问的是“记录放哪”还是“谁适合范围查询”

易错点：

孩子数和关键字数关系记错
分裂时不知道谁上移
删除时不知道先借还是先合并
把 B 树和 B+ 树的索引层、叶子层作用混掉

23.7 Hash 表题¶

这一类题通常围绕：

给定散列函数构造表
开放定址法冲突处理
拉链法构造和查找
成功 / 失败 ASL
堆积现象
删除时的逻辑删除

这类题最像“过程模拟题”，做题时一定要肯一步步写。

做题思路：

先算初始地址
再按题目给的冲突处理规则继续走
成功题就走到找到为止
失败题就走到确认失败为止

易错点：

漏掉回绕
把线性探测和拉链法混着算
不理解为什么开放定址法删除常用逻辑删除

23.8 这一版整理后的使用方法¶

现在最推荐这样用这部分：

做题前先看题型分类，判断题目属于哪一类
做题时按该类题的固定思路去推
做完后再回看对应章节内容和代码

这样用会比“从头往后乱刷”更稳，因为它会强迫学生先建立题型识别能力。

24. 原书试题逐题详细解答版（基础部分）¶

24.1 高频题 1：为什么有序链表不适合折半查找¶

题目本质：

这类题不是在问“链表能不能有序”，而是在问：

链表这种存储结构，能不能低代价地支持折半查找的关键动作。

正确结论：

有序链表通常不适合折半查找
原因不是它无序，而是它不支持像顺序表那样快速定位中间元素

详细思路：

折半查找每一步都依赖“直接访问中间位置”
在顺序表中，访问 A[mid] 很自然
在链表中，想拿到中间结点，往往仍要从头走过去
这样“折半缩区间”的优势会被找中点的线性代价抵消

易错点：

只看到“有序”就条件反射想到折半查找
忽略了“存储结构是否支持随机访问”这个关键前提

24.2 高频题 2：折半查找判定树到底在表示什么¶

题目本质：

这类题不是在考你会不会画图，而是在考：

你是否把折半查找的比较过程真正树形化了。

正确结论：

判定树中的每个内部结点，对应一次真实比较到的元素
元素所在层数，就对应查找这个元素时的比较次数
失败查找时，要看失败结点或空位置所在层数

详细思路：

折半查找第一次比较的是整个区间的中点
所以中点元素就是判定树根结点
左区间的中点成为左子树根
右区间的中点成为右子树根
继续递归展开，就得到整棵判定树

易错点：

把判定树误画成 BST
把“元素值大小关系”当成判定树结构来源
忘记失败查找看的不是成功结点，而是失败位置

24.3 高频题 3：BST 的中序遍历为什么一定递增¶

题目本质：

这类题表面是性质题，实际上在考 BST 的定义有没有真正吃透。

正确结论：

BST 中序遍历结果一定是递增序列

详细思路：

BST 定义规定：左子树关键字都小于根，右子树关键字都大于根
中序遍历顺序是“左、根、右”
所以访问顺序天然满足“左边都比根小，右边都比根大”
递归到每棵子树也仍成立

易错点：

只会背结论，不会解释为什么
把普通二叉树和 BST 混起来，误以为任何二叉树中序都可能有序

24.4 高频题 4：BST 删除双孩子结点时为什么要找后继或前驱¶

题目本质：

这类题在考：

删除一个结点后，怎样在不破坏 BST 有序性的前提下把坑补上。

正确结论：

删除有两个孩子的结点时，常用右子树最小结点或左子树最大结点替代

详细思路：

直接删掉当前结点后，这个位置必须有人顶上
顶上来的人必须满足：
比左子树所有结点大
比右子树所有结点小
右子树最小结点正好满足这个条件
左子树最大结点也同样满足

易错点：

随便找一个孩子替代
只替换值，不继续删除原来的后继 / 前驱结点

24.5 高频题 5：AVL 插入后为什么只调整最小不平衡子树¶

题目本质：

这类题在考 AVL 调整的局部性。

正确结论：

插入后，从插入结点向上回溯遇到的第一个失衡结点，就是最小不平衡子树根
只要把这棵子树调整好，整棵树就能恢复平衡

详细思路：

插入前整棵树是平衡的
插入后，只有插入路径上的结点高度可能改变
最先失衡的那个结点，就是最低层的失衡点
对它做旋转，能把这部分局部高度关系恢复正常
更高层的结构也因此重新合法

易错点：

以为要从根一路调整到叶
不会判断“第一个失衡点”才是调整对象

24.6 高频题 6：如何快速判断 LL、RR、LR、RL¶

题目本质：

这类题不是在考你背缩写，而是在考你能不能从插入路径识别失衡类型。

正确结论：

看插入路径是“外侧高”还是“内侧高”
外侧高用单旋，内侧高用双旋

详细思路：

LL
根 -> 左 -> 左
右旋
RR
根 -> 右 -> 右
左旋
LR
根 -> 左 -> 右
先左旋再右旋
RL
根 -> 右 -> 左
先右旋再左旋

易错点：

只看“左高还是右高”，不看插入发生在内侧还是外侧
LR、RL 时还想当然地用单旋

24.7 高频题 7：红黑树为什么说是“适度平衡”¶

题目本质：

这类题在考你是否理解红黑树和 AVL 的定位差异。

正确结论：

红黑树并不像 AVL 那样追求严格高度平衡
它通过红黑性质限制树不能过分失衡，因此称为适度平衡

详细思路：

红黑树要求不能出现连续红结点
并要求从某结点到所有叶结点路径上的黑结点数相同
这两条会限制树的高度不要过大
但它不要求像 AVL 那样左右子树高度差必须不超过 1

易错点：

把“黑高相等”理解成“树高完全相等”
误以为红黑树一定比 AVL 查找更快

24.8 高频题 8：B 树为什么适合做外存索引¶

题目本质：

这类题不只是在考定义，而是在考你是否理解“页 / 块 / I/O”背景。

正确结论：

B 树适合外存索引，因为它是多路平衡树，树高更低，访问磁盘页的次数更少

详细思路：

外存访问代价大，关键目标是减少层数
B 树一个结点可容纳多个关键字和多个孩子
一层能分出更多分支，所以树比二叉平衡树更矮
每下降一层往往对应一次页访问，因此总 I/O 次数减少

易错点：

只说“B 树快”，但说不出快在哪
只看关键字比较次数，不看 I/O 次数

24.9 高频题 9：B+ 树和 B 树最大的区别抓什么¶

题目本质：

这类题在考“结构差异”和“应用差异”的对应关系。

正确结论：

B+ 树非叶结点主要用于索引
叶结点保存全部关键字对应的信息
叶结点通常按关键字顺序链接，顺序访问更方便

详细思路：

B 树中，非叶结点也可能存有效记录信息
B+ 树中，非叶结点更像目录
真正完整的数据更集中在叶子层
所以范围查询、顺序查询通常更适合 B+ 树

易错点：

只会背“B+ 树适合数据库”
却说不出它为什么更适合顺序和范围访问

24.10 高频题 10：Hash 表冲突为什么不是错误¶

题目本质：

这类题在考你是不是把 Hash 表理解成“理想一一映射”。

正确结论：

冲突是 Hash 表的正常现象，不是程序写错了
关键在于如何处理冲突

详细思路：

关键字空间通常远大于表长
多个不同关键字映射到同一地址是自然现象
所以 Hash 表设计时，本来就预设了冲突会出现
开放定址法和拉链法，本质上都是冲突处理方案

易错点：

认为“好的散列函数就不会冲突”
把“冲突少”误解成“绝不冲突”

24.11 高频题 11：为什么开放定址法删除不能随便物理删除¶

题目本质：

这类题在考你是否理解“探测路径不能被截断”。

正确结论：

开放定址法删除时常用逻辑删除，不能随便物理清空

详细思路：

某元素被放到后面，往往是因为前面发生了冲突
如果前面某个位置直接物理清空
后续查找探测到这里时，可能会误判“查找失败”
这样就会把原本应该继续向后找的路径截断

易错点：

把顺序表删除的直觉直接搬到开放定址法里
忘记“查找失败往往是碰到真正空位置才成立”

24.12 基础题解学习提示¶

这一部分先覆盖的是第 7 章最核心、最常见、最能建立题感的一批题：

折半查找前提与判定树
BST 性质与删除
AVL 调整
红黑树定位
B 树 / B+ 树高频区别
Hash 表冲突与删除

这意味着第 7 章现在已经不只是有“题型目录”，而是开始有“逐题详解层”了。

24.13 高频题 12：顺序查找成功 ASL 为什么是 `(n + 1) / 2`¶

题目本质：

这类题不是单纯在考公式，而是在考你是否理解“平均比较次数”是怎么来的。

正确结论：

在等概率情况下，顺序查找成功时的平均查找长度为 (n + 1) / 2

详细思路：

第一个元素被找到，需要比较 1 次
第二个元素被找到，需要比较 2 次
第三个元素被找到，需要比较 3 次
一直到第 n 个元素，需要比较 n 次
如果每个元素被查到的概率都相同，那么平均比较次数就是：
(1 + 2 + ... + n) / n
结果就是 (n + 1) / 2

所以这个公式不是背出来的，而是“逐个位置平均”出来的。

易错点：

只背公式，不知道它从哪里来
把成功 ASL 和失败 ASL 混在一起

24.14 高频题 13：折半查找比较次数题怎么做最稳¶

题目本质：

这类题在考你是不是会把折半查找过程一步步展开，而不是凭感觉猜。

正确结论：

折半查找比较次数，等于目标元素在折半判定树中的层数
做题时最稳的方法，是把每一步中点写出来

详细思路：

先写当前区间的 low 和 high
算出 mid
判断当前元素和目标值的大小关系
再进入左半边或右半边
把比较路径完整写出来

例如路径若是：

23 -> 57 -> 68

那比较次数就是 3

易错点：

看到题目就直接口算
漏掉某一步区间更新
不会把比较路径和层数对应起来

24.15 高频题 14：由给定序列构造 BST 时，为什么有的序列结果相同¶

题目本质：

这类题在考你是否理解“BST 结构由插入顺序决定，但不是所有顺序变化都会改变树形”。

正确结论：

不同插入序列，可能构造出相同的 BST
关键不在于序列完全相同，而在于各元素相对地落入哪些子树

详细思路：

根结点由第一个插入元素决定
之后所有比根小的元素，一定落在左子树
所有比根大的元素，一定落在右子树
左子树内部、右子树内部又分别重复同样逻辑
因此，只要某些元素虽然顺序有变化，但它们在各级子树中的相对插入结构没变，最终树形也可能不变

易错点：

以为插入序列只要顺序不同，BST 就一定不同
不会按“根、左子树、右子树”递归地分组分析

24.16 高频题 15：AVL 插入题为什么一定要先按 BST 插¶

题目本质：

这类题在考你有没有把“AVL 是在 BST 基础上做平衡”这件事真正理解到位。

正确结论：

AVL 插入第一步一定是按 BST 规则插入
只有插完之后，才谈平衡调整

详细思路：

AVL 本质上仍然是二叉查找树
所以大小关系这条主线不能破
先按 BST 规则找到空位置插入
插完之后再回溯检查哪里失衡
最后根据失衡类型做旋转

也就是说，AVL 不是“直接旋转插入”，而是“先插入、再修复”。

易错点：

一上来就想判断旋转，不先插入
旋转前就把结点位置改乱，破坏 BST 性质

24.17 高频题 16：B 树插入过程题，最关键的是谁上移¶

题目本质：

这类题在考你是不是抓住了 B 树插入分裂的核心动作。

正确结论：

当结点满而又要插入新关键字时，要分裂
分裂时，中间关键字上移到父结点

详细思路：

先把新关键字放进当前结点的有序位置
如果关键字数没有超界，插入结束
如果超界，就把当前结点分成左右两部分
中间关键字上移
父结点接收该关键字和新的孩子分支
如果父结点也满了，就继续向上分裂

所以这类题做题时，最关键的动作不是“左右怎么摆”，而是先盯住：

哪个关键字是中间关键字
它应该上移到哪里

易错点：

分裂时上移的不是中间关键字
左右分裂后关键字顺序被打乱
忘记分裂可能会继续向上传播

24.18 高频题 17：B 树删除过程题，为什么总是先看能不能借¶

题目本质：

这类题在考你是否理解 B 树删除后的“局部修复优先”思路。

正确结论：

删除后若结点关键字过少，先看相邻兄弟能不能借
借不到再考虑合并

详细思路：

删除后当前结点可能低于下界
如果兄弟结点有富余关键字，就优先借一个过来
同时父结点中相关关键字要跟着调整
如果兄弟也不富余，就只能合并
合并后父结点可能继续出问题，再向上处理

这类题的主线是：

先局部补救
不够再合并
合并后再看上层

易错点：

一上来就合并，不先判断能不能借
只调整孩子，不调整父结点中的分隔关键字

24.19 高频题 18：Hash 表构造题为什么一定要一步一步写¶

题目本质：

这类题在考的是过程模拟，不是概念背诵。

正确结论：

Hash 表构造题一定要按关键字输入顺序，一个一个插
每个关键字都要完整走完“算地址 -> 冲突处理 -> 最终落点”

详细思路：

先对当前关键字求散列地址
看该位置是否冲突
如果冲突，就按题目指定方法继续探测或挂链
确定最终落点后，再处理下一个关键字

这类题手算时，最怕“脑中省略步骤”，因为一旦前面某个关键字落点算错，后面全错。

易错点：

不按输入顺序构造
少写一次冲突处理步骤
开放定址法忘记回绕

24.20 高频题 19：Hash 表成功 / 失败 ASL 题该怎么分开做¶

题目本质：

这类题在考你是不是把“找到目标”和“确认不存在目标”当成两种不同过程。

正确结论：

成功 ASL 看的是已有元素被找到前的比较次数
失败 ASL 看的是确认目标不存在之前经历的探测或比较次数

详细思路：

开放定址法：

成功 ASL
看每个已插入元素的探测次数
失败 ASL
看从各起始地址出发，要走到真正空位置为止的探测次数

拉链法：

成功 ASL
看链上元素被找到前比较了几次
失败 ASL
看整条链比完后仍找不到的比较次数

所以成功和失败 ASL 不能混成一套公式，而要先分清题目在问什么。

易错点：

直接把成功查找的比较次数拿去算失败 ASL
不会区分“探测次数”和“关键字比较次数”

24.21 进阶题解学习提示¶

这一部分覆盖的是第 7 章里最容易拉开差距的过程题和效率题：

顺序查找 ASL
折半查找比较次数
BST 构树题
AVL 插入题
B 树插入 / 删除过程题
Hash 建表与 ASL 题

学完这一部分后，第 7 章已经不只是“讲义 + 题型目录”，而是开始具备比较完整的题解层了。

25. 第7章后半段代码专题：红黑树、B树、B+树¶

本节学习重点，是把第 7 章里最容易让学生仍想翻回原 PDF 看图和过程的后半段，再往代码层推进一大步。

本节重点补三块内容：

红黑树：从“只会背性质”推进到“能看真实插入代码”
B 树：从“只会做过程题”推进到“能跑查找和插入代码”
B+ 树：从“只会说适合数据库”推进到“能看叶子链、查找和范围查询”

25.1 红黑树的真实代码覆盖内容¶

之前第7章里的红黑树，主要还是：

性质
和 AVL 的比较
高频判断题

代码层已经补入以下内容：

RBNode
IsRedRB
CreateRBNode
RBRotateLeft
RBRotateRight
RBFlipColors
RBInsert
RBSearch
RBInorder

这里采用更适合教学的“左倾红黑树”写法。
它的好处是：

旋转逻辑更集中
更容易把“红链接”和 2-3 树的对应关系讲清楚
不会一上来就把学生拖进工业级删除修复细节

所以现在这一块已经不再只是“知道有红黑树”，而是开始能真正看到：

为什么会旋转
为什么要翻转颜色
为什么它说是“适度平衡”

25.2 B 树的真实代码覆盖内容¶

B 树已经不再只停留在讲义和过程题层，而是已经落到真实代码层：

BTreeNode
CreateBTreeNode
BTreeSearch
BTreeSplitChild
BTreeInsertNonFull
BTreeInsert
BTreePrint

现在学生可以直接对着代码理解：

一个结点为什么能装多个关键字
结点满了以后为什么要分裂
为什么中间关键字会上移
为什么树高会被压低

程序输出里也已经能直接看到树形结果，而不只是纸面描述。

25.3 B+ 树的真实代码覆盖内容¶

B+ 树这一部分优先补入的是最应该先落地的内容：

BPlusNode
BuildSampleBPlusTree
BPlusFindLeaf
BPlusSearch
BPlusPrintLeaves
BPlusPrintRange

这套代码重点不在于一上来就把完整插入 / 删除写到最复杂，而是先把最关键的三个直觉跑出来：

非叶结点主要做索引
叶结点按顺序串起来
范围查询为什么会自然很多

也就是说，现在学生已经可以不靠抽象描述，而是直接从程序输出里理解：

B+ 树叶子链长什么样
为什么范围查询可以沿叶子链扫
为什么它比 B 树更适合顺序访问

25.4 新增代码阅读重点¶

当前第7章代码里，后半段最值得优先看的函数现在是：

第7章普通代码版 里的 RBInsert
第7章普通代码版 里的 RBRotateLeft
第7章普通代码版 里的 RBRotateRight
第7章普通代码版 里的 BTreeSplitChild
第7章普通代码版 里的 BTreeInsert
第7章普通代码版 里的 BPlusFindLeaf
第7章普通代码版 里的 BPlusPrintRange

程序现在新增的关键输出包括：

Red-black inorder
Red-black search 45
B-tree structure
B-tree search 35
B+ leaves
B+ search 24
B+ range [18, 42]

这意味着第7章后半段终于不再只是“概念能讲”，而是已经开始“结构能跑，结果能看”。

25.5 后半章能力提升¶

学完这一部分以后，第7章变化最大的地方是：

红黑树已经从纯概念层推进到真实插入代码层
B 树已经从过程题层推进到真实查找 / 插入代码层
B+ 树已经从抽象比较层推进到可运行的查找 / 范围查询演示层

这一步非常关键，因为它直接减少了学生在第7章后半段回原 PDF 查图、查过程、查结构的需要。

25.6 代码专题与题解对照：红黑树、B树、B+树¶

为使新增代码不只是“能跑”，而且能够真正对上高频题型，这里把第 7 章后半段最容易卡住学生的几类题，再往“代码视角”补了一层。

第一类是红黑树插入题。
这类题以前最容易停在“记五条性质”和“背几种调整情况”，但现在更适合直接对着 第7章普通代码版 里的 RBInsert、RBRotateLeft、RBRotateRight 来看。
最该抓的不是“颜色变化很花”，而是下面这条主线：

先按二叉查找树规则插进去
如果出现右红左黑，就左旋，把红链接往左收
如果出现连续左红，就右旋，避免一条链过长
如果左右孩子都红，就翻色，把“临时 4-结点”往上推

这样做以后，红黑树插入题就不再只是纸面变色游戏，而是能和真实函数里的局部调整一一对上。
学生现在做这类题时，最稳的想法应该是：
“我不是在背图，而是在模拟 RBInsert 递归回溯时依次做哪些修复。”

第二类是 B 树插入和分裂题。
这类题最容易让人乱的地方，是“到底哪个关键字上移、分裂后左右各剩谁、父结点什么时候会继续满”。
现在更适合直接对着：

第7章普通代码版 里的 BTreeSplitChild
第7章普通代码版 里的 BTreeInsert

来理解。
BTreeSplitChild 这段代码本质上就在做三件事：

把满孩子拆成左右两个结点
把中间关键字上移到父结点
给父结点腾出新的孩子指针位置

所以做 B 树插入题时，最稳的不是凭感觉画，而是每一步都问自己：

当前插入前，这个孩子是不是满的
如果满了，中间关键字是谁
分裂后，我接下来应该下沉到左边还是右边继续插

只要这三问不乱，B 树过程题通常就不会崩。

第三类是 B 树查找题。
很多学生纸面上会说“在结点里顺序比较”，但真正做题时还是会混。
现在对着 BTreeSearch 看，会更容易理解它本质是在做：

先在当前结点内部定位关键字应落在哪个区间
找到就返回
找不到就沿对应孩子继续下探

也就是说，B 树查找题最核心的不是“层数多不多”，而是“结点内区间判断”有没有做对。
学生以后看到这类题，应该先盯“当前关键字落在两个已有关键字之间，还是落在最左 / 最右区间”，这样会比单纯背定义稳得多。

第四类是 B+ 树范围查询题。
以前这类题经常只停留在一句话：
“B+ 树更适合范围查询。”
但现在可以直接对着：

第7章普通代码版 里的 BPlusFindLeaf
第7章普通代码版 里的 BPlusPrintRange

来看它为什么天然更顺。
这两段代码已经把最关键的直觉跑出来了：

先定位到起始关键字所在叶结点
再沿叶子链顺序扫描
扫到超过右边界就停

这意味着以后做“为什么 B+ 树更适合数据库索引 / 范围查询”的题，就不需要回原书找抽象描述了。
直接记成一句更像程序的话就够了：
“先找入口叶子，再沿叶子链顺扫。”

第五类是最适合立刻回刷的后半段题型。
如需把第 7 章后半段与新代码真正联动起来，建议优先回刷以下题型：

红黑树插入后颜色与旋转判断题
B 树结点分裂与关键字上移题
B 树查找路径判断题
B+ 树叶结点、索引结点和范围查询题

因为这几类题现在已经不再只是“讲义里能解释”，而是“代码里能对应”。

经过上述讲解和代码补充后，第 7 章后半段终于形成了一个更完整的闭环：

概念能讲
结构能画
过程能做
代码能跑
题型能对齐

这会继续减少学生在红黑树、B 树、B+ 树这三块回原 PDF 查图和查过程的需要。

25.7 删除与调整代码专项：红黑树、B树、B+树¶

这里继续把第 7 章后半段往“尽量不回原 PDF”推进的关键点，是把最容易被卡住的“删除 / 调整”部分也真正补到了代码层。

先说红黑树。
前一轮它已经能插入，但很多学生真正会回原书的地方，其实是：
“删除以后为什么还要继续修？”
代码中已经补入以下内容：

第7章普通代码版 里的 RBMoveRedLeft
第7章普通代码版 里的 RBMoveRedRight
第7章普通代码版 里的 RBFixUp
第7章普通代码版 里的 RBDeleteMin
第7章普通代码版 里的 RBDelete

这一组函数最该抓的主线不是“删除分多少情况”，而是：

删除前先把要下探的那一边尽量变成“可删状态”
删完回来以后再统一做 FixUp
红黑树删除并不是单独一坨，而是“下探修路 + 回溯收口”

所以以后学生做红黑树删除题时，最稳的理解不应该只是背图，而应该是：
“删除前要先保证路径上不会出现无法继续往下删的黑链问题。”

再说 B 树。
B 树最容易让学生在题目里回原书的地方，就是删除时到底什么时候借、什么时候合并、什么时候往前驱 / 后继转。
真实代码已经补入以下内容：

第7章普通代码版 里的 BTreeFindKey
第7章普通代码版 里的 BTreeBorrowFromPrev
第7章普通代码版 里的 BTreeBorrowFromNext
第7章普通代码版 里的 BTreeMergeChildren
第7章普通代码版 里的 BTreeFillChild
第7章普通代码版 里的 BTreeDeleteFromNode
第7章普通代码版 里的 BTreeDelete

这几段代码其实把 B 树删除题最核心的判断顺序已经固定下来了：

先看目标关键字是不是就在当前结点
如果在内部结点，再看左孩子或右孩子能不能借出足够关键字
如果都借不出来，就先合并，再继续删
如果目标关键字不在当前结点，就先保证要下探的孩子不“太瘦”，再继续往下走

也就是说，现在学生再做 B 树删除题，不需要再依赖原书图示逐格照抄了。
更稳的做法是：
“每一层先判断借还是并，再判断继续往哪边删。”

最后说 B+ 树。
这一块以前最虚的地方，是大家都知道它适合范围查询，但一问插入 / 删除后叶子链怎么维护，就又容易回原书。
代码已经补入以下内容：

第7章普通代码版 里的 BPlusInsert
第7章普通代码版 里的 BPlusInsertRecursive
第7章普通代码版 里的 BPlusBorrowFromPrev
第7章普通代码版 里的 BPlusBorrowFromNext
第7章普通代码版 里的 BPlusMergeChildren
第7章普通代码版 里的 BPlusDeleteRecursive
第7章普通代码版 里的 BPlusDelete

这一组函数最该抓的，是下面这条非常“工程化”的主线：

插入时先把数据真正落到叶结点
叶结点满了再分裂，并把右侧最小关键字往上提
删除时如果叶子太空，就优先借，再考虑合并
一旦合并，叶子链也要同步维护

这个顺序一旦理解了，学生对 B+ 树就不再只停在“数据库喜欢用它”，而是开始真的知道它为什么能一边维护层次索引，一边维持顺序访问能力。

至此，第 7 章后半段又多形成了一层闭环：

插入能看懂
删除能看懂
调整能看懂
输出结果能验证

当前程序里已经能直接看到这些新增验证点：

Red-black inorder after deleting 20
B-tree after deleting 30
After inserting 44 and 46
After deleting 24

这意味着现在学生不只是能看“查找结构长什么样”，还开始能看“结构在修改后会变成什么样”。
这一步对于减少回原 PDF 查过程图，非常关键。

站内代码入口¶

对应代码专题：第7章查找代码
如果你想逐行对照实现，建议把正文页和代码专题页一起打开。

继续阅读¶

← 上一章：第6章图下一章：第8章排序 →

第7章 查找 自学版¶

1. 本章定位¶

2. 学习目标¶

3. 前置知识¶

4. 本章结构总览¶

5. 7.1 查找的基本概念¶

5.1 什么叫查找¶

5.2 静态查找和动态查找¶

5.3 平均查找长度 ASL¶

6. 7.2 线性结构中的查找¶

6.1 顺序查找¶

6.2 折半查找¶

6.3 分块查找¶

7. 7.3 树形查找¶

7.1 二叉排序树 BST¶

7.2 为什么 BST 会退化¶

7.3 平衡二叉树 AVL¶

7.4 红黑树¶

8. 7.4 B 树和 B+ 树¶

9. 7.5 散列（Hash）表¶

9.1 散列思想¶

9.2 两类高频冲突处理方法¶

10. 第7章代码阅读入口¶

14. 当前边界说明¶

14. 7.2 重点展开¶

14.1 顺序查找再讲透一点¶

14.2 顺序查找的 ASL 怎么理解¶

14.3 顺序查找：原书思路版伪代码¶

14.4 顺序查找：对应真实代码¶

14.5 折半查找再讲透一点¶

14.6 折半查找的判定树怎么理解¶

14.7 折半查找：原书思路版伪代码¶

14.8 折半查找：对应真实代码¶

14.9 折半查找为什么不能随便用¶

14.10 分块查找再讲透一点¶

14.11 分块查找：原书思路版伪代码¶

14.12 分块查找：对应真实代码¶

14.13 7.2 三种查找方法怎么放在一起比较¶

14.14 7.2 高频易错点¶

15. 7.2 进一步展开¶

15.1 折半查找判定树例题怎么做¶

15.2 折半查找成功 ASL 的例题直觉¶

15.3 折半查找失败 ASL 为什么常常更绕¶

15.4 一个最典型的折半查找比较次数题¶

15.5 顺序查找和折半查找的 ASL 对比怎么看¶

15.6 为什么有序链表不适合折半查找¶

15.7 分块查找例题的固定做法¶

15.8 7.2 高频题统一抓法¶

15.9 7.2 当前最容易丢分的点¶

15.10 本节小结¶

16. 7.3 重点展开¶

16.1 BST 不是“另一种二叉树”，而是“带查找规则的二叉树”¶

16.2 BST 查找：原书思路版伪代码¶

16.3 BST 查找：对应真实代码¶

16.4 BST 插入：本质上是在找“应该落在哪里”¶

16.5 BST 插入：原书思路版伪代码¶

16.6 BST 删除为什么最容易出错¶

16.7 BST 删除：对应真实代码¶

16.8 AVL 为什么比 BST 更稳¶

16.9 AVL 的四种失衡类型怎么理解¶

16.10 AVL 旋转：对应真实代码¶

16.11 AVL 插入：原书思想和真实代码怎么对上¶

16.12 红黑树先抓概念，不先硬啃实现¶

16.13 BST、AVL、红黑树怎么放在一起比较¶

16.14 7.3 高频易错点¶

17. 7.3 进一步展开¶

17.1 BST 高频题：中序遍历为什么总是有序¶

17.2 BST 高频题：由插入序列构造 BST 时该怎么想¶

17.3 BST 高频题：删除结点后树形为什么可能变化很大¶

17.4 AVL 高频题：为什么插入后只调整最小不平衡子树¶

17.5 AVL 典型例题：LL 和 RR 怎么快速判断¶

17.6 AVL 典型例题：LR 和 RL 为什么一定是双旋¶

17.7 AVL 插入调整题的固定做法¶

17.8 红黑树高频题：先抓五条性质¶

17.9 红黑树和 AVL 的高频比较题¶

17.10 7.3 高频选择题统一抓法¶

17.11 7.3 当前最容易丢分的点¶

17.12 本节小结¶

18. 7.4 重点展开¶

18.1 为什么学到这里会突然出现 B 树¶

第7章查找自学版¶

24.13 高频题 12：顺序查找成功 ASL 为什么是 `(n + 1) / 2`¶