数据结构第九章：查找

Posted on | In , | |

Abstract：查找。

9.1 查找的基本概念与术语

查找表：用于查找操作的数据结构。由同类型数据元素组成的集合。

  • 在查找表中查找某个具体的数据元素；
  • 在查找表中插入数据元素；
  • 从查找表中删除数据元素；

静态查找表：只做查找操作，不改动表中数据元素。

动态查找表：在做查找操作的同事，进行插入、删除操作。

关键字：属性

  • 主关键字：即主码。唯一标识符。
  • 次关键字：不具有唯一性

静态查找表是数据元素的线性表，可以是基于数组的顺序存储或以线性链表存储。

1
2
3
4
5
6
7
8
9
10
11
/* 顺序存储结构*/
typedef struct{
ElemType *elem； /* 数组基址*/
int length； /* 表长度*/
}S_TBL；

/* 链式存储结构结点类型*/
typedef struct NODE{
ElemType elem； /* 结点的值域*/
struct NODE *next； /* 下一个结点指针域*/
}NodeType；

9.2 静态查找表—顺序查找

查找过程：顺序查找又称线性查找，是最基本的查找方法之一。其查找方法为：从表的一端开始，向另一端逐个按给定值kx 与关键码进行比较，若找到，查找成功，并给出数据元素在表中的位置；若整个表检测完，仍未找到与kx 相同的关键码，则查找失败，给出失败信息。

【算法9.1】以顺序存储为例，数据元素从下标为1 的数组单元开始存放，0 号单元留空。

1
2
3
4
5
6
7
8
int s_search( S_TBL tbl KeyType kx )
{                               /*在表tbl 中查找关键码为kx 的数据元素，若找到返回该元素在数组中的下标，否则返回0 */
	tbl.elem[0].key = kx ；  /* 存放监测，这样在从后向前查找失败时，不必判表是否检测完， */
/* 从而达到算法统一*/
			  for ( i = tbl.length; tbl.elem[i].key < > kx ； i-- )
		；               /* 从标尾端向前找*/
		return i ；
		       }

性能分析：

  • 分析查找算法的效率，通常用平均查找长度ASL 来衡量。
  • 定义：在查找成功时，平均查找长度ASL 是指为确定数据元素在表中的位置所进行的关键码比较次数的期望值。

ASL

其中：Pi 为表中第i 个数据元素的查找概率，
Ci 为表中第i 个数据元素的关键码与给定值kx 相等时，按算法定位时关键码的比较次数。显然，不同的查找方法，Ci 可以不同。

就上述算法而言，对于n 个数据元素的表，给定值kx 与表中第i 个元素关键码相等，即定位第i 个记录时，需进行n-i+1 次关键码比较，即Ci=n-i+1。则查找成功时，顺序查找的平均查找长度为：

success

ASL

查找不成功时，关键码的比较次数总是n+1 次。

算法中的基本工作就是关键码的比较，因此，查找长度的量级就是查找算法的时间复杂度，其为O(n).

许多情况下，查找表中数据元素的查找概率是不相等的。为了提高查找效率，查找表需依据查找概率越高，比较次数越少；查找概率越低，比较次数就较多的原则来存储数据元素。

顺序查找缺点是当n 很大时，平均查找长度较大，效率低；优点是对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。

9.2 静态查找表—有序表的折半查找

有序表即是表中数据元素按关键码升序或降序排列。

折半查找的思想为：在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键码相等，则查找成功；若给定值小于中间元素的关键码，则在中间元素的左半区继续查找；若给定值大于中间元素的关键码，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。

【步骤】
① low=1；high=length； // 设置初始区间
② 当low>high 时，返回查找失败信息// 表空，查找失败
③ low≤high，mid=(low+high)/2; // 取中点
a. 若kxtbl.elem[mid].key，low=mid+1；转② // 查找在右半区进行
c. 若kx=tbl.elem[mid].key，返回数据元素在表中位置// 查找成功

【例9.１】有序表按关键码排列如下：
7，14，18，21，23，29，31，35，38，42，46，49，52
在表中查找关键码为14 和22 的数据元素。

⑴ 查找关键码为14 的过程

查找关键码为14 的过程

