第8章 查找 8.1 静态查找表 8.2 动态查找表 8.3 哈希表

动态查找表 静态查找表 平均查找长度ASL(Average search length) Pi=1/n(1≤i≤n)

8.1 静态查找表 顺序查找、二分查找和分块查找 typedef int keytype; typedef struct { keytype key; /* 关键字域 */ 　datatype others; /* 其他数据项，读者可根据需要自行定义 */ }elemtype; /* 查找表中数据元素类型 */ { elemtype *elem; /* 顺序表基地址 */ int length; /* 顺序表长度 */ }stable; /* 查找表类型 */

8.1.1 顺序查找 查找过程为：从表的一端开始，依次将表中元素关键字和给定的值key比较，如果表中某个记录的关键字值与给定值相等，则查找成功；若到表的另一端后，仍然没有找到关键字与给定值相等的记录，则查找失败。

顺序查找的一般算法如下： int seqsearch1(stable ST,keytype key) { int i; for(i=ST.length;i>0;i--) if(ST.elem[i].key==key) return i; return 0; }

改进后的顺序查找算法如下： int seqsearch2(Stable ST,keytype key) { int i; ST.elem[0].key=key; /* 设置监视哨 */ for(i=ST.length;ST.elem[i].key!=key;i--); /* 循环体为空 */ return i; }

从顺序查找过程可见，平均查找长度公式中的Ci 取决于被查找的记录在表中的位置。 如查找表中最后一个记录时，只需比较一次； 而查找表中第一个记录时，需比较n次 一般情况下Ci 等于n-i+1。这里设n=ST.length，则顺序查找的平均查找长度为 ASL=nP1+(n-1)P2+...+Pn

假设每个记录的查找概率相等，即Pi=1/n，则在等概率情况下顺序查找成功时的平均查找长度为

为简化运算，假如设查找成功和不成功的概率相同，则查找成功时的概率为Pi=1/2n，查找失败时的概率为1/2。所以顺序查找的平均查找长度为

顺序查找的优点: 算法简单且适用面广，对查找表的结构无任何要求。无论是用顺序表还是用链表来存放记录，也无论记录之间是否按关键字已排序，都可以使用这种查找方法。 顺序查找的缺点: 查找效率低，尤其是不适合于表内元素较多时查找。

8.1.2 二分查找--折半查找 基本思想：在有序(以升序为例)顺序表中确定当前待查记录所在的范围(区间)，设区间范围为[low ..high]，首先确定该区间的中点位置mid=(low+high)/2；然后让待查值key 与查找表中元素的关键字值ST.elem[mid].key比较，若相等，则查找成功，返回下标mid值，否则，要根据比较结果缩小查找区间，当key<ST.elem[mid].key则待查找值必在区间[low ..mid-1]，即原表的左半区中，否则，则待查找值必在区间[mid+1..high]，即原表的右右半区中。下一次的查找应是在确定的区间内重复上面的过程，直到找到返回下标mid ，或者没找到，即当前查找区间为空(low>high)，返回0下标。

