备考数据结构大多数人一上来就啃代码结果“查找”这一章学完问起折半查找凭什么快、哈希表为什么能O(1)、B树和B树到底解决什么问题脑子里只有一堆零散的函数名。尤其是考研复习时间紧、题目活你得先把“查找”背后的逻辑链条拉直——这章真正考的不是你背了多少代码而是你对“比较”和“分布”的理解有多深。这篇就是纯概念、纯原理、纯手算的梳理不含一行代码。所有结论都能在草稿纸上推出来能自己模拟一遍那考场上无论出选择题还是大题你都稳。1. 查找复习的整体框架先搞懂“查找”到底在查什么1.1 查找的核心衡量指标ASL才是唯一的尺子查找这件事本质上就是在一堆数据里定位某个目标。你从第一个元素一个个往后比和直接按下标取差别就是“比较了多少次”。考试里衡量一个查找算法好坏的指标叫平均查找长度ASLAverage Search Length定义是ASL Σ(Pᵢ × Cᵢ)Pᵢ 是查第 i 个元素的概率Cᵢ 是查到它需要的比较次数。如果默认每个元素等概率那 Pᵢ 1/nASL 就纯粹取决于比较次数之和除以 n。这里有个特别容易踩的坑ASL 分“查找成功”和“查找失败”两种情况。很多同学只记成功时的公式结果题目一问“查找失败的平均查找长度”直接懵。失败 ASL 计算的是“为了确定目标不存在需要比较多少次才能停”它依赖的是查找路径上的空位置判断次数而不是把表里元素全数一遍。后面讲折半和哈希的时候这个区分特别关键。1.2 静态查找结构全家桶顺序表、有序表、索引表考研大纲里查找部分先讲三种“静态”结构它们的特点是一个数据进去就不动了重点在于怎么组织才能少比较顺序查找无序表、链表都能用从头比到尾。成功 ASL (n1)/2失败 ASL n1加了哨兵之后是 n1 次比较因为最后一次比较是和哨兵比然后确定失败。折半查找前提是顺序存储且有序。每次跟 mid 比缩小一半范围成功 ASL 约等于 log₂(n1) - 1但是精确值要通过“判定树”算不能光套对数。分块查找块间有序、块内任意。先用折半或顺序查索引表确定块再在块内顺序查。ASL 查索引表 ASL 查块内 ASL。这三种结构的学习顺序其实暗含了一条线数据从无序到有序查找策略从“傻乎乎地全比”到“聪明地跳着比”。分块查找则是中间态——不想花 O(n log n) 的代价把所有数据排好序那就只排“块”的索引用空间换查找时间。这个思想后面哈希表还会再用一次。1.3 动态查找结构数据要变光排序不够顺序、折半、分块都是“静态查找”因为一旦插入、删除要么数组整体移动要么索引需要重建。可真实场景里数据是会变的——数据库加一条记录、符号表里删一个变量你不能每次都重排。于是有了动态查找结构二叉排序树BST中序遍历有序插入删除都是 O(树高)。平衡二叉树AVL强制左右子树高度差不超过 1保证树高 O(log n)。B 树、B 树多路平衡查找树一个结点存多个关键字专门为磁盘设计。哈希表不是“比较”而是“计算地址”从根上改变查找方式。动态结构是考研大题和选择题的密集区尤其是 BST 和 AVL 的“手工模拟”题你必须能在纸上画出每一轮插入、旋转后的样子。接下来一章一章拆。2. 二叉排序树与平衡二叉树动态查找的分水岭2.1 二叉排序树插入规则很简单但删除才是大坑BST 的定义一句话左子树所有结点值 根结点值 右子树所有结点值且左右子树也是 BST。因此中序遍历它得到的就是递增序列。这个性质极其重要很多证明题都是围绕它展开的。插入操作规则统一从根开始比当前结点小往左走比当前结点大往右走直到空位就挂上去。新结点一定是叶子不会破坏原结构所以插入相对无脑。删除就麻烦多了分三种情况这是必考手工模拟的点删除叶子结点直接摘掉父结点对应指针置空。删除只有一棵子树的结点用它的孩子顶替自己就像“孙子直接接爷爷的班”。删除有两棵子树的结点这里有两种策略。一种是用前驱左子树中最大的结点顶替另一种是用后继右子树中最小的结点顶替。找到前驱/后继后把它的值复制到被删结点位置然后删掉那个前驱/后继——而前驱/后继一定只有一棵子树或没有子树问题又回到了情况 1 或 2。很多同学搞不清楚“前驱后继到底是谁”我教你个土办法对 BST 做中序遍历被删结点的前驱就是中序序列里它前面的那个元素后继就是它后面的那个元素。不用去背“左子树最右”这种绕口的话画中序序列一眼就能看出来。2.2 AVL 平衡旋转四个旋转方向本质就一句话BST 最怕输入序列有序比如 1,2,3,4,5 依次插入BST 直接退化成长链查找长度从 O(log n) 变 O(n)。AVL 就是给 BST 加了个规矩每个结点的左右子树高度差平衡因子绝对值不得超过 1一旦超了就要旋转调整。平衡因子 左子树高度 - 右子树高度取值只能是 -1、0、1。插入一个结点后从插入点向上回溯找到第一个平衡因子变成 ±2 的结点以它为根做旋转。四种情况LL新结点插在失衡结点的左孩子的左子树。解法对失衡结点做一次右旋。RR新结点插在失衡结点的右孩子的右子树。解法对失衡结点做一次左旋。LR新结点插在失衡结点的左孩子的右子树。解法先对左孩子做一次左旋变成 LL再对失衡结点做一次右旋。RL新结点插在失衡结点的右孩子的左子树。解法先对右孩子做一次右旋变成 RR再对失衡结点做一次左旋。怎么记“失衡结点的哪个孩子方向重了就往反方向转”转完之后还要保证 BST 的中序序列不变。我复习的时候自己推导过一遍旋转后的指针变化右旋就是把失衡结点变成它左孩子的右孩子原来左孩子的右子树变成失衡结点的左子树。你自己推一遍比背一百遍都管用。AVL 插入后的调整有个原则只需要调整从插入点到根路径上的结点且第一次出现失衡的结点就是最小失衡子树根。调整这一棵子树后整个树就平衡了。这个结论可以直接用来解“插入后哪些结点需要调整”的选择题。2.3 查找长度计算树高决定成败BST 和 AVL 的查找过程都是从根往下走一条路径所以一次查找的比较次数 该结点所在的层数。成功 ASL 所有结点层数之和 / n。AVL 保证了树高不超过 log₂n 的常数倍所以 ASL 是 O(log n)。但这里有个考研常挖的坑AVL 的树高并不是严格的 ⌈log₂(n1)⌉而是斐波那契数列相关的递推。最少结点数的 AVL 树满足 N(h) N(h-1) N(h-2) 1其中 N(0)1, N(1)2。比如高度 5 的 AVL 至少需要 12 个结点而不是 2⁵-131 个。这个公式选择题考过多次务必背下来推导也不难根是一层左右子树一棵高度 h-1、一棵 h-2才能达到结点最少。3. B 树与 B 树为磁盘而生的多路平衡树3.1 为什么需要多路一次磁盘 IO 换更低的树高内存里比较数据快得可以忽略时间但磁盘 IO 一次寻道加读盘的时间比内存比较慢好几个数量级。数据库动辄百万千万条记录如果用 AVL 树树高 20 层查一次聚簇索引就可能要读 20 个磁盘页每个页一次 IO太慢。B 树的思路是一个结点里多存几个关键字让每一层能覆盖更多的数据范围。m 阶 B 树每个结点最多 m-1 个关键字、最多 m 棵子树最少 ⌈m/2⌉-1 个关键字。树高大幅降低IO 次数自然减少。考研对 B 树的要求很明确能画图、能模拟插入删除、能算树高范围不要求写代码。3.2 B 树的查找、插入分裂、删除合并查找从根开始在结点内用顺序或折半找关键字没找到就根据大小关系进入对应子树指针。注意 B 树的查找是“结点内比较 跨结点移动”的组合结点内比较不算 IO跨结点才算。插入先找到最底层叶子层的插入位置直接插入。如果插入后关键字个数超过 m-1就触发分裂把结点从中间第 ⌈m/2⌉ 个关键字劈开左边留在原结点右边放进新结点中间关键字上提到父结点。父结点如果也满了继续上提分裂直到根。如果根也分裂树高加一层。删除分两种情况——删除非叶子结点关键字时用它的前驱或后继关键字顶替变成删除叶子层的关键字。删除叶子层关键字后如果关键字个数少于 ⌈m/2⌉-1需要借兄弟兄弟有多余关键字通过父结点中转旋转或合并兄弟也不够就把当前结点、兄弟结点和父结点中间的枢纽关键字合并成一个新结点。B 树的删除有点绕但考试最爱考“借兄弟”的旋转细节。记一个判断标准如果兄弟结点关键字数 ⌈m/2⌉-1可以借如果兄弟刚好最少只能合并。3.3 B 树把“所有数据”赶到叶子层B 树和 B 树的区别考研常考对比B 树中非叶子结点的关键字都作为索引不存实际记录指针数据只在叶子结点。B 树的叶子结点通过链表按顺序连在一起所以范围查询特别快——找到下界后沿着链表一路往后扫就行B 树做范围查询要反复中序遍历效率差很多。B 树的非叶子结点可以存更多关键字树高更低IO 次数更少。所有关键字在叶子结点都会出现一次而且按序排列B 树的关键字分布在各层不重复。数据库索引之所以普遍选 B 树而不是 B 树核心就是“叶子链表 全数据在叶子”这两个特性。考试如果问“为什么用 B 树做索引”你要能答出减少 IO树高矮、支持高效范围扫描叶子链表、查询稳定所有数据都在同一层。4. 哈希表不比较算地址4.1 哈希函数和“冲突”的本质哈希表的思路彻底变了不是比较而是通过哈希函数直接算出记录存放的位置。理想情况下key 经过哈希函数 f 得到数组下标直接 O(1) 取出来。但现实是哈希函数可能把不同 key 映射到同一地址这就是冲突。注意冲突是不可避免的因为地址空间小于关键字空间鸽巢原理所以研究的核心就是“冲突怎么处理”。考研常考的哈希函数除留余数法f(key) key mod pp 一般取不大于表长 m 的最大质数这样分布最均匀。直接定址法f(key) a×key b适合关键字连续的情况不会冲突但可能浪费空间。数字分析法抽取关键字中分布较均匀的几位作为地址。平方取中法key²取中间几位让中间位跟所有位都相关。4.2 开放定址法冲突了就去探测下一个空位线性探测冲突后依次往后找Hᵢ (H(key) i) mod m。它的问题是容易产生堆积聚集——连续冲突的元素挤在一起后来的元素要绕很远才能找到空位。查找成功 ASL 和失败的都跟装载因子 α 密切相关算的时候必须结合哈希表的“探测序列”手推。平方探测二次探测Hᵢ (H(key) ± i²) mod m能避免堆积但要求表长 m 是 4k3 形式的质数不然可能探不完所有位置。再散列法冲突后用另一个哈希函数重新算地址。伪随机序列法冲突后用伪随机数序列作为增量。考试计算 ASL 时默认“等概率查找”你要会画表、数比较次数。比如表长 13用除留余数法和线性探测插入一串 key求成功 ASL 每个 key 找到自己所需比较次数之和 / 关键字个数失败 ASL 对每个哈希地址0~12从该地址开始按探测序列找直到空位置所需的比较次数 / 13。很多同学算失败 ASL 老错是因为他们一直“从头开始找”实际上失败 ASL 是从哈希地址开始找碰到空位就停不是从 0 地址开始。4.3 拉链法冲突了就挂链表拉链法把冲突的同义词挂在同一个桶链表里不互占位置所以不会发生“堆积”。查找时先算地址再到链表里顺序找。拉链法的 ASL 计算更直观成功 ASL Σ(每个链表中结点深度1) / n失败 ASL Σ(每条链表长度) / m。这里 m 是地址空间长度即桶个数。拉链法还有个隐性优点删除方便。开放定址法删除一个元素不能真的置空否则会切断后面同义词的探测路径只能打“删除标记”拉链法直接删链表结点就行。这个点在选择题里经常出现一定要记得。4.4 装填因子 α哈希表最重要的宏观指标装填因子 α 表中记录数 n / 表长 m。α 越大表越满冲突概率越高ASL 越大。但注意哈希表的平均查找长度不是 n 的确定函数而是 α 的函数——哪怕表里有一万个元素只要把表长设计得足够大α 合适ASL 还是能保持在常数级别。这就是哈希表“空间换时间”的代价表不能填太满否则性能急转直下。开放定址法一般要求 α ≤ 0.75 左右拉链法可以容忍 α 到 1 以上因为链表长度分摊下来了。5. 常见错误与复习避坑这些坑我当年全踩过5.1 判定树高度和折半查找的 ASL 算错折半查找的判定树是一棵“平衡的二叉排序树”n 个结点的判定树高度是 ⌈log₂(n1)⌉但 ASL 不是简单套这个高度。你得画出具体判定树把每一层有几个结点数清楚。常见错误是把“树高”当“所有结点的层数”比如 n11 的判定树第 1 层 1 个、第 2 层 2 个、第 3 层 4 个、第 4 层 4 个成功 ASL (1×1 2×2 3×4 4×4) / 11 33/11 3。没事多画几棵感受“判定树前几层满二叉树、最后一层分布不均”的规律。5.2 BST 删除用前驱还是后继结果不一样但都对有些教材讲 BST 删除双孩子结点时只讲“用前驱顶替”有的只讲“用后继顶替”其实两种都合法但考试时必须跟题目要求一致。如果题目没指定你默认用前驱即可。还有一个隐藏考点删完再插入同一个结点BST 结构不一定恢复原样但如果删的是叶子再插回去结构完全不变——这个结论选择题考过。5.3 AVL 旋转时忘了更新平衡因子手工模拟 AVL 插入时画对了旋转方向但忘了把旋转涉及的几个结点的平衡因子重新算一遍这是丢分重灾区。提醒自己旋转之后凡是子树结构变了的结点平衡因子都要重算。LR 和 RL 的第二步旋转旋转中心是原左孩子的右孩子或右孩子的左孩子它的平衡因子从 ±1 变成 0别漏。5.4 B 树插入分裂时把“中间关键字”上提错了B 树分裂最容易错的部分是中间关键字的选取到底是第几个。m 阶 B 树分裂时取第 ⌈m/2⌉ 个关键字上提。比如 5 阶 B 树结点最多 4 个关键字分裂时从第 3 个⌈5/2⌉3上提。左边留 2 个右边留 2 个。有些同学习惯“从中间一刀切”导致左右个数不等答案就错了。5.5 线性探测的失败 ASL 探到“表尾”要回绕表长 m 的哈希表是环状的线性探测到 m-1 地址还没空位要回到 0 继续探。算失败 ASL 时每个起始地址探测到第一个空位置即可停止探测次数是“从起始地址走到空位经过的非空位置数 1”。画图时把表看成一个环别把它当成一条直线不然表尾那几个地址的失败 ASL 全会算错。5.6 哈希表删除的“假删除”陷阱开放定址法表里删除一个元素绝不能直接置空而要放一个“已删除”标记。否则后续查找某个同义词时探测到这个空位就停了导致明明存在的元素找不到。这个点在“删除后还能不能正常查找”的判断题里反复出现。拉链法没有这个问题可以直接摘链。6. 复习顺序与做题策略查找这一章该怎么拿分我个人的建议是按“静态 → 动态 → 多路 → 哈希”的顺序推进因为这条线正好是“数据范围从小到大、结构从简单到复杂”的演进过程先吃透顺序查找和折半查找把判定树画熟练这是后面所有树结构的基础。再攻 BST 和 AVL重点放在手工旋转和删除模拟上每天画两遍四种旋转形成肌肉记忆。然后学 B 树和 B 树理解“磁盘 IO”是主线插入删除必须自己走三遍完整流程。最后学哈希重点区分两种冲突处理方法的 ASL 计算和删除差异。刷题时注意查找这章的选择题特别喜欢“概念对比”比如 B 树和 B 树、线性探测和拉链法、顺序查找和折半查找适用场景。大题则基本锁定在“画 BST/AVL/B 树”和“哈希表 ASL 计算”这两类。建议复习后期自己出几道综合题比如“给定一组关键字先构造 BST再转换成 AVL最后用哈希表重新组织分别计算 ASL”把整章串成一条线。提示查找这章的特点是“看着简单算着容易错”。ASL 计算题一定要在草稿纸上一步一步写清楚比较过程不要心算心算必错。我在实际复习中最大的体会是这章不靠背靠画。折半判定树画多了自然理解“为什么有序表用折半、无序表只能顺序”AVL 旋转画多了自然理解“为什么平衡因子能保证 O(log n)”——因为每转一次都是为了把“链”变回“树”。如果时间紧张优先掌握折半查找的判定树构造、AVL 的四种旋转、B 树的插入/删除模拟、哈希表的两种冲突处理 ASL 计算这四个题型几乎覆盖了历年考研真题里查找章节 80% 的分数。剩下的边角概念考前翻一遍教材就能带过不用纠结。