【考研复习：数据结构】查找（不含代码篇）

2023-10-31

前言：

1、此篇是基于博主对严蔚敏版教材《数据结构》、王道书《数据结构》和在网上相关资料的查询，对第七章 “ 查找 ” 的学习总结。

2、查找这一章含代码（C++）会写在另一篇。写好后再放链接。

3、博主比较喜欢用表格使思路稍微清晰一些，还有一些博主自己怕记乱的内容便标为注意点，只为了方便复习和记忆。

4、有些内容可能不是很全，基于时间和精力，只总结考试中可能会出现的内容。算是纯理论，请结合书中例题或网上例题来理解，应该会理解记忆更深。

5、欢迎各位大神帮忙纠正和补充。

一、基本概念：

（一）静态查找、动态查找

基本概念	内容
静态查找	顺序查找、折半查找（二分查找）、分块查找（索引顺序查找）、散列查找（哈希表）、斐波那契查找
动态查找	散列查找（哈希表）、各种树（二叉排序树、AVL树、B / B+ 树、红黑树等）

（二）结构

结构	内容
线性结构	顺序查找、折半查找（二分查找）、分块查找（索引顺序查找）
树形结构	二叉排序树、二叉平衡树、B 树、B+ 树
散列结构	散列表（哈希表）

注意：

1、顺序查找、折半查找、分块查找，查找表为线性表，其中折半查找效率较高。

2、线性表的查找更适合静态查找。

3、二叉排序树，又称二叉搜索树（BST）、二叉查找树。

4、AVL树：平衡二叉树（二叉排序树的一种特殊类型、4种平衡调整方法）

定义：

（1）空树；

（2）具备两个条件的二叉排序树：a、左子树和右子树的深度之差的绝对值不超过1；

b、左子树和右子树也是平衡二叉树。

5、B 树（B-tree）：多路平衡查找树。（外存文件系统中常用的动态索引技术）【B 树的阶m（即 m 路，m叉）：所有结点的孩子个数的最大值。】

6、B+ 树：（B树的变形，更适合用于文件索引系统）

7、B 树与 B+ 树区分：（ m - 1 = n 个关键字，非空树，各自的优点见 “ 二、查找方法的区分 ”）

树

根结点

每个结点（非根内部结点）

叶结点

非叶结点

树高 h

m 阶 B+ 树

每个分支结点最多有 m 棵子树。

$2\leq n \leq m$

$\left \lceil \frac{m}{2} \right \rceil \leq n \leq m$

1、包含全部关键字，即非叶结点中的关键字也会出现在叶结点中。

2、叶结点都出现在同一层次，包含信息。

3、叶结点中将关键字按小到大顺序排列。

4、叶结点之间通过指针链接。

仅起索引作用，其中每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。

非叶根结点至少 2 棵子树，其它分支结点至少 $\left \lceil \frac{m}{2} \right \rceil$ 根子树

m 阶 B 树

每个结点至多 m 棵子树，至多含 m - 1 个关键字。

$1\leq n \leq m-1$

$\left \lceil \frac{m}{2} \right \rceil -1\leq n \leq m-1$

1、（最外层内部结点）包含的关键字和其他结点包含的关键字是不重复的。

2、叶结点都出现在同一层次，并且不带任何信息。

3、各结点中的关键字均升序或降序排列。

4、不要求叶结点之间通过指针链接。

每个非终端结点中包含有n个关键字信息。

除根结点外的所有非叶结点：

1、至少 $\left \lceil \frac{m}{2} \right \rceil$ 根子树，即至少含有 $\left \lceil \frac{m}{2} \right \rceil -1$ 个关键字；

2、至多 m 棵子树，至多含 m - 1 个关键字。

$\tiny log_m(n+1)\leq h \leq [log_{\left \lceil \frac{m}{2} \right \rceil}(\frac{n+1}{2})]+1$

解释：

（1）根据图判断是 B 树还是 B+ 树：

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

（2）叶结点（最外层内部结点）包含的关键字和其他结点包含的关键字是不重复的。即任何一个关键字出现且只出现在一个结点中；

（3）B 树：所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；（读者反馈@冷岳：这里有错，叶子节点只是没有孩子和指向孩子的指针，这些节点也存在，也有元素。@研究者July：其实，关键是把什么当做叶子结点，因为如红黑树中，每一个NULL指针即当做叶子结点，只是没画出来而已）。

注：（3）摘自CSDN博主「v_JULY_v」的原创文章，原文链接：https://blog.csdn.net/v_JULY_v/article/details/6530142/

（4）B 树、B+ 树详解： https://www.cnblogs.com/lianzhilei/p/11250589.html

（以上两个网址里都可以看插入、删除操作，里面有图再结合上表内容易理解记忆）

（5）具有 n 个关键字的 m 阶 B 树，应有 n + 1 个叶结点。

（6）高度为 h 的 m = 3 阶 B 树，至少有 $(m-1)^h-1$ 个结点，至多有 $m^h-1$ 个结点。