二分查找算法如下： int binsearch(stable ST,keytype key) { int low=1,high=ST.length,mid; while(low<=high) { mid=(low+high)/2; if(ST.elem[mid].key==key) return mid; if(key<ST.elem[mid].key) high=mid-1; else low=mid+1; } return 0;

1 2 3 4 5 6 7 8 9 10 11 例 5 13 19 21 37 56 64 75 80 88 92 找21 low high mid

1 2 3 4 5 6 7 8 9 10 11 例 5 13 19 21 37 56 64 75 80 88 92 找21 low mid high

1 2 3 4 5 6 7 8 9 10 11 例 5 13 19 21 37 56 64 75 80 88 92 找21 low high mid 查找成功

1 2 3 4 5 6 7 8 9 10 11 例 5 13 19 21 37 56 64 75 80 88 92 找70 low high mid

1 2 3 4 5 6 7 8 9 10 11 例 5 13 19 21 37 56 64 75 80 88 92 找70 low mid high

1 2 3 4 5 6 7 8 9 10 11 例 5 13 19 21 37 56 64 75 80 88 92 找70 low high mid

1 2 3 4 5 6 7 8 9 10 11 例 5 13 19 21 37 56 64 75 80 88 92 找70 low high mid

1 2 3 4 5 6 7 8 9 10 11 例 5 13 19 21 37 56 64 75 80 88 92 找70 high low 查找失败

由以上二分查找的思想可知，只有查找表中记录按关键字有序时，才能确定下一次查找的范围是左半区还是右半区 在算法描述中，表中记录是按关键字递增有序的，若查找表中记录是按关键字递减有序的，只需将算法中的比较运算符“<”换成“>”即可

二分查找的过程还可以用一棵二叉树来描述，树中每个结点为表中的一个记录，结点中的值为此记录在表中的下标值(或关键字值)。我们把当前查找区间的中间位置作为二叉树的根，则左半区中的记录即为左子树，而右半区中的记录则为右子树。依此类推，得到的二叉树，称之为描述二分查找过程的二分查找判定树。判定树的形态只与表中记录个数n有关，而与表中的元素值无关。假定n=11，则判定树形态如图6.1所示。

图8.1 ST.elem[1..11]表的二分查找判定树(n=11) 1～2 <1 10～11 2～3 9～10 6～7 3～4 8～9 7～8 5～6 4～5 >11 11 1 2 3 4 5 10 8 9 7 6

图中方形结点表示查找失败时的外部结点，“i～j”表示被查找值介于ST.elem[i].key和ST.elem[j].key之间。 思考 键字比较次数 : 查找成功时? 查找失败时? 若记录的总数为n，则二分查找判定树的高度为log2n+1(不包括外部记录结点)。树中第i层上的记录数为2i-1，查找该层上的每个记录需要进行i次比较。

由此，在等概率条件下，二分查找成功时的平均查找长度为 二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最好情况下查找成功的比较次数也不超过判定树的深度(含外部结点) log2n+2。因此，二分查找的平均性能其最好情况与最坏情况相近。

二分查找的效率较高，但它要求查找表要按顺序存储，且按关键字有序。排序本身是一种很费时的运算，一般采用最高效的排序方法也要花费O(nlog2n)的时间。 顺序存储结构，不适合经常作插入和删除操作。 因此，二分查找特别适合于那些一经建立就很少改动、而又经常需要查找的顺序表。

(1)查找给定值为37的元素，依次与表中73，25，49，37元素比较。 【例8.1】给定13个数据元素的有序顺序表(1,13,25,37,49,61,73,84,96,108,110,125, 130),采用折半查找方法,则:(1)查找给定值为37的元素,将依次与表中哪些元素比较?(2)查找给定值为82的元素,将依次与哪些元素比较?(3)在等概率情况下,计算查找成功时的平均查找长度。 (1)查找给定值为37的元素，依次与表中73，25，49，37元素比较。 (2)查找给定值为82的元素，依次与表中73，108，84元素比较。 (3)等概率情况下，成功时的平均查找长度

110 108 125 130 例8.1图 73 25 1 84 49 13 37 61 96

8.1.3 分块查找--索引顺序查找 线性表内元素按如下索引方式存储：将表ST.elem[1..n](n=ST.length)平均分为b 块，前b-1 块中每块的记录个数为s, 第b块中的记录数小于等于s；每一块中的记录不一定按关键字有序，但前一块中的最大关键字必须小于其后块中的最小关键字，即表是分块有序的。将各块中最大关键字及其起始位置构成一个索引表，记作Idx[1..b]，其中，Idx[i](1≤i≤b)中存放着第i块的最大关键字及该块在表ST中的起始位置。由于表ST是分块有序的，所以索引表是一个递增有序表。

分块查找的算法思想：首先在索引表用折半查找(因索引表为递增有序)或顺序查找方法，确定待查记录所在的块，然后在已确定的块中进行顺序查找(因块内无序)。 采用折半查找索引表的分块查找算法如下: Idxsearch(Idx I,int s,Stable ST,KeyType key) { int low=1,high=s,mid,i; /* s为索引表中元素个数即原表块数 */ int b=ST.length/s; /* b为每块中元素数 */ while(low<=high) { mid=(low+high)/2; if(I[mid].key>=key) high=mid-1; else low=mid+1; } if(low>s) return 0; /* low为key所对应记录可能在的块的入口 */ for(i=I[low].link;i<=I[low].link+b-1&&ST.elem[i].key!=key;i++); if(i<=I[low].link+b-1) return i; /* 找到，返回key所在下标 */ else reutrn 0; /* 未找到，返回0 */

平均查找长度是两次查找过程的平均查找长度之和。 如果以折半查找来确定块，那么分块查找成功时的平均查找长度为： ASL=ASL分块+ASL顺序=log2(b+1)-1+(s+1)/2≈log2(n/s+1)+s/2 如果用顺序查找来确定块，那么分块查找成功时的平均查找长度为： ASL=ASL分块+ASL顺序=(b+1)/2+(s+1)/2=(s2+2s+n)/2s So当s=时，ASL取最小值+1。因此，当采用顺序查找确定块时，应将各块中的记录数(b)设为。

分块查找的优点是：可以将欲查找的记录范围限定在整个数据表中的一小段区间内，节省了平均查找时间，比较适合于对大批量的数据进行查找的过程。 缺点是：查找过程较为繁琐，需要一个存放索引表的辅助数组空间，并要对整个查找表进行初始分块排序的处理。

【例8．2】对于有196个元素的文件，如果采用分块查找的方法查找元素，应分为几块？每块的最佳长度为多少个元素？若索引表采用顺序查找法查找，分块查找的平均查找长度为多少？若索引表采用折半查找法查找，分块查找的平均查找长度是多少？假若设每块长度为9，则总共会为多少块？ 【解】对于有196个元素的文件，如果采用分块查找的方法查找元素，应分为14块，每块的最佳长度为14个元素。 假若块内采用顺序查找方法，平均查找长度为：ASL=1(b+s)/2+1=16.5 假若块内采用折半查找方法，平均查找长度为：ASL=log2(b+1)-1+s/2=9.01 假若每块长度为9，则总共应有b=196/9 =22块。

8.2 动态查找表 上一节介绍的三种查找方法的特点是在查找过程中对找到的元素可以读取其属性，更新其值，一般不对查找表进行插入和删除元素操作，所以，常采用静态查找表作为存储结构。如果在查找过程中还要进行插入和删除操作，则采用动态查找表作存储结构。动态查找表的表结构是在查找过程中动态生成的，如果被查找的值与查找表中记录的关键字值相等，则可能要进行删除操作，否则可能要进行插入操作。通常以树或二叉树作为动态查找表的组织形式 .

8.2.1 二叉排序树(Binary Sort Tree,简称BST)--二叉查找树 定义为: 二叉排序树或者是空树，或者是满足以下条件的二叉树: (1)若它的左子树不空，则左子树上所有记录的关键字值均小于根记录关键字的值。 (2)若它的右子树不空，则右子树上所有记录的关键字值均大于根记录关键字的值。 (3)它的左、右子树本身也是二叉排序树。

图8.3 二叉排序树示例 January May November October December September July August June April March February 12 2 16 1 8 15 30 4 10 28 20

结点类型定义如下： #include "stdio.h" typedef int keytype; typedef struct node { keytype data; struct node *left,*right; }bitnode,*bitree;

1.二叉排序树的查找 在二叉排序树上进行查，是一个从根结点开始，沿某一个分支逐层向下进行比较判断是否相等的过程。 即，当二叉排序树不空时，首先将给定值和根结点关键字值比较，若相等，则查找成功，带回其双亲结点或自身的地址；否则，根据给定值与根结点关键字之间的大小关系，分别在左子树或右子树上继续进行查找，直到左子树或右子树空为止，此时查找失败，带回空值。具体算法如下：

查找70 具有n个结点的二叉排序树的平均检索 长度为O(log2n),和二叉树的形态有关 80 60 120 110 150 55 70 53 void searchbst(bitree T,bitree *F,bitree *C,keytype key) {while(T!=NULL) if(T->data==key) { *C=T;break;} else if(key<T->data) { *F=T;T=T->left;} else { *F=T;T=T->right;} } 查找成功 具有n个结点的二叉排序树的平均检索 长度为O(log2n),和二叉树的形态有关

2.二叉排序树的插入 算法思路为： ① 在插入之前，先使用查找算法在树中检查要插入的元素是否存在。 ② 搜索成功: 树中已有这个元素，不再插入，可能会作删除操作。 ③ 搜索失败: 树中没有关键字值等于给定值的结点，将新元素接入到查找停止处。

int insertbst(bitree *T,keytype key) { bitree F=NULL,C=NULL,s; searchbst(*T,&F,&C,key); /* T为二级指针，存储根结点地址的指针，*/ if(C!=NULL) return 0; /* 查找算法只需要根结点的地址，所以search */ s=(bitree)malloc(sizeof(bitnode)); /* 函数的第一个参数形式为*T */ s->data=key; s->left=s->right=NULL; if(F==NULL) *T=s; /* 插入结点为根结点 */ else if(key<F->data) F->left=s; /* 接入新结点 */ else F->right=s; return 1; }

3.二叉排序树的创建 二叉排序树是一种动态树，树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字值等于待查值的结点时，将查找的值作为一个新结点添加到排序树中去。由此可以创建一棵二叉排序树。即从空树开始建树，输入序列以输入一个结束标志值结束。这个值应当取不可能在输入序列中出现的值，例如输入序列的值都是正整数时，取标志值为0或负数。

void creatbst(bitree *T) /* 根结点的初值为空 */ { KeyType key;*T=NULL; scanf("%d",&key); while(key!=-1) /* 设-1为输入数据结束标志 */ { insertbst(T,key); }

4.二叉排序树的删除 其删除过程为：先查找被删除的结点是否存在，若不存在，则算法结束，否则按以下原则删除(见图8.4)： ① 删除叶子结点，只需将其双亲结点中指向它的指针置空，再释放它即可。 ② 被删结点无右子树，可以拿它的左孩子结点顶替它的位置，再释放它。 ③ 被删结点无左子树，可以拿它的右孩子结点顶替它的位置，再释放它。 ④ 被删结点同时有左子树和右子树，可采用以下两种方法处理：

I．先找到被删结点的左子树的最右下结点(右子树为空的结点)，记作S。将被删结点的右子树作为S的右子树，然后用被删结点的左子树顶替被删结点；反之也可以先找到被删结点的右子树的最左下结点(左子树为空的结点)，记作S，将被删结点的左子树作为S的左子树，然后用被删结点的右子树顶替被删结点。 II．先找到被删结点的左子树的最右结点(右子树为空)，记作S，将被删结点值用S结点值替代。因S只有左子树，所以只须将S的左子树作为S的双亲结点的右子树。当S正好是被删结点的左孩子时，则将S的左子树作被删结点的左子树(下面的算法用此方法)。 ⑤ 删除根结点，与(4)情况相同，只是需要返回新根结点的地址。

(a) 无左子树，用右子树替换 (b) 无右子树，用左子树替换 (c) 左右子树都存在时，用左子树的最右下结点替换被删结点 8.4 二叉排序树的删除 53 17 87 9 98 85 82 84 68 80 94 65 88 删除88 (c) 78 23 删除78 (a) 48 59 删除48

int deletebst(bitree *T,keytype key) { bitree F=NULL,P=NULL,S,Q; searchbst(*T,&F,&P,key); if(!P) { printf("被删结点不存在");return 0;} if(P->left==NULL) /* 左子树空，则重接其右子树 */ { Q=P;P=P->right;} else if(P->right==NULL) /* 右子树空，则重接其左子树 */ { Q=P;P=P->left;} else /* 左右子树都不空 */ { Q=P;S=P->left; while(S->right!=NULL) { Q=S;S=S->right;} /* 找到P的左子树的最右下结点S */ if(Q!=P) Q->right=S->left; /* 重接Q的右子树 */ else Q->left=S->left; /* 重接Q的左子树 */ Q=S;P->data=S->data; /* 用S 结点的值替换P结点的值 */ }

if(F==NULL) *T=P; /* 若被删结点为根结点，则将P改为根结点 */ else if(Q!=S)/* 对于左子树为空或右子树为空的结点P与其双亲结点重新链接 */ if(key<F->data) F->left=P; else F->right=P; free(Q); }

5.二叉排序树的查找分析 若查找成功，则是从根记录出发到待查记录的路径；若查找不成功，则是从根出发到某个叶子结点的路径。所以与二分查找类似，和关键字比较的次数不超过树的深度。 但是二分查找判定树的形态是惟一的，与关键字值的顺序无关，而含有n个记录的二叉排序树的形态却不惟一，相应的深度也不一样，甚至可能差别很大。

例 ASL=(1+2+3+4+5)/5=3 ASL=(1+2*2+3*2)/5=2.2 最佳二叉排序树 定义：平均检索长度最小的二叉排序树 构造方法：平分法 例 用1，2，3，4，5，6，7，8，9构造最佳二叉排序树 5 2 7 ASL=(1+2*2+3*4+4*2)/9=25/9 1 3 6 8 9 4

例如：由关键字序列 1、2、3、4、5构造而得的二叉排序树，如图8 例如：由关键字序列 1、2、3、4、5构造而得的二叉排序树，如图8.5(a)所示。则其等概率下的平均查找长度为：ASL=(1+2+3+4+5)/5=3，而由关键字序列3、1、2、5、4构造而得的二叉排序树如图8.5 (b)所示，则其等概率下的平均查找长度为: ASL=(1×1+2×2+3×2)/5=2.2。 图8.5 不同形态的二叉树 (a) (b) 3 1 5 2 4

二叉树实际为一棵深度接近n的单支树，它的平均查找长度与单链表的顺序查找长度相同即(n+1)/2。而在最好情况时，在二叉排序树生成的过程中，构成的树的形态左右比较平衡，即树形状接近于一棵二分查找判定树时，其平均查找长度大约是log2n+1。在二叉排序树上进行查找时的平均查找长度与二叉排序树的形态有关。最坏情况时为n个关键字已基本有序，此时所得到的

【例8．3】对于一组关键字的集合1(73,25,1,13,108,49,37,61,84,96,125,110,130)及同一组关键字，不同顺序构成的集合2(73,13,1,49,61,25,37,110,84,108,96,125,130),分别在空树的基础上按表中元素顺序创建各自的二叉排序树，画出这两棵二叉排序树，并分别计算在等概率条件下查找成功时的平均查找长度。

集合1图 73 25 1 13 49 37 61 84 96 110 108 125 130 集合2图 图8.6 例8.3中的二叉排序树

【解】得到的二叉排序树如图8.6所示，其中各自的平均查找长度分别为： 　　　ASL1= =3.154 ASL2

8.2.2 平衡二叉树 图8.7 平衡及不平衡二叉树 (a) (b) 3 1 5 2 4

平衡二叉排序树 结点平衡因子＝右子树高度－左子树高度 定义:AVL,任一结点的平衡因子只可能取-1,0,+1 优点：总能保持检索长度为O(log2n) 1 -1 30 20 60 40 70 10 50 2 -1 30 60 40

一棵平衡二叉树中每个结点的平衡因子取值只能为-1、0和1 三种可能 ? 当向一棵平衡二叉树中插入一个新结点时，对于那些插入新结点后左右子树高度不变的结点不会影响其平衡因子，而那些插入新结点后，左或右子树的高度增加1 ，就会影响到这些结点的平衡因子，这时需要调整这些结点的位置使之保持平衡。具体根据插入位置有以下三种情况：

1.若某结点在新结点插入前满足HL-H R=0，即平衡因子为0，插入新结点后将使该结点平衡因子的绝对值变为1，但仍满足平衡二叉树的要求，不需要对它们进行调整。 2.若某结点在新结点插入前满足HL-H R=1，即平衡因子为1，但新结点插入在其右子树上；或在新结点插入前满足HL-H R=-1，即平衡因子为-1，但新结点插入在其左子树上。以上两种情况都将使此结点的平衡因子变为0，平衡情况得到改善，因此也不需要进行调整。

3.若某结点在新结点插入前左右子树高度之差为1或-1，即平衡因子绝对值为1，插入新结点后若使平衡因子绝对值变为2 ，则破坏了平衡二叉树的特性，需要对这些结点进行调整，使二叉树中的所有结点都重新满足平衡二叉树的要求，如图8.8所示。 由8.8图可以看出插入新结点后破坏二叉排序树失平衡的情况有以下四种： ① LL型：在某结点的左孩子结点的左子树上插入一个新结点使得该结点失去平衡。 ② RR型：在某结点的右孩子结点的右子树上插入一个新结点使得该结点失去平衡。 ③ LR型：在某结点的左孩子结点的右子树上插入一个新结点使得该结点失去平衡。(a)552025202520119201115201120112120252320252–1–21–1–2(b)(c)(d)(a) LL型 　　(b) RR型 　　 (c) LR型 　　 (d)RL型 图8.8 平衡因子从1变为2或从-1变为-2 ④ RL型：在某结点的右孩子结点的左子树上插入一个新结点使得该结点失去平衡。

(a) LL型 (b) RR型 (c) LR型 (d)RL型 55 20 25 11 9 15 2 1 23 –1 –2 (b) (c) (d) (a) LL型 　　(b) RR型 　　 (c) LR型 　　 (d)RL型 图8.8 平衡因子从1变为2或从-1变为-2

(a) LL型 (b) RR型 (c) LR型 (d) RL型 -1 -2 图8.9 不同类型二叉排序树的平衡调整过程 (a) LL型 (b) RR型 (c) LR型 (d) RL型 BL h A B AR BR 2 1 AL (b) (c) h+1 C CR CL (d)

① LL型调整：在平衡因子为1的结点A的左孩子结点B的左子树上插入新结点，使得该结点的平衡因子从1变为2失去平衡。这种情况的调整方法为：单向右旋平衡。即，将A的左孩子结点B向右上旋转代替A成为A子树的根结点，A结点被旋转下来成为B的右子树的根结点，而B的原右子树则成为A结点的左子树，A结点原有的右子树依然保留。因调整前后对应的中序遍历序列相同，所以调整后仍保持了二叉排序树的性质不变。如图8.9(a)所示。

② RR型调整：在平衡因子为-1的结点A的右孩子结点B的右子树上插入新结点，使得该结点的平衡因子从-1变为-2失去平衡。这种情况的调整方法为：单向左旋平衡。即，将A的右孩子B向左上旋转代替A成为A子树的根结点，A结点被旋转下来成为B的左子树的根结点，而B的原左子树则成为A结点的右子树，A结点原有的左子树依然保留。因调整前后对应的中序遍历序列相同，所以调整后仍保持了二叉排序树的性质不变。如图8.9(b)所示。

③ LR型调整：在平衡因子为1的结点A的左孩子结点B的右子树上插入新结点，使得该结点的平衡因子从1变为2失去平衡。这种情况的调整方法为：先左旋转后右旋转平衡。也就是先将A结点的左孩子结点B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把C结点向右上旋转提升到A结点的位置。C结点原有的左子树成为B结点的右子树，C结点原有的右子树成为A结点的左子树。因调整前后对应的中序遍历序列相同，所以调整后仍保持了二叉排序树的性质不变。如图8.9(c)所示。

④ RL型调整：在平衡因子为-1的结点A的右孩子结点B的左子树上插入新结点，使得该结点的平衡因子从-1变为-2失去平衡。这种情况的调整方法为：先右旋转后左旋转平衡。也就是先将A结点的右孩子结点B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把C结点向左上旋转提升到A结点的位置。C结点原有的右子树成为B结点的左子树，C结点原有的左子树成为A结点的右子树。因调整前后对应的中序遍历序列相同，所以调整后仍保持了二叉排序树的性质不变。如图8.9(d)所示。

在平衡的二叉排序树上插入一个新的数据元素key的递归算法思想为： 3)若key的关键字小于平衡二叉排序树的根结点的关键字，并且在平衡二叉排序树的左子树中不存在与关键字key相同的结点，那么将在平衡二叉排序树的左子树上插入以key为关键字的结点，当插入之后的左子树深度增加1 时，按以下不同情况进行旋转处理：

b) 平衡二叉排序树的根结点的平衡因子为0时，将根结点的平衡因子更改为1，平衡二叉排序树的深度增1。 a) 平衡二叉排序树的根结点的平衡因子为-1时，将根结点的平衡因子更改为0，平衡二叉排序树的深度不变。 b) 平衡二叉排序树的根结点的平衡因子为0时，将根结点的平衡因子更改为1，平衡二叉排序树的深度增1。 c) 平衡二叉排序树的根结点的平衡因子为1 时：

