考研笔记

查找的基本概念

这一节只有五个定义，但第 7 章后面每一道计算题的答案都是从这五个定义里推出来的。

整章的结构是：先给一堆查找方法，再用同一把尺子量它们。这把尺子就是 。折半查找要算它、分块查找要算它、二叉排序树要算它、散列表要算它——方法在变，量法不变。所以这一节写错一个词，后面五节的数都是错的。

这一节还立了全章的第一条分界线：静态查找表 / 动态查找表。这条线决定了 7.2.2 折半查找 为什么不能用链表存、7.3.1 二叉排序树 为什么存在。

机制

五个定义

术语定义
查找在数据集合中寻找满足某种条件的数据元素的过程。结果只有两种：查找成功、查找失败
查找表用于查找的数据集合，由同一类型的数据元素（或记录）组成
静态查找表只涉及查找操作，无须动态修改的查找表
动态查找表需要动态插入或删除的查找表
关键字数据元素中唯一标识该元素的某个数据项的值

「查找表」是一个逻辑上的说法，不是一种存储结构。 顺序表、链表、树、散列表都可以充当查找表——这一章讲的就是用不同的结构充当查找表时，查找的代价各是多少。

静态与动态：全章的第一条分界线

适合的查找方法
静态查找表顺序查找、折半查找、散列查找
动态查找表二叉排序树的查找、散列查找

散列查找是唯一同时出现在两栏里的。 这不是排版重复，是散列表的实质：它既能 查，也能 插入和删除，两种场合都称职。折半查找做不到——它一插入就要移动元素；二叉排序树反过来，动态很强但静态时性能不如折半稳定（见 7.3.1 末尾的对比）。

边界辨析：

「静态 / 动态」说的是查找表要不要变，不是查找算法本身的性质。 同一个折半查找算法，用在一张永不修改的表上是静态查找，硬用在频繁增删的表上也能跑， 只是每次插入要 移动元素，代价不合算。教材说「适合」，不是说「只能」。

平均查找长度

  • ：查找表的长度
  • ：查找第 个数据元素的概率，一般认为等概率，即
  • ：找到第 个数据元素所需进行的比较次数

平均查找长度是衡量查找算法效率的最主要的指标。

查找长度是比较次数，不是边数

的定义是「需要比较的关键字次数」。这个措辞要一个字一个字读：

  • 不是走过的边数
  • 不是层数减一
  • 在判定树 / 二叉排序树上，它等于从根结点到目的结点路径上的结点数（7.2.2 判定树那一段的原话）

所以根结点的查找长度是 1 不是 0，第二层是 2 不是 1。

口径差异：

算法竞赛里习惯用「深度」「层数」描述树上位置，且常从 0 起算。 408 的查找长度一律从 1 起算，且数的是结点不是边。 手算 时若按算竞习惯从 0 数，整张表会系统性地差 1，而分子分母都被污染， 最后的分数看起来很像对的——这是最难自查出来的一类错。

成功与不成功要分开算

后面每一节都要给出两个 ：

  • 成功：在表中找到时的平均比较次数
  • 不成功：确认不在表中所需的平均比较次数

真正拉开各方法差距的是「不成功」那一个。 顺序查找和有序线性表的顺序查找，成功 完全一样，差别全在不成功：前者 ，后者约 （7.2.1）。散列表也一样——装填因子对成功和不成功的影响幅度差得很远（7.5.4）。

看到题目只说「平均查找长度」而没说哪一个，先看它给的是不是「等概率查找表中任一元素」——是，则指成功。

手算模板

算任何一种查找方法的 ，都是同样三步：

  1. 画出这种方法的判定结构——折半查找画判定树、分块查找画索引表+块、二叉排序树就是树本身、散列表列出探测序列。
  2. 给每个位置标查找长度：成功看圆形结点（到它的路径上的结点数）；失败看方形结点（到它父结点的路径上的结点数）。
  3. 加权平均：等概率时，成功除以 ，失败除以失败结点个数（通常是 ，散列表是表长或散列函数的值域大小，见 7.5.4）。

第 3 步的分母最容易错：成功除 ，失败不除 。

边界

说法判断说明
「查找表是一种存储结构」❌是逻辑上的数据集合，可用顺序表 / 链表 / 树 / 散列表实现
「静态查找表不能做查找以外的操作」⚠️是「无须动态修改」，不是「不允许」
「关键字可以重复」❌关键字唯一标识元素；可重复的叫次关键字，基于它的查找结果不唯一
「 里的 一定是 」❌只是一般认为等概率。给了不等概率就必须按给定概率加权（2013、2020 都考过）
「查找长度就是树的层数」❌是路径上的结点数，等于层数（层从 1 起算）；从 0 起算就错了
「不成功的 除以 」❌除以失败结点个数，一般是
「散列查找只适合静态查找表」❌两种都适合，是唯一横跨两栏的方法

对照速查

量式子
平均查找长度
等概率时
成功的分母
不成功的分母失败结点个数（一般 ）
分界线静态查找表动态查找表
要不要改表不改要插入 / 删除
典型方法顺序、折半、散列二叉排序树、散列
本章对应节7.2.1、7.2.27.3.1、7.4.1

考点

  • 的定义式与两个变体，全章计算的地基。
  • 查找长度数结点不数边、从 1 起算。
  • 不成功的 分母不是 。
  • 静态 / 动态的适用方法表，尤其散列横跨两栏。
  • 不等概率时按给定 加权，不能默认 。

链接

反向链接