定义

查找是在数据集合中寻找满足某种条件的数据元素。用于查找的数据集合称为查找表或查找结构，通常由同一类型的数据元素组成。

关键字是数据元素中能够标识该元素的数据项。若使用关键字查找，且关键字能唯一标识元素，则查找结果应当唯一。

查找表按操作需求可分为两类：

类型 主要操作 关注点
静态查找表 只查找 查找速度
动态查找表 查找、插入、删除 查找速度与插入、删除是否方便

ASL

查找长度是在一次查找过程中进行关键字比较的次数。平均查找长度 ASL 是所有查找过程的关键字比较次数的加权平均：

$$
ASL=\sum_{i=1}^{n}P_iC_i
$$

其中 $P_i$ 是第 $i$ 种查找情况发生的概率，$C_i$ 是对应的查找长度。若默认所有元素等概率，则每个成功查找的概率通常取 $1/n$。

查找判定树

判定树是分析查找过程的工具。一次查找不是只看“结果成功还是失败”，而是看比较过程如何一步步把可能情况分开。把每一次关键字比较画成一个结点，把比较结果画成分支，就得到查找判定树。

只要某种查找过程可以用“比较关键字后进入下一种情况”来描述，就可以用判定树分析 ASL。顺序查找、折半查找、二叉排序树查找都可以使用这个视角。

判定树中有两类结点：

  • 成功结点：对应“找到了某个实际关键字”。
  • 失败结点：对应“目标不在表中”的某个失败区间或失败位置。

用判定树计算查找长度时，核心规则是：

  • 成功结点的查找长度等于该结点所在层数。
  • 失败结点的查找长度等于到达该失败情况前已经比较过的关键字个数；若把失败结点画在空链域位置，则它等于其父结点所在层数。

所以，ASL 的计算本质就是给判定树结点按层数加权：

$$
ASL=\sum P_i \times \text{对应情况的查找长度}
$$

若各成功情况等概率，成功 ASL 就是所有成功结点层数的平均值。若各失败情况等概率，失败 ASL 就是所有失败情况对应查找长度的平均值。

分类