第 7 章 查找

查找的基本概念

（1）查找 （2）查找表 （3）静态查找表&动态查找表：若一个查找表的操作只涉及查找操作，则无须动态地修改查找表，此类查找表称为静态查找表。与此对应，需要动态地插入或删除的查找表称为动态查找表。适合静态查找表的查找方法有顺序查找、折半查找、散列查找等;适合动态查找表的查找方法有二叉排序树的查找、散列查找等 （4）关键字 （5）平均查找长度：一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值

顺序查找和折半查找

顺序查找

顺序查找又称线性查找，它对顺序表和链表都是适用的。对于顺序表，可通过数组下标递增 来顺序扫描每个元素:对于链表，可通过指针 next 来依次扫描每个元素。顺序查找通常分为对一般的无序线性表的顺序查找和对按关键字有序的线性表的顺序查找

1. 一般线性表的顺序查找

2. 有序线性表的顺序查找

折半查找

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

int Binary(SSTable L , ElemType key){
  int low = 0, high = L.length - 1,mid;
  while(low < hight){
    mid = (low + hight) / 2;
    if(key == L.elem[mid]) return mid;
    else if(key < L.elem[mid]) hight = mid -1;
    else (key > L.elem[mid]) low = mid +1;
  }
  return -1;
}

当折半查找算法选取中间结点时，既可以采用向下取整，又可以采用向上取整。但每次查找 的取整方式必须相同.

折半查找路径

折半查找判定树 折半查找的过程可用图 7.2 所示的二叉树来描述，称为判定树。树中每个圆形结点表示一个记录，结点中的值为该记录的关键字值:树中最下面的叶结点都是方形的，它表示查找失败的区间。从判定树可以看出，查找成功时的查找长度为从根结点到目的结点的路径上的结点数，而查找失败时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数;每个结点值均大于其左子结点值，且均小于其右子结点值。若有序序列有 n 个元素，则对应的判定树有 n 个圆形的非叶结点和 n+1 个方形的叶结点。显然，判定树是一棵平衡二叉树。

分块查找

分块查找又称索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。

基本思想：将查找表分为若干子块。块内的元素可以无序，但块间的元素是有序的，即第一个块中的最大关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键小于第三个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第 一个元素的地址，索引表按关键字有序排列。（块内无序，块间有序）

分块查找的过程分为两步:第一步是在索引表中确定待查记录所在的块，可以顺序查找或折 半查找索引表;第 二步是在块内顺序查找。（块间折半，块内顺序）

树的查找

二叉排序树

构造一棵二叉排序树的目的并不是排序，而是提高查找、插入和删除关键字的速度，二叉排序树这种非线性结构也有利于插入和删除的实现。

1. 二叉排序树的定义 二叉排序树 (也称 二叉查找树)或者是 一棵空树，或者是具有下列特性的 二叉树: 1️⃣ 若左子树非空，则左子树上所有结点的值均小于根结点的值。 2️⃣ 若右子树非空，则右子树 上所有结点的值均大于根结点的值。 3️⃣ 左、右子树也分别是一棵二叉排序树 。 根据二叉排序树的定义，左子树结点值 <根结点值 <右子树结点值，因此对二叉排序树 进行中序遍历，可以得到一个递增的有序序列。例如，图 7. 4 所示 二叉排序树的中序遍历序列 为 123468。

2. 二叉排序树的查找

二叉排序树的查找是从根结点开始，沿某个分支逐层向下比较的过程。若二叉排序树非空， 先将给定值与根结点的关键字比较，若相等，则查找成功;若不等，若小于根结点的关键字，则 在根结点的左子树上查找，否则在根结点的右子树上查找。这显然是一个递归的过程。

非递归：

BSTNode *BST_Search(BiTree T , ElemType key){
  while(T != NULL && key != T->data){
    if(key < T->data) T = T->lchild;
    else T=T->rchild;
  }
  return T
}

3. 二叉排序树的插入

二叉排序树作为一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找过程中， 当树中不存在关键字值等于给定值的结点时再进行插入的。

int BST_Insert(BiTree T , KeyType k){
  if(T ==NULL){
    T = (BiTree)malloc(sizeof(BSTNode));
    T->data = k;
    T->lchild = T->rchild = NULL;
    return 1
  }else if(K == T->data) return 0;
  else if(k < T->data) return BST_Insert(T->lchild,k)
  else return BST_Insert(T->rchild,k)
}

4. 二叉排序树的构造

5. 二叉排序树的删除

思考:若在 二叉排序树中删除并插入某结点，得到的 二叉排序树是否和原来的相同

6. 二叉排序树的查找效率分析