（7）含有 n 个非叶结点的 m 阶 B 树中至少包含 $(n-1)*(\left \lceil \frac{m}{2} \right \rceil-1)+1$ 个关键字。

8、散列表：

（1）散列表属于线性结构，但不同于线性表的查找。顺序查找、二分查找、分块查找是以关键字比较为基础进行查找，而散列表是通过一种散列函数把记录的关键字和它在表中的位置建立起对应关系，并在存储记录发生冲突时采用专门的冲突的方法。

（2）散列表的平均查找长度与记录总数无关，是通过调节装填因子，把平均查找长度控制在所需的范围内。

（3）装填因子 $\alpha =\frac{n}{m}$ （表中记录数 n ，散列表长度 m）。装填因子越大（越 “ 满 ”），发生冲突的可能性越大。

（4）开放地址法和链地址法的比较（这两种都是处理冲突的方法）

比较项目	开放地址法	链地址法
空间	无指针域，存储效率较高	附加指针域，存储效率较低
时间	查找	有二次聚集现象，查找效率低	无二次聚集现象，查找效率高
插入、删除	不易实现	易于实现
适用情况	表的大小固定，适于表长无变化的情况	结点动态生成，适于表长经常变化的情况

（5）散列函数的 “ 好坏 ” 首先影响出现冲突的频繁程度。但一般情况下认为：凡是 “ 均匀的 ” 散列函数，对同一组随机的关键字，产生冲突的可能性相同，此时影响 ASL 的因素只有两个：处理冲突的方法和装填因子。

（6）产生堆积现象，即产生冲突，它对存储效率、散列函数和装填因子均不会有影响，而 ASL 会因为堆积现象而增大。

二、查找方法的区分

查找方法		平均查找长度	时间复杂度	空间复杂度	优点	缺点	备注
查找成功	查找失败
顺序查找	一般线性表	$\tiny ASL=\sum_{i = 1}^{n}P_i(n-i+1)$ $\tiny P_i = \frac{1}{n}, ASL=\frac{n+1}{2}$	ASL = n + 1	O(n)	O(1)	1、对数据元素的存储没有要求，顺序存储或链式存储都可。 2、对表中记录的有序性无要求。注意: （1）对线性的链表只能进行顺序查找。（2）有序线性表的顺序查找可链式存储。（区分折半查找）	当 n 比较大时，ASL较大，效率低
有序表	$\tiny ASL=\frac{n}{2}+\frac{n}{n+1}$
二分查找	有序表（仅适用于顺序存储结构）	$\small ASL=\frac{1}{n}(11+22+....+h*2^{h-1})$ 树高 $\tiny h = \left \lceil log_2(n+1) \right \rceil$ 也可为 $h = \left \lfloor log_2n \right \rfloor+1$ 树的高度，也是查找成功和查找失败的最多次数	$\tiny ASL =$ $\tiny \frac{1}{n+1}[(h-1)(n+1-n_0)+hn_02]$ $\tiny n_0$ 是叶结点数，h 是判定树的树高 $\tiny n_0$ 2是方形结点，查找不成功的数量	$\tiny O(log_2n)$		比较次数少，查找效率在大部分情况下比顺序查找高	1、不适用于数据元素经常变化动的线性表； 2、不适用于链式存储结构。	二分查找的判定树是平衡二叉树
分块查找	有动态结构、适于快速查找	将长度为 n 的查找表均匀地分为 b 块，每块有 s 个记录，等概率时，平均查找长度：块内和索引表都用顺序查找： $\tiny ASL=\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^2+2s+n}{2s}$ 当 $\tiny s=\sqrt{n}$ （理想块长）时，平均查找长度取最小值 $\tiny ASL=\sqrt{n}+1$	$\tiny O(log_2n)$		由于块内无序，插入和删除比较容易，无需进行大量移动。	要增加一个索引表的存储空间并对初始索引表进行排序运算	1、块内无序，块间有序； 2、若对索引项和索引块内部都采用折半查找，则查找效率最高。 3、查找效率介于顺序查找和二分查找之间。
块内用顺序查找，索引表用二分查找： $\tiny ASL=\left \lceil log_2(b+1) \right \rceil+\frac{s+1}{2}$
当 $\tiny s=\sqrt{n}$ （理想块长）时，块内和索引表都用二分查找： $\dpi{150} \tiny ASL=\left \lceil log_2(s+1) \right \rceil+\left \lceil log_2(s+1) \right \rceil$
二叉排序树	适用于经常进行插入、删除和查找运算的表。（ASL与树的形态有关）	最差情形：关键字有序，形成单支树（树的深度为 n ）： $\tiny ASL=\frac{n+1}{2}$	O(n)		1、数据结构采用树的二叉链表表示，就维护表的有序性而言，二叉排序树比二分查找更有效，因为无需移动记录，只需修改指针即可完成对结点的插入和删除操作。 2、可快速检索。	1、顺序存储可能会浪费空间(在非完全二叉树的时候) 2、最坏的情况——关键字有序(大到小或小到大排序)，此时，二叉排序树就退化成了普通链表，其检索效率就会很差。	中序遍历，结点值递增的有序序列（AVL树可参考二叉排序树）
最好情形：和折半查找的判定树相似，ASL 和 $\tiny log_2n$ 成正比	$\tiny O(log_2n)$
B 树		ASL 请见二叉排序树			若经常访问的数据离根结点很近，而B树的非叶子结点本身存有关键字其数据的地址，所以这种数据检索时效率会比 B+ 树高。		不支持顺序查找，支持多路查找（随机查找）。
树高 h: $\tiny log_m(n+1)\leq h \leq [log_{\left \lceil \frac{m}{2} \right \rceil}(\frac{n+1}{2})]+1$
B+ 树		ASL 请见二叉排序树			1、比 B 树层级更少、查询速度更快、更复稳定； 2、具备排序功能，即所有叶子结点是一个有序链表； 3、全节点遍历更快，B+ 树遍历整棵树只用遍历所有叶子结点；		1、支持顺序查找、随机查找 2、在 B+ 树中查找，无论查找成功与否，每次查找都是一条从根结点到叶结点的路径。
散列查找		（查找概率相等时） ASL（成功） = 查找成功所有记录所需的比较次数之和 / 散列表记录的个数 ASL（失败） = 查找失败所有的散列函数取值比较次数之和 / 散列函数取值的个数（此处的 ASL 建议看严蔚敏版教材《数据结构》来理解）	O(1)				查找效率取决于三个因素：散列表、处理冲突的方法、装填因子

