第六章 查找

（一） 查找的基本概念和顺序查找

1 查找的定义

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

2 查找表

用于查找的数据集合

3 静态查找表

如果一个查找表只涉及查询某个数据元素是否在查找表或查询某个元素的属性的操作

4 动态查找表

在静态查找表的基础上。还对查找表进行插入或删除某个元素的操作

5 关键字

数据元素中某个可以唯一标识该元素的数据项

数据元素往往包含除了关键字以外的很多数据 这个数据元素也叫做是记录

6 平均查找长度（ASL：Average Search Length）

在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值

ASL相当于是查找算法的基本操作执行次数

ASL=$\sum_{i = 1}^{n}p_{i} \times c_{i}$i=1∑n​pi​×ci​ n是查找表中数据元素的个数，$p_{i}$pi​是查找第i个元素的概率。一般是等概率查找， $p_{i}$pi​值为1/n。 $c_{i}$ci​是找到第i个元素需要比较的关键字次数，即查找长度。

7 顺序查找

顺序查找(线性查找)，主要用于在线性表中进行查找。从查找表的一端开始，顺序扫描查找表，依次将扫描到的关键字和待查找的值key进行比较。如果相等，则查找成功。如果扫描结束仍然没有发现相等的数据元素，则查找失败。

（二） 拆半查找

折半查找仅适用于有序的顺序表

1 算法思路

首先将给定值key与表中中间位置元素的关键字比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分中。然后在缩小的范围内继续进行同样的查找，如此重复直到找到为止，或者确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。

对于折半查找，查找的比较次数就是从根结点到该结点经历的结点数，具有N个（N>0）结点的完全二叉树的高度为
log2(N+1)或 log2N+1，所以折半查找的时间复杂度为O(logn)

（三） 分块查找

分块查找又称为索引顺序查找

需要额外建立一个索引表来存储索引，每个索引对应表中每一块。

1 分块查找思想

①确定待查找值在哪个块（折半查找）

②在确定的块中查找待查找值（顺序查找）

由于分块查找实际是进行两次查找，所以整个算法的平均查找长度是两次查找的平均查找长度之和。即ASL分块=ASL折半+ASL顺序

设将长度为n的查找表均匀的分为b块，每块有s个记录，在等概率的情况下

1. 如果块间采用折半查找，块内采用顺序查找SL分块=ASL折半+ASL顺序

=⌈$\log$log2(b+1) ⌉+ $\frac{1 + s}{2}$21+s​

1. 如果块间和块内都采用顺序查找ASL分块=ASL块间顺序+ASL块内顺序

= $\frac{1 + b}{2}$21+b​ + $\frac{1 + s}{2}$21+s​ = $\frac{1 + n/s}{2}$21+n/s​ +
$\frac{1 + s}{2}$21+s​ = $\frac{s2 + 2s + n}{2s}$2ss2+2s+n​

（四） 二叉排序树

**二叉排序树(Binary Search Tree
也叫二叉搜索树)**或者是一棵空树，或者是具有以下性质的二叉树

1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值。

2. 若右子树不空，则右子树上所有结点的值均大于它的根结点的值。

3. 它的左右子树也是一棵二叉排序树。

1 算法思路

由于二叉排序树的特点(左子树<根结点<右子树),所以每次查找一个关键字，需要先和根结点进行比较：

如果这个关键字小于根结点的值，则再到这个根结点的左子树进行同样的比较操作一直进行下去直到找到该关键字，表示查找成功，或者是空指针，表示查找失败。

如果这个关键字大于根结点的值，则再到这个根结点的右子树进行同样的比较操作一直进行下去直到找到该关键字，表示查找成功，或者是空指针，表示查找失败。

二叉排序树的目的，不是为了排序，而是为了提高查找和插入删除关键字的速度。

2 二叉排序树插入算法思路

1)空树：直接插入新结点返回成功

2)树不空：检查是否存在关键字重复的结点：

1. 存在：返回插入失败

2. 不存在：检查根结点的值和待插入关键字值的大小关系递归插入左右子树

3 二叉排序树删除结点

1. 删除的是叶子结点

方法：直接删去该结点即可

1. 删除的是仅有左子树或者右子树的结点

方法：“子承父业”

1. 删除的是左右子树都有的结点

仿照②类型，先将一个孩子“继承父业”，另一个孩子“归顺”于这个孩子

方法：找到待删除结点的直接前驱或者直接后继结点，用该结点来替换待删除结点，再删除该结点。

