企业官网建设流程全解析

临近期末，复习数据结构第九章“查找”的同学，很多都会掉进同一个坑：把顺序查找、二分查找、二叉排序树、AVL、B树、哈希表当成一堆相互独立的算法，挨个背定义、背复杂度、背公式。背完合上书，拿到一道综合题还是不知道从哪下手。这一章确实信息量大，但它不是算法的堆砌，而是一条非常清晰的演进主线——从无序到有序，从静态到动态，从内存到磁盘，从“比较”到“计算”。你只要抓住这条线，所有知识点会自动串起来，复习效率完全不一样。

这篇内容适合两类人：一类是刚开始复习、想把整章框架理顺的同学；另一类是已经刷过几轮题、但总在细节上丢分的同学。我会把查找章的核心原理、期末高频考点和实操画图套路都拆开讲一遍，尽量用大白话把“为什么”说清楚，而不是让你死记结论。

1. 为什么你背了一堆查找算法，做题还是懵

1.1 查找章不是算法清单，而是一条演进主线

你回想一下整章内容，是不是这样一条逻辑链：一开始数据是无序存放在数组里，只能从头到尾一个个比，这叫顺序查找，复杂度O(n)。数据太慢，就想到先排序再用二分，比较次数砍到O(log n)。可二分要求数据静态有序，插一个数就得移动一堆元素，于是有了二叉排序树，插入、删除、查找都能维持在O(log n)。但二叉排序树遇到有序输入会退化成链表，于是有了平衡二叉树，强制左右子树高度差不超过1。数据量再大，内存放不下，要上磁盘，于是有了B树和B+树，用多路平衡把树高压下去，减少磁盘IO。最后人们想，能不能连比较都不做了？于是哈希表登场，直接算出地址，理想情况O(1)。

这一整条线，本质是数据结构组织方式的不断升级。查找算法不是凭空蹦出来的，它是为解决前一种方案的问题而诞生的。复习的时候你多问一句“为什么会出现这个东西”，记起来会轻松得多。我见过太多同学把查找章拆成七八个孤立小节去背，结果碰到“二分查找和二叉排序树的适用场景对比”这种基础题都答不全，就是因为脑子里没有主线。

1.2 用ASL统一全局：看懂一切查找算法的钥匙

这一章最核心的度量指标只有一个：平均查找长度，简称ASL。它表示查找过程中关键字比较次数的平均值，是所有查找算法横向比较的“统一语言”。ASL定义本身不复杂，但期末丢分往往丢在两个细节上：一是没有区分查找成功和不成功的ASL，二是没有弄明白“比较次数”到底怎么数。

先看成功的情况。假设有n个记录，第i个记录被查到的概率是pi，查到它需要比较ci次，那么成功ASL就是p1c1 + p2c2 + ... + pn*cn。很多教材默认每个记录查找概率相等，pi = 1/n，那么顺序查找的ASL就简化成(1+2+...+n)/n = (n+1)/2。这里要注意的是ci到底从1开始数，还是从0开始数。绝大多数教材从1开始数，也就是第一次比较就算1次，后面我们统一用这个口径。

再看失败的情况。查找不成功的时候，同样要数比较次数。比如在长度为n的无序表里顺序查找一个不存在的值，必须把n个位置都比完才能下结论，失败ASL就是n。二分查找的失败比较次数则要看判定树的高度。很多同学只记成功ASL，考题一出“查找失败的平均比较次数”就懵了，这其实是用ASL这个统一尺子串起后面所有算法之前，必须想清楚的基本功。

2. 静态查找三件套：顺序、二分与分块，分别解决什么问题

2.1 顺序查找：简单但别小看它的ASL推导

顺序查找的逻辑不用多说，从表头到表尾一个个比。它最大的优点是“无脑”：对存储结构没要求，数组、链表都行；对表中数据的排列顺序也没要求，乱序照样查。缺点是慢，成功ASL是(n+1)/2，失败ASL是n。期末题里顺序查找一般不会直接考代码，而是结合概率考ASL变体。