二又排序树的查找效率，主要取决于树的高度。若二叉排序树的左、右子树的高度之差的绝对值不超过 1(平衡二叉树，下一节)，它的平均查找长度为 O(log2n)。若二叉排序树是一个只有右(左)孩子的单支树(类似于有序的单链表)，则其平均查找长度为 O(n)。

就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，平均执行时间为 O(log2n)。二分查找的对象是有序顺序表，若有插入和删除结点的操作，所花的代价是 O(n)。当有序表是静态查找表时，宜用顺序表作为其存储结构，而采用二分查找实现其找操作;若有序表是动态查找表，则应选择二叉排序树作为其逻辑结构。

平衡二叉树

1. 平衡二叉树的定义 为了避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除结点时，要保证任意结点的左、右子树高度差的绝对值不超过 1，将这样的二叉树称为平衡二叉树(BalancedBinaryTree)，也称AVL 树。定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是 -1、0 或 1 。

2. 平衡二叉树的插入

每当在二叉排序树中插入(或删除)一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点 A，再对以 A 为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

平 衡 二 叉 树 的 插 入 及 调 整 操 作 的 实 例

构造平衡叉树的过程(2013)

3. 平衡二叉树的删除

4. 平衡二叉树的查找 在平衡二又树上进行查找的过程与二又排序树的相同。因此，在查找过程中，进行关键字的比较次数不超过树的深度。含有 n 个结点的平衡二又树的最大深度为O(log2n)，因此平均查找效率为O(log2n)。

红黑树

1. 红黑树的定义 首先它是一颗平衡二叉树 1️⃣ 根叶黑 2️⃣ 不红红 3️⃣ 黑路同

B 树和 B+树

B 树及其基本操作

所谓 m 阶 B 树是所有结点的平衡因子均等于 0 的m 路平衡查找树。

1. B 树的定义和特点 一棵 m 阶 B 树或为空树，或为满足如下特性的 m 叉树:

• 树中每个结点至多有 m 棵子树，即至多有 m- 1 个关键字。
• 若根结点不是叶结点，则至少有 2 棵子树，即至少有 1 个关键字。
• 除根结点外的所有非叶结点至少有(m/2)向上取整棵子树，即至少有（m/2）向上取整-1 个关键字
• 所有的叶结点都出现在同一层次上，并且不带信息(可以视为外部结点或类似于折半查 找判定树的失败结点，实际上这些结点并不存在，指向这些结点的指针为空)。
• （m/2）向上取整-1 <= n <= m-1

2. B 树中关键字数和结点数的分析

3. B 树的查找 B 树的查找包含两个基本操作:1️⃣ 在 B 树中找结点:2️⃣ 在结点内找关键字。由于 B 树常存储在磁盘上，则前一查找操作是在磁盘上进行的，而后一查找操作是在内存中进行的，即在磁盘上找到目标结点后，先将结点信息读入内存，然后再采用顺序查找法或折半查找法。因此，在磁盘上进行查找的次数即目标结点在 B 树上的层次数，决定了 B 树的查找效率。

4. B 树的高度（磁盘存取次数） B 树中的大部分操作所需的磁盘存取次数与 B 树的高度成正比。 下面来分析 B 树在不同情况 下的高度。当然，首先应该明确 B 树的高度不包括最后的不带任 何信息的叶结点所处的那一层(有些书对 B 树的高度的定义中，包含最后的那一层)。

5. B 树的插入

6. B 树的删除

B+树的基本概念

一棵 m 阶 B+树应满足下列条件：

• 每个分支结点最多有 m 棵子树(孩子结点)。
• 非叶根结点至少有两棵子树，其他每个分支结点至少有m/2向上取整棵子树。
• 结点的子树个数与关键字个数相等。
• 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来(支持顺序查找)。
• 所有分支结点(可视为索引的索引)中仅包含它的各个子结点(即下一级的索引块)中关键字的最大值及指向其子结点的指针

B 树和 B+树的差异

• 在 B+树中，具有 n 个关键字的结点只含有 n 棵子树，即每个关键字对应 一棵子树;而在 B 树中，具有 n 个关键字的结点含有 n +1 棵子树。
• 在 B+树中，每个结点(非根内部结点)的关键字个数 n 的范围是「m/2 ≤n≤m(非叶根结点:2≤n≤m):而在 B 树中，每个结点(非根内部结点)的关键字个数 n 的范围是「m/2 -1 ≦ n ≦ m-1 (根结点：1≦ n≦ m-1)
• 在 B+树中，叶结点包含了全部关键字，非叶结点中出现的关键字也会出现在叶结点中;而 在 B 树中，最外层的终端结点包含的关键字和其他结点包含的关键字是不重复的。
• 在 B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有对应记录的存储地址。这样能使一个磁盘块存储更多的关键字，使得磁盘读/写次数更少，查找速度更快。
• 在 B+树中，用一个指针指向关键字最小的叶结点，将所有叶结点串成一个线性链表。