4 时间复杂度

最好的情况就是这棵树能够足够平衡，也就是像左图这种完全二叉树。这种情况下查找时间复杂度为o(logn)

最坏的情况是这棵树是一个只有左或者右孩子的单分支斜树，此时它相当于是一个单链表，查找时间复杂度是O(n)

（五） 平衡二叉树（AVL树）

1 平衡二叉树的定义

**平衡二叉树(AVL树)**是特殊的二叉排序树，特殊的地方在于左右子树的高度之差绝对值不超过1，而且左右子树又是一棵平衡二叉树。

定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是−1、0或1

平衡二叉树的建立过程和二叉排序树的建立过程是相似的，都是从一棵空树开始陆续插入结点。不同的地方在于对于平衡二叉树的建立过程中，由于插入结点可能会破坏结点的平衡性，所以需要进行平衡调整。

每插入一个结点，都要检查二叉排序树的平衡性，如果出现不平衡，那么平衡调整首先要找出最小不平衡子树，然后对这个最小不平衡子树进行调整。

2 平衡调整

含有n个结点平衡二叉树的最大深度为O(log2n)，因此，平衡二叉树的平均查找长度为O(log2n)

（六） B树和B+树

1 2-3树

1. 2结点包含一个元素和两个孩子(或者没有孩子)。

2. 左子树包含的元素小于该结点的元素值，右子树包含的元素大于该结点的元素值

3. 2结点要不有两个孩子，要不就没有孩子，不允许有一个孩子

4. 3结点包含一大一小两个元素和三个孩子(或者没有孩子)。(两个元素按大小顺序排列好)

5. 左子树包含的元素小于该结点较小的元素值，右子树包含的元素大于该结点较大的元素值，中间子树包含的元素介于这两个元素值之间。

6. 3结点要不有三个孩子，要不就没有孩子，不允许有一个或两个孩子

7. 2-3树所有叶子结点都在同一层次

2 2-3-4树

1. 2结点包含一个元素和两个孩子(或者没有孩子)。

2. 左子树包含的元素小于该结点的元素值，右子树包含的元素大于该结点的元素值

3. 2结点要不有两个孩子，要不就没有孩子，不允许有一个孩子

4. 3结点包含一大一小两个元素和三个孩子(或者没有孩子)。

5. 左子树包含的元素小于该结点较小的元素值，右子树包含的元素大于该结点较大的元素值，中间子树包含的元素介于这两个元素值之间。

6. 3结点要不有三个孩子，要不就没有孩子，不允许有一个或两个孩子

7. 4结点包含小中大三个元素和四个孩子(或者没有孩子)。

8. 左子树包含的元素小于该结点最小的元素值，第二个子树包含大于最小的元素值小于中间元素值的元素，第三个子树包含大于中间元素值小于最大元素值的元素，右子树包含的元素大于该结点最大的元素值。

9. 4结点要不有四个孩子，要不就没有孩子，不允许有一个或两个或三个孩子

10. 2-3-4树所有叶子结点都在同一层次

3 B树

B树也是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例，我们把树中结点最大的孩子数目称为B树的阶。通常记为m。

一棵m阶B树或为空树，或为满足如下特性的m叉树：

1. 树中每个结点至多有m棵子树。（即至多含有m-1个关键字)
   (“两棵子树指针夹着一个关键字”)

2. 若根结点不是终端结点，则至少有两棵子树。(至少一个关键字)

3. 除根结点外的所有非叶结点至少有 ⌈m/2⌉棵子树。（即至少含有⌈m/2⌉-1个关键字）

4. 所有非叶结点的结构如下：

1. 所有的叶子结点出现在同一层次上，不带信息。(就像是折半查找判断树中查找失败的结点)

B树的查找操作

查找过程：①先让待查找关键字key和结点的中的关键字比较，如果等于其中某个关键字，则查找成功。

②如果和所有关键字都不相等，则看key处在哪个范围内，然后去对应的指针所指向的子树中查找。Eg:如果Key比第一个关键字K1还小，则去P0指针所指向的子树中查找，如果比最后一个关键字Kn还大，则去Pn指针所指向的子树中查找

B树的插入操作

分裂的方法：取这个关键字数组中的中间关键字(⌈n/2⌉)作为新的结点，然后其他关键字形成两个结点作为新结点的左右孩子。

B树的删除操作