比如题目告诉你，每个记录的查找概率不相等，问你如何组织记录让ASL最小。答案是把概率高的记录放在前面，因为顺序查找比较次数等于记录位置，概率高的位置越靠前，加权和越小。还有一种考法是把“监视哨”写出来——把待查关键字放在数组下标0位置，从后往前查，循环里省掉判断下标越界。这个写法的好处是循环内只比较关键字，不比较下标，代码更简洁、更快。但是有些同学背了监视哨的代码，却不知道它背后的意图是“用空间换时间、减少一次分支判断”，考到“为什么用监视哨”就答不上来。

还有一点容易被忽略：顺序查找的ASL只对“等概率、查找成功”给出(n+1)/2。不等概率时一定要回到加权和的定义来算。期末偶尔会给你一张概率表，让你按位置算ASL，这种题没什么技巧，老老实实把每个位置的概率乘以位置序号再求和就行。

2.2 二分查找：判定树、边界更新和失败比较次数

二分查找的前提是有序存储，而且一般要求是顺序表，链表很难支持高效的随机访问。核心思路每次取中间位置mid = (low + high) / 2，和目标比较一次，然后丢掉一半。代码模板很多同学都会背，但有两个细节是期末考试最喜欢挖坑的地方。

第一，边界更新必须是low = mid + 1或者high = mid - 1，不是low = mid或high = mid。因为mid这个位置已经和key比较过了，如果key不等于a[mid]，下次搜索区间必须把它排除掉。如果把high写成mid，当key小于a[mid]时，剩下区间包含mid，又会再比一次mid，极端情况下会陷入死循环。我见过不少同学上机写二分查找，就是这里少写了+1和-1，结果在只剩两个元素时反复横跳。

第二，二分查找的过程可以画成一棵判定树。比如n=11的有序表，第一次比较的是第6个元素，如果key小，就去查第6个元素左边的子区间，也就是第1到第5个元素，它们的中间位置是第3个元素；如果key大，就去查右边第7到第11个元素的中间位置，也就是第9个元素。这样一路展开，就形成一棵理想平衡树。画判定树不仅帮你理解比较路径，更重要的是可以数失败结点。一棵有n个内部结点的判定树，必然有n+1个外部失败结点，对应所有查找失败的情况。所以二分查找成功ASL是内部结点深度加权平均，失败ASL和失败结点的层次有关。期末画图题如果让你“画出n=10时的判定树并求ASL”，你画树这一步对了，后面的计算基本就是送分题。

2.3 分块查找：索引与分块的最优块长推导

分块查找也叫索引顺序查找，它是顺序查找和二分查找的折中：把表分成若干块，块内无序，块间有序，也就是前一块的最大关键字小于后一块的最小关键字。再建一个索引表，索引表里存每块的最大关键字和起始地址。查找时分两步：先在索引表里定位块（索引表可以顺序查也可以二分查），再到块内顺序查找。

分块查找的ASL计算是期末容易考简答题的点。假设表长n，分成b块，每块长度s，有n = b*s。查找成功ASL = 索引查找ASL + 块内查找ASL。如果索引表用顺序查找，总的ASL ≈ (b+1)/2 + (s+1)/2。这个式子展开后，在b和s乘积固定时，当s = √n时总ASL取得最小值，约为√n + 1。很多教材直接把结论写成“块长取√n时最优”，但如果你能自己推导一遍，考试遇到变式题（比如告诉你索引表用二分查找）也能算出来。

分块查找的隐藏考点是“为什么块间有序但块内无序也行”。原因是查找分成两级，索引表承担了“指路”任务，块内无序所以只能用顺序查，但这不影响正确性。这种设计对插入删除友好多了：新元素来了，先定位到正确的块，插到块内任意位置，文件不需要大规模搬移。在顺序查找和二分查找之间，它是工程上一个相当实际的过渡方案。

