Abo

数据结构-查找

查找,说到底也是排序思想的基础,主要是针对树的查找


hoodie

前言:查找(Searching)就是根据给定的某个值,在查找表中确定一个其关键字等于定值的数据元素(或记录)

  • 查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合
  • 关键字(Key)是数据元素中某个数据项的值,又称为键值,用它可以标识一个数据元素。也可以标识一个记录的某个数据项(字段),我们称为关键码
  1. 若此关键字可以唯一地标识一个记录,则称此关键字为主关键字(Primary Key),注意这意味着,对不同的记录,其主关键字均不相同,主关键字所在的数据项称为主关键码
  2. 那么对于那些可以识别多个数据元素(或记录)的关键字,我们称为次关键字(Secondary Key),次关键字可以理解为是不以唯一标识一个数据元素(或记录)的关键字,它对应的数据项就是次关键码

查找表按照操作方式分两大种:

  1. 静态查找表(Static Search Table):只作查找操作的操作表
  2. 动态操作表(Dynamic Search Table):在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已经存在的某个数据元素

顺序表查找

  • 顺序查找(Sequential Search)又叫线性查找,是最基本的查找技术。
1
2
3
4
5
6
7
8
9
10
11
/*顺序查找,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;
}

到这里并非足够完美,因为每次循环时都需要对i是否越界,即是否小于等于n进行判断,我们不妨设置一个哨兵

1
2
3
4
5
6
7
8
9
10
11
12
/*顺序表查找优化:有哨兵顺序查找*/
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则说明查找失败*/
}

对于这种顺序查找算法来说,查找成功最好的情况就是第一个位置就找到了,算法时间复杂度为O(1),最坏的情况是最后一个位置才找到,需要n次比较,时间复杂度为O(n),当查找不成功时,需要n+1次比较,时间复杂度为O(n)

我们推导过,关键字在任何一位置的概率是相同的,所以平均查找次数为(n+1)/2,所以最终时间复杂度为O(n)


有序表查找

又称为二分查找,它的前提是线性表中的记录必须是关键码有序(通常从小到大有序),线性表必须采用顺序存储。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*折半查找*/
int Binary_Search(int *a,int n,int key)
{
int low,high,mid;
low=1; /*定义最低下标为记录首位*/
high=n; /*定义最高下标为记录末位*/
while(low<=mid)
{
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;
}

因此最终折半算法的时间复杂度为O(logn),它显然远远好于顺序查找的O(n)时间复杂度


换句话说,我们只需要在折半查找算法的代码中更改一下第8行的代码

如下

1
mid = low + (high-low) * (key-a[low])/(a[high]-a[low]);  /*插值*/
  • 我们得到了另一种有序表查找算法,差值查找法,插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法。

其核心就在于插值的计算公式,应该说,从时间复杂度来看,也是O(logn),但是对于表长较大的,关键字分布又比较均匀的查找表来说,插值查找算法的平均性能要比折半查找好很多


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
/*斐波那契查找*/
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;
}

线索索引查找

  • 索引就是把一个关键字与它对应的记录相关联的过程,所以线性索引就是将索引项集合组织为线性结构,也称为索引表,我们重点介绍三种线性索引:稠密索引,分块索引和倒排索引

二叉排序树(Binary Sort Tree)

又称为二叉寻找树。它或者是一棵空树,或者是具有下列性质的二叉树

  1. 若它的左子树不空,则左子树上所有结点的值均小于它 的根结构的值;
  2. 若它的右子树不空,则右子树上所有结点的值均大于它的根节点的值;
  3. 它的左,右子树也分别为二叉排序树
  • 二叉排序树查找操作
