查找 | DS

基本概念

查找

在数据集合中寻找满足某种条件的过程。

查找结果：成功、失败。

查找表

用于查找的数据集合。由同一类型的数据元素（或记录）组成。

对查找表的常见操作

查询某个特定元素是否在查找表中。
检索满足条件的某个特定的数据元素的各种属性。
插入。
删除。

静态查找表

只涉及上述 1 和 2 操作。

适合静态查找表的查找方法：顺序查找、折半查找、散列查找等。

动态查找表

需要动态地插入或删除的查找表。

适合动态查找表的查找方法：二叉排序树的查找、散列查找等。

关键字

数据元素中唯一标识该元素的某个数据项的值。

使用基于关键字的查找，查找结果应该是唯一的。

平均比较次数/平均查找长度 ASL

ASL = $\sum^n_{i=1}P_i C_i$

$n$ 为查找表记录个数/长度；$P_i$ 为查找第 $i$ 个记录的概率，一般取 $\frac{1}{n}$，即认为每个数据元素的查找概率相等；$C_i$ 为找到第 $i$ 个记录需要比较的次数。

线性结构的查找

顺序查找

又称线性查找，对顺序表和链表都适用。

一般线性表

$ASL_{成功}=\frac{n+1}{2}$，$ASL_{失败}=n+1$（使用了哨兵）。

有序线性表

树中的矩形结点称为失败结点。若有 $n$ 个结点，则相应地有 $n+1$ 个失败结点。

$ASL_{成功}=\frac{n+1}{2}$，$ASL_{失败}=\frac{1+2+\cdots+n+n}{n+1}$ = $\frac{n}{2}+\frac{n}{n+1}$。

⚠注意：顺序查找，每个元素查找成功的比较次数只与其位置有关，与是否有序无关，因此无序表和有序表查找成功的 ASL 相同。

折半查找

又称二分查找，仅适用于有序的顺序表⚠。

折半查找判定树

有序序列有 $n$ 个元素，则对应的判定树有 $n$ 个非叶结点和 $n+1$ 个叶结点，其中叶结点表示查找不成功的情况。
是一棵平衡二叉排序树。
所有结点的左子树结点数量与右子树结点数量的关系统一。

与折半查找算法在选取中间结点时是向上取整还是向下取整有关。

折半查找的平均查找长度

🔥设判定树最下的一层非叶结点有 $m$ 个，不包含矩形非叶结点的树高为 $h$，则：

$ASL_{成功}=\frac{1}{n}(1×1+2×2+3×2^2……+h×m)$
$ASL_{失败} = \frac{1}{n+1} ((h-1)×(2^{h-1}-m)+h×2m)$

若为满二叉树，则 $ASL_{成功}=\frac{n+1}{n}\log_2(n+1)-1\approx\log_2(n+1)-1$。

🔥$h=\lceil \log_{2}(n+1) \rceil$，$h-1$ 层（圆形结点，即记录）必满。

🔥最大查找长度为 $h$（不管是成功还是失败）。

时间复杂度 $O(\log_2n)$，平均情况下比顺序查找的效率高。

二叉排序树最好情况下（即平衡）的平均查找长度与折半查找相同（二叉排序树的查找性能与数据的输入顺序有关）。

分块查找

又称索引顺序查找。

查找表分块，块间有序，块内可无序。

对查找表建立索引表，索引项对应表块，索引项由键值分量（本块最大/小关键字）和链值分量（本块第一个元素的地址），索引表按关键字有序排列。

分块查找的过程

使用二分/顺序查找在索引表中确定待查记录所在的块。
使用二分/顺序查找在该块内精确查找。

王道书上第二步是块内顺序查找。具体使用何种查找要看题目。元素很多的有序表，效率最快的分块查找是块内块间都采用折半查找。

分块查找的平均查找长度

ASL = 索引查找 ASL + 块内查找 ASL。

理想块长为 $\sqrt{n}$，若此时在块内和索引表中均采用顺序查找，则 $ASL=\sqrt{n}+1$。