2.4 一张表看清三种静态查找的适用边界

复习到这里，我建议你自己动手整理一张对比表，趁热把三种静态查找放一起横向看。下面是我的整理，方便你对照检查：

注意“动态插入/删除”这一列，恰恰是引出下一节内容的钥匙。二分查找快是快，但每次插入都要O(n)地移动元素，静态数据用没问题，一旦频繁更新就很痛苦。那有没有一种结构，既能像二分查找那样沿着某条路径快速决策，又能把插入删除的代价降下来？有，二叉排序树。

3. 二叉排序树的平衡难题：AVL旋转其实有直觉

3.1 为什么有了二分查找还要二叉排序树

二分查找的问题不是查找本身慢，而是“维护有序”的成本太高。你插入一个新元素，先找到位置，再把后面元素全部后移一位，最坏O(n)。如果删除一个元素，也要搬移元素。数据一旦频繁变动，二分查找的整体代价就上去了。

二叉排序树把线性结构换成树形结构。左子树所有结点都小于根，右子树所有结点都大于根。查找时走一条从根到叶子的路径，平均情况下比较次数是O(log n)，和二分查找同一量级。但插入和删除只需要改动有限的几个指针，不需要整个数组搬移，动态场景下优势明显。中序遍历二叉排序树还能得到一个递增序列，这也是一道很常见的简答题考点：为什么二叉排序树的中序序列是有序的？因为它的定义就是“左小右大”，中序遍历自然升序。

二叉排序树最怕的是什么？最怕输入序列本身有序。比如按1, 2, 3, 4, 5依次插入，每次新结点都变成当前最右孩子，树退化成一条链，查找又变成O(n)。所以二叉排序树的“平均O(log n)”是有条件的，前提是树形尽量平衡。这才有了平衡二叉树存在的意义。

3.2 BST删除的三种情况，期末最容易写错的if分支

二叉排序树的插入很简单，从根向下比大小，走到空位置就挂上。查找更简单，比大小往下走。删除是三种操作里最容易出错的地方，期末笔试和机考都喜欢考。

删除分三种情况。第一种，被删结点是叶子，直接让它父亲结点的对应指针置空，完事。第二种，被删结点只有一个孩子，用这个孩子顶替被删结点的位置。具体写代码时要判断待删结点是父亲左孩子还是右孩子，然后把它的独生孩子接上去。第三种最麻烦，被删结点有两个孩子。标准做法是找它的中序前驱或中序后继来替换它。中序前驱是左子树里最大的结点，中序后继是右子树里最小的结点，两者都至多有一个孩子，所以替换后删除操作退化成前面两种情况。

这里有个很多同学纠结的问题：到底用前驱替换还是用后继替换？理论上都可以。有的教材习惯用前驱，有的教材用后继，最终中序序列都会删掉一个结点、保持有序。实操上我建议你选“右子树的最小结点”来替换，因为找右子树最小结点的代码逻辑更清晰，不容易写错。但如果你所在学校的教材或PPT默认用左子树最大结点，那考试画图题请遵循教材口径，别跟标准答案对着干。

3.3 四种失衡一网打尽：LL/RR/LR/RL的旋转口诀

AVL树的定义很简洁：每个结点左右子树高度差的绝对值不超过1。这个高度差叫平衡因子，等于左子树高度减去右子树高度。期末题一般是给你一个插入序列，要求画出每一步插入后的AVL树，遇到失衡需要做旋转调整。

失衡类型一共四种，按“插入位置相对于最小失衡子树根的位置”命名。LL型：插在根的左孩子的左子树，处理方式是右旋。RR型：插在根的右孩子的右子树，处理方式是左旋。LR型：插在根的左孩子的右子树，需要先对左孩子左旋，变成LL型，再对根右旋。RL型：插在根的右孩子的左子树，需要先对右孩子右旋，变成RR型，再对根左旋。