【算法9.2】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Binary_Search( S_TBL tbl KEY kx )
{                                                               /* 在表tbl 中查找关键码为kx 的数据元素，若找到返回该元素在表中的位置，否则，返回0 */
	int mid flag = 0 ；
		       low = 1 ； high = length ；                /* ①设置初始区间*/
					while ( low <= high )   /* ②表空测试*/
	{                                                       /* 非空，进行比较测试*/
		mid = (low + high) / 2 ；                        /* ③得到中点*/
		      if ( kx < tbl.elem[mid].key )
			high = mid - 1 ；                        /* 调整到左半区*/
			       else if ( kx > tbl.elem[mid].key )
				low = mid + 1 ；                 /* 调整到右半区*/
				      else { flag = mid ； break ； }
		                                                /* 查找成功，元素位置设置到flag 中*/
	}
	return(flag);
}

性能分析】
从折半查找过程看，以表的中点为比较对象，并以中点将表分割为两个子表，对定位到的子表继续这种操作。所以，对表中每个数据元素的查找过程，可用二叉树来描述，称这个描述查找过程的二叉树为判定树。

二叉判定树

可以看到，查找表中任一元素的过程，即是判定树中从根到该元素结点路径上各结点关键码的比较次数，也即该元素结点在树中的层次数。对于n 个结点的判定树，树高为k，则有2k-1 -1<n≤2k-1，即k-1<log2(n+1)≤k，所以k= 。因此，折半查找在查找成功时，所进行的关键码比较次数至多为。

接下来讨论折半查找的平均查找长度。为便于讨论，以树高为k 的满二叉树(n=2k-1)为例。假设表中每个元素的查找是等概率的，即Pi= ，则树的第i 层有2i-1 个结点，因此，折半查找的平均查找长度为：

ASL

所以，折半查找的时间效率为O(log2n)。

9.2 静态查找表—有序表的插值查找和斐波那契查找

1.插值查找

插值查找通过下列公式

插值查找

求取中点，其中low 和high 分别为表的两个端点下标，kx 为给定值。
若kxtbl.elem[mid].key，则low=mid+1，继续右半区查找；
若kx=tbl.elem[mid].key，查找成功。

插值查找是平均性能最好的查找方法，但只适合于关键码均匀分布的表，其时间效率依然是O(log2n)。

2.斐波那契查找

斐波那契查找通过斐波那契数列对有序表进行分割，查找区间的两个端点和中点都与斐波那契数有关。斐波那契数列定义如下：

斐波那契数列定义

设n 个数据元素的有序表，且n 正好是某个斐波那契数-1，即n=F(k)-1 时，可用此查找方法。

斐波那契查找分割的思想为：对于表长为F(i)-1 的有序表，以相对low 偏移量F(i-1)-1 取中点，即mid=low+F(i-1)-1，对表进行分割，则左子表表长为F(i-1)-1，右子表表长为F(i)-1-[F(i-1)-1]-1=F(i-2)-1。可见，两个子表表长也都是某个斐波那契数-1，因而，可以对子表继续分割。

【算法9.3】
① low=1；high=F(k)-1； // 设置初始区间
F=F(k)-1；f=F(k-1)-1； // F 为表长，f 为取中点的相对偏移量
② 当low>high 时，返回查找失败信息// 表空，查找失败
③ low≤high，mid=low+f; // 取中点
a. 若kxtbl.elem[mid].key，则
F=F-f-1； // 调整表长F
f=f-F-1； // 计算取中点的相对偏移量
low=mid+1；转② // 查找在右半区进行
c. 若kx=tbl.elem[mid].key，返回数据元素在表中位置// 查找成功

当n 很大时，该查找方法称为黄金分割法，其平均性能比折半查找好，但其时间效率仍为O(log2n)，而且，在最坏情况下比折半查找差，优点是计算中点仅作加、减运算。

9.2 静态查找表—分块查找

分块查找：索引顺序查找，是对顺序查找的改进。

分块查找要求将查找表分成 若干个子表，并对子表建立索引表，查找表的每一个子表由索引表中的索引项确定。索引 项包括两个字段：关键码字段(存放对应子表中的最大关键码值) ；指针字段(存放指向对 应子表的指针) ，并且要求索引项按关键码字段有序。查找时，先用给定值kx 在索引表中 检测索引项，以确定所要进行的查找在查找表中的查找分块(由于索引项按关键码字段有序，可用顺序查找或折半查找) ，然后，再对该分块进行顺序查找。