通常不要求每个索引块中的元素个数都相等。

树形结构的查找

二叉排序树 BST

二叉排序树 Binary Sort Tree、二叉查找/搜索树 Binary Search Tree。

BST 定义

或是一棵空树，或是具有下列特性的二叉树：

左子树上所有结点的值均小于根结点的值（若左子树非空）。
则右子树上所有结点的值均大于根结点的值（若右子树非空）。
左、右子树也分别是一棵二叉排序树。

二叉排序树的中序遍历序列是递增有序的。

BST 基本操作

查找

平均查找长度：平衡时 $O(\log_2{n})$，单支时 $O(n)$。
插入

插入的结点一定是一个新添加的叶结点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子。
删除

叶子结点直接删。

只有左/右子树，删了顶上。

左右子树都有，则赋上直接前驱（左子树最右）或直接后继（右子树最左）的值，再按前两种情况删掉直接前驱或直接后继。
构造

从一棵空树出发，依次插入。

二叉排序树的查找 vs 二分查找

平均时间性能差不多。

二分查找判定树唯一（算法决定），二叉排序树不唯一（插入顺序决定）。

就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，平均执行时间为 $O(\log_2{n})$；二分查找的对象是有序顺序表，若有插入和删除操作，所花的时间代价是 $O(n)$。

当有序表是静态查找表时，宜用顺序表作为其存储结构，而采用二分查找实现其查找操作；若有序表是动态查找表，则应选择二叉排序树作为其逻辑结构。

平衡二叉树 AVL

平衡二叉树 (Balanced Binary Tree 或 Height-Balanced Tree)，或称 AVL 树。

AVL 树定义

或是一棵空树，或是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过 1。

若将二叉树上结点的平衡因子 BF (Balanced Factor) 定义为该结点的左子树的深度减去它的右子树的深度，则 AVL 树上所有结点的平衡因子只可能是 -1、0、1。

有真题将平衡二叉树默认为平衡二叉排序树，做题时要根据题意判别。

给定高度下平衡二叉树的最少结点数🔥

$n_0=0$，$n_1=1$，$n_2=2$，$n_h=n_{h-1}+n_{h-2}+1$（下标是高度）。

所有非叶结点的平衡因子均为 1。

亦可用于求解给定结点数的平衡二叉排序树的查找所需的最多比较次数（或平衡二叉树的最大高度）。

平衡二叉排序树的插入

先用二叉排序树的方法对结点进行插入。

每当在平衡二叉排序树中插入一个结点时，都要进行检查。若其插入路径上的结点因为此次操作而导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点 A，再对以 A 为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

调整对象：最小不平衡子树。

平衡调整

LL 平衡旋转（右单旋转）

新插入结点落在最小不平衡子树根结点的左孩子的左子树上：
RR 平衡旋转（左单旋转）

新插入结点落在最小不平衡子树根结点的右孩子的右子树上：
LR 平衡旋转（先左后右双旋转）

新插入结点落在最小不平衡子树根结点的左孩子的右子树上：
RL 平衡旋转（先右后左双旋转）

新插入结点落在最小不平衡子树根结点的右孩子的左子树上：

平衡二叉排序树的删除

先用二叉排序树的方法对结点进行删除。

删除后若不平衡，则对最小不平衡子树进行平衡调整。

⚠与插入后的平衡调整的不同：删除后的平衡调整可能需要多次。每次调整完当前最小不平衡子树时，都有可能造成该树根结点的祖先结点不平衡，需要继续平衡调整，甚至可能回溯到根结点（导致树高减 1）。

平衡二叉排序树的查找

最大深度为 $O(\log_{2}n)$，因此平均查找长度为 $O(\log_{2}n)$。

红黑树

红黑树定义

一棵红黑树是满足下列红黑性质的二叉排序树：