这里不要死记“左旋右旋”的字眼，记住一个直觉：树往哪边歪，就往反方向掰。LL型是左边太高，整棵树往左歪，把根向右旋转，让左孩子升上来当新根；RR型相反，往右歪就往左掰。LR型就是左下角被塞进一个结点，单纯右旋一次不够，得先把底下“捋直”，所以是先左旋再右旋。我当年记这四个类型，就靠画图：每一次旋转，你盯住三个结点——根、出问题的内侧孩子、外侧孩子，它们的相对位置变化就是旋转方向。

考试画AVL树时，强烈建议每插入一个结点，就在旁边标出所有受影响的平衡因子，找到绝对值变成2的结点作为最小失衡子树的根。不要一上来就盯着全树试图旋转，那是最容易晕的写法。处理完最小失衡子树后，上级子树的高度通常恢复原状，不需要继续往上调整。

3.4 旋转结果自检：中序遍历序列必须不变

这个技巧可能教材里不会专门讲，但期末画图题用它自查非常管用。无论你怎么旋转、旋转多少次，AVL树始终是二叉排序树，而一棵二叉排序树的中序遍历序列是唯一且固定的，取决于所有结点的相对大小顺序。

所以每做完一次旋转，你可以把旋转前后子树的中序遍历序列拉出来对比，如果顺序变了，那说明旋转转错了。反过来，如果你画完AVL树不确定对不对，就做一次中序遍历，看得到的序列是否还是递增。这个检查方法对LL、RR、LR、RL四种类型全部适用。我辅导过的几个学弟学妹，画AVL图总出错，后来让他们每次旋转完都做这一步检查，正确率立刻上来了。期末考场上时间宝贵，不需要每个结点都去验证，但在关键几步上做一次自检很值得。

4. B树和B+树：从内存思维切换到磁盘思维

4.1 为什么在内存里的二叉树搬到磁盘上会“太矮才够用”

学B树之前，很多人的思维还停留在“内存里比较一下很快”这个层面。但是当数据量大到内存装不下，必须存在磁盘上时，比较本身已经不重要了，真正贵的是磁盘IO。一次磁盘读写的耗时比一次内存比较高出好几个数量级。所以磁盘上的数据结构目标很明确：尽量少访问磁盘块。

二叉排序树和AVL虽然查找路径短，但那是针对内存的。树高20层，查找时可能要访问20个不同的结点，每个结点分布在不同的磁盘块，那就是20次磁盘IO，慢得离谱。如果我们把一棵树压扁，让每个结点能存几十上百个关键字，每个结点对应一个磁盘块，那么树高度能压到3到4层，一次查找最多访问几个磁盘块就结束了。这就是B树“多路平衡”的意义：降低树高，让每次访问能带回尽可能多的信息。

4.2 m阶B树性质：别背定义，按“子树与关键字的数量关系”推理

m阶B树的性质，几乎是期末简答题的保留节目。死背容易背混，特别是“关键字个数范围”和“子树个数范围”这两个数字。我建议你先抓住一个总规律：每个结点里有n个关键字，就会把这n个关键字隔成n+1个区间，所以关键字数始终比子树数少1。这是理解B树一切性质的基础。

具体到m阶B树，每条性质都可以从“平衡多路”的目标推导。每个结点最多m棵子树，这是“m阶”的定义；根结点至少两棵子树，除非它是叶子；除根外每个分支结点至少有ceil(m/2)棵子树，这是为了保证树形“足够紧凑”，不会退化成瘦高的二叉链。每棵子树至少ceil(m/2)棵，那么结点内至少有ceil(m/2)-1个关键字，最多有m-1个关键字。所有叶子结点都在同一层，这保证了所有失败查找的路径长度一致，这是“平衡”二字的直接体现。

还有个隐藏性质考试也可能考：一棵m阶B树里，所有结点的子树总数等于关键字总数加1。这其实还是上面那条“n个关键字对应n+1棵子树”全树累加的结果。遇到“给定关键字总数求B树最大高度”这类题，用这个关系就能推出来。