1
2
3
4
5
6
/*二叉树的二叉链表结点结构定义*/
typedef struct BiTNode /*结点结构*/
{
int data; /*结点数据*/
struct BiTNode *lchild,*rchild; /*左右孩子指针*/
}BiTNode,*BiTree;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*递归查找二叉排序树T中是否存在key*/
/*指针f指向T的双亲,其初始调用值为NULL*/
/*若查找成功,则指针p指向该数据元素结点,并返回TRUE*/
/*否则指针p指向查找路径上访问的最后一个结点并返回FALSE*/
Status SearchBST(BiTree T,int key,BiTree f,BiTree *p)
{
if(!T) /*查找不成功*/
{
*p = f;
return FALSE;
}
else if(key == T->data) /*查找成功*/
{
*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
18
19
20
21
/*当二叉排序树T中不存在关键字等于key的数据元素时*/
/*插入key并返回TRUE,否则返回FALSE*/
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
int i;
int a[10] = {62,22,41,53,76,33,77,12,16,75}
BiTree T = NULL;
for(i=0;i<10;i++)
{
InsertBST(&T,a[i])
}
  • 二叉排序树删除操作(三种情况)
  1. 叶子结点
  2. 仅有左或右子树的结点
  3. 左右子树都有的结点,我们来看代码,下面这个算法是递归方式对二叉排序树T查找key,查到是删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素结点*/
Status DeleteBST(BiTree *T,int key)
{
if(!*T) /*不存在关键字等于key的数据元素*/
return FALSE;
else
{
if(key == (*T)->data) /*找到关键字等于key的数据元素*/
return Delete(T);
else if(key<(*T)->data)
return DeleteBST(&(*T)->lchild,key);
else
return DeleteBST(&(*T)->rchild,key);
}
}

Let’s delete !

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
/**/
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;
}

二叉排序树总结

  • 二叉排序树是以链接的方式存储,保存了链接存储结构在执行插入或删除操作时不用移动元素的优点,只要找到合适的插入和删除位置后,仅需修改链接指针即可。插入删除的时间性能比较好。
  • 二叉排序树的查找性能取决于二叉排序树的形状,也就是说我们希望二叉排序树是平衡的,即深度与完全二叉树相同,均为[log2n]+1,那么查找的时间复杂度也就为O(logn),类似于折半查找,不平衡的最坏情况就是斜树,查找时间复杂度为O(n),这等同于顺序查找

平衡二叉树(AVL树)

  • 平衡二叉树(Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree),是一种二叉排序树,其中每一个节点的左子树和右子树的高度差至多为1.
  • 顾名思义,这是一种高度平衡的二叉排序树,我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor)
  • 距离插入结点最近的,且平衡因子的绝对值大于1的结点为根的子树,我们称为最小不平衡子树

平衡二叉树实现原理

  • 当最小不平衡树根结点的平衡因子BF是大于1时,就右旋,小于-1时就左旋。插入结点后,最小不平衡树的BF与它的子树的BF符号相反时,就需要对结点先进行一次旋转以使得符号相同后,再反向旋转一次才能够完成平衡操作

平衡二叉树实现算法

1
2
3
4
5
6
7
/*二叉树的二叉链表结点结构定义*/
typedef struct BiTNode /*结点结构*/
{
int data; /*结点数据*/
int bf; /*结点的平衡因子*/
struct BiTNode *lchild,*rchild; /*左右孩子指针*/
}BiTNode,*BiTree;

右旋操作

1
2
3
4
5
6
7
8
9
10
/*对以p为根的二叉排序树作右旋处理*/
/*处理之后p指向新的树根结点,即旋转处理之前的左子树的根节点*/
void R_Rotate(BiTree *P)
{
BiTree L;
L=(*P)->lchild; /*L指向P的左子树根结点*/
(*P)->lchild=L->rchild; /*L的右子树挂接为P的左子树*/
L->rchild=(*P);
*P=L; /*P指向新的根结点*/
}

左旋操作与右旋代码是对称的,不做解释