【例9.2】关键码集合为：
88，43，14，31，78，8，62，49，35，71，22，83，18，52

按关键码值31，62，88 分为三块建立的查找表及其索引表如下：

分块查找

【性能分析】性能分析

9.3 动态查找表—二叉排序树（Binary Sort Tree）

1.二叉排序树定义：或者是一棵空树；或者是具有下列性质的二叉树：

  • 若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值。
  • 左右子树也都是二叉排序树。

由图9.4 可以看出，对二叉排序树进行中序遍历，便可得到一个按关键码有序的序列，因此，一个无序序列，可通过构一棵二叉排序树而成为有序序列。

二叉排序树示例

2.查找过程：

从其定义可见，二叉排序树的查找过程为：

  • 若查找树为空，查找失败。
  • 查找树非空，将给定值kx 与查找树的根结点关键码比较。
  • 若相等，查找成功，结束查找过程，否则，
    • a．当给kx 小于根结点关键码，查找将在以左子女为根的子树上继续进行，转①
    • b．当给kx 大于根结点关键码，查找将在以右子女为根的子树上继续进行，转①

以二叉链表作为二叉排序树的存储结构，则查找过程算法程序描述如下：

1
2
3
4
typedef struct NODE
{ ElemType elem; /*数据元素字段*/
struct NODE *lc,*rc; /*左、右指针字段*/
}NodeType; /*二叉树结点类型*/

【算法9.4】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int SearchElem( NodeType *t, NodeType **p, NodeType **q, KeyType kx )
{                                                               /*在二叉排序树t 上查找关键码为kx 的元素，若找到，返回1，且q 指向该结点，p 指向其父结点；*/
/*否则，返回0，且p 指向查找失败的最后一个结点*/ int flag = 0; *q = t; while ( *q )  /*从根结点开始
	                                                         * 查找*/
	{
		if ( kx > (*q)->elem.key )                      /*kx 大于当前结点*q 的元素关键码*/
		{
			*p = *q; *q = (*q)->rc;
		}                                               /*将当前结点*q 的右子女置为新根*/
		else{ if ( kx < (*q)->elem.key )                /*kx 小于当前结点*q 的元素关键码*/
		      {
			      *p = *q; *q = (*q)->lc;
		      } /*将当前结点*q 的左子女置为新根*/
		      else { flag = 1; break; } /*查找成功，返回*/
		}
	} /*while*/
	return(flag);
}

3.插入操作和构造一棵二叉排序树

先讨论向二叉排序树中插入一个结点的过程：设待插入结点的关键码为kx，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，待插入结点已存在，不用插入；查找不成功时，则插入之。因此，新插入结点一定是作为叶子结点添加上去的。

构造一棵二叉排序树则是逐个插入结点的过程。

【例9.3】记录的关键码序列为：63，90，70，55，67，42，98，83，10，45，58，则构造一棵二叉排序树的过程如下：

从空树开始建立二叉排序树的过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int InsertNode( NodeType **t, KeyType kx )
{                                                                       /*在二叉排序树*t 上插入关键码为kx 的结点*/
	NodeType *p = *t, *q, *s; int flag = 0;
	if ( !SearchElem( *t, &p, &q, kx ) )
		;                                                       /*在*t 为根的子树上查找*/
	{ s		= (NodeType *) )malloc( sizeof(NodeType) );     /*申请结点，并赋值*/
	  s->elem.key	= kx; s->lc = NULL; s->rc = NULL;
	  flag		= 1;                                            /*设置插入成功标志*/
	  if ( !p )
		  t = s;                                                /*向空树中插入时*/
	  else{ if ( kx > p->elem.key )
			p->rc = s;                                      /*插入结点为p 的右子女*/
		else p->lc = s;                                         /*插入结点为p 的左子女*/
	  } }
	return(flag);
}

4.删除操作