4.3 插入分裂与删除合并的期末画图套路

B树插入的画图题，核心是分裂。先到叶子结点插入关键字，如果插入后关键字个数超过m-1，就分裂：把中间位置的关键字提升到父结点，左右两部分拆成两个结点。如果父结点也满了，就继续向上分裂，最坏情况下根结点也被分裂，树高加1。

这里很多同学画错，是因为搞不清“中间位置是哪个”。对m阶B树，如果结点满时关键字个数是m-1，再插入一个变成m个。分裂时一般取第ceil(m/2)个关键字作为中间值上提。比如5阶B树，满结点有4个关键字，插入后变成5个关键字，中间的是第3个，第3个上提，左右各2个。我建议你考试时先把这m个关键字从小到大排一行，然后用竖线把中间位置标出来，再往两个结点里填，这样不容易数错。

B树删除比插入复杂，分三种情况。如果删除的是叶子结点的关键字且删除后关键字数不小于下限，直接删。如果删除后下溢，先看左右兄弟有没有富余关键字，有就跟兄弟“借”，通过父结点做一次旋转调整；没有兄弟可借，就跟兄弟合并，并且父结点里夹在它们中间的关键字会掉下来。如果掉下来导致父结点也下溢，就继续向上处理。期末画图题通常只考第一步和简单的“借兄弟”，但你要知道合并机制是怎么回事，简答题才说得清楚。

4.4 B树vs B+树对比表与“为什么数据库爱用B+树”

B+树是B树的变体，期末对比简答题高频。它和B树最核心的差异在三点：B+树的内部结点只存索引关键字，不存实际数据；所有数据都挂在叶子结点上，而且叶子结点通过链表串在一起；内部结点的n个关键字对应n棵子树，而不是n+1棵，因为关键字本身就是“区间分界”。

用表格理一下最直观：

数据库索引为什么普遍采用B+树？理由有三层。第一，内部结点不存数据，一页磁盘里能放更多的索引项，树更矮，IO次数更少。第二，叶子结点有序串成一个链表，做范围查询时，找到下界之后沿着链表一路往后遍历，效率极高，而B树每次范围扫描都要反复回到内层结点。第三，所有数据都在叶子层，查询路径稳定，性能更可控。这些点复习时你从“磁盘IO”和“范围查询”两个角度随口就能答出来，比背大段文字管用。

5. 哈希表：把“比较查找”变成“直接算地址”

5.1 哈希函数的构造：除留余数法为什么是首选

哈希表的思路和前几种方案完全不一样。前面所有查找算法都是“比较”，哈希表则是“计算”：给定关键字key，通过哈希函数h(key)直接算出这个记录应该存放在哪个地址，理想情况下一次内存访问就能找到，复杂度O(1)。

构造哈希函数有直接定址法、数字分析法、平方取中法、折叠法、除留余数法。期末考得最多的是除留余数法，因为它实现最简单、分布也足够均匀。公式是h(key) = key mod p，其中p通常取不大于表长的最大质数，或者干脆小于等于表长的最大质数。为什么要提“质数”？因为如果p有因数，比如p是偶数，那么所有偶数的key取模后都会落在同一些位置，奇数的又落在另一批位置，分布会极不均匀。取质数能减少这种规律性，让记录尽量散开。这是一个典型的“知其所以然”考点，简答题让你解释为什么p取质数，照着这个思路答就行。

当然，除留余数法要求key本身是整数。如果关键字是字符串，通常要先通过某种编码方式，比如把字符的ASCII码做加权和，转成一个整数，再取模。这里加权时尽量避免简单累加，否则“ab”和“ba”会映射到同一个值，冲突概率变大。用乘以一个质数系数的滚动哈希，效果会好得多。

5.2 冲突处理的两大流派：开放定址和链地址