每个结点或是红色，或是黑色的
根结点是黑色的
叶结点（虚构的外部结点、NULL 结点）都是黑色的
不存在两个相邻的红结点（即红结点的父结点和孩子结点均是黑色的）
对每个结点，从该结点到任意一个叶结点的简单路径上，所含黑结点的数量相同。

左根右，根叶黑，不红红，黑路同

黑高 bh

从某结点出发（不含该结点）到达任一叶结点的简单路径上的黑结点总数称为该结点的黑高。

根结点的黑高称为红黑树的黑高。

红黑树特点

从根到叶结点的最长路径不大于最短路径的 2 倍。

从根到叶结点的最短路径，必然全由黑结点构成。

从根到叶结点的最长路径，必然由黑红结点相间构成。
根的黑高至少为 $h/2$（不算叶结点），于是有：

1）内部结点数 $n \geq 2^{h/2} -1$。

2）有 $n$ 个内部结点的红黑树的高度 $h \leq 2\log_{2}(n+1)$。

如果红黑树的所有结点都是黑色的，那么它一定是一棵满二叉树。

二叉排序树 vs 平衡二叉排序树 vs 红黑树

为了保持 AVL 树的平衡性，插入和删除操作后，非常频繁地调整全树整体拓扑结构，代价较大。

红黑树的 “适度平衡”，由 AVL 树的 “高度平衡”，降低到 “任意一个结点的左右子树的高度，相差不超过 2 倍”，使得插入和删除很多时候不会破坏 “红黑” 特性，降低了动态操作时调整的频率。即使需要调整，一般都可以在常数级时间内完成。

对于一棵动态查找树，若插入和删除的操作比较少，查找操作比较多，采用 AVL 树比较合适，否则采用红黑树比较合适。

由于维护高度平衡所付出的代价比获得的效益大得多，红黑树的实际应用更广泛。

红黑树的插入（看叔脸色）

先用二叉排序树的方法对结点进行插入，然后进行染色和调整（若需要）。

新结点是根 → 染为黑色。
新结点非根 → 染为红色。

1）满足红黑树定义（不红红），则插入结束。

2）不满足红黑树定义（即父结点为红），则需要调整。

① 黑叔 → 旋转 + 变色
- LL 型：右单旋（父换爷），父爷变色。
- RR 型：左单旋（父换爷），父爷变色。
- LR 型：左、右双旋（儿换爷），儿爷变色。
- RL 型：右、左双旋（儿换爷），儿爷变色。
② 红叔 → 叔父爷变色，爷变新结点（递归）。

仅在出现连续两个红结点时才需要调整。

红黑树的删除

TODO

B 树

$m$ 阶 B 树——所有结点的平衡因子均等于 0 的 $m$ 路平衡查找树。

B 树定义

一棵 $m$ 阶 B 树，或是空树，或是满足下列性质的 $m$ 叉树：

每个结点至多 $m$ 棵子树（即至多含 $m-1$ 个关键字）。
根结点至少有 2 棵子树（根结点不是叶结点时）。

即根结点不是叶结点时，至少有一个关键字。
除根结点外的所有分支结点至少有 $\lceil m/2 \rceil$ 棵子树（即至少含 $\lceil m/2 \rceil-1$ 个关键字）。

为什么要至少含 $\lceil m/2 \rceil-1$ 个关键字？

因为 B 树核心特征是实现平衡、多路、查找树。小出度的结点容易造成树过深，不能很好地达到减少 I/O 次数、提高访问磁盘效率的设计目的。

如此规定一是为了保证存储密度，二是避免树结构退化，保证其在磁盘存储器中的存储优势。
所有叶结点在同一层，不包含任何信息。

实际上并不存在，指向这些叶结点的指针为空，可以视为外部结点或查找失败结点。

关键字个数为 $n$ 时，叶结点个数为 $n+1$。

王道：大多数教材将 B 树的叶结点定义为失败结点，而 408 真题中却常将 B 树的叶结点定义为最底层的终端结点。
所有非叶结点的结构

