8. 第六章：查找

8.1 查找的基本概念

8.1.1 查找定义：

查找（Search），又称为搜索，指从数据表中找出符合特定条件的记录。

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

8.1.2 关键字：

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

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

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

其中， 为数据规模， 为查找第 个记录的概率， 为查找第 个记录所需要的关键字比较次数。

8.2 线性表查找

根据在查找过程中是否对表有修改操作，分为静态查找和动态查找。根据数据结构不同又分为线性表查找、树表查找和散列表查找。散列表查找是一种比较特殊的查找技术。

8.2.1 顺序查找(线性查找)

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

顺序查找是最简单的查找方式，以暴力穷举的方式依次将表中的关键字与待查找关键字比较。

算法步骤

1）将记录存储在数组 中，待查找关键字存储在 中。

2）依次将 与 比较，比较成功则返回 ，否则返回 。

算法复杂度分析

（1）时间复杂度

顺序查找最好的情况是一次查找成功，最坏的情况是n次查找成功。假设查找每个关键字的概率均等，即查找概率 ，查找第i个关键字需要比较i次成功，则查找成功的平均查找长度如下。

如果查找的关键字不存在，则每次都会比较n次，时间复杂度也为 。

（2）空间复杂度

算法只使用了一个辅助变量i，空间复杂度为 。

8.2.2 折半查找

8.2.2.1 算法思路：

用一维数组 存储该有序序列，设变量 和 表示查找范围的下界和上界， 表示查找范围的中间位置， 为特定的查找元素。

算法步骤

1）初始化。令 ，即指向有序数组 的第一个元素； ，即指向有序数组 的最后一个元素。

2）判定 是否成立，如果成立，转向第3步，否则，算法结束。

3） ，即指向查找范围的中间元素。

4）判断 与 的关系。如果 ，则搜索成功，算法结束；如果 ，则令 ；否则令 ，转向第2步。

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

算法复杂度分析

（1）时间复杂度

对于二分查找算法，时间复杂度怎么计算呢？如果用T(n)来表示n个有序元素的二分

查找算法的时间复杂度，那么：

• 当n=1时，需要一次比较， 。
• 当n>1时，待查找元素和中间位置元素比较，需要 时间。如果比较不成功，那么需要在前半部分或后半部分搜索，问题的规模缩小了一半，时间复杂度变为 。
• 当n>1时，可以递推求解如： 递推最终的规模为1，令 ，则 。
• 二分查找的非递归算法和递归算法查找的方法是一样的，时间复杂度相同，均为 。

（2）空间复杂度

二分查找的非递归算法中，变量占用了一些辅助空间，这些辅助空间都是常数阶的，因此空间复杂度为 。

在递归算法中，每一次递归调用都需要一个栈空间存储，那么我们只需要看看有多少次调用。假设原问题的规模为n，那么第一次递归就分为两个规模为n/2的子问题，这两个子问题并不是每个都执行，只会执行其中之一。因为和中间值比较后，要么去前半部分查找，要么去后半部分查找；再把规模为n/2的子问题继续划分为两个规模为n/4的子问题，选择其一；继续分治下去，最坏的情况会分治到只剩下一个数值，那么算法执行的节点数就是从树根到叶子所经过的节点，每一层执行一个，直到最后一层，如图8-12所示。

递归调用最终的规模为1，即 ，则 。假设阴影部分是搜索经过的路径，则一共经过了 个节点，也就是说递归调用了 次。递归算法使用的栈空间为递归树的深度，因此二分查找递归算法的空间复杂度为 。

8.2.2.2 折半查找分析

• 折半查找判定树

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

8.3 分块查找

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

分块查找思想：

• ①确定待查找值在哪个块（折半查找）
• ②在确定的块中查找待查找值（顺序查找）

分块查找分析

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

8.4 二叉排序树

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

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

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

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

特点：“左小右大”

8.4.1 算法思想

由于二叉排序树的特点(左子树<根结点<右子树),所以每次查找一个关键字，需要先和根结点进行比较：如果这个关键字小于根结点的值，则再到这个根结点的左子树进行同样的比较操作一直进行下去直到找到该关键字，表示查找成功，或者是空指针，表示查找失败。如果这个关键字大于根结点的值，则再到这个根结点的右子树进行同样的比较操作一直进行下去直到找到该关键字，表示查找成功，或者是空指针，表示查找失败。

查找关键字代码

插入关键字代码

• 1)空树：直接插入新结点返回成功
• 2)树不空：检查是否存在关键字重复的结点：

• ①存在：返回插入失败
• ②不存在：检查根结点的值和待插入关键字值的大小关系递归插入左右子树

构造代码

删除结点

①删除的是叶子结点

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

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

方法：“子承父业”

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