冲突不可避免，这是哈希表绕不过去的问题。所谓冲突，就是两个不同关键字算出来同一个地址。处理冲突的两大流派，期末一定会考一个。

开放定址法的思路是：地址被占用了，就在表里继续找下一个空位。最朴素的是线性探测，地址冲突时依次探查下一个地址，也就是地址+1、+2……直到找到空位。线性探测的优点是简单，缺点是“堆积”：连续占用的一串区域会越来越长，冲突时很难快速找到空位，导致查找性能下降。为了缓解堆积，又发展出二次探测、伪随机探测和再哈希法。二次探测按1、-1、4、-4这样的序列跳跃，能避开一段连续区域；再哈希法是准备第二个哈希函数，冲突时用第二个函数算步长。

链地址法的思路完全不同：每个哈希地址对应一条链表，所有同义词都挂到同一条链上。表里存的是链表头指针。这种方法不怕堆积，填装因子可以大于1，删除也方便——直接在链表里删结点。很多教材会用“坐座位”和“柜子抽屉”打比方：开放定址就像电影院找座位，坐了人就去旁边空位；链地址就像储物柜，一个柜子放不下多件行李？不，链地址更像是柜子后面挂了几件行李串。这个直觉能帮你记住：开放定址是在同一个表里挪位置，链地址是每个桶可以装任意多记录。

5.3 成功ASL与失败ASL的计算坑

哈希表的ASL是期末考试的重灾区，因为它不像顺序查找那样有固定公式，必须按实际构造出来的表从头算。

成功ASL的算法是：对每个已插入的关键字，数它在插入过程中一共做了多少次探测，把这些探测次数加起来，除以记录总数。比如线性探测插入时第一个位置就是空的，探测1次；如果第一个位置被占，探查到第3个位置才放下，就算3次。

失败ASL就麻烦一点。笔者的理解是，查找一个不存在的关键字时，从它哈希地址出发，沿着探测序列一路找，直到遇到某个空位还找不到，就说明这个关键字不存在。把这个过程中探测的次数作为该哈希地址对应的失败代价。要计算失败ASL，需要遍历哈希函数所有可能的输入值（一般是从0到p-1，p是哈希函数取模的数），数从每个可能的哈希地址出发，走到最近空位的探测次数，再取平均。很多同学拿成功ASL公式去套，或者忘了遍历全部哈希值，算出来肯定错。记住：失败ASL考察的是“空位最近有多远”，不是“已存记录平均走了多远”。

5.4 装填因子与“删除标记”这些课本没说透的事

装填因子α = 表中已有的记录数 / 哈希表的长度，它反映哈希表的“拥挤程度”。α越大，冲突越频繁，ASL越大。这也是为什么哈希表不能无脑塞到满，当α超过一定阈值时，插入和查找都会明显变慢。很多教材还会给近似公式：线性探测的成功ASL约等于(1 + 1/(1-α)) / 2，链地址法的成功ASL约等于1 + α/2。这两个公式不要求精确记忆，但你要能根据α判断性能趋势。

开放定址还有一个特别容易踩的坑：删除记录时不能直接把位置清空。如果你把某个位置置为空，那么后续跟它冲突、本来需要通过它作为跳板继续探测的关键字，可能在中途就遇到空位，误以为自己要找的关键字不存在，查找直接失败。正确做法是给这个位置打一个“已删除”标记，查找时空位才算真正的空，遇到“已删除”要跳过继续查。等到将来插入时，可以覆盖“已删除”的位置。这个点每年都有不少同学在填空题和判断题上栽跟头。

6. 期末冲刺：高频考点、易错清单与复盘方法

6.1 期末必考的六类画图题，考前必须过一遍