从二叉排序树中删除一个结点之后，使其仍能保持二叉排序树的特性即可。设待删结点为p（p 为指向待删结点的指针），其双亲结点为f，以下分三种情况进行讨论。
p 结点为叶结点，由于删去叶结点后不影响整棵树的特性，所以，只需将被删结点的双亲结点相应指针域改为空指针。如图9.6。 p 结点只有右子树pr 或只有左子树pl，此时，只需将pr 或pl 替换f 结点的p 子树即可。如图9.7。
p 结点既有左子树Pl 又有右子树Pr，可按中序遍历保持有序进行调整。
设删除p 结点前，中序遍历序列为：
P 为F 的左子女时有：…，Pl 子树，P，Pj ，S 子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，F，…
P 为F 的右子女时有：…，F，Pl 子树，P，Pj ，S 子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，…
则删除*p 结点后，中序遍历序列应为：
P 为F 的左子女时有：…，Pl 子树，Pj ，S 子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，F，…
P 为F 的右子女时有：…，F，Pl 子树，Pj ，S 子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，…

有两种调整方法：
直接令pl 为f 相应的子树，以pr 为pl 中序遍历的最后一个结点pk 的右子树；
令p 结点的直接前驱Pr 或直接后继（对Pl子树中序遍历的最后一个结点Pk）替换p 结点，再按⒉的方法删去Pr 或Pk。图9.8 所示的就是以p 结点的直接前驱Pr 替换*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
int DeleteNode( NodeType **t, KeyType kx )
{
	NodeType	*p	= *t, *q, *s, **f;
	int		flag	= 0;
	if ( SearchElem( *t, &p, &q, kx ) )
		;
	{ flag = 1;                                     /*查找成功，置删除成功标志*/
	  if ( p = = q )
		  f = &(*t);                            /*待删结点为根结点时*/
	  else{                                         /*待删结点非根结点时*/
		  f = &(p->lc); if ( kx > p->elem.key )
			  f = &(p->rc);
	  } /*f 指向待删结点的父结点的相应指针域*/
	  if ( !q->rc )
		  *f = q->lc;                           /*若待删结点无右子树，以左子树替换待删结点*/
	  else{ if ( !q->lc )
			*f = q->rc;                     /*若待删结点无左子树，以右子树替换待删结点*/
		else{                                   /*既有左子树又有右子树*/
			p = q->rc; s = p;
			while ( p->lc )
			{
				s = p; p = p->lc;
			}  /*在右子树上搜索待删结点的前驱p*/
			*f = p; p->lc = q->lc;          /*替换待删结点q，重接左子树*/
			if ( s != p )
			{
				s->lc	= p->rc;        /*待删结点的右子女有左子树时，还要重接右子树*/
				p->rc	= q->rc;
			}
		} }
	  free( q ); }
	return(flag);
}

对给定序列建立二叉排序树，若左右子树均匀分布，则其查找过程类似于有序表的折半查找。但若给定序列原本有序，则建立的二叉排序树就蜕化为单链表，其查找效率同顺序查找一样。因此，对均匀的二叉排序树进行插入或删除结点后，应对其调整，使其依然保持均匀。

9.3 动态查找表—平衡二叉树(AVL树)

平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树：它的左子树和右子树都是平衡二叉树，且左子树和右子树高度之差的绝对值不超过1。

平衡和非平衡二叉树

图9.9 给出了两棵二叉排序树，每个结点旁边所注数字是以该结点为根的树中，左子树与右子树高度之差，这个数字称为结点的平衡因子。由平衡二叉树定义，所有结点的平衡因子只能取-1，0，1 三个值之一。若二叉排序树中存在这样的结点，其平衡因子的绝对值大于1，这棵树就不是平衡二叉树。如图9.9 （a）所示的二叉排序树。

在平衡二叉树上插入或删除结点后，可能使树失去平衡，因此，需要对失去平衡的树进行平衡化调整。设a 结点为失去平衡的最小子树根结点，对该子树进行平衡化调整归纳起来有以下四种情况：

一. 左单旋转

左单旋转

如图9.10 的图(a)为插入前的子树。其中，B 为结点a 的左子树，D、E 分别为结点c的左右子树，B、D、E 三棵子树的高均为h。图(a)所示的子树是平衡二叉树。在图(a)所示的树上插入结点x，如图(b)所示。结点x 插入在结点c 的右子树E 上，导致结点a 的平衡因子绝对值大于1，以结点a 为根的子树失去平衡。