仿照②类型，先将一个孩子“继承父业”，另一个孩子“归顺”于这个孩子方法：找到待删除结点的直接前驱或者直接后继结点，用该结点来替换待删除结点，再删除该结点。

算法复杂度分析

（1）时间复杂度

二叉查找树的查找时间复杂度和树的形态有关，可分为最好情况、最坏情况和平均情况分析。

最好情况下，二叉查找树的形态和二分查找的判定树相似，如图8-18所示。每次查找可以缩小一半的搜索范围，查找路径最多从根到叶子，比较次数最多为树的高度 ，最好情况的平均查找长度为 。

最坏情况下，二叉查找树的形态为单支树，即只有左子树或只有右子树，如图8-19所示。每次查找的搜索范围缩小为n−1，退化为顺序查找，最坏情况的平均查找的长度为 。

个节点的二叉查找树有 棵（有的形态相同），可以证明，在平均情况下，二叉查找树的平均查找长度也为 。

（2）空间复杂度

空间复杂度为 。

8.5 平衡二叉树(AVL树)

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

8.5.1 平衡因子

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

8.5.2 平衡调整

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

以插入操作为例，调整平衡可以分为4种情况：LL型、RR型、LR型、RL型。

LL调整(左孩子的左子树上插入结点导致)

插入新节点x后，从该节点向上找到最近的不平衡节点A。如果最近不平衡节点到新节点的路径前两个都是左子树L，即为LL型。也就是说，x节点插入在A的左子树的左子树中，A的左子树因插入新节点高度增加，造成A的平衡因子由1增为2，失去平衡。需要进行LL旋转（顺时针）调整平衡。

LL旋转：A顺时针旋转到B的右子树，B原来的右子树T3被抛弃，A旋转后正好左子树空闲，这个被抛弃的子树T3放到A左子树即可，如图8-47所示。

RR调整(右孩子的右子树上插入结点导致)

插入新节点x后，从该节点向上找到最近的不平衡节点A，如果最近不平衡节点到新节点的路径前两个都是右子树R，即为RR型。需要进行RR旋转（逆时针）调整平衡。

RR旋转：A逆时针旋转到B的左子树，B原来的左子树T2被抛弃，A旋转后正好右子树空闲，这个被抛弃的子树T2放到A右子树即可。如图8-48所示。

LR调整(左孩子的右子树上插入结点导致)

插入新节点x后，从该节点向上找到最近的不平衡节点A，如果最近不平衡节点到新节点的路径前两个依次是左子树L、右子树R，即为LR型。

LR旋转：分两次旋转，首先，C逆时针旋转到A、B之间，C原来的左子树T2被抛弃，B正好右子树空闲，这个被抛弃的子树T2放到B右子树。这时已经转变为LL型，做LL旋转即可，如图8-49所示。实际上，也可以看作C固定不动，B做RR旋转，然后再做LL旋转即可。

RL调整(右孩子的左子树上插入结点导致)

插入新节点x后，从该节点向上找到最近的不平衡节点A，如果最近不平衡节点到新节点的路径前依次是右子树R、左子树L，即为RL型。

RL旋转：分两次旋转，首先，C顺时针旋转到A、B之间，C原来的右子树T3被抛弃，B正好左子树空闲，这个被抛弃的子树T3放到B左子树。这时已经转变为RR型，做RR旋转即可，如图8-50所示。实际上，也可以看作C固定不动，B做LL旋转，然后再做RR旋转即可。

8.5.3 分析

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

8.6 B树和B+树

8.6.1 2-3树

2-3树是一种多路查找树：2和3的意思就是2-3树包含两种结点

• 1.) 2结点包含一个元素和两个孩子(或者没有孩子)。    ①左子树包含的元素小于该结点的元素值，右子树包含的元素大于该结点的元素值    ②2结点要不有两个孩子，要不就没有孩子，不允许有一个孩子
• 2.) 3结点包含一大一小两个元素和三个孩子(或者没有孩子)。(两个元素按大小顺序排列好)    ①左子树包含的元素小于该结点较小的元素值，右子树包含的元素大于该结点较大的元素值，中间子树包含的元素介于这两个元素值之间。    ②3结点要不有三个孩子，要不就没有孩子，不允许有一个或两个孩子
• 3.) 2-3树所有叶子结点都在同一层次

8.6.2 2-3-4树

2-3-4树也是一种多路查找树：2和3和4的意思就是2-3-4树包含三种结点