I)左子树根结点的平衡因子为1：先进行单向右旋转平衡处理，然后把根结点和其右子树根结点的平衡因子改为0，树的深度不变。 II)左子树根结点的平衡因子为-1：先进行单向左旋转，再进行单向右旋转，并且在旋转处理之后，将根结点及其左、右子树根结点的平衡因子改为0，树的深度不变。

a) 平衡二叉排序树的根结点的平衡因子为1时：将根结点的平衡因子更改为0，平衡二叉排序树的深度不变。 4)若key的值大于平衡二叉排序树的根结点的关键字，并且在平衡二叉排序树的右子树中不存在与关键字key相同的结点，那么将在平衡二叉排序树的右子树上插入以key为关键字的结点，当插入之后的右子树深度增加1 时，按以下不同情况进行旋转处理： a) 平衡二叉排序树的根结点的平衡因子为1时：将根结点的平衡因子更改为0，平衡二叉排序树的深度不变。 b) 平衡二叉排序树的根结点的平衡因子为0时，将根结点的平衡因子更改为-1，平衡二叉排序树的深度增1。 c) 平衡二叉排序树的根结点的平衡因子为-1 时：

I)右子树根结点的平衡因子为-1：先进行单向左旋转平衡处理，然后把根结点和其右子树根结点的平衡因子改为0，树的深度不变。 II)右子树根结点的平衡因子为1：先进行单向右旋转，再进行单向左旋转，并且在旋转处理之后，修改根结点以及其左、右子树根结点的平衡因子，树的深度不变。