三、题目解答（放松下，题目源自牛客网，都是博主做过的觉得还可以学习积累的，可以结合上述来做）

1、集合中任何两个元素都可以比较大小，但比较不满足传递性，可以通过hash索引使得在集合中查找元素的时间复杂度降到O(1)。

解：哈希所以可以认为是单纯的数值计算，并没有大小比较操作。

2、在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为 (n + 1) / 2。

解：因为每一个位置出现的几率相同故为 p = 1 / n

n 的位置查找的总次数为 A = n * (1 + n) / 2

平均下来的次数 = p * A = (n + 1) / 2 = 平均查找长度

顺序查找的平均时间 = n / 2

3、若有一个顺序有序表A[1:18] 中有18个元素，现进行二分查找，则查找 A［3］的比较序列的下标依次为9, 4, 2, 3。

解：假设[1:18]是单调递增，设A[3] = x。

先查找[1:18]的中间值mid =（1 + 18）/ 2 = 9.5，向下取整为9,

A[9] > x，于是范围变成了中值左边的取值，左右值变成了[1:9-1]即为[1:8]

mid =（1 + 8）/ 2 = 4.5，取值4

A[4] > x，于是范围变成了中值左边的取值，左右值变成了[1:4-1]即为[1:3]

mid = (1 + 3) / 2 = 2

A[2] < x，于是范围变成了中值右边的取值，范围变成[2+1:3]即为[3:3]

A[3] = X

由上：查找 A［3］的比较序列的下标依次为（9,4,2,3）。

4、一个文件包含了200个记录，若采用分块查找法，每块长度为4，则平均查找长度为28。

解：要看 200 / 4 = 50个块之间是否是有序的。

要是有序，可以二分查找，然后确定在那一个块中((n+1)log2(n + 1)) / n - 1 ，然后在这个块中查找。

要是无序，则顺序查找，平均查找长度就是（1 + 50）/ 2 = 25.5，然后块中查找(1 + 4) / 2 = 2.5 总共28。

5、已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key) = key%7 计算散列地址，并散列存储在散列表A【0....6】中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为 2 。

解：依次进行取模运算求出哈希地址：

A	0	1	2	3	4	5	6
记录	63	48		38	25	74	52
查找次数	1	3		1	1	2	4

平均查找长度 = 总的查找次数 / 元素数

总的查找次数：

38 % 7 = 3（第1次出现3，无冲突，放在位置3，查找次数为1）

25 % 7 = 4（第1次出现4，无冲突，放在位置4，查找次数为1）

74 % 7 = 4（第2次出现4，有冲突，放在位置5，查找次数为2）

63 % 7 = 0（第1次出现0，无冲突，放在位置0，查找次数为1）

52 % 7 = 3（第2次出现3，有冲突，发现冲突3,4,5，故只能放到6，查找次数为4）

48 % 7 = 6 （第1次出现6，有冲突，发现冲突6,0，故只能放到1，查找次数为3）

结果：（1 + 1 + 2 + 1 + 4 + 3）/ 6 = 2

6、一个线性序列（30，14，40，63，22，5），假定采用散列函数Hash(key) = key % 7来计算散列地址，将其散列存储在A[0~6]中，采用链地址法解决冲突。若查找每个元素的概率相同，则查找成功的平均查找长度是 4 / 3。

解：30 % 7 = 2 查找一次

14 % 7 = 0 查找一次

40 % 7 = 5 查找一次

63 % 7 = 0 查找两次

22 % 7 = 1 查找一次

5 % 7 = 5 查找两次

查找成功的平均查找长度 =（1 + 1 + 1 + 2 + 1 + 2）/6 = 4/3

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)