查找。在数据集合中寻找满足条件的数据元素的过程称为查找。查找的结果分为

查找成功，查找失败

。
查找表(查找结构)。用于查找的数据集合称为查找表，它由同一类型的数据元素(或记录)组成，可以是一个数组或链表等数据类型。
关键字。数据元素中

唯一

标识该元素的某个数据项的值。使用基于关键字的查找，查找结果应该是唯一的。
平均查找长度。在查找过程中，

一次查找的长度是指需要比较的关键字次数

,而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值。
$ASL=\sum P_{i}C_{i}$
，即概率×比较次数

7.2 顺序查找和折半查找

7.2.1 顺序查找

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

顺序查找也称线性查找，

它对顺序表和链表都是适用的

。对于顺序表，可通过数组下标递增来顺序扫描每个元素。

// 一般线性表顺序查找
typedef int Elemtype;

typedef struct {//查找表的数据结构
	Elemtype* elem; //元素存储空间基址，建表时按实际长度分配，0号留空
	int TableLen;	//表的长度
}SSTable;

int Search_Seq(SSTable ST, Elemtype key) {
	ST.elem[0] = key;	//ST.elem[0]充当哨兵
	for (int i = ST.TableLen; ST.elem[i] != key; i--);
	return i;
}

引入“哨兵”的算法可以避免很多不必要的判断语句，可以提高程序效率。

查找成功时，顺序表查找的平均长度为：

$ASL=\sum_{i=1}^{n}P_{i}(n-i+1)$

查找不成功时，与表中关键字的比较次数显然是n+1次，故

ASL=n+1

。

2.有序表的顺序查找

若在查找之前就已经知道表是关键字有序的，则查找失败时就可以不用再比较到表的另一端就能返回查找失败的信息。

可以用下图所示的判定树来表述有序线性表的查找过程。

查找成功的

平均查找长度

与一般线性表相同
$ASL=\sum_{i=1}^{n}P_{i}(n-i+1)$
$ASL_{Defeat}=\frac{1+2+3+\cdot \cdot \cdot +n+n}{n+1}$

注意，有序线性表的顺序查找和后面的折半查找思想不一样，

且有序线性表的顺序查找中的线性表可以是链式存储结构

。

7.2 折半查找—二分法查找

它仅适用于有序的顺序表。代码实现如下：

// 折半查找
typedef struct {
	Elemtype* elem;
	int TableLen;	
}SeqList;
int Binary_Search(SeqList L, Elemtype key)//key为待查找元素
{
	int low = 0, high = L.TableLen - 1, mid;
	while (low <= high) {
		mid = (low + high) / 2;//取中间位置
		if (L.elem[mid] == key)
			return mid;
		else if (L.elem[mid] > key)
			high = mid - 1;//如果中间值比key还要大，则从前半部分继续查找
		else
			low = mid + 1; //如果中间值比key还要小，则从后半部分继续查找
	}
	return -1;
}

折半查找的过程可用如图所示的二叉树来描述，称为判定树。

很明显，判定树是一颗平衡二叉树且是一棵二叉排序树。

查找成功时，查找长度即为平衡二叉树树高。

树高为
$h=\left \lceil log_{2}(n+1) \right \rceil$

运用上述
$ASL=\sum_{i=1}^{n}P_{i}(n-i+1)$
可以推出对于折半查找树

平均查找长度

为：
$ASL=log_{2}(n+1)-1$

查找不成功的查找长度为图中方框结点，查找成功为圆形结点。

注意，由于折半查找要求随机存取的特性，因此该查找发

仅适合于顺序存储结构，且要求元素按照关键字有序排列

。

7.2.3 分块查找

分块查找基本思想：将查找表分为若干子块，

块内元素可以无序，块间必须是有序的

。分块查找的过程分为两步：第一步是在索引表中确定待查记录所在的块，

可以顺序查找或折半查找索引表

；第二步是在

块内顺序查找

。

假设索引查找和块内查找的平均查找长度分别为a和b，则分块查找的平均查找长度

ASL=a+b

。

将长度为n的查找表

均匀分为b块，每块有s个记录

，在等概率情况下，块内和索引表

均用顺序查找

则:

$ASL=L_{s}+L_{b}=\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^{2}+2s+n}{2s}$
，

此时若

s=n^1/2

，则平均查找长度取最小值为

n^1/2+1

若对索引表

采用折半查找时

，平均查找长度为:

$ASL=L_{s}+L_{b}=\left \lceil log_{2}(b+1) \right \rceil+\frac{s+1}{2}$

7.3 树型查找

7.3.1 二叉排序树—BST

二叉排序树也称为二叉查找树或者是一棵空树，或者是具有下列特性的二叉树：