$n$ 为结点中关键字的个数（$\lceil m/2 \rceil -1 \leq n \leq m-1$）。

$K_i$ 为关键字，且满足 $K_1 ＜ K_2 ＜ … ＜ K_n$（降序也可，各结点内关键字有序）。

$P_i$ 为指向子树根结点的指针，且指针 $P_{i-1}$ 所指子树中所有结点的关键字均小于 $K_i$，$P_{i}$ 所指子树中所有结点的关键字均大于 $K_i$（降序就反过来）。

实际上在 B 树的每个结点中还应包括 $n$ 个指向每个关键字的记录的指针。

B 树的高度

这里 B 树高度不计入叶结点。

若 $n \geq 1$，则对任意一棵包含 $n$ 个关键字、高度为 $h$、阶数为 $m$ 的 B 树：

$n \leq (m-1)(1+m+m^2+…+m^{h-1})=m^h-1$

也可理解从叶结点个数考虑： $n+1 \leq m^h$。

因此有 $h \geq \log_m(n+1)$。
$n+1 \geq 2(\lceil m/2 \rceil)^{h-1}$（根结点两棵子树，其他分支结点 $\lceil m/2 \rceil$ 棵子树）

因此有 $h \leq \log_{\lceil m/2 \rceil}((n+1)/2)+1$

B 树的查找

包含 2 个基本操作：

在 B 树中找结点（磁盘）
在结点内找关键字（内存）

即在磁盘上找到目标结点后，先将结点信息读入内存，然后在结点内采用顺序查找法或折半查找法。

显然，在磁盘上进行一次查找比在内存上进行一次查找耗费时间多得多，因此，在磁盘上进行查找的次数，即待查关键字所在结点在 B 树上的层次数，是决定 B 树查找效率的首要因素。

B 树的插入

定位

利用查找算法找插入位置。

插入位置一定是最底层的某个非叶结点（终端结点）。
插入

插入后使得结点关键字个数大于 $m-1$，则必须对结点进行分裂。

分裂方法：中间位置即第 $\lceil m / 2\rceil$ 的关键字挤到父结点，其左边关键字放在原结点，右边关键字放到新结点中。

若造成父结点溢出，则父结点继续分裂。若最终导致根结点分裂，则树高 +1。

B 树的删除

要删除的关键字不在终端结点

用该关键字的前驱或后继替代，然后删除用来替代的关键字。

如此最终要删除的关键字必定落在某个终端结点，这样就转换成了要删除的关键字位于终端结点的情况。
要删除的关键字位于终端结点

该结点关键字个数 $＞ \lceil m/2 \rceil - 1$：直接删。

该结点关键字个数 $=\lceil m/2 \rceil - 1$，且有关键字个数 $＞\lceil m/2 \rceil - 1$ 的相邻兄弟结点：借关键字 + 父子换位。

该结点及其相邻兄弟结点关键字个数 $=\lceil m/2 \rceil - 1$：将关键字删除后与左或右兄弟结点及夹在二者中间的位于双亲结点中的关键字进行合并。合并会导致双亲结点关键字个数 -1，如有需要则继续递归向上合并，直到符合 B 树的要求为止。若最终导致根结点关键字减少为 0，则直接将根结点删除，合并后的新结点成为根。

⚠删除操作一定会导致叶结点的变化。

练手：王道 P325 选择 21（22 真题）。

B+树

应数据库所需而出现的一种 B 树的变形树。

B+树定义

一棵 $m$ 阶的 B+树需满足下列条件：

每个分支结点最多有 $m$ 棵子树。
结点子树个数与关键字个数相等。
非叶根结点至少 2 棵子树，其它分支结点至少 $\lceil m / 2\rceil$ 棵子树。
所有叶结点包含了全部关键字及指向相应记录的指针，且关键字有序。

有一个指针指向含最小关键字的叶结点，所有叶子结点链接成一个线性链表。
所有分支结点仅包含各子结点中关键字的最大值及指向其子结点的指针。

