数据结构（十）—查找算法（顺序表查找、有序表查找、线性索引查找、二叉排序树、AVL树、B树、散列表）_有序搜索算法流程图(例子)

一、查找的定义

查找的相关术语词:

• 查找表：是由同一类型的数据元素（或记录）构成的集合。
• 关键字：是数据元素中某个数据项的值
• 主关键字：若关键字可以唯一地标志一个记录，则可以称此关键字为主关键字。
• 次关键字：可以识别多个数据元素的关键字，我们称为次关键字
• 静态查找表：只作查找操作的查找表。
• 动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。

查找就是根据主关键词或者次关键词，获取到某条记录或者对象。

二、顺序表查找(时间复杂度O(n))

初学C语言的时候，当时学了最简单的一个查找，就是顺序表查找，就是从数组中一个一个地去对比，直到查到这个数据为之。代码也很好实现

/* 顺序查找，a为数组，n为要查找的数组个数，key为要查找的关键字 */
int Sequential_Search(int *a,int n,int key)
{
	int i;
	for(i=1;i<=n;i++)
	{
		if (a[i]==key)
			return i;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11

我们来分析一下这段代码，在for循环中，进行一次i小于n的比较，再进行i++，循环内，还有一个a[i]==key的比较，这三步能否合成一步呢，改成while循环就好了嘛。

/* 有哨兵顺序查找 */
int Sequential_Search2(int *a,int n,int key)
{
	int i;
	a[0]=key;			/* 设置a[0]为关键字值，我们称之为“哨兵”*/
	i=n;				/* 循环从数组尾部开始 */
	while(a[i]!=key)
	{
		i--;
	}
	return i;			/* 返回0则说明查找失败 */
}
1
2
3
4
5
6
7
8
9
10
11
12

这样就只用比较两步了，分别是while中的一次判断，一次i–；这就是一个很简单的思想，但是在要处理巨大数据量的时候，这一步可以节省很多时间。

三、有序表查找(时间复杂度O(logn))

表必须是有序的，要么从大到小，要么从小到大。

3.1折半查找（二分查找）

折半查找的思想，就跟之前很火的小游戏一个思想，从一组数中间开始，比如50，然后报一个数，裁判告诉大了还是小了，大了，那么目标数字就是在50-这个数，小了，那么目标数就是在这个数-50，思考一下，这种算法，就不用像顺序表查找那样一个一个地去对比了，很多元素是不需要对比的。
代码实现：

/* 折半查找 */
int Binary_Search(int *a,int n,int key)
{
	int low,high,mid;
	low=1;					/* 定义最低下标为记录首位 */
	high=n;					/* 定义最高下标为记录末位 */
	while(low<=high)
	{
		mid=(low+high)/2;	/* 折半 */
		if (key<a[mid])		/* 若查找值比中值小 */
			high=mid-1;		/* 最高下标调整到中位下标小一位 */
		else if (key>a[mid])/* 若查找值比中值大 */
			low=mid+1;		/* 最低下标调整到中位下标大一位 */
		else
		{
			return mid;		/* 若相等则说明mid即为查找到的位置 */
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.2插值查找

插值查找与折半查找只是差了一行代码而已，修改了计算mid的方法而已，之前计算就是一直取中而已，但是这里就是改成了mid=low+ (high-low)*(key-a[low])/(a[high]-a[low]);

/* 插值查找 */
int Interpolation_Search(int *a,int n,int key)
{
	int low,high,mid;
	low=1;	/* 定义最低下标为记录首位 */
	high=n;	/* 定义最高下标为记录末位 */
	while(low<=high)
	{
		mid=low+ (high-low)*(key-a[low])/(a[high]-a[low]); /* 插值 */
		if (key<a[mid])		/* 若查找值比插值小 */
			high=mid-1;		/* 最高下标调整到插值下标小一位 */
		else if (key>a[mid])/* 若查找值比插值大 */
			low=mid+1;		/* 最低下标调整到插值下标大一位 */
		else
			return mid;		/* 若相等则说明mid即为查找到的位置 */
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

改成这样的好处有啥好处呢，如果是表中数据分布是均匀的，数字相差不大，那么使用插值查找就有一定优势（不信可以找一个数列试试），但是对于数据里有1,10000,这样的数据，那么插值查找就不如折半查找有优势。

3.3斐波那契查找

这种方法与前面两种方法很类似，只不过，这里运用了斐波那契数列来进行辅助查找。同样是对Mid的计算方式进行了修改。
上代码：

int Fibonacci_Search(int *a,int n,int key) /* 斐波那契查找 */
{
	int low,high,mid,i,k;
	low=1;						/* 定义最低下标为记录首位 */
	high=n;						/* 定义最高下标为记录末位 */
	k=0;
	while(n>F[k]-1)				/* 计算n位于斐波那契数列的位置 */
		k++;
	for (i=n;i<F[k]-1;i++)		/* 将不满的数值补全 */
		a[i]=a[n];
	while(low<=high)
	{
		mid=low+F[k-1]-1;		/* 计算当前分隔的下标 */
		if (key<a[mid])			/* 若查找记录小于当前分隔记录 */
		{
			high=mid-1;			/* 最高下标调整到分隔下标mid-1处 */
			k=k-1;				/* 斐波那契数列下标减一位 */
		}
		else if (key>a[mid])	/* 若查找记录大于当前分隔记录 */
		{
			low=mid+1;			/* 最低下标调整到分隔下标mid+1处 */
			k=k-2;				/* 斐波那契数列下标减两位 */
		}
		else
		{
			if (mid<=n)
				return mid;		/* 若相等则说明mid即为查找到的位置 */
			else 
				return n;		/* 若mid>n说明是补全数值，返回n */
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

四、线性索引查找

4.1稠密索引

稠密索引是指线性索引中，将数据集中的每个记录对应一个索引项。索引项一定是按照关键码有序排列的。
我们可以通过查找索引项来找到记录，而索引项是顺序排列的，故可以使用有序表查找。

4.2分块索引

稠密索引，每一条记录都对应一条索引项，这样会造成大量的空间浪费，故我们借鉴图书馆分类管理的思想，可以得出分块索引的方法，对于索引表，它可以存储块的长度，块中的最大数据，块中的第一条数据的地址。那么，在进行查找时，我们就可以根据块来查找，去到特定的块中查找，其他块不用管了。这样查找，索引表数量只有块的数量，节省了很多空间，并且还能一定程度上减少时间。
块内无序，块间有序。 可以保证快速找到要去哪一个块。

4.3倒排索引

为什么需要倒排索引呢？我们想象一个场景，当我们在网页搜索一个关键词的时候，可以产生很多条信息，这些信息中都有这个关键词，根据之前的索引方式来看，是不可能实现的，所以需要一种新的索引方式——倒排索引。

我们将文章中出现的单词作为关键码，这各单词出现在哪几篇文章中，将这几篇文章的地址存储下来，在查找的时候就可以将这几篇文章一次性查找出来。

当然现实中用的搜索引擎中的算法都是很复杂的，往往为了方便记忆关键码，还对关键码进行了一定规则的编码转化。

五、二叉排序树

什么是二叉排序树呢？首先，它是一棵树，其次，它是一棵二叉树，再有，它是排序树，是有序的。

这就是二叉排序树，那他怎么实现排序的呢，我们规定，在这颗二叉树中插入元素的时候，如果比根结点大的，就加在结点右子树，比结点大就加在左子树，就出现下面这样的二叉树。

我们可以看出来，每一个结点的子树也是一棵二叉排序树。

所以我们总结一下二叉排序树的性质;

• 若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值。
• 若它的右子树不为空，则右子树上所有结点的值均小于它的根结点的值。
• 它的左右子树也分别为二叉排序树。

5.1二叉排序树的查找操作

这个查找过程就是不断的每一层每一层的对比，与根结点对比完，与它的孩子结点对比，比结点大，那么就往右子树比较，比结点小则往左子树比较下去，直到找到要查找的数据为之，这就是二叉排序树的查找操作。

代码实现：

Status SearchBST(BiTree T, int key, BiTree f, BiTree *p) 
{ /* 递归查找二叉排序树T中是否存在key, */ 
	if (!T)		/* 若查找不成功，指针p指向查找路径上访问的最后一个结点并返回FALSE */
	{ 
		*p = f;  
		return FALSE; 
	}
	else if (key==T->data) /* 若查找成功，则指针p指向该数据元素结点，并返回TRUE */
	{ 
		*p = T;  
		return TRUE; 
	} 
	else if (key<T->data) 
		return SearchBST(T->lchild, key, T, p);  	/* 在左子树中继续查找 */
	else  
		return SearchBST(T->rchild, key, T, p);  	/* 在右子树中继续查找 */
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

5.2二叉排序树的插入操作

插入操作非常简单，就是在树中添加一个结点，根据二叉排序树的定义，可以很容易根据定义找到新添加的元素应该位于哪一个位置。

Status InsertBST(BiTree *T, int key) 
{  
	BiTree p,s;
	if (!SearchBST(*T, key, NULL, &p)) /* 查找不成功 */
	{
		s = (BiTree)malloc(sizeof(BiTNode));
		s->data = key;  
		s->lchild = s->rchild = NULL;  
		if (!p) 
			*T = s;			/*  插入s为新的根结点 */
		else if (key<p->data) 
			p->lchild = s;	/*  插入s为左孩子 */
		else 
			p->rchild = s;  /*  插入s为右孩子 */
		return TRUE;
	} 
	else 
		return FALSE;  /*  树中已有关键字相同的结点，不再插入 */
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

5.3二叉排序树的删除操作

二叉排序树删除总共分三种情况：

• 删除叶子结点
• 仅有左或者右子树的结点
• 左右子树都有的结点

我们来看这三种不同情况的区别，对于叶子结点，我们直接删除它，由于它没有孩子结点，所以删除后，仍然是二叉排序树，且对树的结构没有较大影响。

仅有左子树或者右子树的结点，我们把这个结点删除后，将这个结点的子树继续接到这个结点的父结点上，这样是不影响二叉排序树的结构的，这仍然是一棵二叉排序树。

对于第三种情况则比较麻烦，我们要处理删除结点的左右子树，那么有两种思路，要么将一支子树接上去，另一支子树的所有元素都重新挨个插入，但是这样会造成很大的操作量。我们能否找一个左右子树中的数据替代删除结点的位置呢？保持只要挪动一个元素位置便可继续保持二叉排序树。
我们可以发现，在使用中序遍历的时候，删除结点的前驱和后继元素可以取代删除结点的位置，于是我们可以用中序遍历中的删除元素的前驱和后继元素来填补被删结点的位置，树仍然是二叉排序树。
代码实现;

/* 从二叉排序树中删除结点p，并重接它的左或右子树。 */
Status Delete(BiTree *p)
{
	BiTree q,s;
	if((*p)->rchild==NULL) /* 右子树空则只需重接它的左子树（待删结点是叶子也走此分支) */
	{
		q=*p; *p=(*p)->lchild; free(q);
	}
	else if((*p)->lchild==NULL) /* 只需重接它的右子树 */
	{
		q=*p; *p=(*p)->rchild; free(q);
	}
	else /* 左右子树均不空 */
	{
		q=*p; s=(*p)->lchild;
		while(s->rchild) /* 转左，然后向右到尽头（找待删结点的前驱） */
		{
			q=s;
			s=s->rchild;
		}
		(*p)->data=s->data; /*  s指向被删结点的直接前驱（将被删结点前驱的值取代被删结点的值） */
		if(q!=*p)
			q->rchild=s->lchild; /*  重接q的右子树 */ 
		else
			q->lchild=s->lchild; /*  重接q的左子树 */
		free(s);
	}
	return TRUE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

六、平衡二叉树（AVL树）

平衡二叉树的定义：
平衡二叉树是一种特殊的二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1。我们将左子树高度减去右子树高度的值称为平衡因子BF。

为什么需要平衡二叉树呢？
我们在构造二叉排序树的时候，可能会出现左右子树分布不均匀的情况，而最差的情况就是元素全部集中在右子树或左子树，这就变成了链表，那么二叉排序树的优势就无法体现出来了，于是我们需要引入平衡二叉树。这样查找起来就会很方便

如何将一棵不是平衡二叉树的二叉排序树变成平衡二叉树呢？
我们找取每一个不平衡的结点，查看他的BF值，若是小于-1，则进行左旋，如果是大于1，则进行右旋，啥是左旋和右旋呢？看图

就是把它变成一个父节点和两个孩子结点的方法。注意旋转的时候，如果旋转后的父节点本来就有一个子结点，要将原本的子树拼接到根结点的另一条子树上。
如下图3结点接到了左子树上。

左平衡函数：

void LeftBalance(BiTree *T)
{ 
	BiTree L,Lr;
	L=(*T)->lchild; /*  L指向T的左子树根结点 */ 
	switch(L->bf)
	{ /*  检查T的左子树的平衡度，并作相应平衡处理 */ 
		 case LH: /*  新结点插入在T的左孩子的左子树上，要作单右旋处理 */ 
			(*T)->bf=L->bf=EH;
			R_Rotate(T);
			break;
		 case RH: /*  新结点插入在T的左孩子的右子树上，要作双旋处理 */ 
			Lr=L->rchild; /*  Lr指向T的左孩子的右子树根 */ 
			switch(Lr->bf)
			{ /*  修改T及其左孩子的平衡因子 */ 
				case LH: (*T)->bf=RH;
						 L->bf=EH;
						 break;
				case EH: (*T)->bf=L->bf=EH;
						 break;
				case RH: (*T)->bf=EH;
						 L->bf=LH;
						 break;
			}
			Lr->bf=EH;
			L_Rotate(&(*T)->lchild); /*  对T的左子树作左旋平衡处理 */ 
			R_Rotate(T); /*  对T作右旋平衡处理 */ 
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

右平衡函数：

/*  对以指针T所指结点为根的二叉树作右平衡旋转处理， */ 
/*  本算法结束时，指针T指向新的根结点 */ 
void RightBalance(BiTree *T)
{ 
	BiTree R,Rl;
	R=(*T)->rchild; /*  R指向T的右子树根结点 */ 
	switch(R->bf)
	{ /*  检查T的右子树的平衡度，并作相应平衡处理 */ 
	 case RH: /*  新结点插入在T的右孩子的右子树上，要作单左旋处理 */ 
			  (*T)->bf=R->bf=EH;
			  L_Rotate(T);
			  break;
	 case LH: /*  新结点插入在T的右孩子的左子树上，要作双旋处理 */ 
			  Rl=R->lchild; 			/*  Rl指向T的右孩子的左子树根 */ 
			  switch(Rl->bf)
			  { 						/*  修改T及其右孩子的平衡因子 */ 
				case RH: (*T)->bf=LH;
						 R->bf=EH;
						 break;
				case EH: (*T)->bf=R->bf=EH;
						 break;
				case LH: (*T)->bf=EH;
						 R->bf=RH;
						 break;
			  }
			  Rl->bf=EH;
			  R_Rotate(&(*T)->rchild); /*  对T的右子树作右旋平衡处理 */ 
			  L_Rotate(T); /*  对T作左旋平衡处理 */ 
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

重头戏，实现平衡二叉树：

/*  若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 */ 
/*  数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树 */ 
/*  失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。 */
Status InsertAVL(BiTree *T,int e,Status *taller)
{  
	if(!*T)
	{ /*  插入新结点，树“长高”，置taller为TRUE */ 
		 *T=(BiTree)malloc(sizeof(BiTNode));
		 (*T)->data=e; (*T)->lchild=(*T)->rchild=NULL; (*T)->bf=EH;
		 *taller=TRUE;
	}
	else
	{
		if (e==(*T)->data)
		{ /*  树中已存在和e有相同关键字的结点则不再插入 */ 
			*taller=FALSE; return FALSE;
		}
		if (e<(*T)->data)
		{ /*  应继续在T的左子树中进行搜索 */ 
			if(!InsertAVL(&(*T)->lchild,e,taller)) /*  未插入 */ 
				return FALSE;
			if(*taller) /*   已插入到T的左子树中且左子树“长高” */ 
				switch((*T)->bf) /*  检查T的平衡度 */ 
				{
					case LH: /*  原本左子树比右子树高，需要作左平衡处理 */ 
							LeftBalance(T);	*taller=FALSE; break;
					case EH: /*  原本左、右子树等高，现因左子树增高而使树增高 */ 
							(*T)->bf=LH; *taller=TRUE; break;
					case RH: /*  原本右子树比左子树高，现左、右子树等高 */  
							(*T)->bf=EH; *taller=FALSE; break;
				}
		}
		else
		{ /*  应继续在T的右子树中进行搜索 */ 
			if(!InsertAVL(&(*T)->rchild,e,taller)) /*  未插入 */ 
				return FALSE;
			if(*taller) /*  已插入到T的右子树且右子树“长高” */ 
				switch((*T)->bf) /*  检查T的平衡度 */ 
				{
					case LH: /*  原本左子树比右子树高，现左、右子树等高 */ 
							(*T)->bf=EH; *taller=FALSE;	break;
					case EH: /*  原本左、右子树等高，现因右子树增高而使树增高  */
							(*T)->bf=RH; *taller=TRUE; break;
					case RH: /*  原本右子树比左子树高，需要作右平衡处理 */ 
							RightBalance(T); *taller=FALSE; break;
				}
		}
	}
	return TRUE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

七、多路查找树（B树）

为什么需要B树？对于计算机存储，我们每次访问记录的时候都要去访问内存，这个操作会造成很大的消耗，所以可以使用B树，B树对于每一个结点，它不再单独的只存放一个结点，它可以存放多个数据元素，因此它可以访问一次内存，获取多个数据。
B树的相关操作这里就不写了~

八、散列表（哈希表）

前面介绍了那么多的查找方法，但并没有哪个实现了时间复杂度为O（1）的算法，于是我们就开始寻找，有没有什么方法能实现时间复杂度为1的查找的。那就是散列表，也就是哈希表。

我们先来看一下这个名字的来历，hash的中文名字是零散的，拆散的，这很符合我们的哈希表的定义，首先我们来了解一个哈希函数的概念。哈希函数可以实现将一条数据进行处理，然后获得一个数字。那么这个数据就可以和这个数字实现一一对应的关系，将这条数据存入这个数字对应的地址中，那么第二次查找这个元素的时候，同样用哈希函数进行处理，得出地址数，然后直接去对应地址里找，就获得了数据，这样时间复杂度直接就为1了。

那这个哈希函数怎么实现呢？研究出来哈希函数的这个人一定是研究密码学的，我们可以通过一定的规则，将要处理的数据变成独一无二的数字，就像学号一样，我们可以取班级03，序号28来编码，存进0328，也就是328这个地址里。这样无论你的学号多长，我们就用这四位数来实现一一对应，且不会重复。说白了哈希函数就是对信息进行重新编码，得到一个数字。

哈希表存在的问题：（哈希冲突）高效查找的代价
我们现实生活中，并不存在一个万能的哈希函数能够实现对所有对象都编码出独一无二的数字，可能两个不同的数据，通过哈希函数会编码出相同的数字，那么此时就不是一一对应的关系了，会造成信息混乱。

解决哈希冲突的几种方法：

• 开放地址法
• 多个哈希函数共同作用
• 再散列函数法
• 链地址法
• 公共移除区法

其实这几种方法仍然存在一定程度上的哈希冲突。感兴趣的小伙伴可以去看Java1.8中是如何实现hashmap的，它运用了哈希函数+红黑树的方法来解决的哈希冲突。