以下是左平衡旋转处理的函数代码

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
#define LH +1  /*左高*/
#define EH 0 /*等高*/
#define RH -1 /*右高*/
/*对以指针T所指结点为根的二叉树作左平衡旋转处理*/
/*本算法结束时,指针T指向新的根结点*/
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/*若在平衡的二叉排序树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=EN;
*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
int i;
int a[10]={3,2,1,4,5,6,7,10,9,8};
BiTree T=NULL;
Status taller;
for(i=0;i<10;i++)
{
InsertAVL(&T,a[i],&taller);
}

不平衡的二叉排序树查找效率是非常低的,由此我们需要在构建时,就让这棵二叉排序树是平衡二叉树,此时我们的查找时间复杂度就为O(logn),而插入和删除也为O(logn),这显然是比较理想的一种动态查找表算法


多路查找树(B树)

  • 多路查找树(multl-way search tree):其每一个结点的孩子数可以多于两个,且每一个结点处可以存储多个元素。
  • 2-3树:其中每一个结点都具有两个孩子(我们称它为2结点)或三个孩子(我们称它为3结点)
  1. 一个2结点包含一个元素和两个孩子(或没有孩子)

与二叉排序树类似,左子树包含的元素小于该元素,右子树同理

不过,这个2结点要么没有孩子,要么就有两个,不能只有一个孩子

  1. 一个3结点包含一小一大两个元素和三个孩子(或没有孩子)

一个3结点要么没有孩子,要么具有三个孩子,左最小,中介于,右最大

  1. 2-3树中所有叶子都在同一层次上

了解一下2-3树的插入实现与删除实现

  • 2-3-4树:其实就是2-3树的概念拓展,包括了4结点的使用,一个4结点包括小中大三个元素和四个孩子(或没有孩子)
  • B树(B-tree)是一种平衡的多路查找树,2-3树和2-3-4树都是B树的特例。结点最大的孩子数目称为B树的阶(order),因此2-3树是3阶B树,2-3-4是4阶B树

对于n个关键字的m阶B树,最坏情况是要查找几次呢?

第一层至少有1个结点,第二层至少有2个结点,由于除根结点外每个分支结点至少有(m/2)棵子树,则第三层至少有2X(m/2)个结点,….这样第k+1层至少有2X(m/2)^k-1^

  • B+树

散列表查找(哈希表)概述

  • 散列技术是在记录的存储位置和它的关键字之间建立一个确立的对应关系f,使得每个关键字key对应一个存储位置f(key)

查找时,根据这个确定的对应关系找到给定值key的映射f(key),若查找集合中存在这个记录,则必定在f(key)的位置上

  • 这里我们把这种对应关系f称为散列函数,又称哈希(Hash)函数。按这个思想,采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表(Hash table),那么关键字对应的记录存储位置我们称为散列地址

散列技术既是一种存储方法,也是一种查找方法,散列技术最合适的求解问题是查找与给定值相等的记录.

  • 我们通常会碰到两个关键字key1≠key2,但是却有f(key1)=f(key2),这种现象我们称为冲突(collision),并把key1和key2称为这个散列函数的同义词(synonym)


散列函数的构造方法

  • 直接定址法

也就是说,我们可以取关键字的某个线性函数值为散列地址,即f(key)=a x key+b (a,b为常数)

  • 数字分析法
  • 平方取中法
  • 折叠法
  • 除留余数法
  • 随机数法

处理散列冲突的方法

  1. 开放地址法

所谓的开放地址,就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入

f1(key) = (f(key)+di) MOD m (di=1,2,3,….,m-1)

我们把这种解决冲突的开放地址法称为线性探测法

  • 在解决冲突的时候,我们会碰到这种本来都不是同义词却需要争夺一个地址的情况,我们称这种现象为堆积。

另外增加平方运算的目的是为了不让关键字都聚集在某一刻区域,我们称这种方法为二次探测法

即改进di=1^2^,-1^2^,2^2^,-2^2^,…

  • 还有一种方法是,在冲突时,对于位移量di采用随机函数计算得到,我们称之为随机探测法

这里的随机其实是伪随机数,伪随机数就是说,如果我们设置随机种子相同,则不断调用随机函数生成不会重复的数列,我们在查找时,用同样的随机种子,它每次得到的数列是相同的,相同的di也会得到相同的数列地址

随机种子了解一波?

总之,开放定址法只要在散列表未填满时,总是能找到不发生冲突的地址,是我们常用的解决冲突的方法

  1. 再散列函数法(事先准备多个散列函数)
  2. 链地址法

公共溢出区法(溢出表)


散列表查找实现

首先是需要定义一个散列表的结构以及一些相关的常数,其中HashTable就是散列表结构,机构当中的elem为一个动态数组

1
2
3
4
5
6
7
8
9
10
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12 /*定义散列表长为数组的长度*/
#define NULLKEY -32768
typedef struct
{
int *elem; /*数据元素存储基址,动态分配数组*/
int count; /*当前数据元素个数*/
}HashTable;
int m=0; /*散列表表长,全局变量*/

有了结构的定义,我们可以对散列表进行初始化

1
2
3
4
5
6
7
8
9
10
11
/*初始化散列表*/
Status InitHashTable(HashTable *H)
{
int i;
m=HASHSIZE;
H->count=m;
H->elem=(int*)malloc(m*sizeof(int));
for(i=0;i<m;i++)
H->elem[i]=NULLKEY;
return OK;
}

为了插入时计算地址,我们需要定义散列函数,散列函数可以根据不同情况更改算法。


1
2
3
4
5
/*散列函数*/
int Hash(int key)
{
ruturn key % m; /*除留余数法*/
}

初始化完成后,我们可以对散列表进行插入操作。

1
2
3
4
5
6
7
8
/*插入关键字进散列表*/
void InsertHash(HashTable *H,int key)
{
int addr = Hash(key); /*求散列地址*/
while(H->elem[addr] != NULLKEY) /*如果不为空,则冲突*/
addr = (addr+1) % m; /*开放地址法的线性探测*/
H->elem[addr] = key; /*直到有空位后插入关键字*/
}

散列表存在后,我们在需要时就可以通过散列表查找要的记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*散列表查找关键字*/
Status SearchHash(HashTable H,int key,int *addr)
{
*addr = Hash(key); /*求散列地址*/
while(H.elem[*addr] != key) /*如果不为空,则冲突*/
{
*addr = (*addr+1) % m; /*开放定址法的线性探测*/
if(H.elem[*addr] == NULLKEY || *addr == Hash(key))
{ /*如果循环回到原点*/
return UNSUCCESS; /*则说明关键字不存在*/
}
}
return SUCCESS;
}

查找的代码和插入的代码非常类似,只需做一个不存在关键字的判断而已


散列表查找性能分析

如果没有冲突,散列查找是本章所有查找效率最高的,因为它的时间复杂度为O(1)