分支结点可视为索引的索引。

$m$ 阶 B 树 vs $m$ 阶 B+树

B+树：具有 $n$ 个关键字的结点只含有 $n$ 棵子树，即每个关键字对应一棵子树。

B 树：具有 $n$ 个关键字的结点含有 $n+1$ 棵子树。
B+树：叶结点包含了全部关键字，非叶结点中出现的关键字也会出现在叶结点中，有一定冗余。

B 树：最外层的终端结点包含的关键字和其他结点包含的关键字是不重复的。
B+树：叶结点包含信息，而所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。

B 树：每个关键字对应一个记录的存储地址。
B+树比 B 树更加适用于文件索引和数据库索引（磁盘读写代价更低，查询效率更稳定）。
可以对 B+树进行两种查找：从最小关键字开始的顺序查找、从根结点开始的多路查找。因为 B+树中通常有两个头指针，一个指向根结点，一个指向关键字最小的叶结点。

B 树只支持多路查找/随机查找。
B+树的查找、插入和删除操作和 B 树的基本类似

只是在查找过程中，非叶结点上的关键字值等于给定值时并不终止，而是继续向下查找，直到叶结点上的该关键字为止。

所以在 B+树中查找时，无论查找成功与否，每次查找都是一条从根结点到叶结点的路径。

散列结构的查找

线性表和树表，记录在表中的位置与记录的关键字之间不存在确定关系，查找方法建立在 “比较” 的基础上，查找的效率取决于比较的次数。

基本概念

散列表/哈希表

根据关键字而直接进行访问的数据结构。

散列表建立了关键字和存储地址之间的一种直接映射关系。

理想情况下，对散列表进行查找的时间复杂度为 O(1)，即与表中元素的个数无关。

散列函数/哈希函数

一个把查找表中的关键字映射成该关键字对应的地址的函数。

记为 $Hash(key) = Addr$，这里的地址可以是数组下标、索引或内存地址等。

冲突

散列函数把两个或两个以上的不同关键字映射到同一地址的情况。

冲突总是不可避免的。一方面，设计得好的散列函数应尽量减少冲突；另一方面，还要设计好处理冲突的方法。

同义词

发生冲突的不同关键字。

散列函数的构造方法

构造原则

散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。
散列函数计算出的地址应尽可能均匀地分布在整个地址空间，尽可能减少冲突。
散列函数应尽量简单，能够在较短时间内计算出任意一个关键字对应的散列地址。

下面介绍常用的散列函数。

直接定址法

直接取关键字的某个线性函数值为散列地址。

$H(key)=key$ 或 $H(key)=a×key+b$（$a、b$ 为常数）。

优点：计算最简单，不会产生冲突。

缺点：若关键字分布不连续，空位较多，则会造成存储空间的浪费。

适用：关键字的分布基本连续的情况。

除留余数法

$H(key) = key \% p, p \leq 表长$。

关键是选好 $p$，使得每个关键字通过该函数转换后等概率地映射到散列空间的任一地址，从而尽可能减少冲突的可能性。

$p$ 选择不大于表长的最大质数，或不包含小于 20 的质因数的合数（前提是小于表长）。

数字分析法

需要事先知道可能出现的关键字，选取关键字若干数位组成散列地址，选取时尽量减少冲突。

适用于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

例 1：设关键字是 $r$ 进制数，而 $r$ 个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为散列地址。

例 2：比方关键字集合是一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体同样，这种出现冲突的几率就会非常大。但年月日的后几位表示月份和详细日期的数字区别非常大，若用后面的数字来构成散列地址，则冲突的几率会明显减少。

平方取中法

取关键字平方值的中间几位作为散列地址（具体取多少位视实际情况而定）。

这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀。

适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

处理冲突的方法

任何设计出来的散列函数都不可能完全避免冲突。

需要考虑冲突发生时应该如何处理，即为产生冲突的关键字寻找下一个 “空” 的散列地址。