散列（Hash）表

散列表的基本概念

在前面介绍的线性表和树表的查找中，查找记录需进行一系列的关键字比较，记录在表中的位置与记录的关键字之间不存在映射关系，因此在这些表中的查找效率取决于比较的次数。

散列函数(也称哈希函数):一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr(这里的地址可以是数组下标、索引或内存地址等)。

散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生冲突的不同关键字称为同义词。一方面，设计得好的散列函数应尽量减少这样的冲突;另一方面，由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方法。

散列表(也称哈希表):根据关键字而直接进行访问的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。

散列函数的构造方法

1. 直接定址法 直接取关键字的某个线性函数值 散列地址，散列函数为

H(key) = key 或 H(key)=a x key + b

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

2. 除留余数法 这是一种最简单、最常用的方法，假定散列表表长为 m，取一个不大于 m 但最接近或等于 m 的质数 p，利用以下公式把关键字转换成散列地址。散列函数为

   H (key)= key % p

   除留余数法的关键是选好 p，使得每个关键字通过该函数转换后等概率地映射到散列空间上 的任意 一个地址，从而尽可能减少冲突的可能性。

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

4. 平方取中法 顾名思义，这种方法取关键字的平方值的中间几位作为散列地址。具体取多少位要视实际情 况而定。这种 方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀， 适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

处理冲突的方法

1. 开放定址法 所谓开放定址法，是指表中可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式

Hi = (H(key) + di) % m

式中，H(key)为散列函数:i=1,2，...，k(k≤m-1);m 表示散列表表长;d 为增量序列。

堆 积 现 象 导 致 的 结 果

（1）线性探测法，又称线性探测再散列法。d，= 1, 2，...，m- 1。它的特点是:冲突发生时，顺序查看表中下一个单元(探测到表尾地址 m- 1 时，下一个探测地址是表首地址 O)，直到找出一个空闲单元(当表未填满时一定能找到一个空闲单元)或查遍全表。 线性探测法可能使第;个散列地址的同义词存入第 i+ 1 个散列地址，这样本应存入第 i+ 1 个散列地址的元素就争夺第 i+ 2 个散列地址的元素的地址......从而造成大量元素在相邻的散列地址上聚集(或堆积)起来，大大降低了查找效率

（2) 平方探测法，又称二次探测法。d，=1^2，-1^2,2^2，-2^2，... ，其中 K≤m/2，散列表长度 m 必须是一个可以表示成 4k+3 的素数。 平方探测法是一种处理冲突的较好方法，可以避免出现“ 堆积” 问题，它的缺点是不能 探测到散列表上的所有单元，但至少能探测到一半单元。

（3）双散列法。di= ixHash2(key)。需要使用两个散列函数，当通过第一个散列函数 H(key)得到的地址发生冲突时，则利用第二个散列函数 Hash(key)计算该关键字的地址增量。它的具体散列函数形式如下:

Hi= (H(key)+i x Hash2(key))%m

初始探测位置 H0=H(key)%m。i 是冲突的次数，初始为 0。 （4) 伪随机序列法。di = 伪随机数序列

采用开放定址法时，不能随便物理删除表中已有元素，否则会截断其他同义词元素的查找 路径。因此，要删除一个元素时，可以做一个删除标记，进行逻辑删除 。但这样做的副作用是: 执行多次删除后，表面上看起来散列表很满，实际上有许多位置未利用

2. 拉链法(链接法，chaining）

显然，对于不同的关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突， 可以把所有的同 义词存储在一 个线性链表中，这个线性链表由其散列地址唯一标识。假设散列地 址为 i 的同义词链表的头指针存放在散列表的第;个单元中，因而查找、插入和删除操作主要在 同义词链中进行。拉链法适用于经常进行插入和删除的情况。

散列查找及性能分析

影 响 散 列 表 查 找 效 率 的 因 素

从散列表的查找过程可见: （1）虽然散列表在关键字与记录的存储位置之间建立了直接映像，但由于 “冲突” 的产生， 使得散列表的查找过程仍然是 一个给定值和关键字进行比较的过程。因此，仍然需要以平均查找长度作为衡量散列表的查找效率的度量。 （2）散列表的查找效率取决于三个因素:散列函数、处理冲突的方法和装填因子。 装填因子。散列表的装填因子一般记为 a，定义为一个表的装满程度 a= 表中记录数n / 散列表长度m

散列表的平均查找长度依赖于散列表的装填因子 a，而不直接依赖于 n 或 m。直观地看，a 越大，表示装填的记录越“满”，发生冲突的可能性越大;反之发生冲突的可能性越小