【调整策略】
调整后的子树除了各结点的平衡因子绝对值不超过1，还必须是二叉排序树。由于结点c 的左子树D 可作为结点a 的右子树，将结点a 为根的子树调整为左子树是B，右子树是D，再将结点a 为根的子树调整为结点c 的左子树，结点c 为新的根结点，如图(c)。

【平衡化调整操作判定】
沿插入路径检查三个点a、c、E，若它们处于“\”直线上的同一个方向，则要作左单
旋转，即以结点c 为轴逆时针旋转。

二、右单旋转

右单旋转

右单旋转与左单旋转类似，沿插入路径检查三个点a、c、E，若它们处于“/”直线上的同一个方向，则要作右单旋转，即以结点c 为轴顺时针旋转，如图9.11 所示。

三. 先左后右双向旋转

如图9.12 为插入前的子树，根结点a 的左子树比右子树高度高1，待插入结点x 将插入到结点b 的右子树上，并使结点b 的右子树高度增1，从而使结点a 的平衡因子的绝对值大于1，导致结点a 为根的子树平衡被破坏，如图9.13(a)、9.14(d)所示。

先左后右双向旋转

沿插入路径检查三个点a、b、c，若它们呈“<”字形，需要进行先左后右双向旋转：

  • 首先，对结点b 为根的子树，以结点c 为轴，向左逆时针旋转，结点c 成为该子树的新根，如图(b、e)；
  • 由于旋转后，待插入结点x 相当于插入到结点b 为根的子树上，这样a、c、b 三点处于“/”直线上的同一个方向，则要作右单旋转，即以结点c 为轴顺时针旋转，如图(c、f)。

在平衡的二叉排序树T 上插入一个关键码为kx 的新元素，递归算法可描述如下：

  • 若T 为空树，则插入一个数据元素为kx 的新结点作为T 的根结点，树的深度增1；
  • 若kx 和T 的根结点关键码相等，则不进行插入；
  • 若kx 小于T 的根结点关键码，而且在T 的左子树中不存在与kx 有相同关键码的结点， 则将新元素插入在T 的左子树上，并且当插入之后的左子树深度增加1 时，分别就下列情况进行处理：

① T 的根结点平衡因子为-1(右子树的深度大于左子树的深度)，则将根结点的平衡因子更改为0，T 的深度不变；
② T 的根结点平衡因子为0(左、右子树的深度相等)，则将根结点的平衡因子更改为1，T 的深度增加1；
③ T 的根结点平衡因子为1(左子树的深度大于右子树的深度)，则若T 的左子树根结点的平衡因子为1，需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变；若T 的左子树根结点平衡因子为-1，需进行先左后右双向旋转平衡处理，并且在旋转处理之后，修改根结点和其左、右子树根结点的平衡因子，树的深度不变。

  • 若kx 大于T 的根结点关键码，而且在T 的右子树中不存在与kx 有相同关键码的结点，则将新元素插入在T 的右子树上，并且当插入之后的右子树深度增加1 时，分别就不同情况处理之。其处理操作和(3.) 中所述相对称，读者可自行补充整理。
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
typedef struct NODE {
	ElemType	elem;                                                   /*数据元素*/
	int		bf;                                                     /*平衡因子*/
	struct NODE	*lc, *rc;                                               /*左右子女指针*/
}NodeType;                                                                      /*结点类型*/
void R_Rotate( NodeType **p )
{                                                                               /*对以*p 指向的结点为根的子树，作右单旋转处理，处理之后，*p 指向的结点为子树的新根*/
	lp		= (*p)->lc;                                             /*lp 指向*p 左子树根结点*/
	(*p)->lc	= lp->rc;                                               /*lp 的右子树挂接*p 的左子树*/
	lp->rc		= *p; *p = lp;                                          /* *p 指向新的根结点*/
}


void L_Rotate( NodeType **p )
{                                                                               /*对以*p 指向的结点为根的子树，作左单旋转处理，处理之后，*p 指向的结点为子树的新根*/
	lp		= (*p)->rc;                                             /*lp 指向*p 右子树根结点*/
	(*p)->rc	= lp->lc;                                               /*lp 的左子树挂接*p 的右子树*/
	lp->lc		= *p; *p = lp;                                          /* *p 指向新的根结点*/
}