若左子树非空，则左子树上

所有

结点的值均小于根结点的值。
若右子树非空，则右子树上

所有

结点的值均大于根结点的值。

根据二叉排序树的定义，左子树结点值<根结点<右子树结点，所以对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

1. BST的查找

//二叉排序树结点定义
typedef struct BSTNode {
	Elemtype data;
	BSTNode* lchild, * rchild;
}BSTNode,* BSTree;

//二叉排序树的非递归查找算法
BSTNode* BST_Search(BSTree T, Elemtype key)
{
	while (T->data != key || T != NULL) {
		if (key > T->data)
			T = T->rchild;
		else
			T = T->rchild;
	}
	return T;
}

2. BST的插入

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

//二叉排序树插入操作的算法
int BST_Insert(BSTree& T, KeyType p) {
	if (T == NULL) {
		T = (BSTree)malloc(sizeof(BSTNode));
		T->data = p;
		T->lchild = T->rchild = NULL;
		return 1;
	}
	else if (T->data == p)	//当结点中存在p，插入失败
		return 0;
	else if (T->data < p)
		return BST_Insert(T->lchild, p);//插入到T的左子树
	else if (T->data > p)
		return BST_Insert(T->rchild, p);//插入到T的右子树
}

3. BST的删除

若被删除结点z是叶结点，则直接删除。
若z只有一棵左子树或者一棵右子树，则直接令z的子树成为z父结点的子树。
若z既有左子树又有右子树，则令z的

直接后继

或是

直接前驱

替代z。

4. BST的查找效率

最好的情况下，二叉排序树的左右子树高度差的绝对值之和不超过1，这样的二叉树称为平衡二叉树，其平均查找长度为
$O(log_{2}n)$
。

最坏的情况下，构造二叉排序树的输入序列是有序的。则会形成一个倾斜的单只结构，平均查找长度为
$O(n)$
。

7.3.2 平衡二叉树

1. 平衡二叉树的定义

为避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉结点时，保证任意结点的左，右子树高度差的绝对值不大于1，将这样的树称为平衡二叉树(Balance Binary Tree)。

//平衡二叉树结点定义
typedef struct AVLNode {
	Elemtype key;
	int balance; //平衡因子
	AVLNode* lchild, * rchild;
}AVLNode,* AVLTree;

2. 平衡二叉树的插入

结点插入

遵守二叉排序树的前提

，若此次插入导致了不平衡，则要做出调整。

当插入结点在LL—左子树的最左端时，导致了平衡破坏，采用右单旋转。

当插入结点在RR—右子树的最右端时，导致了平衡破坏，采用左单旋转。

当插入结点在LR时，采用先左单旋再右单旋策略。

当插入结点在RL时，采用先右单旋再左单旋策略。

3. 平衡二叉树的删除

1.删除结点时方法如同二叉排序树：

若删除结点是叶子结点，直接删除。
该结点只有一个子树，用子树替代当前结点
若删除结点有两个子树，用直接前驱或是直接后继顶替。

2.再删除了这个结点之后，一直向上扫描入，如果树的平衡性质没有破坏，删除操作结束。

3.如果平衡被破坏了，寻找

最小不平衡树

下高度最大的儿子结点与孙子结点：

如果孙子结点在LL，儿子右单旋转
如果孙子结点在RR，儿子左单旋转
如果孙子在LR，孙子先右旋再左旋
如果孙子在RL，孙子先左旋再右旋

4.如果不平衡继续传导，则继续第3步。

4.平衡二叉树的查找

若以
$n_{h}$
表示深度为h的平衡二叉树中含有的

最少结点数

；(牢记递推公式)可以推出
$n_{h}=n_{h-1}+n_{h-2}+1$
。由于含有n个结点的平衡二叉树的最大深度为
$O(log_2{n})$
,故平均查找长度为
$O(log_2{n})$
。

一棵平衡二叉树当它含有最少结点时，它每个非叶结点的平衡因子为1。

7.3.3 红黑树

1. 红黑树的定义

为保证AVL树的平衡性，再删除与插入操作时，会频繁调整树的拓扑结构，代价较大。为此在AVL树的平衡标准上进一步放宽了条件，引入红黑树结构：

每个结点要么是红色，要么是黑色。—

一条简单路径上至少一半结点是黑结点，根的黑高至少为h/2，于是有
$n\geq 2^{h/2}-1$
，不含叶结点。
根结点只能是黑色。
叶结点(虚构的外部结点、NULL结点)是黑色。
不存在两个相邻的红结点。—

当某条路径最长时，这条路径必然是红黑相间的。
对任一结点，从这个结点到任一叶子结点的简单路径上，黑结点数量相同。—

当某条路径最短时这条路径必然全是黑结点。