构造：动态平衡技术 最小不平衡子树：以离插入点最近且平衡因子绝对值大于1的结点为根的子树 左调整与右调整 Ki -2 -1 Kj h T2 h+1 T1 T3 Ki Kj h T3 h+1 T1 T2 (a) Ks Ki -2 1 Kj Ks Ki Kj (b)

-1 Ks Ki -2 1 Kj h T1 T2 T4 h-1 T3 Ks Ki 1 Kj h T1 T2 T4 h-1 T3 (c) 1 Ks Ki -2 Kj h T1 T3 T4 h-1 T2 Ks Ki -1 Kj h T1 T3 T4 h-1 T2 (d)

例 用（9，8，7，5，3，6）构造平衡二叉排序树 9 7 -2 8 5 -1 3 9 -1 8 9 -2 8 -1 7 9 7 8 9 7 7 -2 8 5 -1 3 9 -1 8 9 -2 8 -1 7 9 7 8 9 7 -1 8 5 9 (a) (a) 9 7 -1 8 -2 5 1 3 6 9 7 8 -1 5 3 8 1 6 7 5 3 9 (c)

二叉排序树的结构类型定义为： typedef int keytype; typedef struct node { keytype key; int bf; /* 结点的平衡因子 */ struct node *left,*right; /* 结点的左右子树指针 */ }bitnode,*bitree; #define LH +1 /* 左子树高于右子树 */ #define EH 0 /* 左子树与右子树等高 */ #define RH –1 /* 左子树低于右子树 */