#define LH	1                                                               /* 左高*/
#define EH	0                                                               /* 等高*/
#define RH	1                                                               /* 右高*/
void LeftBalance ( (NodeType * *p)
		   {                                                            /*对以*p 指向的结点为根的子树，作左平衡旋转处理，处理之后，*p 指向的结点为子树的新根*/
			   lp = (*p)->lc;                                       /*lp 指向*p 左子树根结点*/
			   switch ( (*p)->bf )                                  /*检查*p 平衡度，并作相应处理*/
			   {
			   case LH:                                             /*新结点插在*p 左子女的左子树上，需作单右旋转处理*/
				   (*p)->bf = lp->bf = EH; R_Rotate( p ); break;
			   case EH:                                             /*原本左、右子树等高，因左子树增高使树增高*/
				   (*p)->bf = LH; *paller = TRUE; break;
			   case RH:                                             /*新结点插在*p 左子女的右子树上，需作先左后右双旋处理*/
				   rd = lp->rc;                                 /*rd 指向*p 左子女的右子树根结点*/
				   switch ( rd->bf )                            /*修正*p 及其左子女的平衡因子*/
				   {
				   case LH: (*p)->bf = RH; lp->bf = EH; break;
				   case EH: (*p)->bf = lp->bf = EH; break;
				   case RH: (*p)->bf = EH; lp->bf = LH; break;
				   } /*switch(rd->bf)*/
				   rd->bf = EH; L_Rotate( &( (*p)->lc) );       /*对*p 的左子树作左旋转处理*/
				   R_Rotate( p );                               /*对*t 作右旋转处理*/
			   } /*switch((*p)->bf)*/
		   } /*LeftBalance*/
		   int InsertAVL( NodeType **t, ElemType e, Boolean *taller )
		   {                                                            /*若在平衡的二叉排序树t 中不存在和e 有相同关键码的结点，则插入一个数据元素为e 的*/
/*新结点，并反回1，否则反回0。若因插入而使二叉排序树失去平衡，则作平衡旋转处理，*/
/*布尔型变量taller 反映t 长高与否*/
			   if ( !(*t) )                                         /*插入新结点，树“长高”，置taller 为TURE*/
			   {
				   *t = (NodeType *) malloc( sizeof(NodeType) ); (*T)->elem = e;
				   (*t)->lc = (*t)->rc = NULL; (*t)->bf = EH; *taller = TRUE;
			   } /*if*/
			   else{ if ( e.key == (*t)->elem.key )                 /*树中存在和e 有相同关键码的结点，不插入*/
				 {
					 taller = FALSE; return(0);
				 }
				 if ( e.key < (*t)->elem.key )
				 {                                              /*应继续在*t 的左子树上进行*/
					 if ( !InsertAVL( &( (*t)->lc) ), e, &taller )
						 ) return(0);                   /*未插入*/
					 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;
						 }
				 } /*if*/
				 else{                                          /*应继续在*t 的右子树上进行*/
					 if ( !InsertAVL( &( (*t)->rc) ), e, &taller )
						 ) return(0);                   /*未插入*/
					 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;
						 }
				 } /*else*/
			   } /*else*/
			   return(1);
		   } /*InsertAVL*/

【平衡树的查找分析】
在平衡树上进行查找的过程和二叉排序树相同，因此，在查找过程中和给定值进行比较的关键码个数不超过树的深度。那么，含有n 个关键码的平衡树的最大深度是多少呢？

为解答这个问题，我们先分析深度为h 的平衡树所具有的最少结点数。假设以Nh 表示深度为h 的平衡树中含有的最少结点数。显然，N0=0，N1=1，N2=2，并且Nh=Nh-1+Nh-2+1。这个关系和斐波那契序列极为相似。利用归纳法容易证明：当h≥0间复杂度为O(logn)。

上述对二叉排序树和二叉平衡树的查找性能的讨论都是在等概率的提前下进行的。

9.3 动态查找表—B-树和B+树

一.B-树及其查找

B-树是一种平衡的多路查找树，它在文件系统中很有用。

二.B-树的插入和删除

三. B+树

B+树是应文件系统所需而产生的一种B-树的变形树。

9.4 哈希表查找(杂凑法)—哈希表与哈希方法

