查找

# 查找

# 查找基本概念

# 基本概念

查找 —— 在数据集合中寻找满足某种条件的数据元素的过程称为查找
查找表（查找结构）—— 用于查找的数据集合称为查找表，它由同⼀类型的数据元素（或记录）组成
关键字 —— 数据元素中唯⼀标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯⼀的。

# 对查找表的常见操作

查找符合条件的数据元素
插入、删除某个数据元素

# 查找算法的评价指标

查找长度 —— 在查找运算中，需要对比关键字的次数称为查找长度
平均查找长度（ASL, Average Search Length ）—— 所有查找过程中进行关键字的比较次数的平均值

通常认为查找任何⼀个元素的概率都相同

评价⼀个查找算法的效率时，通常考虑查找成功 / 查找失败两种情况的 ASL

ASL 的数量级反应了查找算法时间复杂度

# 顺序查找

# 顺序查找的算法思想

顺序查找，又叫 “线性查找”，通常用于线性表。

算法思想：从头到尾挨个找（或者反过来也可以）

typedef struct { //查询表的数据结构（顺序表）
	ElemType *elem;//动态数组基址
	int TableLen; //表的长度
} SSTable;

//顺序查找
int Search_Seq(SSTable ST, ElemType key) {
	int i;
	for (i = 0; i < ST.TableLen && ST.elem[i] != key; ++i);
	//查找成功，则返回元素下标；查找失败，则返回-1
	return i == ST.TableLen ? -1;

}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 顺序查找的实现（哨兵）

typedef struct { //查询表的数据结构（顺序表）
	ElemType *elem;//动态数组基址
	int TableLen; //表的长度
} SSTable;