B树中的删除操作与插入操作类似，但要稍微复杂些，要使得删除后的结点中的关键字个数≥⌈m/2⌉-1
，因此将涉及结点的“合并”问题。由于删除的关键字位置不同，可以分为关键字在终端结点和不在终端结点上两种情况。

1. 如果删除的关键字在终端结点上（最底层非叶子结点）：

2. 结点内关键字数量大于⌈m/2⌉-1
   ，这时删除这个关键字不会破坏B树的定义要求。所以直接删除。

3. 结点内关键字数量等于⌈m/2⌉-1 ，并且其左右兄弟结点中存在关键字数量大于⌈m/2⌉-1
   的结点，则去兄弟阶段中借关键字。

4. 结点内关键字数量等于⌈m/2⌉-1
   ，并且其左右兄弟结点中不存在关键字数量大于⌈m/2⌉-1 的结点，则需要进行结点合并

5. 如果删除的关键字不在终端结点上（最底层非叶子结点）：需要先转换成在终端结点上，再按照在终端结点
   上的情况来分别考虑对应的方法。

6. 第一种情况：存在关键字数量大于⌈m/2⌉-1
   的左子树或者右子树，在对应子树上找到该关键字的相邻关键字，然后将相邻关键字替换待删除的关键字。

7. 第二种情况：左右子树的关键字数量均等于⌈m/2⌉-1
   ，则将这两个左右子树结点合并，然后删除待删除关键字。

相邻关键字：对于不在终端结点上的关键字,它的相邻关键字是其左子树中值最大的关键字或者右子树中值最小的关键字。

4 B+树

B+树是常用于数据库和操作系统的文件系统中的一种用于查找的数据结构

m阶的B+树与m阶的B树的主要差异

1）在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有(n+1)棵子树。

2）在B+树中，每个结点（非根内部结点）关键字个数n的范围是
⌈m/2⌉≤n≤m（根结点1≤n≤m），在B树中，每个结点（非根内部结点）关键字个数n的范围是⌈m/2⌉
-1≤n≤m-1（根结点：1≤n≤m-1）。

3）在B+树中，叶结点包含信息，所有非叶结点仅起到索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。

4）在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。

5）在B+树中，有一个指针指向关键字最小的叶子结点，所有叶子结点链接成一个单链表。

5 散列表

散列表的定义

根据给定的关键字来计算出关键字在表中的地址的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。

散列函数

一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr。

散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为“冲突”，这些发生碰撞的不同关键字称为同义词。

构造散列函数的tips

1）散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。

2）散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间，从而减少冲突的发生。

3）散列函数应尽量简单，能够在较短的时间内就计算出任一关键字对应的散列地址。

常用Hash函数的构造方法

开放定址法

直接取关键字的某个线性函数值为散列地址，散列函数为H(key)=a×key+b。式中，a和b是常数。这种方法计算最简单，并且不会产生冲突

除留余数法

假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，利用以下公式把关键字转换成散列地址。散列函数为H(key)=key
%
p。除留余数法的关键是选好p，使得每一个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性

数字分析法

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

平方取中法

顾名思义，取关键字的平方值的中间几位作为散列地址。具体取多少位要看实际情况而定。这种方法得到的散列地址与关键字的每一位都有关系，使得散列地址分布比较均匀。

折叠法

将关键字分割成位数相同的几部分（最后一部分的位数可以短一些），然后取这几部分的叠加和作为散列地址，这种方法称为折叠法。关键字位数很多，而且关键字中每一位上数字分布大致均匀时，可以采用折叠法得到散列地址。

常用Hash函数的冲突处理办法

开放定址法

将产生冲突的Hash地址作为自变量，通过某种冲突解决函数得到一个新的空闲的Hash地址。

线性探测法

冲突发生时，顺序查看表中下一个单元（当探测到表尾地址m-1时，下一个探测地址是表首地址0），直到找出一个空闲单元（当表未填满时一定能找到一个空闲单元）或查遍全表。

平方探测法

设发生冲突的地址为d,平方探测法得到的新的地址序列为d+12，d-12，d+22，d-22…，平方探测法是一种较好的处理冲突的方法，可以避免出现“堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。

再散列法

又称为双散列法。需要使用两个散列函数，当通过第一个散列函数H(Key)得到的地址发生冲突时，则利用第二个散列函数Hash2(Key)计算该关键字的地址增量。

伪随机序列法

当发生地址冲突时，地址增量为伪随机数序列，称为伪随机序列法。

拉链法

对于不同的关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。拉链法适用于经常进行插入和删除的情况。

散列函数和冲突处理办法