$H_i$ 表示处理冲突中第 $i$ 次探测得到的散列地址。

开放定址法

指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。

$H_i=(H(key)+d_i)\%m$

$m$ 表示散列表表长；$d_i$ 为增量序列；$i=0,1,2,…,k (k<m)$

取定某一增量序列后，对应的处理方法就是确定的。通常有以下 4 种取法：

线性探测法/线性探测再散列法

$d_i=i$，即 $d_i=1,2,…,m-1$

冲突发生时，顺序查看表中下一个单元，直到找出一个空闲单元或查遍全表。

容易产生聚集/堆积问题，导致其他本没有同义词的关键字也发生冲突，大大降低了查找效率。

🚩只有线性探测法容易引发堆积。
平方探测法/二次探测法/二次探测再散列法

$d_i = 1^2,-1^2,2^2,-2^2,…,k^2$,$-k^2$（$k ≤ m/2$）

表长 $m$ 只有是能够表示成 $4k+3$ 的素数时才能保证探测到整个散列表空间。

优点：可避免出现堆积问题，是一种处理冲突的较好方法。

缺点：不能保证探测到散列表上所有的单元（但至少能探测到一半单元）。
双散列法

使用两个散列函数，当通过第一个散列函数 $H(key)$ 得到的地址发生冲突时，利用第二个散列函数 $H_2(key)$ 计算该关键字的地址增量。

$d_i = H_2(key)$，$H_i = (H(key) + i × H_2(key)) \% m$

$i$ 是冲突的次数，初始探测位置 $H_0=H(key)\%m$

最多经过 $m - 1$ 次探测就会遍历表中所有位置，回到 $H_0$。
伪随机序列法/伪随机探测再散列

$d_i=$ 伪随机序列

🚧在开放定址的情形下，不能随便物理删除表中的已有元素，不然会会截断其他具有相同散列地址元素的查找地址。可以进行逻辑删除📍，但执行多次逻辑删除后，散列表表面上看起来很满，实际上有许多位置未利用，因此需要定期维护散列表，把带有删除标记的元素物理删除。

堆积问题是同义词冲突的探查序列和非同义词之间不同的探查序列交织在一起，导致关键字查询需要经过较长的探测距离，会降低散列的效率。

拉链法/链接法 chaining

散列表每个单元存放的不再是记录本身，而是相应同义词线性链表的表头指针。

查找、插入、删除操作主要在同义词链中进行。

适用于经常进行插入和删除的情况。

再散列法/再哈希法

$H_i=RH_i(key)$，$i=1,2,…,k$

$RH_i$ 均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。

这种方法不易产生 “聚集”，但增加了计算的时间。

散列函数 → 冲突/碰撞，冲突处理 → 堆积/聚集

散列查找及性能分析

散列查找过程

对于一个给定的关键字 $key$，根据散列函数可以计算出其散列地址

初始化：$Addr=Hash(key)$

检测查找表中地址为 $Addr$ 的位置上是否有记录

若无记录，返回查找失败；若有记录，比较它与 $key$ 的值，若相等，则返回查找成功标志，否则执行步骤 2；
用给定的处理冲突方法计算 “下一个散列地址”，并把 $Addr$ 置为此地址，转入步骤 1。

散列查找效率

虽然散列表在关键字与记录的存储位置之间建立了直接映像，但由于冲突的产生，使得散列表的查找过程仍是一个给定值和关键字进行比较的过程，因此仍需要以平均查找长度 ASL 作为衡量散列表查找效率的度量。

🔥散列表的查找效率取决于：① 散列函数、② 冲突处理方法、③ 装填因子 $\alpha$。
散列表的装填因子 $\alpha$

定义为一个表的装满程度，即 $\alpha=\frac{表中记录数n}{散列表长度m}$

散列表的平均查找长度依赖于散列表的装填因子 $\alpha$，而不直接依赖于表中记录数 $n$ 或散列表长度 $m$。