由此可以衍生出结论：

从根到叶结点最长路径不大于最短路径两倍。
有n个内部结点的红黑树高度
$h\leqslant 2log_{2}n+1$
。

2. 红黑树的插入

1.查找插入位置(

原理与二叉排序树相同

)，插入结点

2.若新结点为根–染黑

3.若新结点非根–染红

4.插入结点后依然满足红黑树定义，则插入结束；否则做出如下调整：

若该结点的叔叔结点是红色的：

叔结点、父结点、爷结点都染色。
爷结点变为新结点。

若该结点的叔叔结点时黑色的：

LL型：右单旋后使得父结点换爷结点；父结点与爷结点染色。
LR型：先左旋后右旋使儿结点换爷结点；儿结点与爷结点染色。
RR与RL有着异曲同工之妙，不再赘述。

3. 红黑树的删除

应该不会考。

7.4 B树与B+树

7.4.1 B树及其基本操作

B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树：

树中每个结点至多有m棵子树，即至多含有m-1个关键字。
若根结点不是终端结点，则至少有两棵子树。
除根结点外所有非叶节点至少有
$\left \lceil m/2 \right \rceil$
棵子树，即至少
$\left \lceil m/2 \right \rceil-1$
个关键字。
所有叶结点出现在同一层次上并且不带信息（实际上这些节点不存在，指向这些结点的指针为空）代表查找失败的位置。
B树是所有结点的平衡因子均等于0的多路平衡查找树。

1. B树的高度

B树中的大部分操作所需的磁盘存取次数与B树的高度成正比。

1）因为B树中每个结点最多有m棵子树，m-1个关键字，所以在一棵高度为h的m阶B树中关键字的个数应满足
$n\leqslant (m-1)(1+m+m^{2}+\cdot \cdot \cdot +m^{h-1})=m^{h}-1$
因此有
$h\geq log_{m}(n+1)$
。

2）如果让每个节点中关键字个数达到最少，查找不成功的结点数为n+1，由此有
$n+1\geq 2(\left \lceil m/2 \right \rceil)^{h-1}$
即
$h\leq log_{\left [ m/2 \right ]^{h-1}}$

2. B树的查找

B树查找就是m叉的二叉排序树的查找。

3. B树的插入

1）根据B树的查找算法进行定位。

2）插入后结点关键字数目小于m则可直接插入；倘若大于m-1时，必须进行分裂操作：

分裂的方法是取一个新结点插入key后的原结点，从中间位置
$\left \lceil m/2 \right \rceil$
割裂为两部分，左部分包含关键字放在原结点中，右部分包含的关键字放在新结点中，中间位置
$\left \lceil m/2 \right \rceil$
插入原结点的父结点；若此时导致结点内关键字个数也超过了上限，则继续分裂。

这里写图片描述

4. B树的删除

当删除B树中的关键字后，关键字结点个数可能会小于
$\left \lceil m/2 \right \rceil-1$
，因此会用到合并操作。

文字叙述不易明白，直接看图。

第一种情况：

这里写图片描述

第二种情况—兄弟够借：

这里写图片描述

第三种情况—兄弟不够借：

7.4.2 B+树的基本概念

B+树的产生原因是源自于操作系统的文件索引和数据库的索引。

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

每个分支结点最多有m棵子树。
非叶根结点至少有两棵子树，其他每个分支结点最多有至少有
$\left \lceil m/2 \right \rceil$
棵子树。
结点子树与关键字数目相等。
所有叶结点包含全部关键字及指向相应记录的指针。
叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互连接起来。

m阶B树与B+树的主要差异如下：

B+树中，包含n个关键字的结点只含有n棵子树；B树中n个关键字对应n+1棵子树。
在B+树中，每个结点的关键字个数n的范围是
$\left [ m/2 \right ]\leq n\leq m$
。
在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中每个索引项只含有对应子树的最大关键字和指向该子树的指针。

7.5 散列表

7.5.1 散列表的基本概念

散列函数:
$Hash(key) = Addr$
一个把查找表中的关键字映射成该关键字对应的地址的函数。散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为

冲突

。

散列表：根据关键字而直接进行访问的数据结构，也就是说散列表建立了关键字和存储地址之间的一种直接映射关系。理想情况下，对散列表进行查找的时间复杂度为O(1)，即与表中元素个数无关。

7.5.2 散列函数的构造方法

在构造散列函数时，应该要注意以下几点：

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

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

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

1. 直接定址法

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

H(key) = key 或 H(key) = a *key + b，式中，a 和 b 是常数，计算方便，不会产生冲突。

适用于：关键字的分布基本连续，例如：3，4，5，7，8；若关键字分布不连续，空位较多，会造成存储空间的浪费。

