查找从静态查找到动态查找的一整套思路这一章围绕“查找”展开。表面上看查找只是从一组数据中找到某个关键字对应的记录但如果把整章内容连起来看它其实讲的是一个更重要的问题为了让“找”这件事更快我们应该怎样组织数据。也就是说查找问题并不只是某个函数怎么写而是数据组织方式、比较策略和结构设计共同作用的结果。这一章通常会先从查找的基本概念讲起说明什么是查找成功、什么是查找失败、什么是平均查找长度再进入顺序查找、折半查找、分块查找这些静态查找方法接着过渡到二叉排序树、平衡二叉树、B 树等动态查找结构最后再讲散列表把“比较查找”进一步推进到“通过地址直接定位”。如果把这些内容放在一条线上理解就会发现这一章真正想表达的是查找效率的提升本质上来自于信息组织方式越来越聪明。一、查找的本质不只是找到而是尽量少比较所谓查找就是在查找表中寻找具有给定关键字的记录。若找到了则称查找成功若没有找到则称查找失败。这个定义很直接但真正值得重视的是“查找过程”通常伴随着一连串比较。也就是说查找效率高低很大程度上取决于到底要比较多少次。因此这一章特别强调平均查找长度也就是 ASL。它表示在查找成功或查找失败的情况下为了完成查找平均需要进行多少次关键字比较。这个指标是整个查找章节的主线之一。因为顺序查找、折半查找、树表查找、散列查找看起来形式差异很大但最后都可以回到同一个问题平均而言要付出多少比较成本。从这个角度看查找问题并不是单纯“有或没有”的问题而是“代价大不大”的问题。同样是在一张表中找到目标元素若一个方法平均比较十几次另一个方法平均只要三四次它们的本质差别就在于底层结构是否为查找做了优化。二、静态查找与动态查找区别在于表会不会变化教材通常把查找表分为静态查找表和动态查找表。静态查找表指的是在查找过程中表中元素集合基本不变只做查找而不涉及插入和删除动态查找表则不仅要支持查找还要支持不断插入和删除元素。这个区分非常重要。因为有些方法在静态环境下很好用但一旦要频繁插入删除代价就会明显上升。比如折半查找要求表有序如果每插入一个新元素都得重新调整顺序它在动态场景下就不一定合适。相反二叉排序树、平衡树、B 树这类结构正是为了在动态变化中尽量保持较高查找效率而设计出来的。所以这一章最好不要把不同算法割裂来看。前半部分的顺序查找、折半查找、分块查找更多是在静态表条件下讨论后半部分的树表查找和散列技术则是在进一步思考如果数据会不断变化或者数据规模很大还能不能保持高效。三、顺序查找最朴素也最能体现比较代价顺序查找是最基础的查找方法。它从表的一端开始把关键字依次和表中元素比较直到找到目标或扫描完整张表。它的优点是实现简单对表没有特殊要求无论表是否有序、是否顺序存储都可以直接使用。但它的缺点也很明显查找效率依赖于元素位置。若目标刚好靠前查找很快若目标靠后甚至不存在就要比较很多次。在线性表长度为 n 的情况下顺序查找成功时的平均查找长度一般与 n 同阶失败时通常也需要扫描整张表因此时间复杂度通常是 O(n)。这一方法看似简单却特别适合帮助理解 ASL 的意义。因为它最直观地展示了“位置”对查找成本的影响越靠前越省比较越靠后越费比较。也正因为这种代价不稳定才会引出后面各种“想办法让目标更快定位”的优化思路。有时教材还会介绍带监视哨的顺序查找其思想是在表的一端额外设置一个哨兵使查找过程中不必每次都额外判断是否越界。它优化的不是数量级而是常数级开销。这一点也很有代表性数据结构和算法优化并不总是从 O(n) 变到 O(log n)有时也会体现在细节上的减少判断和减少分支。四、折半查找利用有序性把查找区间不断减半折半查找也叫二分查找是静态查找中最经典的方法之一。它适用于有序顺序表。其核心思想是每次先看中间元素若目标值等于中间元素则查找成功若目标值更小则只可能出现在左半区间若目标值更大则只可能出现在右半区间。这样一来每比较一次就能把查找范围缩小一半。折半查找之所以高效本质上是因为它充分利用了“有序”这个额外信息。顺序查找面对的是一张平铺的表只能一个个问而折半查找通过中间值判断能一次性排除掉一半不可能区域。这种“利用结构信息减少搜索空间”的思想是后面很多高级查找方法的共同核心。在长度为 n 的有序表中折半查找的时间复杂度是 O(log2 n)。和顺序查找相比当 n 很大时这种优势会非常明显。比如从一百万个元素里找一个目标顺序查找平均可能要比较几十万次而折半查找只需要二十次左右的数量级。不过折半查找也不是没有条件。它必须建立在有序顺序表之上并且更适合静态表。因为如果表中元素频繁插入和删除为了维持有序性维护成本会很高。这也是为什么折半查找虽然效率高却并没有统一解决所有查找问题。五、分块查找在顺序与折半之间寻找折中分块查找又叫索引顺序查找可以看作顺序查找和折半查找之间的一种折中方案。它的基本思想是先把表分成若干块块内元素可以无序但块与块之间按关键字范围有序同时建立一个索引表索引表中记录每块的最大关键字和块首地址等信息。查找时先在索引表中确定目标可能位于哪一块再到对应块内顺序查找。这一方法的优势在于它不像折半查找那样要求整张表完全有序只要求块间有序同时它又比纯顺序查找多了一层索引因此能更快缩小搜索范围。可以把它理解成一种“两级查找”思想先粗定位再细查找。分块查找的效率取决于分块方式。如果块太大那么块内顺序查找成本会偏高如果块太小则索引表变大查索引的成本也会增加。因此块长的选择会直接影响平均查找长度。教材中常会推导在一定条件下的最佳块长这其实是在说明一个非常重要的事实查找结构设计并不只是“有索引就行”还要让不同层级之间的代价尽量平衡。六、从静态查找到动态查找关键变化在于“查找结构本身会成长”静态查找方法更多是建立在“表已经给定”的前提下而动态查找则要求结构在查找、插入、删除中持续保持较高效率。要做到这一点就不能只靠一张平铺表而需要引入具有层次关系的组织方式这就是树表查找的出发点。树表查找最重要的代表是二叉排序树。它通过一种递归的大小关系把数据组织成一棵查找树对任一结点左子树上所有结点关键字都小于该结点右子树上所有结点关键字都大于该结点。这样一来查找时就像在折半查找中不断决定去左半区还是右半区一样只不过这里的“左右划分”不是依靠数组中点而是依靠树的结点结构动态形成的。也就是说二叉排序树把“有序性”从线性表扩展成了一种层次式结构。它既保留了关键字大小关系又允许通过插入操作逐步长成一棵树因此特别适合动态查找场景。七、二叉排序树查找、插入、删除都围绕大小关系展开二叉排序树的查找过程非常自然。若目标值等于当前结点则成功若目标值更小则去左子树查找若目标值更大则去右子树查找。这个过程本质上是在不断根据比较结果缩小查找范围因此若树形较均匀查找效率会比较高。插入操作也类似。每次比较待插入关键字与当前结点大小小则沿左子树走大则沿右子树走直到遇到空位置再把新结点插进去。也就是说插入过程本身不会破坏二叉排序树的有序性而是顺着这种有序性找到一个合适的落点。删除操作则稍微复杂一些因为删掉一个结点后还必须维持整棵树的有序结构。通常要分三种情况讨论。若被删结点是叶子结点直接删除即可若只有一棵子树则让其子树直接接替它的位置若同时有左、右两棵子树则一般要用其直接前驱或直接后继来替换该结点再转化为删除前驱或后继结点的问题。二叉排序树这一部分特别值得认真理解因为它第一次把查找问题和树的结构维护紧密结合起来。你会发现这时“查找”已经不只是一个比较过程而是在一个不断生长和调整的结构中进行。八、二叉排序树的问题不在原理而在可能退化二叉排序树虽然很好地兼顾了查找和动态更新但它有一个明显弱点树形结构受插入顺序影响很大。若关键字输入顺序恰好比较均匀树会长得较平衡查找效率接近 O(log n)但若输入序列本身接近有序二叉排序树就可能退化成一条单支链此时查找、插入、删除的时间复杂度都会恶化到 O(n)。这说明一个非常重要的事实光有“大小关系”还不够结构形态本身也会影响查找效率。也正是为了解决这一问题才引出了平衡二叉树等更进一步的查找结构。换句话说二叉排序树解决了“动态环境下如何保持有序”但还没有彻底解决“如何始终保持高效”。九、平衡二叉树在动态变化中尽量维持接近平衡平衡二叉树又常见为 AVL 树它是在二叉排序树基础上的进一步改进。其核心目标是在每次插入或删除后都尽量维持树的左右子树高度差不过大从而保证整棵树高度保持在 O(log n) 量级。教材中通常把平衡二叉树定义为任一结点的左、右子树高度差的绝对值不超过 1。若某次插入或删除破坏了这一条件就需要通过“旋转”操作恢复平衡。最常见的有 LL、RR、LR、RL 四类调整方式。这里最值得理解的不是记住四种字母缩写而是认识到它们本质上都在做同一件事重新安排局部结点位置使得原来过长的一侧回缩原来过短的一侧得到补偿同时又不破坏二叉排序树原有的大小关系。也就是说旋转不是随便转而是在维持查找有序性的前提下调整形状。平衡二叉树的价值就在于它把二叉排序树“平均情况下快、最坏情况下可能退化”的局面改进成了“最坏情况下也能维持对数级效率”。这是动态查找结构中一次非常关键的提升。十、红黑树保持二叉排序树适度平衡红黑树是为了在二叉排序树的动态操作中降低维护平衡的代价而引入的一种自平衡结构它不像AVL树那样追求严格的高度平衡任意结点左右子树高度差不超过1而是通过放宽平衡限制来减少插入和删除后的调整频率从而在频繁更新的场景中获得更好的综合性能。一棵红黑树必须满足以下性质每个结点要么红色要么黑色、根结点为黑、虚构的外部叶结点全为黑、红结点的父子不能同为红、从任一结点到其所有后代叶结点的路径上黑结点数量相等。基于这些规则红黑树保证了最长路径不超过最短路径的两倍且树高始终维持在 O(log ⁡n) 级别实现了“适度平衡”。插入新结点时初始设为红色只有当父结点也是红色时才需要依据叔结点的颜色进行重新着色或旋转叔红则变色叔黑则根据结构选择单旋或双旋删除操作更复杂一些删除黑色结点会引入“双黑”概念需根据兄弟及其子结点的颜色分四种情形借助旋转和变色来恢复平衡。十一、B 树面向多路分支和外存环境的进一步扩展当数据规模很大时仅靠二叉树未必足够高效。因为即使树高是 O(log n)若每访问一个结点都要进行一次外存读写那么层数太多仍然会带来较大开销。于是就引出了 B 树这类多路平衡查找树。B 树的核心思想是让一个结点中容纳多个关键字和多个分支从而使树不再是二叉分支而是多路分支。这样一来虽然在一个结点内部可能要做多次比较但整棵树的高度会明显降低。对于外存查找来说这样做非常重要因为一次读入一个磁盘块后就能在块内完成多个关键字比较减少层数就相当于减少磁盘访问次数。教材中通常会讲 B 树结点中关键字个数、孩子个数、最小度数、插入分裂等基本规则。它们看起来较繁琐但本质目标只有一个在动态更新过程中始终维持一棵低而宽的平衡多路树。与 AVL 树相比B 树更加适合大规模数据和磁盘存储环境。从理解路径看可以把 B 树看成对平衡二叉树的一次“块化升级”不是只让一个结点存一个关键字而是让一个结点存一批有序关键字用空间局部性换取更少的层次和更少的外存访问。十二、散列表不再强调比较路径而是直接算地址前面几类查找方法不管是顺序表、折半查找还是各种树核心都还是“通过比较不断缩小范围”。而散列表则走向了另一种思路既然比较本身要花成本能不能根据关键字直接计算出它应该存放的位置。这就是散列技术的基本思想。通过一个散列函数把关键字映射成表中的存储地址。若设计得好查找时就可以很快直接定位到目标位置从而避免大量比较。理想情况下查找、插入和删除的平均时间复杂度都可以接近 O(1)。这一思想非常重要因为它意味着查找优化不一定非得靠“更巧妙的比较次序”也可以通过“更直接的地址映射”来实现。可以说散列表是查找章节中思路变化最大的一部分。十三、散列函数与冲突说明“直接映射”并不总能一步到位散列技术的关键在于散列函数。散列函数希望把关键字尽量均匀地分布到表中地址上使不同关键字映射到同一地址的概率尽可能小。但在实际中由于关键字集合往往远大于表地址范围不同关键字映射到同一位置的情况几乎不可避免这种现象称为冲突。也就是说散列表并不是“算了地址就一定找到”而是“算出一个最可能的位置再处理可能发生的碰撞”。因此散列查找效率高不高不只取决于函数计算快不快还取决于冲突多不多以及冲突后如何解决。教材中常见的散列函数构造方法有直接定址法、除留余数法、数字分析法、平方取中法等。其中最常用的往往是除留余数法即取关键字对某个适当模数取余作为地址。真正重要的不是背这些名字而是理解一个原则好的散列函数应当尽量简单、分布均匀并且适合具体关键字特点。十四、处理冲突的方法本质是在为“同一地址上的竞争”安排秩序冲突解决方法通常分为两大类开放定址法和链地址法。开放定址法的思想是若某个地址已被占用就按照某种探测规则继续寻找下一个可用位置例如线性探测、平方探测等。这样所有元素仍然放在同一张散列表中只不过冲突元素被“挪”到了别的位置。它的好处是结构紧凑不需要额外链表但探测过程中可能会产生堆积现象影响后续查找效率。链地址法的思想则是把散列到同一地址的元素组织成一个链表表中每个地址对应一条链。这样冲突元素不会挤占别的地址而是在本桶内部串联起来。它的优点是处理冲突更灵活也较容易删除元素缺点是需要额外指针空间且查找时要先定位桶再在链中比较。这两类方法本质上体现了两种不同策略开放定址法强调“继续在表中找空位”链地址法强调“允许同地址形成一个局部集合”。理解了这种差异很多关于装填因子、探测次数和堆积现象的问题就会更容易把握。十五、装填因子决定散列表会不会越来越拥挤散列表中有一个特别关键的参数叫装填因子通常记为 α。它反映的是表中已存记录数与散列表长度之间的比值。装填因子越大说明表越满冲突发生的概率通常也越高装填因子越小说明表较空冲突相对较少但空间利用率可能偏低。这个参数特别重要因为它直接连接了散列查找的时间效率和空间效率。若表设计得过小虽然节省空间但会导致冲突频繁查找速度下降若表设计得过大虽然查找更快却会浪费大量空间。因此散列表从来不是“越满越好”或“越空越好”而是要在时间与空间之间找到平衡。这一点其实和前面分块查找选择块长、B 树选择结点规模、平衡树控制高度本质上是同一类问题优秀查找结构的背后总存在某种“代价平衡”的设计思想。十六、把这一章串起来看其实是在不断缩短查找路径如果把整章内容连起来会发现它讲的是一条非常清楚的演化路线。最开始是顺序查找几乎没有额外结构只能逐个比较。接着是折半查找通过有序性把线性比较压缩成对数级。然后是分块查找通过两级结构减少整体比较次数。再往后二叉排序树把有序性组织成动态层次结构平衡二叉树解决树形退化问题B 树进一步为大规模外存环境降低层数散列表则干脆跳出“逐层比较”的框架尝试用地址映射一步逼近目标。也就是说整章所有方法虽然形式不同但都围绕同一个目标让查找路径更短让平均比较次数更少让更新与维护的代价更可控。你会发现所谓查找算法并不只是技巧而是一整套围绕“如何组织数据以支持快速定位”的思想体系。十七、这一章最容易混淆的地方常常都和“前提条件”有关这一章最容易出错的地方通常不是公式不会算而是忘了某种方法的使用条件。第一折半查找必须建立在有序顺序表上不是任意线性表都能直接用。第二二叉排序树虽然平均效率高但最坏情况下可能退化不要把它和平衡二叉树混为一谈。第三平衡二叉树的旋转并不是为了“好看”而是为了控制高度并保持二叉排序树性质。第四B 树适合多路平衡和外存环境不要把它简单看成“更复杂的二叉树”。第五散列表的效率不是绝对 O(1)它依赖于散列函数设计、冲突处理方式以及装填因子控制。冲突一旦增多平均查找长度也会明显上升。第六平均查找长度 ASL 在不同方法中都很重要但它的含义要结合具体结构理解。对于顺序查找它体现的是位置分布对于树表查找它与树高和结点分布有关对于散列表它和冲突情况密切相关。结语这一章表面讲的是“查找”实际上讲的是“为了快速找到目标数据结构可以演化到什么程度”。从线性表中的逐个比较到有序表中的折半缩减从树中的层次定位到散列中的地址映射查找方法的变化其实就是数据组织方式不断升级的过程。真正把这一章学懂之后会逐渐形成一种很重要的认识查找效率高不高往往不是因为程序写得更巧而是因为数据在进入程序之前就已经被组织成了更适合查找的样子。到这里数据结构这门课的核心思想也会变得越来越清晰——算法效率很多时候不是事后补救出来的而是在结构设计之初就决定了方向。重点问题