第10章查找10.1查找的基本概念被查找的对象是由一组记录组成的表或文件，而每个记录则由若干个数据项组成，并假设每个记录都有一个能惟一标识该记录的关键字。在这种条件下，查找的定义是：给定一个值k,在含有n个记录的表中找出关键字等于k的记录。若找到，则查找成功，返回该记录的信息或该记录在表中的位置：否则查找失败返回相关的指示信息。由于查找运算的主要运算是关键字的比较，所以通常把查找过程中对关键字需要执行的平均比较次数（也称为平均查找长度）作为衡量一个查找算法效率优劣的标准。平均查找长度ASL(AverageSearchLength)定义为：其中,n是查找表中记录的个数。pi是查找第i个记录的概率，一般地，均认为每个记录的查找概率相等,即pi=1/n(1≤i≤n),ci是找到第i个记录所需进行的比较次数。10.2线性表的查找10.2.1顺序查找顺序查找是一种最简单的查找方法。它的基本思路是：从表的一端开始，顺序扫描线性表,依次将扫描到的关键字和给定值k相比较，若当前扫描到的关键字与k相等，则查找成功；若扫描结束后，仍未找到关键字等于k的记录,则查找失败。10.2.2二分查找二分查找也称为折半查找要求线性表中的结点必须已按关键字值的递增或递减顺序排列。它首先用要查找的关键字k与中间位置的结点的关键字相比较,这个中间结点把线性表分成了两个子表,若比较结果相等则查找完成；若不相等，再根据k与该中间结点关键字的比较大小确定下一步查找哪个子表，这样递归进行下去，直到找到满足条件的结点或者该线性表中没有这样的结点。二分查找过程可用二叉树来描述，我们把当前查找区间的中间位置上的记录作为根,左子表和右子表中的记录分别作为根的左子树和右子树，由此得到的二叉树，称为描述二分查找的判定树或比较树。10.2.3分块查找分块查找又称索引顺序查找，它是一种性能介于顺序查找和二分查找之间的查找方法。它要求按如下的索引方式来存储线性表：将表R[0.n-1]均分为b块,前b-1块中记录个数为s=n/b，最后一块即第b块的记录数小于等于s；每一块中的关键字不一定有序,但前一块中的最大关键字必须小于后一块中的最小关键字，即要求表是“分块有序”的：抽取各块中的最大关键字及其起始位置构成一个索引表IDX[0..b-1],即IDX[i](O≤i≤b-1)中存放着第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的,所以索引表是一个递增有序表。10.3树表的查找当表的插入或删除操作频繁时，为维护表的有序性需要移动表中很多记录。这种由移动记录引起的额外时间开销，就会抵消二分查找的优点。也就是说，二分查找只适用于静态查找表。若要对动态查找表进行高效率的查找，可采用下面介绍的几种特殊的二叉树或树作为表的组织形式，在这里将它们统称为树表。下面将分别讨论在这些树表上进行查找和修改操作的方法。10.3.1二叉排序树二叉排序树（简称BST)又称二叉查找（搜索)树,其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：
第 10 章 查找 10.1 查找的基本概念 被查找的对象是由一组记录组成的表或文件,而每个记录则由若干个数据项组成,并假设 每个记录都有一个能惟一标识该记录的关键字。 在这种条件下,查找的定义是：给定一个值 k,在含有 n 个记录的表中找出关键字等于 k 的 记录。若找到,则查找成功,返回该记录的信息或该记录在表中的位置；否则查找失败,返回相 关的指示信息。 由于查找运算的主要运算是关键字的比较,所以通常把查找过程中对关键字需要执行的平均 比较次数(也称为平均查找长度)作为衡量一个查找算法效率优劣的标准。平均查找长度 ASL(Average Search Length)定义为： 其中,n 是查找表中记录的个数。pi 是查找第 i 个记录的概率,一般地,均认为每个记录的查找 概率相等,即 pi=1/n(1≤i≤n),ci 是找到第 i 个记录所需进行的比较次数。 10.2 线性表的查找 10.2.1 顺序查找 顺序查找是一种最简单的查找方法。 它的基本思路是：从表的一端开始,顺序扫描线性表,依次将扫描到的关键字和给定值 k 相比较,若当前扫描到的关键字与 k 相等,则查找成功；若扫描结束后,仍未找到关键字等于 k 的记录,则查找失败。 10.2.2 二分查找 二分查找也称为折半查找要求线性表中的结点必须己按关键字值的递增或递减顺序排 列。它首先用要查找的关键字 k 与中间位置的结点的关键字相比较,这个中间结点把线性表 分成了两个子表,若比较结果相等则查找完成;若不相等,再根据k与该中间结点关键字的比较 大小确定下一步查找哪个子表,这样递归进行下去,直到找到满足条件的结点或者该线性表中 没有这样的结点。 二分查找过程可用二叉树来描述,我们把当前查找区间的中间位置上的记录作为根,左子表和 右子表中的记录分别作为根的左子树和右子树,由此得到的二叉树,称为描述二分查找的判定 树或比较树。 10.2.3 分块查找 分块查找又称索引顺序查找,它是一种性能介于顺序查找和二分查找之间的查找方法。 它要求按如下的索引方式来存储线性表：将表 R[0.n-1]均分为 b 块,前 b-1 块中记录 个数为 s= n/b ,最后一块即第 b 块的记录数小于等于 s；每一块中的关键字不一定有序,但 前一块中的最大关键字必须小于后一块中的最小关键字,即要求表是“分块有序”的；抽取 各块中的最大关键字及其起始位置构成一个索引表 IDX[0.b-1],即 IDX[i](0≤i≤b-1)中存放 着第 i 块的最大关键字及该块在表 R 中的起始位置。由于表 R 是分块有序的,所以索引表是 一个递增有序表。 10.3 树表的查找 当表的插入或删除操作频繁时,为维护表的有序性,需要移动表中很多记录。这种由移动记 录引起的额外时间开销,就会抵消二分查找的优点。也就是说,二分查找只适用于静态查找表。 若要对动态查找表进行高效率的查找,可采用下面介绍的几种特殊的二叉树或树作为表的组 织形式,在这里将它们统称为树表。下面将分别讨论在这些树表上进行查找和修改操作的方 法。 10.3.1 二叉排序树 二叉排序树(简称 BST)又称二叉查找(搜索)树,其定义为：二叉排序树或者是空树, 或者是满足如下性质的二叉树：
（1）若它的左子树非空,则左子树上所有记录的值均小于根记录的值；(2）若它的右子树非空，则右子树上所有记录的值均大于根记录的值；（3）左、右子树本身又各是一棵二叉排序树。1.二叉排序树上的查找因为二叉排序树可看做是一个有序表，所以在二叉排序树上进行查找，和二分查找类似,也是一个逐步缩小查找范围的过程。递归查找算法SearchBSTO如下（在二叉排序树bt上查找关键字为k的记录，成功时返回该结点指针，否则返回NULL)：2.二叉排序树的插入和生成在二叉排序树中插入一个新记录，要保证插入后仍满足BST性质。其插入过程是：若二叉排序树T为空,则创建一个key域为k的结点，将它作为根结点；否则将k和根结点的关键字比较,若二者相等,则说明树中已有此关键字k无须插入,直接返回0：若k<T->key,则将k插入根结点的左子树中否则将它插入右子树中。二叉排序树的生成，是从一个空树开始，每插入一个关键字，就调用一次插入算法将它插入到当前已生成的二叉排序树中。3.二叉排序树的删除删除操作必须首先进行查找，假设在查找过程结束时，已经保存了待删除结点及其双亲结点的地址。指针变量p指向待删除的结点,指针变量q指向待删除结点p的双亲结点。删除过程如下：（1）若待删除的结点是叶子结点,直接删去该结点。如图(a)所示,直接删除结点9。这是最简单的删除结点的情况。(2）若待删除的结点只有左子树而无右子树。根据二叉排序树的特点，可以直接将其左子树的根结点放在被删结点的位置。如图(b)所示，*p作为*q的右子树根结点，要删除*p结点，只需将*p的左子树(其根结点为3)作为*q结点的右子树。(3）若待删除的结点只有右子树而无左子树。与(2)情况类似,可以直接将其右子树的根结点放在被删结点的位置。如图（c)所示*p作为*g的左子树根结点要删除*p结点只需将*p的右子树（其根结点为8)作为*结点的右子树。（4）若待删除的结点同时有左子树和右子树。根据二叉排序树的特点，可以从其左子树中选择关键字最大的结点或从其右子树中选择关键字最小的结点放在被删去结点的位置上。假如选取左子树上关键字最大的结点，那么该结点一定是左子树的最右下结点。如图(d)所示，若要删除*p(其关键字为5)结点,找到其左子树最右下结点4,它的双亲结点为2,用它代替*p结点,并将其原来的左子树(其根结点为3)作为原来的双亲结点2的右子树。10.3.2平衡二叉树(AVL)若一棵二叉树中每个结点的左、右子树的高度至多相差1,则称此二叉树为平衡二叉树。在算法中,通过平衡因子(balancdfactor,用bf表示)来具体实现上述平衡二叉树的定义。平衡因子的定义是：平衡二叉树中每个结点有一个平衡因子域每个结点的平衡因子是该结点左子树的高度减去右子树的高度。从平衡因子的角度可以说若一棵二义树中所有结点的平衡因子的绝对值小于或等于1,即平衡因子取值为1、0或-1,则该二叉树称为平衡二叉树。平衡二叉树和不平衡二叉树假定向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性，首先要找出插入新结点后失去平衡的最小子树根结点的指针，然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树。失去平衡的最小子树是指以离插入结点最近,且平衡因子绝对值大于1的结点作为根的子树。假设用A表示失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列
(1) 若它的左子树非空,则左子树上所有记录的值均小于根记录的值； (2) 若它的右子树非空,则右子树上所有记录的值均大于根记录的值； (3) 左、右子树本身又各是一棵二叉排序树。 1. 二叉排序树上的查找 因为二叉排序树可看做是一个有序表,所以在二叉排序树上进行查找,和二分查找类 似,也是一个逐步缩小查找范围的过程。递归查找算法 SearchBST()如下(在二叉排序树 bt 上 查找关键字为 k 的记录,成功时返回该结点指针,否则返回 NULL)： 2. 二叉排序树的插入和生成 在二叉排序树中插入一个新记录,要保证插入后仍满足 BST 性质。其插入过程是： 若二叉排序树 T 为空,则创建一个 key 域为 k 的结点,将它作为根结点；否则将 k 和根结点的 关键字比较,若二者相等,则说明树中已有此关键字 k,无须插入,直接返回 0；若 k<T->key,则将 k 插入根结点的左子树中,否则将它插入右子树中。 二叉排序树的生成,是从一个空树开始,每插入一个关键字,就调用一次插入算法将它插入到 当前已生成的二叉排序树中。 3. 二叉排序树的删除 删除操作必须首先进行查找,假设在查找过程结束时,已经保存了待删除结点及其双亲 结点的地址。指针变量 p 指向待删除的结点,指针变量 q 指向待删除结点 p 的双亲结点。删 除过程如下： (1) 若待删除的结点是叶子结点,直接删去该结点。如图(a)所示,直接删除结点 9。这是 最简单的删除结点的情况。 (2) 若待删除的结点只有左子树而无右子树。根据二叉排序树的特点,可以直接将其左子树的 根结点放在被删结点的位置。如图(b)所示,*p 作为*q 的右子树根结点,要删除*p 结点,只需将 *p 的左子树(其根结点为 3)作为*q 结点的右子树。 (3) 若待删除的结点只有右子树而无左子树。与(2)情况类似,可以直接将其右子树的根结点 放在被删结点的位置。如图(c)所示,*p 作为*q 的左子树根结点,要删除*p 结点,只需将*p 的右 子树(其根结点为 8)作为*q 结点的右子树。 (4) 若待删除的结点同时有左子树和右子树。根据二叉排序树的特点,可以从其左子树中选择 关键字最大的结点或从其右子树中选择关键字最小的结点放在被删去结点的位置上。假如选 取左子树上关键字最大的结点,那么该结点一定是左子树的最右下结点。如图(d)所示,若要删 除*p(其关键字为 5)结点,找到其左子树最右下结点 4,它的双亲结点为 2,用它代替*p 结点,并 将其原来的左子树(其根结点为 3)作为原来的双亲结点 2 的右子树。 10.3.2 平衡二叉树(AVL) 若一棵二叉树中每个结点的左、右子树的高度至多相差 1,则称此二叉树为平衡二叉 树。在算法中,通过平衡因子(balancd factor,用 bf 表示)来具体实现上述平衡二叉树的定义。 平衡因子的定义是：平衡二叉树中每个结点有一个平衡因子域,每个结点的平衡因子是该结 点左子树的高度减去右子树的高度。从平衡因子的角度可以说,若一棵二叉树中所有结点的 平衡因子的绝对值小于或等于 1,即平衡因子取值为 1、0 或-1,则该二叉树称为平衡二叉树。 平衡二叉树和不平衡二叉树 假定向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性,首先要找出插入新结点 后失去平衡的最小子树根结点的指针,然后再调整这个子树中有关结点之间的链接关系,使之 成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后,原有其他所有不平衡子树 无需调整,整个二叉排序树就又成为一棵平衡二叉树。 失去平衡的最小子树是指以离插入结点最近,且平衡因子绝对值大于 1 的结点作为 根的子树。假设用 A 表示失去平衡的最小子树的根结点,则调整该子树的操作可归纳为下列
四种情况：(1)LL 型调整(2)RR型调整(3)LR型调整(4)RL型调整10.4哈希表查找10.4.1哈希表的基本概念哈希表(HashTable)又称散列表,是除顺序表存储结构、链接表存储结构和索引表存储结构之外的又一种存储线性表的存储结构。哈希表存储的基本思路是：设要存储的对象个数为n,设置一个长度为m(m≥n)的连续内存单元,以线性表中每个对象的关键字ki(0≤i≤n-1）为自变量,通过一个称为哈希函数的函数h(ki),把ki映射为内存单元的地址(或称下标)h(ki)并把该对象存储在这个内存单元中。h(ki)也称为哈希地址（又称散列地址）。把如此构造的线性表存储结构称为哈希表。但是存在这样的问题,对于两个关键字ki和kji≠j),有ki≠kj(ij),但h(ki)=h(ki)。我们把这种现象叫做哈希冲突。通常把这种具有不同关键字而具有相同哈希地址的对象称做“同义词”，由同义词引起的冲突称作同义词冲突。在哈希表存储结构的存储中同义词冲突是很难避免的除非关键字的变化区间小于等于哈希地址的变化区间，而这种情况当关键字取值不连续时是非常浪费存储空间的。通常的实际情况是关键字的取值区间远大于哈希地址的变化区间。归纳起来：(1)哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；(2)由于哈希函数是一个压缩映象,因此,在一般情况下,很容易产生“冲突”现象,即：key1 key2,而f(keyl)=f(key2)。(3）很难找到一个不产生冲突的哈希函数。一般情况下,只能选择恰当的哈希函数，使冲突尽可能少地产生。10.4.2哈希函数构造方法构造哈希函数的目标是使得到的哈希地址尽可能均匀地分布在n个连续内存单元地址上，同时使计算过程尽可能简单以达到尽可能高的时间效率。1.直接定址法直接定址法是以关键字k本身或关键字加上某个数值常量c作为哈希地址的方法。直接定址法的哈希函数h(k)为：(c≥0)h(k)=k+c这种哈希函数计算简单，并且不可能有冲突发生。当关键字的分布基本连续时，可用直接定址法的哈希函数：否则，若关键字分布不连续将造成内存单元的大量浪费。2.除留余数法除留余数法是用关键字k除以某个不大于哈希表长度m的数p所得的余数作为哈希地址的方法。除留余数法的哈希函数h(k)为：h(k)=kmodp(mod为求余运算,p≤m)p最好取小于m的质数(素数)。3.数字分析法该方法是提取关键字中取值较均匀的数字位作为哈希地址的方法。它适合于所有关键字值都已知的情况，并需要对关键字中每一位的取值分布情况进行分析。例如，对于一组关键字：
四种情况： (1) LL 型调整 (2) RR 型调整 (3) LR 型调整 (4) RL 型调整 10.4 哈希表查找 10.4.1 哈希表的基本概念 哈希表(Hash Table)又称散列表,是除顺序表存储结构、链接表存储结构和索引表存 储结构之外的又一种存储线性表的存储结构。哈希表存储的基本思路是：设要存储的对象个 数为 n,设置一个长度为 m(m≥n)的连续内存单元,以线性表中每个对象的关键字 ki(0≤i≤n-1) 为自变量,通过一个称为哈希函数的函数 h(ki),把 ki 映射为内存单元的地址(或称下标)h(ki), 并把该对象存储在这个内存单元中。h(ki)也称为哈希地址(又称散列地址)。把如此构造的线 性表存储结构称为哈希表。 但是存在这样的问题,对于两个关键字 ki 和 kj(i≠j),有 ki≠kj(i≠j),但 h(ki)=h(kj)。我们把这种 现象叫做哈希冲突。 通常把这种具有不同关键字而具有相同哈希地址的对象称做“同义词”,由同义词引 起的冲突称作同义词冲突。在哈希表存储结构的存储中,同义词冲突是很难避免的,除非关键 字的变化区间小于等于哈希地址的变化区间,而这种情况当关键字取值不连续时是非常浪费 存储空间的。通常的实际情况是关键字的取值区间远大于哈希地址的变化区间。 归纳起来： (1)哈希函数是一个映象,即：将关键字的集合映射到某个地址集合上,它的设置很灵活, 只要这个地址集合的 大小不超出允许范围即可； (2)由于哈希函数是一个压缩映象,因此,在一般情况下,很容易产生“冲突”现象,即： key1 key2,而 f(key1) = f(key2)。 (3) 很难找到一个不产生冲突的哈希函数。一般情况下,只能选择恰当的哈希函数, 使冲突尽可能少地产生。 10.4.2 哈希函数构造方法 构造哈希函数的目标是使得到的哈希地址尽可能均匀地分布在 n 个连续内存单元地址 上,同时使计算过程尽可能简单以达到尽可能高的时间效率。 1. 直接定址法 直接定址法是以关键字 k 本身或关键字加上某个数值常量 c 作为哈希地址的方法。 直接定址法的哈希函数 h(k)为： h(k)=k+c (c≥0) 这种哈希函数计算简单,并且不可能有冲突发生。当关键字的分布基本连续时,可用直 接定址法的哈希函数；否则,若关键字分布不连续将造成内存单元的大量浪费。 2. 除留余数法 除留余数法是用关键字 k 除以某个不大于哈希表长度 m 的数 p 所得的余数作为哈希 地址的方法。除留余数法的哈希函数 h(k)为： h(k)=k mod p (mod 为求余运算,p≤m) p 最好取小于 m 的质数(素数)。 3. 数字分析法 该方法是提取关键字中取值较均匀的数字位作为哈希地址的方法。它适合于所有关键 字值都已知的情况,并需要对关键字中每一位的取值分布情况进行分析。 例如,对于一组关键字：
92317602,92326875,92739628,92343634,9270681692774638,92381262,92394220通过分析可知,每个关键字从左到右的第1、2、3位和第6位取值较集中，不宜作为哈希函数，剩余的第4、5、7和8位取值较分散，可根据实际需要取其中的若干位作为哈希地址。若取最后两位作为哈希地址,则哈希地址的集合为(2,75,28,34,16,38,62,20)。注意：存在冲突。10.4.3哈希冲突解决方法1.开放定址法开放定址法是一类以发生冲突的哈希地址为自变量,通过某种哈希冲突函数得到一个新的空闲的哈希地址的方法。(1)线性探查法。线性探查法是从发生冲突的地址(设为d)开始，依次探查d的下一个地址(当到达下标为m-1的哈希表表尾时，下一个探查的地址是表首地址0),直到找到一个空闲单元为止（当m≥n时一定能找到一个空闲单元)。线性探查法的数学递推描述公式为：d0=h(k)di=(di-1+1)modm (1≤i≤m-1)(2)平方探查法。设发生冲突的地址为d则平方探查法的探查序列为：d+12,d+22,。平方探查法的数学描述公式为：d0=h(k)di=(d0+i2)modm(1≤i≤m-1)平方探查法是一种较好的处理冲突的方法可以避免出现堆积问题。它的缺点是不能探查到哈希表上的所有单元，但至少能探查到一半单元。2.拉链法拉链法是把所有的同义词用单链表链接起来的方法。在这种方法中，哈希表每个单元中存放的不再是记录本身而是相应同义词单链表的头指针。由于单链表中可插入任意多个结点，所以此时装填因子α根据同义词的多少既可以设定为大于1,也可以设定为小于或等于1,通常取a=1。本章小结本章基本学习要点如下：（1）理解查找的基本概念，包括静态查找表和动态查找表、内查找和外查找之间的差异。(2）重点掌握线性表上各种查找算法，包括顺序查找、二分查找和分块查找的基本思路、算法实现和查找效率等。(3）掌握各种树表的查找算法,包括二叉排序树、AVL树和B-树的基本思路、算法实现和查找效率等。(4）掌握哈希表查找技术以及哈希表与其他表的本质区别。(5）灵活运用各种查找算法解决一些综合应用问题。练习教材中p265习题1、2、3和5。上机实习题教材中p166题3和5
{92317602,92326875,92739628,92343634,92706816, 92774638,92381262,92394220} 通过分析可知,每个关键字从左到右的第 1、2、3 位和第 6 位取值较集中,不宜作为哈 希函数,剩余的第 4、5、7 和 8 位取值较分散,可根据实际需要取其中的若干位作为哈希地址。 若取最后两位作为哈希地址,则哈希地址的集合为{2,75,28,34,16,38,62,20}。 注意：存在冲突。 10.4.3 哈希冲突解决方法 1. 开放定址法 开放定址法是一类以发生冲突的哈希地址为自变量,通过某种哈希冲突函数得到一个 新的空闲的哈希地址的方法。 (1)线性探查法。线性探查法是从发生冲突的地址(设为 d)开始,依次探查 d 的下一个地 址(当到达下标为 m-1 的哈希表表尾时,下一个探查的地址是表首地址 0),直到找到一个空闲 单元为止(当 m≥n 时一定能找到一个空闲单元)。线性探查法的数学递推描述公式为： d0=h(k) di=(di-1+1) mod m (1≤i≤m-1) (2)平方探查法。设发生冲突的地址为 d,则平方探查法的探查序列为：d+12,d+22,.。平方探 查法的数学描述公式为： d0=h(k) di=(d0+i2) mod m (1≤i≤m-1) 平方探查法是一种较好的处理冲突的方法,可以避免出现堆积问题。它的缺点是不能 探查到哈希表上的所有单元,但至少能探查到一半单元。 2. 拉链法 拉链法是把所有的同义词用单链表链接起来的方法。在这种方法中,哈希表每个单 元中存放的不再是记录本身,而是相应同义词单链表的头指针。由于单链表中可插入任意多 个结点,所以此时装填因子α根据同义词的多少既可以设定为大于 1,也可以设定为小于或等 于 1,通常取α=1。 本章小结 本章基本学习要点如下： (1) 理解查找的基本概念,包括静态查找表和动态查找表、内查找和外查找之间的差异。 (2) 重点掌握线性表上各种查找算法,包括顺序查找、二分查找和分块查找的基本思 路、算法实现和查找效率等。 (3) 掌握各种树表的查找算法,包括二叉排序树、AVL 树和 B-树的基本思路、算法实 现和查找效率等。 (4) 掌握哈希表查找技术以及哈希表与其他表的本质区别。 (5) 灵活运用各种查找算法解决一些综合应用问题。 练习 教材中 p265 习题 1、2、3 和 5。 上机实习题 教材中 p166 题 3 和 5