临近期末复习数据结构第九章“查找”的同学很多都会掉进同一个坑把顺序查找、二分查找、二叉排序树、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就简化成(12...n)/n (n1)/2。这里要注意的是ci到底从1开始数还是从0开始数。绝大多数教材从1开始数也就是第一次比较就算1次后面我们统一用这个口径。再看失败的情况。查找不成功的时候同样要数比较次数。比如在长度为n的无序表里顺序查找一个不存在的值必须把n个位置都比完才能下结论失败ASL就是n。二分查找的失败比较次数则要看判定树的高度。很多同学只记成功ASL考题一出“查找失败的平均比较次数”就懵了这其实是用ASL这个统一尺子串起后面所有算法之前必须想清楚的基本功。2. 静态查找三件套顺序、二分与分块分别解决什么问题2.1 顺序查找简单但别小看它的ASL推导顺序查找的逻辑不用多说从表头到表尾一个个比。它最大的优点是“无脑”对存储结构没要求数组、链表都行对表中数据的排列顺序也没要求乱序照样查。缺点是慢成功ASL是(n1)/2失败ASL是n。期末题里顺序查找一般不会直接考代码而是结合概率考ASL变体。比如题目告诉你每个记录的查找概率不相等问你如何组织记录让ASL最小。答案是把概率高的记录放在前面因为顺序查找比较次数等于记录位置概率高的位置越靠前加权和越小。还有一种考法是把“监视哨”写出来——把待查关键字放在数组下标0位置从后往前查循环里省掉判断下标越界。这个写法的好处是循环内只比较关键字不比较下标代码更简洁、更快。但是有些同学背了监视哨的代码却不知道它背后的意图是“用空间换时间、减少一次分支判断”考到“为什么用监视哨”就答不上来。还有一点容易被忽略顺序查找的ASL只对“等概率、查找成功”给出(n1)/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结果在只剩两个元素时反复横跳。第二二分查找的过程可以画成一棵判定树。比如n11的有序表第一次比较的是第6个元素如果key小就去查第6个元素左边的子区间也就是第1到第5个元素它们的中间位置是第3个元素如果key大就去查右边第7到第11个元素的中间位置也就是第9个元素。这样一路展开就形成一棵理想平衡树。画判定树不仅帮你理解比较路径更重要的是可以数失败结点。一棵有n个内部结点的判定树必然有n1个外部失败结点对应所有查找失败的情况。所以二分查找成功ASL是内部结点深度加权平均失败ASL和失败结点的层次有关。期末画图题如果让你“画出n10时的判定树并求ASL”你画树这一步对了后面的计算基本就是送分题。2.3 分块查找索引与分块的最优块长推导分块查找也叫索引顺序查找它是顺序查找和二分查找的折中把表分成若干块块内无序块间有序也就是前一块的最大关键字小于后一块的最小关键字。再建一个索引表索引表里存每块的最大关键字和起始地址。查找时分两步先在索引表里定位块索引表可以顺序查也可以二分查再到块内顺序查找。分块查找的ASL计算是期末容易考简答题的点。假设表长n分成b块每块长度s有n b*s。查找成功ASL 索引查找ASL 块内查找ASL。如果索引表用顺序查找总的ASL ≈ (b1)/2 (s1)/2。这个式子展开后在b和s乘积固定时当s √n时总ASL取得最小值约为√n 1。很多教材直接把结论写成“块长取√n时最优”但如果你能自己推导一遍考试遇到变式题比如告诉你索引表用二分查找也能算出来。分块查找的隐藏考点是“为什么块间有序但块内无序也行”。原因是查找分成两级索引表承担了“指路”任务块内无序所以只能用顺序查但这不影响正确性。这种设计对插入删除友好多了新元素来了先定位到正确的块插到块内任意位置文件不需要大规模搬移。在顺序查找和二分查找之间它是工程上一个相当实际的过渡方案。2.4 一张表看清三种静态查找的适用边界复习到这里我建议你自己动手整理一张对比表趁热把三种静态查找放一起横向看。下面是我的整理方便你对照检查查找方法存储要求数据是否有序动态插入/删除成功ASL优点顺序查找数组或链表无序即可方便(n1)/2简单、通用二分查找必须顺序表必须有序不方便需搬移元素O(log2 n)快适合静态数据分块查找顺序表索引表块间有序块内随意较方便√n级别折中兼顾查找和更新注意“动态插入/删除”这一列恰恰是引出下一节内容的钥匙。二分查找快是快但每次插入都要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个关键字隔成n1个区间所以关键字数始终比子树数少1。这是理解B树一切性质的基础。具体到m阶B树每条性质都可以从“平衡多路”的目标推导。每个结点最多m棵子树这是“m阶”的定义根结点至少两棵子树除非它是叶子除根外每个分支结点至少有ceil(m/2)棵子树这是为了保证树形“足够紧凑”不会退化成瘦高的二叉链。每棵子树至少ceil(m/2)棵那么结点内至少有ceil(m/2)-1个关键字最多有m-1个关键字。所有叶子结点都在同一层这保证了所有失败查找的路径长度一致这是“平衡”二字的直接体现。还有个隐藏性质考试也可能考一棵m阶B树里所有结点的子树总数等于关键字总数加1。这其实还是上面那条“n个关键字对应n1棵子树”全树累加的结果。遇到“给定关键字总数求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棵子树而不是n1棵因为关键字本身就是“区间分界”。用表格理一下最直观对比项B树B树关键字与子树数量n个关键字对应n1棵子树n个关键字对应n棵子树数据存放位置关键字所在结点就可能带数据所有数据都在叶子结点叶子结点之间互不相连通过链表按序连接查找终点可能在内层结点命中即结束一定查到叶子结点才结束内部结点作用既是索引也可能存数据纯粹做索引路由数据库索引为什么普遍采用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-1p是哈希函数取模的数数从每个可能的哈希地址出发走到最近空位的探测次数再取平均。很多同学拿成功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个关键字对应n1棵子树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第九章基本就稳了。考前最后几天别再从头到尾翻教材了拿着纸笔对着上面的易错清单和画图清单一条条过比什么都管用。