void L_Rotate(bitree *TT) { bitree rc; rc=(*TT)->right; /* rc指向*TT的右子树的根结点 */ (*TT)->right=rc->left; /* rc的左子树连接成为原根结点的右子树 */ rc->left=(*TT); (*TT)=rc; /* *TT指向新的根结点 */ }

void R_Rotate(bitree *TT) { bitree lc; lc=(*TT)->left; /* lc 指向*TT的左子树的根结点 */ (*TT)->left=lc->right; /* lc 的右子树连接成为原根结点的左子树 */ lc->right=(*TT); /* *TT 指向新的根结点 */ (*TT)=lc; }

void leftbala(bitree *TT) { bitree lc,rd; lc=(*TT)->left; switch(lc->bf) { case LH:(*TT)->bf=lc->bf=EH; R_Rotate(&(*TT)); /* 新结点插入在以*TT为根结点的左 */ break; /* 孩子的左子树上，需作右旋处理。 LL型 */ case RH:rd=lc->right; switch(rd->bf) { case LH:(*TT)->bf=RH;lc->bf=EH; break; case EH:(*TT)->bf=lc->bf=EH; break; case RH:(*TT)->bf=EH; lc->bf=LH; break; } rd->bf=EH; /* 新结点插入在以*TT为根结点的左 */ L_Rotate(&(*TT)->left); /* 孩子的右子树上，为LR型，先左旋 */ R_Rotate(&(*TT)); /* 后右旋 */

void rightbala(bitree *TT) { bitree rc,ld; rc=(*TT)->right; switch(rc->bf) { case RH:(*TT)->bf=rc->bf=EH; L_Rotate(&(*TT)); break; case LH:ld=rc->right; switch(ld->bf) { case LH: (*TT)->bf=RH;rc->bf=EH;break; case EH:(*TT)->bf=rc->bf=EH;break; case RH:(*TT)->bf=EH;rc->bf=LH;break; } ld->bf=EH; R_Rotate(&(*TT)->right); L_Rotate(&(*TT));

Insert(bitree *TT,int key,int *taller) { if(!(*TT)) { (*TT)=(bitree)malloc(sizeof(bitree)); (*TT)->left=(*TT)->right=NULL;(*TT)->bf=EH;*taller=1; (*TT)->data=key; } else { if(key==(*TT)->data){ *taller=0; return 0;} if(key<(*TT)->data) { if(!Insert(&(*TT)->left,key,taller)) return 0; if(*taller) switch((*TT)->bf) { case LH:leftbala(&(*TT)); *taller=0;break; case EH:(*TT)->bf=LH;*taller=1;break; case RH:(*TT)->bf=EH;*taller=0;break;

else { if(!Insert(&(*TT)->right,key,taller)) return 0; if(*taller) switch((*TT)->bf) { case LH:(*TT)->bf=EH;*taller=0;break; case EH:(*TT)->bf=RH;*taller=1;break; case RH:rightbala(&(*TT)); *taller=0;break; } return 1;

void look(bitree root) { if(root) { look(root->left); printf("%d ",root->data); look(root->right); }

平衡二叉排序树的查找分析： 在平衡二叉排序树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡二叉排序树的深度。可以证明，含有n个结点的平衡二叉排序树的最大深度为O(log2n)，因此平衡二叉排序树的平均查找长度也为O(log2n)。

一棵m阶的B_树或者是一棵空树，或者是满足以下要求的m叉树： ① 树中每个结点的度最大为m 。 8.2.3 B_树与B+树 1.B_树 B_树的度 一棵m阶的B_树或者是一棵空树，或者是满足以下要求的m叉树： ① 树中每个结点的度最大为m 。 ② 除根结点和叶子为外，其他结点的度至少为m/2。 ③ 若根结点不是叶结点，则根结点的度至少为2 。 ④ 每个结点的结构为

n p0 k1 p1 k2 p2 ... kn pn 是该结点的关键字，结点内关键字按升序排列,即k1<k2<…<kn；pi(0≦i≦n)是该结点的孩子结点指针，且pi所指结点上的关键字值都大于ki且小于等于ki+1，pn所指结点的关键字值均大于kn。其中，n为该结点中的关键字个数，除根结点外,其他结点满足n≧m/2-1且n≦m-1； ki(1≦i≦n) ⑤ 所有结点的平衡因子均为0。

1 50 图8.10 一棵5阶B_树 1 16 2 72 86 9 ^ 2 4 30 53 3 20 61 2 55 1 73

B_树的查找过程为： 先从根结点出发，沿指针搜索结点，再从结点内进行顺序(或折半)查找，两个过程交叉进行。若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置；若查找失败，则返回插入位置。

B_树的插入过程为：首先查找待插入记录在树中存在否，若查找不成功则需进行插入。显然，关键字插入的位置必定在最下层的结点上，有下列几种情况： ① 插入结点后，该结点的关键字个数n<m，不修改指针；如图8.11中所示的插入60。 ② 插入结点后，该结点的关键字个数n=m，则需进行“结点分裂”，令s=m/2在原结点中保留(p0,k1,...,Ks-1,ps-1)；建新结点(ps,ks+1,...,kn,pn)；将(ks,p)插入双亲结点；如图8.11所示插入90。如若双亲为空，则建新的根结点。例如8.11图中所示插入30后。

50 20 40 90 60 80 80 50 80 60 20 40 30 30 50 80 20 40 图8.11 向3阶B_树插入60,90,30的调整过程

B_树的删除过程为： 与插入的过程相反，首先必须找到待删关键字所在结点，查找成功才可删除，并且要求删除之后，结点中关键字的个数不能小于m/2 ,否则，要从其左(或右)兄弟结点“借调”关键字，若其左(或右)兄弟结点均无关键字可借(结点中只有最少量的关键字)，则必须进行结点的“合并”。

B_树查找性能的分析: 在B_树中进行查找时，其查找时间主要花费在查找结点(或者访问外存)上，即主要取决于B_树的深度。在含N个关键字的B_树上进行一次查找，需访问的结点个数不超过: logm/2((n+1)/2)+1

2. B+树 结点中含有n个关键字和n个指向记录的指针；并且，所有叶子结点彼此链接构成一个有序链表，其头指针指向含最小关键字的结点；每个非叶子结点中的关键字Ki即为其相应指针Pi所指向的子树中关键字的最大值；所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于m/2和每个叶子m 之间。

root 50 96 · · 62 78 96 · · · 15 50 3 8 15 · · · 84 89 96 71 78 56 62 · · 20 26 43 50 · · · · 图8.12 B+树 p

B+树的查找过程为： 在B+树上，既可以进行缩小范围的查找，也可以进行顺序查找；在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束；若在结点内查找时，给定值小于等于Ki， 则应继续在这Pi所指向的子树中进行查找。 B+树的插入和删除操作与B_树上的插入和删除操作类似，必要时，也需要进行结点的“分裂”或“合并”。

图8.13 由数字构成的键树 1 6 2 $ 8a 3 8 4 5 7 9

8.2.4 键树---数字查找树 键树的结构特点是：关键字中的各个符号分布在从根结点到叶子结点的路径上，叶子结点内的符号为“结束”的标志符。键树被设定为是一棵有序树，即同一层中兄弟结点之间自左至右按升序排序，并规定结束符“$”小于任何其他符号。 So键树的深度和关键字集合的大小无关。

键树一般有以下两种存储结构。 ① 双链树：以二叉链表作存储结构实现的键树即孩子兄弟表示方法，如图8.14所示 ② Trie树：以多重链表作存储结构实现的键树，如图8.15所示。

图8.14 双链表存储的键树 ... ∧ H 含关键字的记录 HAD HE HER HERE HIGH HIS 叶结点 分支结点 A D $ E I S G R root

叶子结点 指向记录 的指针 图8.15 多重链表存储的Trie树 8(H) 0 1(A) 3 4 5(E) 9(I) 26 ∧ 4(D) 19(S) 22(V) 0 18(R) 7(G) 19(S) HAD HAS HAVE HE HIS HIGH 叶子结点 0 5(E) HER HERE root 指向记录 的指针

因此，用这类方法表示的查找表，其平均查找长度都不为零，不同的查找方法差别仅在于和给定值进行比较的关键字的顺序不同。 8.3哈希表 8.3.1 哈希表的定义 纵观以上两节讨论的表示查找表的各种结构，有一个共同点：记录在表中的位置和它的关键字之间不存在一个确定的关系，因此，查找的过程是通过给定值和关键字集合中关键字进行比较来实现的，查找的效率主要取决于和给定值进行比较的关键字个数。 因此，用这类方法表示的查找表，其平均查找长度都不为零，不同的查找方法差别仅在于和给定值进行比较的关键字的顺序不同。

对于动态查找表而言：1)表长不确定；2)在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。 因此，在一般情况下需要在关键字集和地址集之间建立一个映射关系，以H(key)作为关键字为key的记录在表中的位置，通常称这个函数H(key)为哈希函数。这个函数并不一定是数学函数。

例如，设哈希函数为：H(key)=(ASC(第一字母)-ASC(‘A’)+1)/2，对于图8 例如，设哈希函数为：H(key)=(ASC(第一字母)-ASC(‘A’)+1)/2，对于图8.16(a)中的关键字序列构造表长为13的哈希表，结果如图8.16(b)所示。 1 Chen 2 Dei 3 4 Han 5 6 Li 7 8 Qian 9 Sun 10 11 Wu 12 Ye 13 Zhao Zhao (90-65+1)/2 13 Qian (81-65+1)/2 8 Sun (83-65+1)/2 9 Li (76-65+1)/2 6 Wu (87-65+1)/2 11 Chen (67-65+1)/2 1 Han (72-65+1)/2 4 Ye (89-65+1)/2 12 Dei (68-65+1)/2 2 (a) 关键字计算过程(上图) (b) 哈希表(右图) 图8.16

由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生冲突。即，key1 key2，而H(key1)= H(key2)。通常把这种具有不同关键字而具有相同的哈希地址的对象称作同义词，由同义词引起的冲突称为同义词冲突 。 在设计哈希函数时，一方面要考虑选择一个“好”的哈希函数；另一方面要给出一种处理冲突的方法。

哈希表存储的基本思想是：设要存储的对象个数为n，设置一个长度为m(m>=n)的连续内存单元，以线性表中每个对象的关键字key为自变量，通过哈希函数，把每个key值映射为内存单元的地址(或称数组下标)，即H(key)的值，并把该对象存储在这个内存单元中。H(key)的值称为哈希地址(又称散列地址)。把这样构造的表存储结构称为哈希表(Hash_Table)。

8.3.2 哈希函数的构造方法 所谓“好”的哈希函数是指对于集合中的任意一个关键字，经哈希函数得到的哈希地址尽可能均匀地分布在表中n 个连续内存单元地址上，从而减少冲突，同时使计算过程尽可能简单，以达到尽可能高的查找效率。根据关键字的结构和分布的不同，可构造出许多不同的哈希函数。对数字的关键字可有下列哈希函数的构造方法，若是非数字关键字，则须先对其进行数字化处理。

哈希函数的构造方法 1 直接定址法 构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=a·key+b 特点 直接定址法所得地址集合与关键字集合大小相等，不会发生冲突 实际中能用这种哈希函数的情况很少

【例8.4】学生的学籍表，可用学号作为表中学生的地址。其哈希函数为 H(key)=key-20000。 表8-1 直接定址哈希函数 01 02 03 04 05 06 ...... 250 学号 20001 20002 20003 20004 20005 20006 20250 ...

2.数字分析法 假设关键字集合中的每个关键字都是由s位数字组成(k1,k2,…,kn)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。一般用于能预先估计出所有关键字的每一位上各种数字出现的频度上。 【例8.5】有一组关键字为(92317602，92326875，92739628，92343634，92706816，92774638，92381262，92394220)。通过观察每个关键字发现，各个关键字从左到右的第1、2、3、6位取值较集中，而其余几位则取值相对比较均匀，可以根据情况选取其中几位组合作为地址。如表长为100，可取最后两位构成哈希地址，得到的哈希表地址表为 (02,75,28,34,16,38,62,20)

3.平方取中法 若关键字的每一位都有某些数字重复出现频度很高的现象，则先求关键字的平方值，以通过“平方”扩大差别，一个数平方后的中间几位受到整个关键字中各个数位的影响，可增加随机性。

4.折叠法 若关键字的位数特别多，则可将其分割成几部分，然后取它们的叠加和为哈希地址。叠加法可有移位叠加和间界叠加两种处理方法。移位叠加是将关键字分割后的几个部分按最低位右对齐进行叠加，结果作为地址。间界叠加是按照每组的个数来回周折进行折叠，结果作为地址。叠加后要舍弃进位。 【例8.6】设商品的条形码为9-787302-037866，若表长为100000，两种折叠过程见图8.17 。

移位叠加法 间界叠加法 37866 73020 02037 +) 978 +) 978 111864 40881 H(key)=11864 H(key)=40881 图8.17 折叠法

5.随机数法 通过随机函数对每个关键字产生一个随机数作为关键字的哈希地址。 H(key)=random(key)。一般用于关键字长度不等时。 6.除留余数法 用关键字key除以一个小于或等于哈希表长度m 的整数p后得到的余数作为该关键字的哈希地址。 H(key)=key % p (p≤m) 一般地，p 应为不大于m 的质数或是不含20以下的两个质因数的乘积。

【例8.7】若关键字集合key={12,39,18,24,33,21}时，若取p=9，则使所有含质因子3的关键字均映射到地址0、3、6上，从而增加了“冲突”的可能性。可设表长为11，取p=11，则可得哈希地址集合如表6-2。 H(12) H(39) H(18) H(24) H(33) H(21) 1 6 7 2 10

8.3.3 处理冲突的方法 处理冲突的基本思想是：当发生冲突时，将待插入的记录存入另一个不产生冲突的地址，即空闲地址中，从而解决冲突。常用的处理冲突的方法有以下几种： 1.开放地址法 所谓开放地址即未填入数据的空闲地址。开放地址法就是为产生冲突的关键字所对应的记录求得一个地址序列： H0,H1,H2,…,Hs 1≤s≤m-1 其中，H0=H(key) Hi=(H(key)+di) % m 　(i=1,2,…,s) 按此序列不断探测，直到找到空闲地址为止。

增量di有三种取法： (1) 线性探测再散列 di=i 即，di=1,2,3,4,… (2) 二次探测再散列(也称平方探测再散列) di=±i2 即，12,-12,22,-22,… (3) 随机探测再散列 di是一组伪随机数列 注意：增量di应具有下面的特性。即，产生的Hi均不相同，且所产生的s(m-1)个Hi的值能覆盖哈希表中所有的地址。由此可以得出：平方探测时的表长m必为4j+3的质数；随机探测时的表长m和di没有公因子。

【例8.8】对于例8.7所示，设表长为9，取p=9时，则采用开放地址法中线性探测再散列(di=i)作为解决冲突的方法，可得以下哈希表8-3： H(12)=3 H(39)=3，冲突，取d1=(H(39)+1) % 9=4 H(18)=0 H(24)=6 H(33)=6，冲突，取d1=(H(33)+1) % 9=7 H(21)=3，冲突，d1=(H(21)+1) % 9=4，仍冲突，取d2=(H(21)+2) % 9=5

地址 1 2 3 4 5 6 7 8 关键字 18 12 39 21 24 33 探查次数

若采用开放地址法中二次线性探测再散列作为冲突的解决办法可得以下哈希表8-4： H(12)=3 H(39)=3，冲突，取d1=(H(12)+12) % 9=4 H(18)=0 H(24)=6 H(33)=6，冲突，取d1=(H(33)+12) % 9=7 H(21)=3，冲突，取d1=(H(21)+12) % 9=4，仍冲突，再取d2=(H(21)-12) % 9=2

地址 1 2 3 4 5 6 7 8 关键字 18 21 12 39 24 33 探查次数

2.链地址法 --拉链法--外部链接法 将所有哈希地址相同的记录都链接在同一链表中。因此，在这种方法中，哈希表的每个单元中存放的不再是对象，而是相应同义词单链表的头指针。

与开放地址法相比，它有几个优点： (1)链地址肯定不会产生二次聚集，平均查找长度较短。 (2)各链表上的记录空间动态申请，比较适合用于造表前无法确定表长的情况。 (3)开放地址法为了避免冲突，有时需要增大表的长度，造成空间的浪费，而链地址法中只增加了结点的指针域，可忽略不计，因此节省空间。 (4)链地址法中增加或删除一个结点时操作易于实现。

【例8.9】如上例表中的元素，仍取p=9，表长为9。用拉链法解决冲突所得哈希表如图 18 ∧ ∧ 2 3 ∧ 4 ∧ 5 6 ∧ 7 ∧ 8 ∧ 12 39 21 ∧ 24 33 ∧ 图8.18 例8.9数据产生的哈希表

3.建立公共溢出区 为了解决冲突，可另外创建一个线性表，将所有与哈希表中的关键字发生冲突的记录都加入到该表中。这样的线性表就称为公共溢出区。

8.3.4 哈希表的查找与分析 哈希表的查找过程和造表过程一致。假设采用开放地址法处理冲突，哈希表为r[m](m为哈希表的表长)，则查找过程为: 对于给定值key，计算哈希地址i=H(key)。若r[i]为空标记，则查找不成功；若r[i].key = key则查找成功。否则，求下一地址Hi，直至r[Hi]为空标记或已搜索了表中的所有单元(查找不成功)，或r[Hi].key=key (查找成功)为止。

决定哈希表查找的平均查找长度的因素为： 选用的哈希函数; 选用的处理冲突的方法; 哈希表的装满程度――装载因子α值的大小。

一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论平均查找长度（ASL）时，可以不考虑哈希函数的因素。因此哈希表的ASL是处理冲突方法和装载因子的函数。 哈希表的装填因子定义为： 一般地，α越小，发生冲突的可能性越小；反之，α越大，表装得越满，冲突的可能性越大，查找时，对于给定值需要进行比较的关键字个数也越多，查找效率越低。

可以证明，采用不同的冲突解决办法，其在查找成功时的ASL分别为： 线性探测再散列 ： 随机探测再散列： 链地址法： 若在采用非链地址法解决冲突的哈希表中删除记录时，不需移动其他记录，只需在被删记录处作一特殊的删除标记，指明后继“同义词”记录所在的位置，以使查找过程继续进行。