查找这一章的笔试题，画图题占了相当大的比重。我统计过常见的题型，主要有六类：一是给定序列画出二叉排序树的插入过程；二是给定插入序列画出AVL树，并标明每一步的失衡类型和旋转操作；三是给定关键字序列构造m阶B树的完整过程，重点考查分裂；四是给定哈希函数和冲突处理方法，构造哈希表并计算ASL；五是画出二分查找的判定树；六是给一棵B树做删除操作，考下溢时借兄弟或合并。这六类题看似各自独立，其实都落到同一个能力上：你对“插入过程中结构如何变化”是否真正理解，而不只是记住结论。建议考前找几道例题，从第一步开始写到最终结构，每一步都不要跳，画错了就直接返回去看教材的定义，比反复看PPT有效得多。

6.2 我见过最多的5个丢分点

下面这几个坑，是我看过很多模拟卷和作业之后总结出来的高频丢分点，你可以对照自检。

第一个是二分查找边界更新写成high = mid而不是high = mid - 1，造成区间不缩水甚至死循环。第二个是二叉排序树删除双孩子结点时，有人直接把左子树最大结点“复制”过来，却忘了删掉原来那个最大结点，造成序列里出现重复值。第三个是B树的分裂位置取错，m阶B树满结点有m-1个关键字，分裂时中间位置取第ceil(m/2)个，不是随便取中间那个。第四个是B+树和B树的关键字与子树数量关系记反，B树是n个关键字对应n+1棵子树，B+树则是n个关键字对应n棵子树。第五个是哈希表线性探测删除时直接把空位置出来，破坏了探测链，导致后续查找失败。这五个点几乎年年都有同学踩中，你复习时对着这张清单自查，比盲目刷题更有针对性。

6.3 一套可行的考前复盘流程与常用算法模板

最后分享一个我比较推荐的复习顺序。第一步，对照教材目录，把第9章所有小节的标题写在一张白纸上，不看内容，尝试在标题旁写出该节解决了什么问题、核心结论是什么。写不出来就翻书，写完再合上。这一步能快速暴露你的知识盲区。第二步，把所有ASL公式自己推导一遍。顺序查找、二分查找判定树、分块查找最优块长、哈希表线性探测和链地址的成功与失败ASL，全部手推一次。公式能不能记住不重要，重要的是推导过程能让你理解每个数字从哪来，考场上题目稍微变形你也不慌。第三步，做画图专项，把6.1里那六类题各挑两三道，按考试要求完整写出来。

代码模板方面，期末笔试不一定要求写完整程序，但递归思路经常考，我建议你把下面几个核心逻辑记住。二叉排序树查找可以这样写递归：当前结点为空返回失败，等于key返回成功，小于key去左子树，大于key去右子树。插入就是在查找失败的位置挂新结点。二分查找的循环模板则是while (low <= high)，每次比较mid之后更新low或high。链地址法的插入可以直接头插到对应桶的链表，O(1)。这些代码都不长，但期末简答题和填空题可能让你写出关键步骤，考前默写一遍非常有必要。

6.4 一些考场小建议

考试做题的顺序，我个人建议先做画图题，因为画图题分值大、步骤明确，而且画完一题就有完整的一题分数到手。ASL计算题容易在细节上丢分，比如失败ASL忘记遍历全部哈希值、二分判定树失败结点画漏等，这类题要预留多一点检查时间。

另外复习时不要把目光只盯在单个知识点上，这一章的主线就是“查找效率的不断升级”。选择题问你“哪种结构适合动态有序查找”，你要能自动在脑子里过一遍：二分有序表插入太慢，二叉排序树可能退化，AVL树最优。简答题问你“数据库为什么用B+树”，你要能从磁盘IO、树高、范围查询三个维度展开。会了主线，遇到没见过的问法也能临场组织出答案。

我自己当年复习到这一章，最大的体会是：死记公式和结论只能对付标准题，真正拉开差距的是对“为什么”的理解。你只要愿意花一个晚上，把从顺序查找一路到哈希表的演进逻辑捋一遍，再亲手画几十个树形图、算十几个ASL，第九章基本就稳了。考前最后几天，别再从头到尾翻教材了，拿着纸笔，对着上面的易错清单和画图清单一条条过，比什么都管用。