2. 除留余数法

除留余数法是一种最简单、最常用的方法，简单介绍除留余数法是如何使用的。

假设散列表表长为 m，取一个不大于 m 但近视接近或等于 m 的质数 p，利用除留余数法的散列函数把关键字转换成散列地址。散列函数为：H(key) = key % p 。

采用除留余数法关键是选好 p，这样就使得每个关键字通过该散列函数转换后等概率地映射到散列空间上地任一地址。

3. 数字分析法

数字分析法基本上不常用，不做介绍。不过数字分析法这种方法适合于已知的关键字集合，若换了关键字，则需要重新构造新的散列函数。

4. 平方取中法

顾名思义，这种方法取关键字的平方值的中间几位作为散列地址。该方法不太适用，且操作相对较麻烦，不过多介绍。

处理冲突的方法

冲突，顾名思义，就是不同的关键字经过 hash 函数的计算可能得到同一个 hash 地址，即 key1 不等于 key2 时，H(key1 ) = H(key2 )，出现的这种现象便叫做冲突。

解决冲突，即在关键字发生冲突时，为产生冲突的关键字寻找下一个“空”的 Hash 地址。利用探测方法进行探测，若探测到的 Hash 地址仍然产生冲突，就继续探测下一个地址，直到为该关键字找到不产生冲突的存储地址即可。

7.5.3 处理冲突的方法

有两种：开放定址法和拉链法（链接法）。

1. 开放定址法

所谓开放定址法，是指可存放新表项的空间地址既向它的同义词开放，又向它的非同义词表项开放。其数学递推公式为：Hi = (H(key)+di)%m，式中，H(key) 为散列函数；i = 0,1,2,…,k(k<=m-1)；m 表示散列表表长；di为增量序列。通常有以下 4 种取法，分别是线性探测法、平方探测法、再散列法和伪随机序列法，简单介绍线性探测法和平方探测法。

线性探测法

当 di =0，1，2，…，m-1时，称为线性探测法。

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

缺点：线性探测法可能使第 i 个散列地址的同义词存入第 i+1 个散列地址，将本该存入第 i+1 个散列地址的元素就争夺第 i+2 个散列地址的元素地址，以此类推，从而照成大量元素在相邻的散列地址上“聚集”（或堆积）起来，大大降低了查找效率。

平方探测法（简单了解即可）

当 di = 0^2， 1^2， -1^2 ， 2^2， -2^2，… ，k^2, -k^2 时，称为平方探测法，其中 k<=m/2，散列表长度 m 必须是一个可以表示成 4K+3 的素数，又称二次探测法。

特点：平方探测法是一种较好的处理冲突的方法，可以避免出现“堆积”问题。

缺点：不能探测到散列表上的所有单元，只能探测到散列表上的一半单元。

2. 拉链法（链接法）

对于不同的关键字可能会通过散列函数映射到同一地址，为避免非同义词发生冲突，把所有的同义词存在在一个线性链表中，线性链表由其散列地址唯一标识。

适用：拉链法常用于进行插入和删除的情况。

关键字序列为 {15,16,29,37,48,12,25,56,67,47,22,34}，应用拉链法处理冲突的散列表如下图所示。

散列表参考：

https://blog.csdn.net/qq_44725331/article/details/115748586

7.5.4 散列查找性能分析

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

散列表的平均查找长度依赖于散列表的装填因子α，而不直接依赖于n和m。α越大，表示记录装载越慢，发生冲突可能性越大。

原文链接：https://blog.csdn.net/weixin_40491661/article/details/124282460

7.1 查找的基本概念

7.2 顺序查找和折半查找

7.2.1 顺序查找

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

2.有序表的顺序查找

7.2 折半查找—二分法查找

7.2.3 分块查找

7.3 树型查找

7.3.1 二叉排序树—BST

1. BST的查找

2. BST的插入

3. BST的删除

4. BST的查找效率

7.3.2 平衡二叉树

1. 平衡二叉树的定义

2. 平衡二叉树的插入

3. 平衡二叉树的删除

4.平衡二叉树的查找

7.3.3 红黑树

1. 红黑树的定义

2. 红黑树的插入

3. 红黑树的删除

7.4 B树与B+树

7.4.1 B树及其基本操作

1. B树的高度

2. B树的查找

3. B树的插入

4. B树的删除

7.4.2 B+树的基本概念

7.5 散列表

7.5.1 散列表的基本概念

7.5.2 散列函数的构造方法

1. 直接定址法

2. 除留余数法

3. 数字分析法

4. 平方取中法

7.5.3 处理冲突的方法

1. 开放定址法

2. 拉链法（链接法）

7.5.4 散列查找性能分析

你可能也喜欢