前述查找法：由于数据元素的存储位置与关键码之间不存在确定的关系，因此，查找时，需要进行一系列对关键码的查找比较，即“查找算法”是建立在比较的基础上的，查找效率由比较一次缩小的查找范围决定。

哈希查找：依据关键码直接得到其对应的数据元素位置，即要求关键码与数据元素间存在一一对应关系，通过这个关系，能很快地由关键码得到对应的数据元素位置。

例9.6】11 个元素的关键码分别为18，27，1，20，22，6，10，13，41，15，25。选取关键码与元素位置间的函数为f(key)=key mod 11

  1. 通过这个函数对11 个元素建立查找表如下：

建立查找表

  1. 查找时，对给定值kx 依然通过这个函数计算出地址，再将kx 与该地址单元中元素的关键码比较，若相等，查找成功。

哈希表与哈希方法：选取某个函数，依该函数按关键码计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值kx 计算地址，将kx 与地址单元中元素关键码进行比，确定查找是否成功，这就是哈希方法(杂凑法)；哈希方法中使用的转换函数称为哈希函数(杂凑函数)；按这个思想构造的表称为哈希表(杂凑表)。

对于n 个数据元素的集合，总能找到关键码与存放地址一一对应的函数。若最大关键为m，可以分配m 个数据元素存放单元，选取函数f(key)=key 即可，但这样会造成存储空间的很大浪费，甚至不可能分配这么大的存储空间。通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突(Collision)，映射到同一哈希地址上的关键码称为同义词。可以说，冲突不可能避免，只能尽可能减少。所以，哈希方法需要解决以下两个问题：

1.构造好的哈希函数
（1）所选函数尽可能简单，以便提高转换速度。
（2）所选函数对关键码计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。

2.制定解决冲突的方案。

9.4 哈希表查找(杂凑法)—常用的哈希函数

1.直接定址法

Hash(key) = a.key + b（a，b为常数）

即取关键码的某个线性函数值为哈希地址，这类函数是一一对应函数，不会产生冲突，但要求地址集合与关键码集合大小相同，因此，对于较大的关键码集合不适用。

【例9.7】关键码集合为{100，300，500，700，800，900}，选取哈希函数为Hash(key)=key/100，则存放如下：

例9.7

2.除留余数法

Hash(key) = key mod p （p是一个整数）

即取关键码除以p 的余数作为哈希地址。使用除留余数法，选取合适的p 很重要，若哈希表表长为m，则要求p≤m，且接近m 或等于m。p 一般选取质数，也可以是不包含小于20 质因子的合数。

3.乘余取整法

Hash(key)= ⎣B(Akey mod 1)⎦ (A、B 均为常数，且0<A<1，B 为整数)以关键码key 乘以A，取其小数部分(Akey mod 1 就是取Akey 的小数部分)，之后再用整数B 乘以这个值，取结果的整数部分作为哈希地址。

该方法B 取什么值并不关键，但A 的选择却很重要，最佳的选择依赖于关键码集合的特征。一般取A= 较为理想。

4.数字分析法

设关键码集合中，每个关键码均由m 位组成，每位上可能有r 种不同的符号。
【例9.8】若关键码是4 位十进制数，则每位上可能有十个不同的数符0～9，所以r=10。
【例9.9】若关键码是仅由英文字母组成的字符串，不考虑大小写，则每位上可能有26 种不同的字母，所以r=26。

数字分析法根据r 种不同的符号，在各位上的分布情况，选取某几位，组合成哈希地址。所选的位应是各种符号在该位上出现的频率大致相同。

【例9.10】有一组关键码如下：

数字分析法

5.平方取中法

对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。

6.折叠法Folding

此方法将关键码自左到右分成位数相等的几部分，最后一部分位数可以短些，然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。这种方法称为折叠法。

有两种叠加方法：

  • 移位法── 将各部分的最后一位对齐相加。
  • 间界叠加法── 从一端向另一端沿各部分分界来回折叠后，最后一位对齐相加。

【例9.11】关键码为key=05326248725，设哈希表长为三位数，则可对关键码每三位一部分来分割。

关键码分割为如下四组： 253 463 587 05

用上述方法计算哈希地址对于位数很多的关键码，且每一位上符号分布较均匀时，可采用此方法求得哈希地址。

折叠法

9.4 哈希表查找(杂凑法)—处理冲突的方法

1.开放定址法