• 1.) 2结点包含一个元素和两个孩子(或者没有孩子)。    ①左子树包含的元素小于该结点的元素值，右子树包含的元素大于该结点的元素值    ②2结点要不有两个孩子，要不就没有孩子，不允许有一个孩子
• 2.) 3结点包含一大一小两个元素和三个孩子(或者没有孩子)。    ①左子树包含的元素小于该结点较小的元素值，右子树包含的元素大于该结点较大的元素值，中间子树包含的元素介于这两个元素值之间。    ②3结点要不有三个孩子，要不就没有孩子，不允许有一个或两个孩子
• 3.) 4结点包含小中大三个元素和四个孩子(或者没有孩子)。    ①左子树包含的元素小于该结点最小的元素值，第二个子树包含大于最小的元素值小于中间元素值的元素，第三个子树包含大于中间元素值小于最大元素值的元素，右子树包含的元素大于该结点最大的元素值。       ②4结点要不有四个孩子，要不就没有孩子，不允许有一个或两个或三个孩子
• 4.) 2-3-4树所有叶子结点都在同一层次

8.6.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）所有非叶结点的结构如下：
• 5）所有的叶子结点出现在同一层次上，不带信息。(就像是折半查找判断树中查找失败的结点)

1.B树的查找操作

查找过程：

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

②如果和所有关键字都不相等，则看key处在哪个范围内，然后去对应的指针所指向的子树中查找。

Eg:如果Key比第一个关键字K1还小，则去P0指针所指向的子树中查找，如果比最后一个关键字Kn还大，则去Pn指针所指向的子树中查找。

2.B树的插入操作

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

3.B树的删除操作

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

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

• ①结点内关键字数量大于⌈m/2⌉-1 ，这时删除这个关键字不会破坏B树的定义要求。所以直接删除。      
• ②结点内关键字数量等于⌈m/2⌉-1 ，并且其左右兄弟结点中存在关键字数量大于⌈m/2⌉-1 的结点，则去兄弟阶段中借关键字。      
• ③结点内关键字数量等于⌈m/2⌉-1 ，并且其左右兄弟结点中不存在关键字数量大于⌈m/2⌉-1 的结点，则需要进行结点合并。

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

• 相邻关键字：对于不在终端结点上的关键字,它的相邻关键字是其左子树中值最大的关键字或者右子树中值最小的关键字。
• 第一种情况：存在关键字数量大于⌈m/2⌉-1 的左子树或者右子树，在对应子树上找到该关键字的相邻关键字，然后将相邻关键字替换待删除的关键字。
• 第二种情况：左右子树的关键字数量均等于⌈m/2⌉-1 ，则将这两个左右子树结点合并，然后删除待删除关键字。

8.6.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树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。

8.7 散列表（哈希表）

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

散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为 。

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

8.7.1 构造散列函数的tips：

• 1）散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。
• 2）散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间，从而减少冲突的发生。
• 3）散列函数应尽量简单，能够在较短的时间内就计算出任一关键字对应的散列地址。

8.7.2 常用Hash函数的构造方法：

1.开放定址法：

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

2.除留余数法：

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

3.数字分析法：

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

4.平方取中法：

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

5.折叠法：

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

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

1.开放定址法：

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

1）线性探测法：

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

2）平方探测法：

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

3）再散列法：

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

4）伪随机序列法：

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

2.拉链法(链地址法)：

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

3.散列表的查找过程：

类似于构造散列表，给定一个关键字Key。先根据散列函数计算出其散列地址。然后检查散列地址位置有没有关键字。        

1)如果没有，表明该关键字不存在，返回查找失败。        

2)如果有，则检查该记录是否等于关键字。                

①如果等于关键字，返回查找成功。                

②如果不等于，则按照给定的冲突处理办法来计算下一个散列地址，再用该地址去执行上述过程。

4.散列表的查找性能：

和装填因子有关。

装填因子反映散列表的装满程度，α 越小，发生冲突的可能性越小；反之，α 越大，发生冲突的可能性越大。例如，表中填入的记录数为12，表长为15，则装填因子α=12/15=0.8；如果装入的记录数为3，则装填因子α =3/15=0.2。表长为15的情况下，只装入3个记录，那么发生冲突的可能性大大降低。但是装填因子过小，也会造成空间浪费。

处理冲突的方法

散列表处理冲突的方法不同，其平均查找长度的数学期望也不同，如表8-1所示。

8.8 查找总结

1）顺序查找（无序，顺序、链式存储均可）查找和插入效率均为 。

2）二分查找（有序，顺序存储）查找效率为 ，插入的效率为 。

3）二叉查找树查找和插入效率平均为 ，可以进行高效地查找和插入操作。但是二叉查找树最坏的情况下查找和插入的效率为 ，因此引入“平衡”。

4）平衡二叉查找树，其最坏和平均情况下查找和插入的效率均为 。

5）散列表能够快速地查找和插入常见数据类型的数据，对其他数据类型需要相应的转换。其查找和插入的效率与处理冲突的方法有关，不同的冲突处理方法效率不同。