直观地看，$\alpha$ 越大，表示散列表越满，发生冲突的可能性越大。

😚$\alpha$ 可能大于 1，比如解决冲突方法采用拉链法时。

ASL 的计算

冲突处理使用开放定址法探查时，遇到表中空关键字默认也算探测/比较一次。

这点比较特殊，前面线性结构和树形结构的查找失败结点以及没有算次数。

拉链法的空指针算还是不算有争议，王道 P337 应用题 03 空指针算一次。

题目有说明就按说明来，没说明的话默认开放定址法空结点算，拉链法空指针不算。
🔥$ASL_{失败}$ 的分母是散列函数的值域长度，探测起点位置只在散列函数的值域范围内，且探测长度最大为表长（即不能套圈）。
$ASL_{成功}$ 的分母一般就是表中关键字个数，因为大多数题目都是按等概率情况。但也要稍微留意一下，小心掉坑。
开放定址探测时遇到逻辑删除的位置也不能停，要继续往后探测，就当那个位置还有元素，所以也算一次探测/比较。

拿来练手：

散列函数为 $H(key)=(3 × key)\%7$，冲突处理方法为线性探测法。

$ASL_{成功}$ = 12/7，$ASL_{失败}$ = (3+2+1+2+1+5+4)/7 = 18/7（两个分母都是 7 只是巧了）。

目前还没遇到综合考虑的题目。

刷题总结

看清题目问的是什么树！
折半查找判定树和二叉排序树，算查找失败 ASL 时是除以 n + 1（等概率），还有 2m 那里。

算 ASL 慢一点，容易算混。
最佳二叉排序树是折半查找判定树，而不是一般的平衡二叉排序树。
高度为 1 的平衡二叉树的形态共有 1 种

高度为 2 的平衡二叉树的形态共有 3 种

高度为 3 的平衡二叉树的形态共有 3×3 + 1×3 + 3×1 = 15 种

高度为 4 的平衡二叉树的形态共有 15×15 + 3×15 + 15×3 = 315 种

……
折半查找判定树的倒数第二层一定是满的。
二叉排序树删除一个结点后再将其插回，则在这番操作前后的二叉排序树：

该结点为叶结点 → 一定相同

该结点为非叶结点 → 一定不相同
平衡二叉排序树删除一个结点后再将其插回，则不管该结点是否为叶结点，在这番操作前后的平衡二叉排序树都有可能相同或不相同。
红黑树首先是一棵二叉排序树。
红黑树的红结点的数目最多是黑结点数目的两倍。
若红黑树所有结点都是黑色的，则它一定是一棵满二叉树。
给定一棵 B 树，并不能根据结点分支数判断是几阶，因为 B 树定义中只根据阶数对结点分支数做了范围限定。
$m$ 阶 B 树共有 $n$ 个关键字，求最大 $h$ 和最小 $h$

叶结点必为 $n+1$

最小 $h$ 的 B 树：全 $m$ 叉

最大 $h$ 的 B 树：根结点 2 叉，下面 $\lceil m/2 \rceil$ 叉

$h =$ 第一个能够容纳 $n+1$ 个结点的层的高度 $-1$

即 $h \geq \log_m(n+1)$，$h \leq \log_{\lceil m/2 \rceil}((n+1)/2)+1$
B 树最多/最少有几个结点/关键字，注意题目问的是什么（王道 P324 选择 08、09）。
计算散列表查找失败的 ASL 时，线性探查法遇到表中空关键字也算比较/探测一次，而链地址法的空指针不算次数。
散列函数 → 冲突/碰撞，冲突处理 → 堆积/聚集。

只有线性探测容易引发聚集。

故可以说发生聚集的原因主要是解决冲突的方法选择不当，而非负载因子过大。
散列查找失败的平均查找长度 P303 18

散列函数的值域

如：$H(key)=(3 × key)\%7$

$ASL_{成功}$ = 12/7，$ASL_{失败}$ = (3+2+1+2+1+5+4)/7 = 18/7