开放定址法：由关键码得到的哈希地址产生冲突，即改地址已存放了数据元素，则去寻找下一个空哈希地址，并存入。

下面介绍找空哈希地址的方法：

1.线性探测法

Hi=(Hash(key)+di) mod m ( 1≤i < m )
其中：
Hash(key)为哈希函数
m 为哈希表长度
di 为增量序列1，2，……，m-1，且di=i

【例9.12】关键码集为{47，7，29，11，16，92，22，8，3}，哈希表表长为11，Hash(key)=key mod 11，用线性探测法处理冲突，建表如下：

建表

2.二次探测法

Hi=(Hash(key)±di) mod m
其中：
Hash(key)为哈希函数
m 为哈希表长度，m 要求是某个4k+3 的质数(k 是整数)
di 为增量序列12，-12，22，-22，……，q2，-q2 且q≤1/2 (m-1)

仍以上例用二次探测法处理冲突，建表如下：

建表

对关键码寻找空的哈希地址只有3 这个关键码与上例不同，
Hash(3)=3，哈希地址上冲突，由
H1=(Hash(3)+12) mod 11=4 仍然冲突；
H2=(Hash(3)-12) mod 11=2 找到空的哈希地址，存入。

  1. 双哈希函数探测法
    Hi=(Hash(key)+i*ReHash(key)) mod m (i=1，2，……，m-1)
    其中：
    Hash(key)，ReHash(key)是两个哈希函数，
    m 为哈希表长度

双哈希函数探测法，先用第一个函数Hash(key)对关键码计算哈希地址，一旦产生地址冲突，再用第二个函数ReHash(key)确定移动的步长因子，最后，通过步长因子序列由探测函数寻找空的哈希地址。

比如，Hash(key)=a 时产生地址冲突，就计算ReHash(key)=b，则探测的地址序列为
H1=(a+b) mod m，H2=(a+2b) mod m，……，Hm-1=(a+(m-1)b) mod m

2. 拉链法

设哈希函数得到的哈希地址域在区间[0，m-1]上，以每个哈希地址作为一个指针，指向一个链，即分配指针数组ElemType eptr[m]；建立m 个空链表，由哈希函数对关键码转换后，映射到同一哈希地址i 的同义词均加入到eptr[i]指向的链表中。

【例9.l3】关键码序列为47,7,29,11,16,92,22,8,3,50,37,89,94,21，哈希函数为Hash(key)=key mod 11

用拉链法处理冲突，建表如图9.21。

拉链法

3. 建立一个公共溢出区

设哈希函数产生的哈希地址集为[0，m-1]，则分配两个表：
一个基本表ElemType base_tbl[m]；每个单元只能存放一个元素；
一个溢出表ElemType over_tbl[k]；只要关键码对应的哈希地址在基本表上产生冲突，则所有这样的元素一律存入该表中。查找时，对给定值kx 通过哈希函数计算出哈希地址i，先与基本表的base_tbl[i]单元比较，若相等，查找成功；否则，再到溢出表中进行查找。

9.4 哈希表查找(杂凑法)—哈希表的查找分析

哈希表的查找过程基本上和造表过程相同。一些关键码可通过哈希函数转换的地址直接找到，另一些关键码在哈希函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对哈希表查找效率的量度，依然用平均查找长度来衡量。

查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：

  • 哈希函数是否均匀
  • 处理冲突的方法
  • 哈希表的装填因子

分析这三个因素，尽管哈希函数的“好坏”直接影响冲突产生的频度，但一般情况下，我们总认为所选的哈希函数是“均匀的”，因此，可不考虑哈希函数对平均查找长度的影响。

就线性探测法和二次探测法处理冲突的例子看，相同的关键码集合、同样的哈希函数，但在数据元素查找等概率情况下，它们的平均查找长度却不同：

线性探测法的平均查找长度ASL=(5×1+3×2+1×4)/9=5/3
二次探测法的平均查找长度ASL=(5×1+3×2+1×2)/9=13/9

哈希表装填因子

α是哈希表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。

实际上，哈希表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。以下给出几种不同处理冲突方法的平均查找长度：

ASL

哈希方法存取速度快，也较节省空间，静态查找、动态查找均适用，但由于存取是随机的，因此，不便于顺序查找。

Thanks!