//顺序查找
int Search_Seq(SSTable ST, ElemType key) {
	ST.elem[0] = key; //哨兵
	int i;
	for (i = ST.TableLen; ST.elem[i] != key; --i);
	//查找成功，则返回元素下标；查找失败，则返回0
	return i;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

优点：无需判断是否越界，效率更高

# 查找效率分析

A S L = \sum_{i = 1}^{n} P_{i} C_{i} \begin{array}{l} {ASL}_{成功} = \frac{1 + 2 + 3 + \dots + n}{n} = \frac{n + 1}{2} \\ {ASL}_{失败} = n + 1 \end{array}

即 $O = (n)$

# 顺序查找的优化（对有序表）

# 用查找判定树分析 ASL

⼀个成功结点的查找长度 = ⾃身所在层数
⼀个失败结点的查找长度 = 其父节点所在层数
默认情况下，各种失败情况或成功情况都等概率发⽣

# 顺序查找的优化（被查概率不相等）

# 总结

# 折半查找

折半查找，又称 “二分查找”，仅适用于有序的顺序表。

33>mid，只可能在右边区域

# 算法思想

只有在 [low, high] 之间才有可能找到目标关键字

失败情况，当 low>high 时

# 代码实现

//折半查找
int Binary_Search(SSTable L, ElemType key) {
	int low = 0; high = L.TableLen - 1, mid;
	while (low <= high) {
		mid = (low + high) / 2; //取中间位置
		if (L.elem[mid] == key) {
			return mid; //查找成功则返回所在位置
		} else if (L.elem[mid] > key) {
			high = mid - 1; //从前半部分继续查找
		} else {
			low = mid + 1; //从后半部分继续查询
		}
	}
	return -1; //查找失败，返回-1
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 查找效率分析

紫色为查找失败，绿色为查找成功

# 折半查找判定树的构造

如果当前 low 和 high 之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等
如果当前 low 和 high 之间有偶数个元素，则 mid 分隔后，左半部分比右半部分少⼀个元素
折半查找的判定树中，若 $mid = ⌊ (low + high) / 2 ⌋$ 则对于任何⼀个结点，必有：右子树结点数 - 左子树结点数 = 0 或 1

判定树结点关键字：左 < 中 < 右，满⾜二叉排序树的定义

失败结点：n+1 个（等于成功结点的空链域数量）

# 折半查找的查找效率

# 总结

# 分块查找

分块查找，又称索引顺序查找，算法过程如下：

在索引表中确定待查记录所属的分块（可顺序、可折半）
在块内顺序查找

# 用折半查找查索引

查找成功

查找失败

若索引表中不包含目标关键字，则折半查找索引表最终停在 low>high，要在 low 所指分块中查找

原因：最终 low 左边⼀定小于目标关键字，high 右边⼀定大于目标关键字。而分块存储的索引表中保存的是各个分块的最大关键字

查找失败

# 查找效率分析（ASL）

若查找表是 “动态查找表”，使用链式存储方式可以更方便的插入删除

# 总结

# B 树

# 5 叉查找树

# 如何查找

# 如何保证查找效率

策略 1：m 叉查找树中，规定除了根节点外，任何结点至少有 $⌈ m / 2 ⌉$ 个分叉，即至少含 $⌈ m / 2 ⌉ - 1$ 个关键字

策略 2：m 叉查找树中，规定对于任何⼀个结点，其所有子树的高度都要相同。

不够 “平衡”，树会很高，要查很多层结点

# B 树

如果满足上述两个策略其实就是一个 5 阶 B 树

B 树，⼜称多路平衡查找树，B 树中所有结点的孩子个数的最大值称为 B 树的阶，通常用 m 表示。⼀棵 m 阶 B 树 或为空树，或为满⾜如下特性的 m 叉树：

树中每个结点至多有 m 棵子树，即至多含有 m-1 个关键字。
若根结点不是终端结点，则至少有两棵子树。
除了根节点外，任何结点至少有 $⌈ m / 2 ⌉$ 个分叉，即至少含 $⌈ m / 2 ⌉ - 1$ 个关键字
所有非叶结点的结构如下：

其中， $K_{i} （ i = 1, 2, \dots, n ）$ 为结点的关键字，且满⾜ $K_{1} < K_{2} < \dots < K_{n} ； P_{i} （ i = 0, 1, \dots, n ）$ 为指向子树根结点的指针，且指针 $P_{i} - 1$ 所指子树中所有结点的关键字均小于 $K_{i}$ ， $P_{i}$ 所指子树中所有结点的关键字均大于 $K_{i}$ ， $n (⌈ m / 2 ⌉ - 1 ⩽ n ⩽ m - 1)$ 为结点中关键字的个数。
所有的叶结点都出现在同⼀层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。

即 m 阶 B 树的核心特性：

根节点的子树数 $\in [2, m]$ ，关键字数 $\in [1, m - 1]$ 。其他结点的子树数 $\in [⌈ m / 2 ⌉, m]$ ；关键字数 $\in [⌈ m / 2 ⌉ - 1, m - 1]$
对任⼀结点，其所有子树高度都相同
关键字的值：子树 0 <关键字 1 < 子树 1 < 关键字 2 < 子树 2<…. (类比二叉查找树左 < 中 < 右)

# B 树的高度

含 n 个关键字的 m 阶 B 树，最小高度、最大高度是多少？

注：大部分学校算 B 树的高度不包括叶子结点（失败结点）

最小高度 —— 让每个结点尽可能的满，有 $m - 1$ 个关键字，m 个分叉，则有

$n ⩽ (m - 1) (1 + m + m^{2} + m^{3} + \dots + m^{h - 1}) = m^{h} - 1, 因此 h \geq \log_{m} (n + 1)$

最大高度 —— 让各层的分叉尽可能的少，即根节点只有 2 个分叉，其他结点只有 $⌈ m / 2 ⌉$ 个分叉各层结点至少有：第⼀层 1、第二层 2、第三层 $2 ⌈ m / 2 ⌉$ … 第 h 层 $2 ⌈ m / 2 ⌉^{h - 2}$

第 h+1 层共有叶子结点（失败结点） $2 ⌈ m / 2 ⌉^{h - 1}$ 个

n 个关键字的 B 树必有 n+1 个叶子结点，则 $n + 1 \geq 2 (⌈ m / 2 ⌉)^{h - 1}, 即 h \leq \log_{⌈ m / 2 ⌉} \frac{n + 1}{2} + 1$

# 总结

# B 树插入和删除

# B 树的插入

5 阶 B 树 —— 结点关键字个数 $⌈ m / 2 ⌉ - 1 \leq n \leq m - 1$ 即：2≤n≤4 （注：此处省略失败结点）

在插⼊ key 后，若导致原结点关键字数超过上限，则从中间位置（ $⌈ m / 2 ⌉$ ）将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置（ $⌈ m / 2 ⌉$ ）的结点插⼊原结点的父结点

新元素⼀定是插⼊到最底层 “终端节点”，用 “查找” 来确定插⼊位置

如插入元素 90

插入元素 99

插入元素 88，右子树节点关键字数超过上限，找出 $⌈ m / 2 ⌉$ 元素进行分裂，再将 $⌈ m / 2 ⌉$ 的结点插入到原父节点中

插入元素 83

插入元素 87

插入元素 70

此时我们 $⌈ m / 2 ⌉$ 是元素 80，哪么元素 80 放置到哪个位置合适？

我们需要把 80 移动到它的原父结点中，但必须保证插入后的结点仍然保持有序性

插入元素 93

插入元素 73，74，75 三元素

在插⼊ key 后，若导致原结点关键字数超过上限，则从中间位置（$\lceil m / 2\rceil $）将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置（ $\lceil m / 2\rceil $）的结点插⼊原结点的父结点。若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致 B 树⾼度增 1。

核⼼要求：

对 m 阶 B 树 —— 除根节点外，结点关键字个数 $⌈ m / 2 - 1 ⌉ \leq n \leq m - 1$
子树 0 < 关键字 1 < 子树 1 < 关键字 2 < 子树 2<….

新元素⼀定是插⼊到最底层 “终端节点”，用 “查找” 来确定插⼊位置

# B 树的删除

# 终端节点 - 直接删除

若被删除关键字在终端节点，则直接删除该关键字（要注意节点关键字个数是否低于下限 $⌈ m / 2 ⌉ - 1$ ）

如删除 60

# 非终端节点 - 直接前驱 / 后驱

若被删除关键字在非终端节点，则用直接前驱或直接后继来替代被删除的关键字，有两种方式 直接前驱：当前关键字左侧指针所指子树中 “最右下” 的元素

如删除 80

直接后继：当前关键字右侧指针所指子树中 “最左下” 的元素

如删除 77

若被删除关键字在非终端节点，则用直接前驱或直接后继来替代被删除的关键字

直接前驱：当前关键字左侧指针所指子树中 “最右下” 的元素
直接后继：当前关键字右侧指针所指子树中 “最左下” 的元素

对非终端结点关键字的删除，必然可以转化为对终端结点的删除操作

# 被删除节点关键字个数低于下限 - 父子换位法

若被删除关键字所在结点删除前的关键字个数低于下限，且与此结点右（或左）兄弟结点的关键字个数还很宽裕，则需要调整该结点、右（或左）兄弟结点及其双亲结点（父子换位法）

如删除 38

此时被删除的节点低于 m 阶 B 树的最小关键字个数，需要向它的右兄弟借，但不能直接换位

即当右兄弟很宽裕时，用当前结点的后继、后继的后继来填补空缺

我们来看借左兄弟的情况，如删除 90

当左兄弟很宽裕时，用当前结点的前驱、前驱的前驱来填补空缺

本质：要永远保证子树 0 < 关键字 1 < 子树 1 < 关键字 2 < 子树 2<….

# 被删除节点关键字个数低于下限 - 兄弟不够借合并

兄弟不够借。若被删除关键字所在结点删除前的关键字个数低于下限，且此时与该结点相邻的左、右兄弟结点的关键字个数 $=\lceil m / 2\rceil $ ，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并

合并后，73 所在的节点也低于 m 阶 B 树的关键字结点个数的最小值，我们同时需要把 73 所在的节点进行合并

根节点为空，可以把根节点删除

在合并过程中，双亲结点中的关键字个数会减 1。若其双亲结点是根结点且关键字个数减少至 0（根结点关键字个数为 1 时，有 2 棵子树），则直接将根结点删除，合并后的新结点成为根；若双亲结点不是根结点，且关键字个数减少到 $⌈ m / 2 ⌉ - 2$ ，则⼜要与它⾃⼰的兄弟结点进⾏调整或合并操作，并重复上述步骤，直至符合 B 树的要求为止。

# 总结

# B + 树

⼀棵 m 阶的 B + 树需满⾜下列条件：

每个分⽀结点最多有 m 棵子树（孩子结点）。
非叶根结点至少有两棵子树，其他每个分⽀结点至少有 $\lceil m / 2\rceil $ 棵子树。
结点的子树个数与关键字个数相等。
所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。
所有分⽀结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。

# B + 树的查找

查询失败例子

B + 树中，无论查找成功与否，最终⼀定都要走到最下面⼀层结点

也可以进行顺序查找，直接查找叶子结点

# B + 树 VS B 树

m 阶 B 树 / B + 树：：

- B + 树：结点中的 n 个关键字对应 n 棵子树
- B 树：结点中的 n 个关键字对应 n+1 棵子树
- B + 树：根节点的关键字数 $\in [1, m]$ 其他结点的关键字数 $\in [⌈ m / 2 ⌉, m]$
- B 树：根节点的关键字数 $\in [1, m - 1]$ 。其他结点的关键字数 $\in [⌈ m / 2 ⌉ - 1, m - 1]$
- B + 树：叶结点包含全部关键字，非叶结点中出现过的关键字也会出现在叶结点中
- B 树：各结点中包含的关键字是不重复的
- B + 树：叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
- B 树：结点中都包含了关键字对应的记录的存储地址

B + 树典型应用：关系型数据库的 “索引”（如 MySQL）

在 B + 树中，非叶结点不含有该关键字对应记录的存储地址。可以使⼀个磁盘块可以包含更多个关键字，使得 B + 树的阶更大，树⾼更矮，读磁盘次数更少，查找更快

# 总结

# 散列查找

# 散列表（Hash Table）

散列表（Hash Table），⼜称哈希表。是⼀种数据结构，特点是：数据元素的关键字与其存储地址直接相关

通过 “散列函数（哈希函数）”： Addr=H(key)

例：有⼀堆数据元素，关键字分别为 {19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}，散列函数 H(key)=key%13

若不同的关键字通过散列函数映射到同⼀个值，则称它们为 “同义词”
通过散列函数确定的位置已经存放了其他元素，则称这种情况为 “冲突”

# 处理冲突的方法 —— 拉链法

拉链法（⼜称链接法、链地址法）处理 “冲突”：把所有 “同义词” 存储在⼀个链表中

例：有⼀堆数据元素，关键字分别为 {19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}，散列函数 H(key)=key%13

# 散列查找

通过散列函数计算目标元素存储地址： Addr=H(Key)

如查找 27 的元素 27%13=1

27 的查找长度 = 3

查找失败

如查找 21 的元素 21%13=8

21 的查找长度 = 0，有的教材也会把 “空指针” 的判定算作⼀次比较 21 的查找长度 = 1，这里我们使用常用的长度为 0

查找长度 —— 在查找运算中，需要对比关键字的次数称为查找长度

# 常见的散列函数

除留余数法 —— H(key) = key % p 散列表表长为 m，取⼀个不大于 m 但最接近或等于 m 的质数 p

为什么要取⼀个不大于 m 但最接近或等于 m 的质数 p？

如果我们可能出现的关键字只有偶数

直接定址法 —— H(key) = key 或 H(key) = a*key + b

其中，a 和 b 是常数。这种方法计算最简单，且不会产⽣冲突。它适合关键字的分布基本连续的情 况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

数字分析法 —— 选取数码分布较为均匀的若⼲位作为散列地址

设关键字是 r 进制数（如十进制数），而 r 个数码在各位上出现的频率不⼀定相同，可能在某些位 上分布均匀⼀些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若⼲位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。