第 9章 检索
检索的基本概念
线性表的检索
最佳二叉排序树和 Huffman树
散列表检索
二叉排序树
B-树
丰满树和平衡树
9.1 检索的基本概念检索 是确定数据元素集合中是否存在数据元素等于特定元素或是否存在元素满足某种给定特征的过程。
要进行检索，必须知道待检索对象的特征，也就是要知道待检索数据元素的 关键字 。
我们将能唯一标识一个数据元素的关键字称为主关键字，而其它关键字称为辅助关键字或从关键字。
静态检索表：检索的前后不会改变查找表的内容。
动态检索表：检索过程中可能会改变数据元素的存储位臵。
检索算法的评价标准：平均查找长度 ASL（ Average
Search Length），也就是为确定某一结点在数据集合中的位臵，给定值与集合中的结点关键字所需进行的比较次数。
对于具有 n个数据元素的集合,查找某元素成功的平均查找长度为：
n
i
ii CP
1
ASL＝
9.2 线性表的检索线性结构是数据元素间最常见的数据结构，基于线性表的检索运算在各类程序中应用非常广泛，
本节介绍三种在线性表上进行检索的方法，它们分别是 顺序检索、二分法检索 与 分块检索 。为简化问题，本节所介绍的检索方法均视为是基于静态查找表上的操作。
9.2.1顺序检索从表的一端开始，顺序（逐个）扫描线性表，
依次将扫描到的结点关键字和给定值 Key相比较，若当前扫描到的结点关键字与 Key相等，则检索成功；
若扫描结束后，仍未找到关键字等于 Key的结点，则检索失败。
存储结构：顺序存储或链式存储本节介绍基于顺序表的顺序检索算法。
/************************************/
/* 线性表检索用的头文件 */
/* 文件名,seqlist.h */
/************************************/
#include <stdio.h>
#define maxsize 100 /*预定义最大的数据域空间 */
typedef int datatype; /*假设数据类型为整型 */
typedef struct {
datatype data[maxsize]; /*此处假设数据元素只包含一个整型的关键字域 */
int len; /*线性表长度 */
} seqlist; /*预定义的顺序表类型 */
算法 9.1给出了基于顺序查找表的顺序检索方法 。
/***************************************************/
/* 顺序检索算法 文件名,s_search.c */
/* 函数名,seqsearch1(),seqsearch2() */
/***************************************************/
#include "seqlist.h"
/*--------顺序查找的非递归实现 ------*/
int seqsearch1(seqlist l,datatype key)
{ int k=l.len-1;
while (k>=0 && l.data[k]!=key ) k--;
return(k);
}
/*-------------顺序查找的递归实现 ----------*/
int seqsearch2(seqlist l,int n,datatype key)
{ int k=0;
if (n==-1)
k=-1;
else if (l.data[n]==key) k=n;
else k=seqsearch2(l,n-1,key);
return(k);
}
算法 9.1 线性表的顺序检索（顺序存储）
顺序检索的缺点是查找时间长 。 假设顺序表中每个记录的查找概率相同,即 Pi=1/n（ i=0,1,…,n-1）,
查找表中第 i个记录所需的进行的比较次数 Ci=n-i。 因此,顺序查找算法查找成功时的平均查找长度为：
算法分析：
1
0
1
0
2/)1()(1
n
i
n
i
ii ninnCP
ASLseq=
查找失败时，算法的平均查找长度为：
nnn
n
i
1
0
1ASLseq=
9.2.2二分法检索二分法检索又称为 折半查找,采用二分法检索可以大大提高查找效率，它要求线性表结点按其关键字从小到大（或从大到小）按序排列并采用 顺序存储 结构。
采用二分搜索时，先求位于搜索区间正中的对象的下标 mid，用其关键码与给定值 x比较,
l[mid],Key = x，搜索成功；
l[mid],Key > x，把搜索区间缩小到表的 前半部分,再继续进行对分搜索；
l[mid],Key < x，把搜索区间缩小到表的 后半部分,再继续进行对分搜索。
每比较一次，搜索区间缩小一半。如果搜索区间已缩小到一个对象，仍未找到想要搜索的对象，则搜索失败。
有一组有序的线性表如下：
（ 10,14,20,32,45,50,68,90,100,120）
例下面分析在其中二分检索关键字 20的过程。
下面分析二分检索关键字 95的过程,
下面给出二分检索法的非递归与递归实现算法，算法中使用 seqlist.h中定义的顺序查找表。
/****************************************************/
/* 二分查找算法 文件名,b_search.c */
/* 函数名,binsearch1(),binsearch2() */
/****************************************************/
/*--------二分查找的非递归实现 ------*/
int binsearch1(seqlist l,datatype key)
{ int low=0,high=l.len-1,mid;
while (low<=high)
{ mid=(low+high)/2; /*二分 */
if (l.data[mid]==key) return mid; /*检索成功返回 */
if (l.data[mid]>key)
high=mid-1; /*继续在前半部分进行二分检索 */
else low=mid+1; /*继续在后半部分进行二分检索 */
}
return -1; /* 当 low>high时表示查找区间为空,检索失败 */
}
/*--------二分查找的递归实现 ------*/
int binsearch2(seqlist l,datatype key,int low,int high)
{ int mid,k;
if (low>high) return -1; /*检索不成功的出口条件 */
else
{ mid=(low+high)/2; /*二分 */
if (l.data[mid]==key) return mid; /*检索成功返回 */
if (l.data[mid]>key)
return /*递归地在前半部分检索 */
else return /*递归地在后半部分检索 */
} }
binsearch2(l,key,low,mid-1);
binsearch2(l,key,mid+1,high);
搜索成功的情形 搜索不成功的情形从有序表构造出的二叉搜索树 (判定树 )
若设 n = 2h-1，则描述对分搜索的二叉搜索树是高度为 h-1 的满二叉树。 2h = n+1,h = log2(n+1)。
第 0层结点有 1个，搜索第 0层结点要比较 1次；第 1
层结点有 2个，搜索第 1层结点要比较 2次； …，
)2...2...232221(1 11210 ki kinASLbins=
在假定每个结点的查找概率相同的情况下,二分检索的平均查找次数为：
1)1(22
1
1
ki k
k
i
i用数学归纳法容易证明：
)1)1)1() ( l o g1((1)1)1(2(1 2 nnnkn kASLbins=
)1(lo g11)1(lo g 22 nnn=
= log2(n+1)-1
9.2.3分块检索分块查找 (Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。
1,查找表存储结构查找表由“分块有序”的线性表和索引表组成
。
（ 1）“分块有序”的线性表线性表 R被均分为若干块，每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是 "分块有序 "的。
（ 2）索引表抽取各块中的最大关键字及其起始位臵构成一个索引表 ID[l..b]，即：
ID[i](1≤i≤b)中存放第 i块的最大关键字及该块在表 R
中的起始位臵。由于表 R是分块有序的，所以索引表是一个递增有序表。
【 例 】 例如，图 9.2就是一个带索引的分块有序的线性表。其中线性表 L共有 20个结点，被分成 3块，第一块中最大关键字 25小于第二块中的最小关键字 27
，第二块中最大关键字 55小于第三块中的最小关键字 60。
图 9.2 分块有序表的索引存储表示
2、分块查找的基本思想分块查找的基本思想是：
（ 1）首先查找索引表索引表是有序表，可采用二分查找或顺序查找，
以确定待查的结点在哪一块。
（ 2）然后在已确定的块中进行顺序查找由于块内无序，只能用顺序查找。
分块检索方法通过将查找缩小在某个块中从而提高了检索的效率，其查找的效率由两部分组成，
一是为确定某一块对索引表的平均查找长度 El，二是块内查找所需的平均查找长度 Eb 。
若以顺序检索来确定块,则分块查找成功时的平均查找长度为：
ASLids=El+Eb=
1212/2 12 1
2
ssnssnsb
当 时,ASLids取最小值 +1 ns? n
若以二分检索来确定块,则分块检索查找成功时的平均查找长度为：
ASL’ids=El+Eb?log2（ b+1） -1+（ s+1） /2
log2（ n/s+1） +s/2
/**************************************************************/
/* 分块查找算法 */
/* 文件名,i_search.c 函数名,indexseqsearch() */
/**************************************************************/
#include "seqlist.h"
typedef struct /*索引表结点类型 */
{ datatype key;
int address;
} indexnode;
/*--------分块查找 --------*/
int indexseqsearch(seqlist l,indexnode index[],int m,datatype
key)
{ /*分块查找关键字为 Key的记录,索引表为 index[0..m-1]*/
int i=0,j,last;
while (i<m && key>index[i].key) i++;
if (i>=m) return -1;
else
{ /*在顺序表中顺序检索 */
if (i==m-1) j=l.len-1;
else j=index[i+1].address-1; /*j初始时指向本块的最后一个结点 */
while (j>=index[i].address && key!=l.data[j] )
j--; /*从后向前逐个查找 */
if (j<index[i].address) return -1;
else return j;
}
}
算法 9.3 分块检索
9.1 在分块检索中,对 256个元素的线性表分成多少块最好？ 每块的最佳长度是多少？ 若每块的长度为 8,其平均检索的长度是多少？
习题
9.3 二叉排序树在线性表的三种检索方法中二分检索法具有最高的查找效率，但是它只适合于顺序存储结构，这给查找表中数据的增、删带来不便。
1、二叉排序树的定义二叉排序树 (Binary Sort Tree)又称二叉查找
(搜索 )树 (Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树
：
①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
③左、右子树本身又各是一棵二叉排序树。
上述性质简称二叉排序树性质 (BST性质 )，故二叉排序树实际上是满足 BST性质的二叉树
2、二叉排序树的特点由 BST性质可得：
（ 1） 二叉排序树中任一结点 x，其左 (右 )子树中任一结点 y(若存在 )的关键字必小 (大 )于 x的关键字。
（ 2） 二叉排序树中，各结点关键字是惟一的。
注意：
实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉排序树定义中 BST
性质 (1)里的 "小于 "改为 "大于等于 "，或将 BST性质
(2)里的 "大于 "改为 "小于等于 "，甚至可同时修改这两个性质。
（ 3） 按中序遍历该树所得到的中序序列是一个递增有序序列。
60
40 80
30 50 68 98
36
30
40
60
58
例 两棵二叉排序树
（ a） （ b）
图 9.3二叉排序树示例对图 9.3（ a） 所示的二叉排序树进行中序遍历得到的结果是 30,36,40,50,60,68,80,98；对图
9.3（ b） 所示的二叉排序树进行中序遍历的结果为 30，
40,50,60。
退化成单链表
/**************************************/
/* 二叉排序树用的头文件 */
/* 文件名,bstree.h */
/**************************************/
#include<stdio.h>
#include<stdlib.h>
typedef int datatype;
typedef struct node /*二叉排序树结点定义 */
{ datatype key; /*结点值 */
struct node *lchild,*rchild; /*左,右孩子指针 */
}bsnode;
typedef bsnode *bstree;
二叉排序树存储结构定义一、基于二叉排序树的查找运算对于一棵给定的二叉排序树,树中的查找运算很容易实现,其算法可描述如下：
（ 1） 当二叉树为空树时,检索失败；
（ 2） 如果二叉排序树根结点的关键字等于待检索的关键字,则检索成功；
（ 3） 如果二叉排序树根结点的关键字小于待检索的关键字,则用相同的方法继续在根结点的右子树中检索；
（ 4） 如果二叉排序树根结点的关键字大于待检索的关键字,则用相同的方法继续在根结点的左子树中检索 。
/**************************************************************/
/* 基于二叉排序树的检索算法 文件名,t_search.c */
/* 函数名,bssearch1(),bssearch2() */
/**************************************************************/
/*-------二叉排序树的非递归查找 -------*/
void bssearch1(bstree t,datatype x,bstree *p,bstree *q)
{ /* q返回待查结点 x在二叉排序树中的地址,p返回待查结点 x
的父结点地址 */
*p=NULL;
*q=t;
while (*q)
{ if (x==(*q)->key) return;
*p=*q;
*q=(x<(*q)->key)? (*q)->lchild:(*q)->rchild;
}
return;
}
/*-------二叉排序树的递归查找 -------*/
bstree bssearch2(bstree t,datatype x)
{ /*在二叉排序树 t中查找关键字为 x的结点,若找到则返回该结点的地址,否则返回 NULL*/
if (t==NULL || x==t->key)
return t;
if (x<t->key)
return bssearch2(t->lchild,x); /*递归地在左子树中检索 */
else
return bssearch2(t->rchild,x); /*递归地在右子树中检索 */
}
算法分析：
在二叉排序树上进行检索的方法与二分检索相似，和关键字的比较次数不会超过树的深度 。
因此，在二叉排序树上进行检索的效率与树的形状有密切的联系。
在最坏的情况下，含有 n个结点的二叉排序树退化成一棵深度为 n的单支树（类似于单链表），它的平均查找长度与单链表上的顺序检索相同，即 ASL=
（ n+1） /2。在最好的情况下，二叉排序树形态比较匀称，对于含有 n个结点的二叉排序树，其深度不超过 log2n，此时的平均查找长度为 O（ log2n）。
60
40 70
30 50 65 80
46 55 75
30
40
46
50
55
60
65
70
75
80
（ a） （ b）
图 9.4两棵具有不同检索效率的二叉排序树例如,对于图 9.4中的两棵二叉排序树,其深度分别是 4和 10,在检索失败的情况下,在这两棵树上的最大比较次数分别是 4和 10；在检索成功的情况下,若检索每个结点的概率相等,则对于图 9.4
（ a） 所示的二叉排序树其平均查找长度为：
ASLa= =
对于图 9.4（ b） 所示的二叉排序树其平均查找长度为,ASLb=（ 1+2+3+4+5+6+7+8+9+10） /10=5.5
10
1i
iicp
310/)3443221(
二、基于二叉树的插入运算假设待插入的数据元素为 x，则二叉排序树的插入算法可以描述为：
若二叉排序树为空，则生成一个关键字为 x的新结点，并令其为二叉排序树的根结点；
否则，将待插入的关键字 x与根结点的关键字进行比较，若二者相等，则说明树中已有关键字 x，无须插入；
若 x小于根结点的关键字，则将 x插入到该树的左子树中，
否则将 x插入到该树的右子树中去。
将 x插入子树的方法与在整个树中的插入方法是相同的，如此进行下去，直到 x作为一个新的叶结点的关键字插入到二叉排序树中，或者直到发现树中已有此关键字为止。
/******************************************************/
/* 基于二叉排序树的结点插入算法 */
/* 文件名,t_insert.c 函数名,insertbstree() */
/******************************************************/
void insertbstree(bstree *t,datatype x)
{ bstree f,p;
p=*t;
while (p) /*查找插入位臵 */
{ if (x==p->key) return; /* 若二叉排序树 t中已有 key,则无需插入 */
f=p; /* f用于保存新结点的最终插入位臵 */
p=(x<p->key)? p->lchild:p->rchild;
}
p=(bstree) malloc(sizeof(bsnode)); /*生成待插入的新结点 */
p->key=x;
p->lchild=p->rchild=NULL;
if (*t==NULL) *t=p; /*原树为空 */
else
if (x<f->key)
f->lchild=p;
else f->rchild=p;
}
程序 9.5 基于二叉排序树的结点的插入算法建立二叉排序树的算法如下：
/******************************************************/
/* 二叉排序树的建立算法 */
/* 文件名,t_creat.c 函数名,creatbstree() */
/******************************************************/
bstree creatbstree(void)
{ /*根据输入的结点序列,建立一棵二叉排序树,并返回根结点的地址 */
bstree t=NULL;
datatype key;
printf("\n请输入一个以 -1为结束标记的结点序列,\n");
scanf("%d",&key); /*输入一个关键字 */
while (key!=-1)
{ insertbstree(&t,key); /*将 key插入二叉排序树 t*/
scanf("%d",&key);
}
return t; /*返回建立的二叉排序树的根指针 */
}
算法 9.6 生成一棵二叉排序树对于输入实例（ 30,20,40,10,25,45）,算法
9.6创建二叉排序树的过程如下：
（ a） 空树
30
（ b） 插入 30
30
20
（ c） 插入 20
30
20 40
（ d） 插入 40
30
20 40
10
（ e）插入 10
30
20 40
10 25
（ f）插入 25
30
20 40
10 25 45
（ g）插入 45
按照（ 30,20,10,25,40，
45）或（ 30,40,45,20,10，
25）的输入次序同样可生成图
9.5（ g）所示的二叉排序树。
但若按照（ 10,20,25，
30,40,45）或（ 45,40，
30,25,20,10）的次序输入，将分别生成只具有单个右分支和单个左分支的两棵二叉排序树。
结论：
二叉排序树的形态与数据的输入次序相关；
由无序序列输入建立二叉排序树，再对其进行中序遍历可得一个有序序列，这种方法便是树排序。
三、二叉排序树的删除从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，并且还要保证删除后所得的二叉树仍然满足 BST性质。
根据二叉排序树的结构特征,删除 *p可以分四种情况来考虑：
（ 1） 待删除结点为叶结点,则直接删除该结点即可 。
若该结点同时也是根结点,则删除后二叉排序树变为空树 。 图 9.6（ a） 给出了一个删除叶结点的例子 。
删除操作的一般步骤
(1) 进行查找查找时，令 p指向当前访问到的结点,parent指向其双亲 (其初值为 NULL)。若树中找不到被删结点则返回，否则被删结点是 *p。
(2) 删去 *p。
删 *p时，应将 *p的子树 (若有 )仍连接在树上且保持 BST性质不变。按 *p的孩子数目分三种情况进行处理。
60
40 70
30 50
36
80
45 7520
删除叶子结点
20和 75
60
40 70
30 50
36
80
45
（ 2）待删除结点 只有左子树，而无右子树 。根据二叉排序树的特点，可以直接将其左子树的根结点替代被删除结点的位臵。即如果被删结点为其双亲结点的左孩子，则将被删结点的唯一左孩子收为其双亲结点的左孩子，否则收为其双亲结点的右孩子。图 9.6（ b）
给出了一个例子。
60
40 70
30 50
36
80
45 7520
删除只有左子树的单孩子结点 50
（ 3）待删除结点只有右子树，而无左子树。与情况
（ 2）类似，可以直接将其右子树的根结点替代被删除结点的位臵。即如果被删结点为其双亲结点的左孩子，则将被删结点的唯一右孩子收为其双亲结点的左孩子，否则收为其双亲结点的右孩子。图 9.6（ c）给出了一个例子。
60
40 70
30 45
36
80
7520
60
40 70
30 50
36
80
45 7520
删除只有右子树的单孩子结点 70
（ 4） 待删除结点既有左子树又有右子树 。根据二叉排序树的特点，可以用被删除结点中序下的前趋结点（或其中序下的后继结点）代替被删除结点，同时删除其中序下的前趋结点（或中序下的后继结点）。而被删除结点的中序前趋无右子树，被删除结点的中序后继无左子树，因而问题转换为第（ 2）
种情况或第（ 3）种情况。
60
40 80
30 50
36 45
75
20
除此之外，还可以直接将被删结点的右子树代替被删除结点，同时将被删除结点的左子树收为被删结点右子树中序首点的左孩子。也可以直接将被删除结点的左子树代替被删除结点，同时将被删结点的右子树收为被删结点左子树中序尾点的右孩子。图 9.6（ d）
给出的示例是直接用被删结点的右子树代替被删结点。
60
40 70
30 50
36
80
45 7520
删除具有 2棵子树的结点 40
60
36 70
30 50 80
45 7520
45
36
50
30
36
45
20
30
50
36
45
20
/**************************************************/
/* 基于二叉排序树的结点删除算法 */
/* 文件名,t_dele.c 函数名,delbstree() */
/**************************************************/
bstree delbstree(bstree t,datatype x)
{ /*在二叉排序树 t中删除结点值为 x的结点 */
bstree p,q,child;
bssearch1(t,x,&p,&q); /*查找被删结点 */
if (q) /*找到了待删除结点 */
{ if (q->lchild==NULL && q->rchild==NULL) /*情况 1,待删结点为叶结点 */
{ if (p) /*待删除结点有双亲 */
{ if (p->lchild==q) p->lchild=NULL; else p->rchild=NULL;}
else t=NULL; /*待删结点为树根 */
free (q);
}
else /*情况 2,待删结点的左子树为空,用待删结点的右子树替代该结点 */
if (q->lchild==NULL)
{ if (p) /*待删结点的双亲结点不为空 */
{ if (p->lchild==q)
p->lchild=q->rchild; /*q是其双亲结点的左儿子 */
else p->rchild=q->rchild; /*q是其双亲结点的右儿子 */
}
else t=q->rchild;
free(q);
}
else /*情况 3,待删结点的右子树为空,用待删结点的左子树替代该结点 */
if (q->rchild==NULL)
{ if (p) /*待删结点的双亲结点不为空 */
{if (p->lchild==q)
p->lchild=q->lchild; /*q是其双亲结点的左儿子 */
else p->lchild=q->lchild; /*q是其双亲结点的右儿子 */
} else t=q->lchild;
free(q);
}
else /*情况 4,待删结点的左右子树均不为空,用右子树代替待删结点,同时将待删结点的左子树收为右子树中序首点的左儿子 */
{ child=q->rchild;
while (child->lchild) /*找待删结点右子树中的中序首点 */
child=child->lchild;
child->lchild=q->lchild; /*将待删结点的左子树收为
child的左孩子 */
if (p) /*待删结点不是树根 */
{ if (p->lchild==q)
p->lchild=q->rchild;
else p->rchild=q->rchild;
} else t=q->rchild; /*待删结点为树根 */
free(q);
}
}
return t;
}
算法 9.7 基于二叉排序树的结点删除二叉排序树中结点的删除操作的主要时间在于查找被删除结点及查找被删结点的右子树的中序首点上,
而这个操作的时间花费与树的深度密切相关 。 因此,
删除操作的平均时间亦为 O（ log2n） 。
9.2 设有关键码 A,B,C和 D,按照不同的输入顺序,
共可能组成多少不同的二叉排序树 。 请画出其中高度较小的 6种 。
9.3 已知序列 17,31,13,11,20,35,25,8,4,11，
24,40,27。 请画出由该输入序列构成的二叉排序树,
并分别给出下列操作后的二叉排序树 。
（ 1） 插入数据 9； （ 2） 删除结点 17； （ 3） 再删除结点 13
9.4 试写一算法判别给定的二叉树是否为二叉排序树,
设此二叉树以二叉链表为存储结构,且树中结点的关键字均不相同 。
习题
9.4丰满树和平衡树二叉排序树上实现的插入,删除和查找等基本操作的平均时间虽然为 O（ log2n）,但在最坏情况下,
二叉排序树退化成一个具有单个分支的单链表,此时树高增至 n,这将使这些操作的时间相应地增至 O
（ n） 。 为了避免这种情况发生,人们研究了许多种动态平衡的方法,包括如何建立一棵,好,的二叉排序树；如何保证往树中插入或删除结点时保持树的
,平衡,,使之既保持二叉排序树的性质又保证树的高度尽可能地为 O（ log2n） 。 本节将介绍两种特殊的二叉树,丰满树和平衡树 。
9.4.1丰满树设 T是一棵二叉树,ki和 kj是 T中孩子结点个数少于
2的任意两个结点,?k是结点 k的树枝长度,如果满足：
|?ki-?kj|
则称 T是一棵 丰满树 。
从上述概念可知，在丰满树中，任意两个非双孩子结点的高度之差的绝对值要小于等于 1，由于树的最下面一层为叶子结点，因此，在丰满树中，
子女结点个数少于 2的结点只出现在树的最低两层之中。图 9.7给出了一棵丰满树和一棵非丰满树。
（ a） 一棵丰满树 （ b） 一棵非丰满树图 9.7 丰满树与非丰满树示例对于 n个结点的任意序列,用 平分法 构造结点序列的丰满树的步骤是：
（ 1） 如果结点序列为空,则得到一棵空的二叉树；
（ 2） 如果序列中有 n1个结点 k1,k2,…,kn,那么令
m=?（ n+1） /2?,所求的树是由根 km,左子树 Tl和右子树 Tr组成 。 其中 Tl和 Tr分别是用平分法由 k1,k2,…,
km-1和 km+1,km+2,…,kn创建的丰满树 。
要用平分法构造丰满的二叉排序树，需保证 n个序列 k1,k2,…,kn是按升序排列的。根据有序数组创建丰满二叉排序树的算法见算法 9.8 。
/*****************************************************/
/* 丰满树构造算法 */
/* 文件名,creatfmt.c 函数名,creatfmt() */
/*****************************************************/
#include<stdio.h>
#include<stdlib.h>
typedef int datatype;
typedef struct node /*二叉树结点定义 */
{ datatype data;
struct node *lchild,*rchild;
} bintnode;
typedef bintnode *bintree;
/*---------平分法创建一棵丰满树 -------------*/
bintree creatfmt(int node[],int low,int high)
{ int mid; bintree s;
if (low<=high)
{ mid=(low+high)/2;
s=(bintree)malloc(sizeof(bintnode)); /*生成一个新结点 */
s->data=node[mid];
s->lchild=creatfmt(node,low,mid-1); /*平分法建左子树 */
s->rchild=creatfmt(node,mid+1,high); /*平分法建右子树 */
return s;
} else return NULL; }
算法 9.8 建立丰满树对于具有 n个结点的丰满二叉排序树,如果树中所有结点都具有相同的使用概率,那么其平均检索长度为：
ASL?log2n
但对动态的二叉排序树进行插入和删除等操作后，
丰满树很容易变为非丰满二叉排序树，并且将非丰满二叉排序树改造成丰满二叉排序树非常困难。因此，
实际应用中经常使用一种称为,平衡树” 的特殊二叉排序树。
9.4.2平衡二叉排序树平衡二叉树又称为 AVL树，它或是一棵空树，或是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树高度之差的绝对值不超过 1。
此处规定二叉树的高度是二叉树的树叶的最大层数,也就是从根结点到树叶的最大路径长度,空的二叉树的高度定义为 -1。
相应地,二叉树中某个结点的左子树高度与右子树高度之差称为该结点的平衡因子 （ 或平衡度 ） 。 由此可知,平衡二叉树 也就是树中任意结点的平衡因子的绝对值小于等于 1的二叉树 。
如果一棵二叉排序树满足平衡二叉树的定义便是一棵平衡的二叉排序树,平衡的二叉排序树又称为平衡查找树 。
研究平衡二叉树的目的在于如何动态地使一棵二叉排序树保持平衡,从而使它具有较高的检索效率 。
由丰满树和平衡树的定义可知，丰满树一定是平衡树，但平衡树却不一定是丰满树。
C
B
A D G
E1
0 1
-1
-1
F 0
0
D
B
A C G
E0
0 1
-1
-2
F 0
0
平衡非满树 非平衡二叉树
G.M.Adelson-Velskii和 E.M.Landis在 1962年提出了动态保持二叉排序树平衡的一个有效办法，后称为 Adelson方法。下面介绍 Adelson方法如何将一个新结点 k插入到一棵平衡二叉排序树 T中去。
Adelson方法由三个依次执行的过程 ——插入,调整平衡度和改组所组成：
（ 1）插入,不考虑结点的平衡度，使用在二叉排序树中插入新结点的方法，把结点 k插入树中，同时臵新结点的平衡度为 0。
（ 2）调整平衡度,假设 k0,k1,…,km=k是从根 k0
到插入点 k路径上的结点，由于插入了结点 k，就需要对这条路径上的结点的平衡度进行调整。
调整方法是,从结点 k开始,沿着树根的方向进行扫描,当首次发现某个结点 kj的平衡度不为零,或者 kj为根结点时,便对 kj与 km-1之间结点进行调整 。 令调整的结点为 ki（ j?i?m）,若 k在 ki的左子树中,则 ki的平衡度加 1；若 k在 ki的右子树中,则 ki的平衡度减 1；此时,
kj+1,kj+2,…,km-1结点不会失去平衡,唯一可能失去平衡的结点是 kj。 若 kj失去平衡,即 kj的平衡因子不是 -
1,0和 1时,便对以 kj为根的子树进行改组,且保证改组以后以 kj为根的子树与未插入结点 k之前的子树高度相同,这样,k0,k1,…,kj-1的平衡度将保持不变,
这就是为何不需要对这些结点进行平衡度调整的原因 。
反之,若 kj不失去平衡,则说明,新结点 k的加入并未改变以 kj为根的子树的高度,整棵树无需进行改组 。
（ 3） 改组：改组以 kj为根的子树除了满足新子树高度要和原来以 kj为根子树的高度相同外,还需使改造后的子树是一棵平衡二叉排序树 。
下面具体讨论 AVL树上因插入新结点而导致失去平衡时的调整方法 。
为叙述方便,假设在 AVL树上因插入新结点而失去平衡的最小子树的根结点为 A（ 即 A为距离插入结点最近的,平衡因子不是 -1,0和 1的结点 ） 。 失去平衡后的调整操作可依据失去平衡的原因归纳为下列四种情况分别进行 。
（ 1） LL型平衡旋转：由于在 A的左孩子的左子树上插入新结点,使 A的平衡度由 1增至 2,致使以 A为根的子树失去平衡,如图 9.9（ a） 所示 。 此时应进行一次顺时针旋转,,提升,B（ 即 A的左孩子 ） 为新子树的根结点,A下降为 B的右孩子,同时将 B原来的右子树 Br
调整为 A的左子树 。
A 2
B 1
BL Br
Ar h
hh
LL型
A 0
B 0
BL
Br Ar hh
h
图 9.9 (a)
（ 2） RR型平衡旋转：由于在 A的右孩子的右子树上插入新结点,使 A的平衡度由 -1变为 -2,致使以 A为根的子树失去平衡,如图 9.9（ b） 所示 。 此时应进行一次逆时针旋转,,提升,B（ 即 A的右孩子 ） 为新子树的根结点,A下降为 B的左孩子,同时将 B原来的左子树 BL调整为 A的右子树 。
图 9.9 (b)
A -2
B-1
BrBL
AL h
hh
RR型
A 0
B 0
Br
AL BL hh
h
（ 3） LR型平衡旋转：由于在 A的左孩子的右子树上插入新结点，使 A的平衡度由 1变成 2，致使以 A为根的子树失去平衡，如图 9.9（ c）所示。此时应进行两次旋转操作（先逆时针，后顺时针），即“提升” C（即 A
的左孩子的右孩子）为新子树的根结点； A下降为 C的右孩子； B变为 C的左孩子； C原来的左子树 CL调整为 B
现在的右子树； C原来的右子树 Cr调整为 A现在的左子树A 2
B -1
Ar h
BL h
LR型
C
CL h-1 Cr h-1
1
A -1B 0
Ar hBL h CL h-1 Cr h-1
C
0
图 9.9 (c)
（ 4） RL型平衡旋转：由于在 A的右孩子的左子树上插入新结点，使 A的平衡度由 -1变成 -2，致使以 A为根的子树失去平衡，如图 9.9（ d）所示。此时应进行两旋转操作（先顺时针，后逆时针），即,提升,C
（即 A的右孩子的左孩子）为新子树的根结点； A下降 C的左孩子； B变为 C的右孩子； C原来的左子树 CL
调整为 A现在的右子树； C原来的右子树 Cr调整为 B现在的左子树。
B -1A 0
Br hAL h CL h-1 Cr h-1
C
0
A -2
B 1
Br h
AL h RL型
CL h-1 Cr h-1
C
1
图 9.9 (d)
综上所述,在平衡的二叉排序树 t上插入一个新的数据元素 x的算法可描述如下：
（ 一 ） 若 AVL树 t为空树,则插入一个数据元素为 x的新结点作为 t的根结点,树的深度增 1；
（ 二 ） 若 x的关键字和 AVL树 t的根结点的关键字相等,
则不进行插入；
（三）若 x的关键字小于 AVL树 t的根结点的关键字，
则将 x插入在该树的左子树上，并且当插入之后的左子树深度增加 1时，分别就下列不同情况进行分情形处理：
（ 1）若 AVL树的根结点的平衡因子为 -1（右子树的深度大于左子树的深度），则将根结点的平衡因子调整为 0，并且树的深度不变；
（ 2） 若 AVL树的根结点的平衡因子为 0（ 左,右子树的深度相等 ）,则将根结点的平衡因子调整为 1,树的深度同时增 1；
（ 3）若 AVL树的根结点的平衡因子为 1（左子树的深度大于右子树的深度），则当该树的左子树的根结点的平衡因子为 1时需进行 LL型平衡旋转；当该树的左子树的根结点的平衡因子为 -1时需进行 LR型平衡旋转。
（四）若 x的关键字大于 AVL树 t的根结点的关键字，
则将 x插入在该树的右子树上，并且当插入之后的右子树深度增加 1时，需要分别就不同情况进行处理。
其处理操作和（三）中所述相对称，读者可以自行分析。
结点序列（ 120,80,30,90,45,60）逐个插入一棵空的 AVL树的过程如下：
120
0
120
1
80
0
120
2
80
1
30
0
120
0
80
0
30
0
120
1
80
-1
30
0
90
0
120
1
80
0
30
-1
90
0
45
0
120
1
80
0
30
-2
90
0
45
-1
60
0
120
1
80
0
30
0
90
0
45
0
60
0
为实现 Adelson方法,先定义 AVL树的存储结构如下：
/*********************************/
/* AVL树使用的头文件 */
/* 文件名,AVL.H */
/*********************************/
typedef int datatype;
typedef struct node
{ datatype key;
struct node *lchild,*rchild;
int bal; /*结点的平衡度 */
} bsnode;
typedef bsnode *bstree;
算法 9.9 给出了基于 AVL树的结点插入算法习题
9.6 含有 12个节点的平衡二叉树的最大深度是多少
（ 设根结点深度为 0）,并画出一棵这样的树 。
9.7 试用 Adelson插入方法依次把结点值为 60,40,30，
150,130,50,90,80,96,25的记录插入到初始为空的平衡二叉排序树中,使得在每次插入后保持该树仍然是平衡查找树 。 请依次画出每次插入后所形成的平衡查找树 。
9.5最佳二叉排序树和 Huffman树对于具有 n个结点的二叉排序树，在考虑每个结点查找概率的情况下，如何使得整棵树的平均检索效率最高，即使得比较的平均次数最少、代价最小，这与二叉排序树的形状密切相关。假定 n个结点的关键字序列为 k1,k2,…k n,ki对应的使用概率为 P（ ki），
树枝长度为?ki，则对 n个结点构成的二叉排序树其查找成功的平均比较次数为：
ASL= （ 9-9）?
n
i
ii kkp
1
)1)((?
当每个结点具有相同的使用概率，即 P（ ki） =1/n时，
ASL= = （ 9-10）?
n
i
ikn
1
)1(1? )1(1
1
n
i
ikn?
本节讨论如何构造 ASL最小的二叉排序树。
9.5.1扩充二叉树给定一棵二叉树,对树中不足两个孩子的结点
（ 包括叶子结点 ） 都添上附加结点,使每个结点都有两个孩子结点,所得的二叉树称为原二叉树的扩充二叉树,称那些附加的结点为 外部结点,称树中原来的结点为 内部结点 。 对于具有 n个内部结点的二叉树,
其外部结点数为 n+1个 。 图 9.11给出了一棵二叉树及其对应的扩充二叉树,图中圆圈表示内部结点,方框表示外部结点 。
（ a）一棵二叉树 t （ b） t的扩充二叉树对一棵二叉排序树进行扩充后便可得到一棵扩充的二叉排序树（又称为扩充查找树）。对扩充查找树进行中序遍历,最左外部结点 代表码值小于内部结点最小码值的可能结点集； 最右外部结点 代表码值大于内部结点最大码值的可能结点集；而其余外部结点代表码值处于原二叉排序树在中序序列下相邻结点码值之间的可能结点集。
最左外部结点最右外部结点在对扩充二叉查找树进行检索过程中,若检索到达外部结点,则表明相应码值的结点不在原二叉排序树中,故也称外部结点为失败结点 。
若一棵扩充二叉查找树中所有内部结点的树枝长度之和记为 I,所有外部结点的树枝长度之和记为 E。
则对于一个具有 n个内部结点的扩充二叉树,其内部树枝长度 In与外部树枝长度 En存在下列关系：
En=In+2n （ 9-11）
根据式 （ 9-11） 可知,在具有 n个结点的所有二叉树中,具有最大 （ 或最小 ） 内部路枝长度的二叉树也一定是具有最大 （ 或最小 ） 外部路枝长度的二叉树,反之亦然 。
当二叉树退化为线性表时,其内部路枝长度最大,
其值为 In=0+1+2+… +（ n-1） =n（ n-1） /2。 为了得到具有最小 In的二叉树,必须使内部结点尽量靠近根结点 。 由二叉树结构可知,根结点只有一个,路枝长度为 1的结点至多有两个,路枝长度为 2的结点至多为四个,路枝长度为 k的结点至多为 2k个 。 所以 In的最小值为：
In=1x0+2x1+4x2+8x3+…=
n
i
i
1
2log
9.4.1节介绍的平分法构造的丰满树具有最小内部路径长度 。
9.5.2最佳二叉排序树在一棵扩充的二叉排序树中,假设内部结点由序列
（ a1,a2,a3,…,ai,…,an ） 构成,且有
a1<a2<a3… <ai… <an。 外部结点由 （ b0,b1,b2,…,
bi,…,bn） 构成,且有 b0<b1<b2… <bi… <bn。 这里将内部结点 ai的检索概率记为 p（ ai）,简记为 pi
（ 1?i?n） ；外部结点 bi的检索概率记为 qi（ 0?i?n）,
它 们对 应的 树枝 长度分 别记 为 ai （ 1?i?n ） 和 bi
（ 0?i?n）,则成功查找所需的平均比较次数为：
n
i
n
i
iiii apap
1 1
)1()1(?的树枝长度而不成功查找所需的平均比较次数为：
n
i
n
i
iiii bqbq
0 0
)()(?的树枝长度不失一般性，一棵二叉排序树的平均查找长度（代价）为：
ASL= （ 9-18）
n
i
n
j
jjii bqap
1 0
))(())1((
对于 n个有序序列（ a1,a2,a3,…,ai,…,an）
作为内部结点和 n+1个有序序列（ b0,b1,b2,…,
bi,…,bn）作为外部结点构成的所有可能的扩充查找树中，具有最少平均比较次数，即式（ 9-18）取值最小的扩充二叉排序树称为最佳二叉排序树，或最优查找树。
当查找成功与查找失败具有相等概率，即
p1=p2=…=p n=q0=q1=…=1/ （ 2n+1）时，平均检索长度 ASL=
n
i
n
j
jjii bqap
1 0
))(())1((
))()1((12 1
1 0
n
i
n
j
ji ban
=
)(12 1 nn EnIn
)2(
12
1 nInI
n nn
)32(
12
1 nI
n n
=
=
= …… （ 9-19）
由式 （ 9-19） 可知,只要 In取最小值,ASL就达到最小 。
而平分法构造的丰满树具有最小内部路径长度。
In=?
n
i
i
1
2log )lo g()( lo g 22
nn nOn?
此时
ASL= = )32(
12
1 nI
n n )lo g( 2
nnO
所以,在检索成功和不成功具有相等概率的情况下,用平分法构造出来的丰满二叉排序树是最佳二叉排序树 。
现考虑查找概率不相等的情况下如何构造最佳二叉排序树。也就是对于给定的 n个内部结点 a1,a2，
a3,…,ai,…,an和 n+1个外部结点 b0,b1,b2,…,
bi,…,bn，它们对应的查找概率分别是 p1,p2，
p3,…,pi,…,pn及 q0,q1,…,qn，找使得
ASL=
n
i
n
j
jjii bqap
1 0
))(())1((
为最小的二叉排序树 （ 以下我们又称 ASL为二叉排序树的代价 （ 或花费 ）） 。
构造最佳二叉排序树时要满足以下两个要求：同一序列构造的不同二叉排序树应具有相同的中序遍历结果；一棵最佳二叉排序树的任何子树都是最佳二叉排序树 。 因此,构造一棵最佳二叉排序树可以先构造包括一个结点的最佳二叉排序树,再根据包括一个结点的最佳二叉排序树构造包括两个结点的最佳二叉排序树,…,如此进行下去,直到把所有的结点都包括进去 。
为描述构造最佳二叉排序树的算法,这里用 T[i,j]
表示 ai+1,…,aj（ i<j） 组成的一棵最佳二叉排序树,
规定当 0?i?n且 i=j时,T[i,j]为空树 （ 即内部结点为空 ） ；当 i>j时表示 T[i,j]无定义；用 C[i,j]表示查找树
T[i,j]的代价；用 rij表示 T[i,j]的根,用 W[i,j]表示 T[i，
j]的权值,它的值是 T[i,j]中内部结点和外部结点查找概率之和 。 即：
W[i,j]=qi+?
j
ik
kk qp
1
)(
根据最佳二叉排序树的构造要求,其构造过程可以按以下步骤进行：
（ 1） 构造包括一个结点的最佳二叉排序树,也就是
T[0,1],T[1,2],…,T[n-1,n]。
（ 2） 构造包括两个结点的最佳二叉排序树,也就是
T[0,2],T[1,3],…,T[n-2,n]。
（ 3）再构造包括三个，四个,…,n-1个结点的最佳二叉排序树，直到最后构造 T[0,n]。
用（ ai+1,ai+2,…,aj）作为内部结点构造最佳二叉排序树 T[i,j]的方法可如下进行：分别用 ai+1，
ai+2,…,aj为根，共考虑 j-i棵二叉排序树，以 ak为根的二叉排序树其左子树包括 ai+1,…,ak-1，而包括这些关键码为内部结点的最佳二叉排序树 T[i,k-1]已在前面的步骤确定,C[i,k-1]已求出，而以 ak为根的二叉排序树其右子树包括 ak+1,ak+2,…,aj，以这些关键码为内部结点的最佳二叉排序树 T[k,j]也已在前面的步骤确定,C[k,j]已求出。对于 i<k?j，找出使 C[i，
k-1]+C[k,j]最小的那个 k’，以 ak’为根,T[i,k’-1]为左子树,T[k’,j]为右子树的那棵二叉排序树就是所求的 T[i,j]。其花费 C[i,j]等于其根的左子树花费 C[i，
k’-1]加上右子树花费 C[k’,j]，再加上结点总的权 W[i，
j]，即 C[i,j]=W[i,j]+ C[i,k’-1]+ C[k’,j]。
综上所述,T[i,j]是最优查找树必须满足条件：
C[i,j]=W[i,j]+ （ C[i,k-1]+C[k,j]） （ 9-20）min
jki
假设 n=4，且（ a1,a2,a3,a4） =（ 10,18,26，
50）；（ p1,p2,p3,p4） =（ 1,4,3,2），（ q0，
q1,q2,q3,q4） =（ 1,2,3,3,1），试构造出有序序列 a1,a2,a3,a4所组成的最优查找树。
例首先根据式（ 9-20）构造包括一个内部结点的最佳二叉排序树，其花费的代价分别是 C[0,1]=4,C[1，
2]=9,C[2,3]=9和 C[3,4]=6，如图 9.12（ a）所示。
a1
b0
1
1 b
1
2
a2
b1
4
2 b
2
3
a3
b2
3
3 b
3
3
a4
b3
2
3 b
4
1
花费 C[0,1]=4 C[1,2]=9 C[2,3]=9 C[3,4]=6
总权 4 9 9 6
（ a）包括一个内部结点的最佳二叉排序树
a3
3
b3 3a2
b1
4
2 b
2
3
a3
b2
3
3 a
4
b3
2
3 b
4
1
a4 2
b4 1a3
b2
3
3 b
3
3
花费 24 C[2,4]=C[3,4]+12=18 21
总权 15 12 12
（ b）包括二个内部结点的最佳二叉排序树
a1
b0
1
1 a
2
b1
4
2 b
2
3
a2
4
b2 3a1
b0
1
1 b
1
2
a2
b1
4
2 a
3
b2
3
3 b
3
3
花费 20 C[0,2]=C[0,1]+11=15 C[1,3]=C[2,3]+15=24
总权 11 11 15
a1
b0
1
1 a
2
b1
4
2 a
3
b2
3
3 b
3
3
a2
4
a1
b0
1
1 b
1
2
a3
b2
3
3 b
3
3
a3
3
b3 3a2
4
b2 3a1
b0
1
1 b
1
2
花费 41 C[0,3]=C[0,1]+C[2,3]+17=30 32
总权 17 17 17
a2
b1
4
2 a
3
b2
3
3 a
4
b3
2
3 b
4
1
a3
3
a2
b1
4
2 b
2
3
a4
b3
2
3 b
4
1
a4
2
b4 1a2
b1
4
2 a
3
b2
3
3 b
3
3
花费 36 C[1,4]=C[1,2]+C[3,4]+18=33 42
总权 18 18 18
（ c）包括三个内部结点的最佳二叉排序树
a1
b0
1
1 a
3
3
a2
b1
4
2 b
2
3
a4
b3
2
3 b
4
1
a2
4
a1
b0
1
1 b
1
2
a3
b2
3
3 a
4
b3
2
3 b
4
1
花费 53 42
总权 20 20
a3
3
a24
b2 3a1
b0
1
1 b
1
2
a4
b3
2
3 b
4
1
a4
2
b4 1a2
4
a1
b0
1
1 b
1
2
a3
b2
3
3 b
3
3
花费 C[0,4]=C[0,2]+C[3,4]+20=41 50
总权 20 20
（ d）包括四个内部结点的最佳二叉排序树
9.8 结点关键字 k1,k2,k3,k4,k5为一个有序序列，
它们的相对使用频率分别为 p1=6,p2=8,p3=12，
p4=2,p5=16，外部结点的相对使用频率分别为 q0=4，
q1=9,q2=8,q3=12,q4=3,q5=2。试构造出有序序列 k1,k2,k3,k4,k5所组成的最优查找树。
习题对于包括 n个关键码的集合,构造最佳二叉排序树过程中需要进行 C[i,j]（ 0?i<j?n） 的计算次数为：
)(6)1( 3
1
1
0
3
nOnij
n
j
j
i
9.5.3 Huffman树给定 n个结点 k1,k2,…,kn,它们的权分别是 W（ ki）
（ 1?i?n）,现要利用这 n个结点作为外部结点 （ 叶子结点 ） 去构造一棵扩充二叉树,使得带权外部路径长度
n
i
iki kw
1
)(?WPL=
达到最小值，其中 wki为外部结点 ki的权值,?ki是从根结点到达外部结点 ki的树枝长度。具有最小带权外部路径长度的二叉树称为 Huffman树。
例如 4个结点 k1,k2,k3,k4，分别带权 10,16,20，
6。利用它们作为外部结点分别构造了以下三棵扩充二叉树（还有其它形式的扩充二叉树）如图 9.13所示。
（ a） （ b） （ c）
图 9.13 具有不同带权路径长度的扩充二叉树其带权路径长度分别为：
（ a） WPL=52?2=104
（ b） WPL=（ 16+20）?3+20?2+6?1=154
（ c） WPL=（ 10+6）?3+16?2+20?1=100
其中图 9.13（ c）所示的扩充二叉树带权外部路径长度最小，可以验证，它恰为 Huffman树。一般情况下，权越大的叶子离根越近，那么二叉树的带权外部路径长度就越小。在实际的应用中，分支程序的判断流程可用一棵 Huffman树来表示，如果出现概率越大的分枝（条件语句）离根越近，那么所需执行的判断语句就越少，这样便可提高程序的执行效率。
Huffman给出了求具有最小带权外部路径长度的扩充二叉树的方法,通常称为 Huffman算法,该算法可描述如下：
（ 1） 根据给定的 n个权值 {w1,w2,…,wn}构造 n棵二叉树的集合 F={T1,T2,…,Tn},其中每棵二叉树
Ti中只有一个带权为 wi的根结点,其左,右子树均为空 。
（ 2） 在 F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且臵新的二叉树的根结点权值为其左,右子树根结点的权值之和 。
（ 3） 在 F中用新得到的二叉树代替这两棵树 。
（ 4） 重复 （ 2）,（ 3） 过程,直到 F中只含有一棵树为止 。
root? 6? 10? 16? 20? 24? 30
具体实现可以采用有序链表存储结构例如：对于结点序列 10,16,20,6,30,24,构造 huffman树的过程如下：
（ 1）建立有序链表
（ 2）从链表中截取前面二棵根结点权值最小的树作为左右子树，生成一棵新的子树，并将新子树按其根的权值插入有序链表中去，如此循环，直到只剩一棵树为止。
root
6
16 20 24 30
10
161
root
6
16
20 24 30
10
16
322
root
6
16 20 24
30
10
16
32 443
root
6
16
20 24 30
10
16
32
44 624
root
6
16
20 24 30
10
16
32
44 62
1065
6
16
20 24 30
10
16
32
44 62
106
a b
c
d e f
0 1
1
1
1
10 0
0
0
Huffman 树的应用
1,Huffman编码各字符的二进制编码为：
a,1100 b,1101 c,111 d,00 e,01 f,10
从二叉树的根开始,用需要译码的二进制位串中的若干个相邻位与二叉树边上标的 0,1相匹配,确定一条到达树叶的路径,一旦到达树叶,则译出了一个字符,再回到树根,从二进制位串的下一位开始继续译码 。
2,huffman译码
9.10假设通讯电文中只用到 A,B,C,D,E,F六个字母，它们在电文中出现的相对频率分别为,8,3，
16,10,5,20，试为它们设计 Huffman编码。
习题
9.6 B-树前面所讨论的查找算法都是在内存中进行的,它们适用于较小的文件,而对较大的,存放在外存储器上的文件就不合适了 。
1972年 R.Bayer和 E.M.McCreight提出了一种称为 B-树的多路平衡查找树，它适合在磁盘等直接存取设备上组织动态的查找表。
9,6,1 B-树的定义
B-树是一种平衡的多路查找树,在文件系统中,已经成为索引文件的一种有效结构,并得到泛的应用 。
在此先介绍这种树的结构及其基本运算 。
一棵 m阶 （ m?3） B-树,或为空树,或为满足下列特性的 m叉树：
（ 1） 树中每个结点至多有 m棵子树；
（ 2） 若根结点不是叶子结点,则至少有两棵子树；
（ 3） 所有的非终端结点中包含下列信息
（ n,p0,k1,p1,k2,p2,…,kn,pn）
其中,ki（ 1?i?n） 为关键字,且 ki<ki+1（ 1?i?n） ； pj
（ 0?j?n） 为指向子树根结点的指针,且 pj（ 0?j<n） 所指子树中所有结点的关键字均小于 kj+1,pn所指子树中所有结点的关键字均大于 kn,n（?m/2?-1?n?m-1） 为关键字的个数 （ n+1为子树个数 ） 。
（ 4） 除根结点之外所有非终端结点至少有?m/2?棵子树,也即每个非根结点至少应有?m/2?-1个关键字；
（ 5） 所有的叶子结点都出现在同一层上,并且不带信息 （ 可以看作是外部结点或查找失败的结点,实际上这些结点不存在,指向这些结点的指针为空 ） 。
2 50 80
root
1^60^1^53^1^43^1^22^ 1^97^1^88^1^75^
2 20 40 2 55 70 1 90
2^10^19^
例,一棵 3阶的 B-树
9,6,2 B-树的基本操作一,基于 B-树的查找运算
2 50 80
root
1^60^1^53^1^43^1^22^ 1^97^1^88^1^75^
2 20 40 2 55 70 1 90
2^10^19^
二,基于 B-树的插入运算在 B-树中插入关键字 k的方法是：首先在树中查找
k，若找到则直接返回（假设不处理相同关键字的插入）；否则查找操作必失败于某个叶子结点上，利用函数 btree_search（）的返回值 *p及 *pos可以确定关键字 k的插入位臵，即将 k插入到 p所指的叶结点的第
pos个位臵上。若该叶结点原来是非满（结点中原有的关键字总数小于 m-1）的，则插入 k并不会破坏 B-树的性质，故插入 k后即完成了插入操作，例如，在图
9.17（ a）所示的 5阶 B-树的某结点（假设为 p结点）
中插入新的关键字 150时，可直接得到图 9.17（ b）所示的结果。
2 100 190 3 100 150 190
图 9.17在关键字个数不满的结点中插入关键字若 p所指示的叶结点原为满，则 k插入后 keynum=m，
破坏了 B-树的性质（ 1），故须调整使其维持 B-树的性质不变。调整的方法是将违反性质（ 1）的结点以中间位臵的关键字 key[?m/2?]为划分点，将该结点（即 p）
（ m,p0,k1,p1,…,km,pm）
分裂为两个结点，左边结点为（?m/2?-1,p0，
k1,…k?m/2?-1,p?m/2?-1），右边结点为（ m-?m/2?，
p?m/2?,k?m/2?+1,…,km,pm），同时把中间关键字
k?m/2?插入到双亲结点中。于是双亲结点中指向被插入结点的指针 pre改成 pre,k?m/2?,pre’三部分。指针 pre
指向分裂后的左边结点，指针 pre’指向分裂后的右边结点。由于将 k?m/2?插入双亲时，双亲结点亦可能原本为满，若如此，则需对双亲做分裂操作。分裂过程的例子如图 9.18所示。
2 … 80 220…
4 90 120 140 160
p
3 … 80 120 220 …
2 90 100 2 140 160
pre pre pre’
k?m/2?
插入 100
以前插入 100
以后如果初始时 B-树为空树，通过逐个向 B-树中插入新结点，可生成一棵 B-树。图 9.19说明了一棵 5阶 B-树的生长过程。
6 8 15 16
6 8
15
16 22 6 8 10
15
16 18 22 32
（ a）插入 6,8,15,16 （ b）插入 22 （ c）插入 10,18,32
6 8 10
15 20
16 18 22 32 6 8 10 12
15 20
16 18 19 22 32 40 50 6 8 10 12
15 20 40
16 18 19 22 32 50 56
（ d） 插入 20 （ e） 插入 12,19,40,50 （ f） 插入 56
6 8
9 15 20 40
16 18 19 22 26 32 36 50 52 55 5610 12 6 8
9 15
16 18 19 22 26 50 52 55 5610 12 36 38
20
32 40
（ g） 插入 9,26,36,52,55 （ h） 插入 38
三、基于 B-树的删除运算在 B-树上删除一个关键字，首先找到该关键字所在结点及其在结点中的位臵。具体可分为两种情况：
（ 1）若被删除结点 ki在最下层的非终端结点（即叶子结点的上一层）里，则应删除 ki及它右边的指针 pi。删除后若结点中关键字数目不少于?m/2?-1，则删除完成，否则要进行“合并”结点的操作。
（ 2）假若待删结点 ki是最下层的非终端结点以上某层的结点，根据 B-树的特性可知，可以用 ki右边指针 pi
所指子树中最小关键字 y代替 ki，然后在相应的结点中删除 y，或用 ki左边指针 pi-1所指子树中最大关键字 x代替 ki，然后在相应的结点中删除 x。例如删除图 9.20
（ a）所示 3阶 B-树中的关键字 50，可以用它右边指针所指子树中最小关键字 60代替 50，尔后转化为删除叶子上面一层的结点中的 60，删除后得到的 B-树如图
9.20（ b）所示。
90 1158 40
28
150 200
85 120
50
60 80
90 1158 40
28
150 200
85 120
60
80
3阶 B-树中删除 50
以 60代替 50
因此，下面主要讨论删除 B-树叶子上面一层结点中的关键字的方法，具体分三种情形：
1）被删关键字所在叶子上面一层结点中的关键字数目不小于?m/2?，则只需要从该结点中删去关键字 ki和相应的指针 pi，树的其它部分不变。
例：
908 40
28
150 200
85 120
50
80 90 11560 80
删除 60与
115
2）被删关键字所在叶子上面一层结点中的关键字数目等于?m/2?-1，而与该结点相邻的右兄弟结点（或左兄弟结点）中的关键字数目大于?m/2?-1，则需要将其右兄弟的最小关键字（或其左兄弟的最大关键字）移至双亲结点中，而将双亲结点中小于（或大于）该上移关键字的关键字下移至被删关键字所在的结点中。例如从图 9.21（ b）中删除关键字 90，结果如图 9.21（ c）所示。
1208 40
28
200
85 150
50
80 90 150 200
2
80
删除 90
3）被删关键字所在叶子上面一层结点中的关键字数和其相邻的兄弟结点中的关键字数目均等于?m/2?-1，
则第（ 2）种情况中采用的移动方法将不奏效，此时须将被删关键字所有结点与其左或右兄弟合并。不妨设该结点有右兄弟，但其右兄弟地址由双亲结点指针
pi所指，则在删除关键字之后，它所在结点中剩余的关键字和指针加上双亲结点中的关键字 ki一起合并到 pi
所指兄弟结点中（若没有右兄弟，则合并至左兄弟结点中）。
例如，从图 9.21（ c）中删去关键字 120，则应删去 120
所在结点，并将双亲结点中的 150与 200合并成一个结点，删除后的树如图 9.21（ d）所示。如果这一操作使双亲结点中的关键字数目小于?m/2?-1，则依同样方法进行调整，最坏的情况下，合并操作会向上传播至根，
当根中只有一个关键字时，合并操作将会使根结点及其两个孩子合并成一个新的根，从而使整棵树的高度减少一层。
1208 40
28
200
85 150
50
80
删除 120
150 200
85
例如，在图 9.21（ d）中删除关键字 8，此关键字所在结点无左兄弟，只检查其右兄弟，然而右兄弟关键字数目等于?m/2?-1，此时应检查其双亲结点关键字数目是否大于等于?m/2?-1，但此处其双亲结点的关键字数目等于?m/2?-1，从而进一步检查双亲结点兄弟结点关键字数目是否均等于?m/2?-1，这里关键字 28所在的结点的右兄弟结点关键字数目正好等于?m/2?-1，因此将
28和 40结合成一个结点,50和 85结合成一个结点，使得树变矮，删除结点 8后的结果如图 9.21（ e）所示。
8 40
28
150 200
85
50
80
删除 8
28 40 150 20080
50 85
习题
9.11含有 9个叶子结点的 3阶 B-树中至少有多少个非叶子结点？ 含有 10个叶子结点的 3阶 B-树中至少有多少个非叶子结点？
9.13用依次输入的关键字 23,30,51,29,2 7,15、
11,17和 16建一棵 3阶 B-树,画出建该树的变化过程示意图 （ 每插入一个结点至少有一张图 ） 。
9.7散列表检索在已经介绍过的线性表、树等数据结构中，记录存储在结构中的相对位臵是随机的，因而相应的检索是通过若干次的比较以寻找指定的记录。本节将介绍一种新的存储结构 ——散列存储，它既是一种存储方式，又是一种常见的检索方法。
9.7.1散列存储散列存储的基本思想是以关键码的值为自变量，
通过一定的函数关系（称为散列函数，或称 Hash
函数），计算出对应的函数值来，以这个值作为结点的存储地址，将结点存入计算得到的存储单元里去。
U
S
k1k
2
k3
k5
k4
0
H(k1)
H(k5)
H(k2)=H(k4)
H(k3)
H(km-1)
图 9.22 散列过程示例散列存储中经常会出现对于两个不同关键字 xi,xjS，
却有 H（ xi） =H（ xj），即对于不同的关键字具有相同的存放地址，这种现象称为冲突或碰撞。碰撞的两个（或多个）关键字称为同义词（相对于函数 H而言）。
“负载因子”?反映了散列表的装填程度，其定义为：
= 散列表中结点的数目基本区域能容纳的结点数当?>1时冲突是不可避免的 。 因此,散列存储必须考虑解决冲突的办法 。
综上所述,对于 Hash方法,需要研究下面两个主要问题：
（ 1） 选择一个计算简单,并且产生冲突的机会尽可能少的 Hash函数；
（ 2） 确定解决冲突的方法 。
9.7.2散列函数的构造
（ 1）除余法
H（ key） =key％ p
例如 S={5,21,65,22,69},若 m=7且 H（ x） =x %
7,则可以得到如表 9.1所示的 Hash表 。
0 1 2 3 4 5 6
21 22 65 5 69
表 9.1 散列表示例
（ 2）平方取中法取关键字平方后的中间几位为 Hash地址,所取的位数和 Hash地址位数相同 。 这是一种较常用的构造 Hash函数的方法 。 因为通常在选定 Hash函数时不一定能知道关键字的全部情况,难以决定取其中哪几位比较合适,而一个数平方后的中间几位数和数的每一位都相关,由此使随机每布的关键字得到的
Hash地址也是随机的 。
（ 3） 数字分析法对于关键字的位数比存储区域的地址码位数多的情况,可以采取对关键字的各位进行分析,丢掉分布不均匀的位留下分布均匀的位作为 Hash地址,这种方法称为数字分析法 。
Key H（ key）
0 1 9 4 2 8 3 2 432
0 1 5 7 9 8 8 5 785
0 1 9 5 9 0 1 3 513
0 1 2 8 1 5 3 8 838
0 1 9 2 1 8 2 7 227
0 1 7 1 1 8 4 6 146
（ 4） 折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）
作为 Hash地址，称为折叠法。关键字位数很多且关键字中每一位上数字分布大致均匀时，可以采用折叠法得到 Hash地址。
在折叠法中数位叠加可以有移位叠加和间界叠加两种方法 。 移位叠加是将分割后的每一部分的最低位对齐,然后相加；间界叠加是从一端向另一端沿分割界来回折迭,然后对齐相加 。 如关键码为 7-302-
03806-6,若 Hash地址取 4位,则此关键字的 Hash地址采用折叠法得到如图 9.23所示的结果 。
8006 8006
0203 3020
+ ) 073 +) 073
8282 11099
H（ key） =8282 H（ key） =1099
（ a） 移位叠加 （ b） 间界叠加图 9.23 由折叠法求得 Hash地址
（ 5） 直接地址法取关键字或关键字的某个线性函数值为哈希地址,即：
H（ key） =key或 H（ key） =a·key+b
9.7.3冲突处理
1,开放定址法开放定址法的基本做法是在发生冲突时,按照某种方法继续探测基本表中的其它存储单元,直到找到一个开放的地址 （ 即空位臵 ） 为止 。 显然这种方法需要用某种标记区分空单元与非空单元 。
开放定址法的一般形式可表示为：
Hi（ k） =（ H（ k） +di） mod m（ i=1,2,…,k（ k?m-1））
其中,H（ k） 为键字为 k的直接哈希地址,m为哈希表长,di为每次再探测时的地址增量 。
当 di=1,2,3,…,m-1时,称为线性探测再散列；
当 di=12,-12,22,-22,…,k2,-k2（ k?m/2） 时,称为二次探测再散列；当 di=随机数序列时,称为随机探测再散列 。
例如，有数据（ 654,638,214,357,376,854，
662,392），现采用数字分析法，取得第二位数作为哈希地址，将数据逐个存放入大小为 10的散列表
（此处为顺序表）中。若采用线性探测法解决地址冲突，则 8个数据全部插入完成后，散列表的状态如表 9.2所示。
392 214 638 654 357 376 854 662
0 1 2 3 4 5 6 7 8 9
2,再哈希法采用再哈希法解决冲突的做法是当待存入散列表的某个元素 k在原散列函数 H（ k）的映射下与其它数据发生碰撞时，采用另外一个 Hash函数 Hi（ k）（ i=1，
2,…,n）计算 k的存储地址（ Hi均是不同的 Hash函数），这种计算直到冲突不再发生为止。
3,拉链法拉链法解决冲突的做法是，将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为
m，则可将散列表定义为一个由 m个头指针组成的指针数组 T[0..m-1]，凡是散列地址为 i的结点，均插入到以 T[i]为头指针的单链表中。
拉链法的缺点主要是指针需要用额外的空间,故当结点规模较小时,开放定址法较为节省空间 。
例如,关键字集合为 {1,13,20,5,14,33}，
散列表长度 m=5,现采用除余法为哈希函数并采用拉链法解决地址冲突,所创建的 Hash链表如图 9.24所示 。
t[0]
t[1]
t[2]
t[3]
t[4]
5
1 ^
20 ^
33 13 ^
14 ^
^
除了上述三种方法外,还有差值法可解决地址冲突 。
这种方法在发生冲突时,处理原则以现在的数据地址加上一个固定的差值,当数据地址超出数据大小时,
则让数据地址采用循环的方式处理 。 另外,还可以建立一个公共溢出区的方法去解决冲突 。 即 m个 Hash地址用数组 t[0..m-1]表示,称此表为基本表,每一个分量存放一个关键字,另外设立一个数组 v[0..n]为溢出表 。
若关键字和基本表中关键字为同义词,不管它由 Hash
函数得到的 Hash地址是什么,一旦发生冲突,都填入溢出表 。
假设负载系数为?,则：
（ 1） 如果用开放定址线性探测再散列法解决冲突,
Hash表查找成功和查找不成功的平均查找长度 Sn和 Un
分别为：
Sn Un
)1 11(21 ))1( 11(21 2
（ 2） 如果用二次探测再散列解决冲突,Hash查找成功和查找不成功的平均查找长度 Sn和 Un分别为：
)1ln (1
)1(
1
Sn Un
（ 2） 如果用拉链法解决冲突,Hash表查找成功和查找不成功的平均查找长度 Sn和 Un分别为：
2
1
e
Sn Un
习题
9.14设散列表长度为 11,散列函数 H（ x） =x % 11，
给定的关键字序列为,1,13,12,34,38,33,27，
22。 试画出分别用拉链法和线性探测法解决冲突时所构造的散列表,并求出在等概率的情况下,这两种方法查找成功和失败时的平均查找长度 。
9.15设散列表为 T[0..12],即表的大小 m=13。 现采用再哈希法 （ 双散列法 ） 解决冲突 。 散列函数和再散列函数分别为：
H0（ k） =k % 13、
Hi=（ Hi-1+REV（ k+1） %11+1） %13； i=1,2,…,m-1
其中,函数 REV（ x） 表示颠倒 10进制数的各位,如
REV（ 37） =73,REV（ 1） =1等 。 若插入的关键码序列为 {2,8,31,20,19,18,53,27}。
（ 1） 试画出插入这 8个关键码后的散列表 。
（ 2） 计算检索成功的平均查找长度 ASL。
检索的基本概念
线性表的检索
最佳二叉排序树和 Huffman树
散列表检索
二叉排序树
B-树
丰满树和平衡树
9.1 检索的基本概念检索 是确定数据元素集合中是否存在数据元素等于特定元素或是否存在元素满足某种给定特征的过程。
要进行检索，必须知道待检索对象的特征，也就是要知道待检索数据元素的 关键字 。
我们将能唯一标识一个数据元素的关键字称为主关键字，而其它关键字称为辅助关键字或从关键字。
静态检索表：检索的前后不会改变查找表的内容。
动态检索表：检索过程中可能会改变数据元素的存储位臵。
检索算法的评价标准：平均查找长度 ASL（ Average
Search Length），也就是为确定某一结点在数据集合中的位臵，给定值与集合中的结点关键字所需进行的比较次数。
对于具有 n个数据元素的集合,查找某元素成功的平均查找长度为：
n
i
ii CP
1
ASL＝
9.2 线性表的检索线性结构是数据元素间最常见的数据结构，基于线性表的检索运算在各类程序中应用非常广泛，
本节介绍三种在线性表上进行检索的方法，它们分别是 顺序检索、二分法检索 与 分块检索 。为简化问题，本节所介绍的检索方法均视为是基于静态查找表上的操作。
9.2.1顺序检索从表的一端开始，顺序（逐个）扫描线性表，
依次将扫描到的结点关键字和给定值 Key相比较，若当前扫描到的结点关键字与 Key相等，则检索成功；
若扫描结束后，仍未找到关键字等于 Key的结点，则检索失败。
存储结构：顺序存储或链式存储本节介绍基于顺序表的顺序检索算法。
/************************************/
/* 线性表检索用的头文件 */
/* 文件名,seqlist.h */
/************************************/
#include <stdio.h>
#define maxsize 100 /*预定义最大的数据域空间 */
typedef int datatype; /*假设数据类型为整型 */
typedef struct {
datatype data[maxsize]; /*此处假设数据元素只包含一个整型的关键字域 */
int len; /*线性表长度 */
} seqlist; /*预定义的顺序表类型 */
算法 9.1给出了基于顺序查找表的顺序检索方法 。
/***************************************************/
/* 顺序检索算法 文件名,s_search.c */
/* 函数名,seqsearch1(),seqsearch2() */
/***************************************************/
#include "seqlist.h"
/*--------顺序查找的非递归实现 ------*/
int seqsearch1(seqlist l,datatype key)
{ int k=l.len-1;
while (k>=0 && l.data[k]!=key ) k--;
return(k);
}
/*-------------顺序查找的递归实现 ----------*/
int seqsearch2(seqlist l,int n,datatype key)
{ int k=0;
if (n==-1)
k=-1;
else if (l.data[n]==key) k=n;
else k=seqsearch2(l,n-1,key);
return(k);
}
算法 9.1 线性表的顺序检索（顺序存储）
顺序检索的缺点是查找时间长 。 假设顺序表中每个记录的查找概率相同,即 Pi=1/n（ i=0,1,…,n-1）,
查找表中第 i个记录所需的进行的比较次数 Ci=n-i。 因此,顺序查找算法查找成功时的平均查找长度为：
算法分析：
1
0
1
0
2/)1()(1
n
i
n
i
ii ninnCP
ASLseq=
查找失败时，算法的平均查找长度为：
nnn
n
i
1
0
1ASLseq=
9.2.2二分法检索二分法检索又称为 折半查找,采用二分法检索可以大大提高查找效率，它要求线性表结点按其关键字从小到大（或从大到小）按序排列并采用 顺序存储 结构。
采用二分搜索时，先求位于搜索区间正中的对象的下标 mid，用其关键码与给定值 x比较,
l[mid],Key = x，搜索成功；
l[mid],Key > x，把搜索区间缩小到表的 前半部分,再继续进行对分搜索；
l[mid],Key < x，把搜索区间缩小到表的 后半部分,再继续进行对分搜索。
每比较一次，搜索区间缩小一半。如果搜索区间已缩小到一个对象，仍未找到想要搜索的对象，则搜索失败。
有一组有序的线性表如下：
（ 10,14,20,32,45,50,68,90,100,120）
例下面分析在其中二分检索关键字 20的过程。
下面分析二分检索关键字 95的过程,
下面给出二分检索法的非递归与递归实现算法，算法中使用 seqlist.h中定义的顺序查找表。
/****************************************************/
/* 二分查找算法 文件名,b_search.c */
/* 函数名,binsearch1(),binsearch2() */
/****************************************************/
/*--------二分查找的非递归实现 ------*/
int binsearch1(seqlist l,datatype key)
{ int low=0,high=l.len-1,mid;
while (low<=high)
{ mid=(low+high)/2; /*二分 */
if (l.data[mid]==key) return mid; /*检索成功返回 */
if (l.data[mid]>key)
high=mid-1; /*继续在前半部分进行二分检索 */
else low=mid+1; /*继续在后半部分进行二分检索 */
}
return -1; /* 当 low>high时表示查找区间为空,检索失败 */
}
/*--------二分查找的递归实现 ------*/
int binsearch2(seqlist l,datatype key,int low,int high)
{ int mid,k;
if (low>high) return -1; /*检索不成功的出口条件 */
else
{ mid=(low+high)/2; /*二分 */
if (l.data[mid]==key) return mid; /*检索成功返回 */
if (l.data[mid]>key)
return /*递归地在前半部分检索 */
else return /*递归地在后半部分检索 */
} }
binsearch2(l,key,low,mid-1);
binsearch2(l,key,mid+1,high);
搜索成功的情形 搜索不成功的情形从有序表构造出的二叉搜索树 (判定树 )
若设 n = 2h-1，则描述对分搜索的二叉搜索树是高度为 h-1 的满二叉树。 2h = n+1,h = log2(n+1)。
第 0层结点有 1个，搜索第 0层结点要比较 1次；第 1
层结点有 2个，搜索第 1层结点要比较 2次； …，
)2...2...232221(1 11210 ki kinASLbins=
在假定每个结点的查找概率相同的情况下,二分检索的平均查找次数为：
1)1(22
1
1
ki k
k
i
i用数学归纳法容易证明：
)1)1)1() ( l o g1((1)1)1(2(1 2 nnnkn kASLbins=
)1(lo g11)1(lo g 22 nnn=
= log2(n+1)-1
9.2.3分块检索分块查找 (Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。
1,查找表存储结构查找表由“分块有序”的线性表和索引表组成
。
（ 1）“分块有序”的线性表线性表 R被均分为若干块，每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是 "分块有序 "的。
（ 2）索引表抽取各块中的最大关键字及其起始位臵构成一个索引表 ID[l..b]，即：
ID[i](1≤i≤b)中存放第 i块的最大关键字及该块在表 R
中的起始位臵。由于表 R是分块有序的，所以索引表是一个递增有序表。
【 例 】 例如，图 9.2就是一个带索引的分块有序的线性表。其中线性表 L共有 20个结点，被分成 3块，第一块中最大关键字 25小于第二块中的最小关键字 27
，第二块中最大关键字 55小于第三块中的最小关键字 60。
图 9.2 分块有序表的索引存储表示
2、分块查找的基本思想分块查找的基本思想是：
（ 1）首先查找索引表索引表是有序表，可采用二分查找或顺序查找，
以确定待查的结点在哪一块。
（ 2）然后在已确定的块中进行顺序查找由于块内无序，只能用顺序查找。
分块检索方法通过将查找缩小在某个块中从而提高了检索的效率，其查找的效率由两部分组成，
一是为确定某一块对索引表的平均查找长度 El，二是块内查找所需的平均查找长度 Eb 。
若以顺序检索来确定块,则分块查找成功时的平均查找长度为：
ASLids=El+Eb=
1212/2 12 1
2
ssnssnsb
当 时,ASLids取最小值 +1 ns? n
若以二分检索来确定块,则分块检索查找成功时的平均查找长度为：
ASL’ids=El+Eb?log2（ b+1） -1+（ s+1） /2
log2（ n/s+1） +s/2
/**************************************************************/
/* 分块查找算法 */
/* 文件名,i_search.c 函数名,indexseqsearch() */
/**************************************************************/
#include "seqlist.h"
typedef struct /*索引表结点类型 */
{ datatype key;
int address;
} indexnode;
/*--------分块查找 --------*/
int indexseqsearch(seqlist l,indexnode index[],int m,datatype
key)
{ /*分块查找关键字为 Key的记录,索引表为 index[0..m-1]*/
int i=0,j,last;
while (i<m && key>index[i].key) i++;
if (i>=m) return -1;
else
{ /*在顺序表中顺序检索 */
if (i==m-1) j=l.len-1;
else j=index[i+1].address-1; /*j初始时指向本块的最后一个结点 */
while (j>=index[i].address && key!=l.data[j] )
j--; /*从后向前逐个查找 */
if (j<index[i].address) return -1;
else return j;
}
}
算法 9.3 分块检索
9.1 在分块检索中,对 256个元素的线性表分成多少块最好？ 每块的最佳长度是多少？ 若每块的长度为 8,其平均检索的长度是多少？
习题
9.3 二叉排序树在线性表的三种检索方法中二分检索法具有最高的查找效率，但是它只适合于顺序存储结构，这给查找表中数据的增、删带来不便。
1、二叉排序树的定义二叉排序树 (Binary Sort Tree)又称二叉查找
(搜索 )树 (Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树
：
①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
③左、右子树本身又各是一棵二叉排序树。
上述性质简称二叉排序树性质 (BST性质 )，故二叉排序树实际上是满足 BST性质的二叉树
2、二叉排序树的特点由 BST性质可得：
（ 1） 二叉排序树中任一结点 x，其左 (右 )子树中任一结点 y(若存在 )的关键字必小 (大 )于 x的关键字。
（ 2） 二叉排序树中，各结点关键字是惟一的。
注意：
实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉排序树定义中 BST
性质 (1)里的 "小于 "改为 "大于等于 "，或将 BST性质
(2)里的 "大于 "改为 "小于等于 "，甚至可同时修改这两个性质。
（ 3） 按中序遍历该树所得到的中序序列是一个递增有序序列。
60
40 80
30 50 68 98
36
30
40
60
58
例 两棵二叉排序树
（ a） （ b）
图 9.3二叉排序树示例对图 9.3（ a） 所示的二叉排序树进行中序遍历得到的结果是 30,36,40,50,60,68,80,98；对图
9.3（ b） 所示的二叉排序树进行中序遍历的结果为 30，
40,50,60。
退化成单链表
/**************************************/
/* 二叉排序树用的头文件 */
/* 文件名,bstree.h */
/**************************************/
#include<stdio.h>
#include<stdlib.h>
typedef int datatype;
typedef struct node /*二叉排序树结点定义 */
{ datatype key; /*结点值 */
struct node *lchild,*rchild; /*左,右孩子指针 */
}bsnode;
typedef bsnode *bstree;
二叉排序树存储结构定义一、基于二叉排序树的查找运算对于一棵给定的二叉排序树,树中的查找运算很容易实现,其算法可描述如下：
（ 1） 当二叉树为空树时,检索失败；
（ 2） 如果二叉排序树根结点的关键字等于待检索的关键字,则检索成功；
（ 3） 如果二叉排序树根结点的关键字小于待检索的关键字,则用相同的方法继续在根结点的右子树中检索；
（ 4） 如果二叉排序树根结点的关键字大于待检索的关键字,则用相同的方法继续在根结点的左子树中检索 。
/**************************************************************/
/* 基于二叉排序树的检索算法 文件名,t_search.c */
/* 函数名,bssearch1(),bssearch2() */
/**************************************************************/
/*-------二叉排序树的非递归查找 -------*/
void bssearch1(bstree t,datatype x,bstree *p,bstree *q)
{ /* q返回待查结点 x在二叉排序树中的地址,p返回待查结点 x
的父结点地址 */
*p=NULL;
*q=t;
while (*q)
{ if (x==(*q)->key) return;
*p=*q;
*q=(x<(*q)->key)? (*q)->lchild:(*q)->rchild;
}
return;
}
/*-------二叉排序树的递归查找 -------*/
bstree bssearch2(bstree t,datatype x)
{ /*在二叉排序树 t中查找关键字为 x的结点,若找到则返回该结点的地址,否则返回 NULL*/
if (t==NULL || x==t->key)
return t;
if (x<t->key)
return bssearch2(t->lchild,x); /*递归地在左子树中检索 */
else
return bssearch2(t->rchild,x); /*递归地在右子树中检索 */
}
算法分析：
在二叉排序树上进行检索的方法与二分检索相似，和关键字的比较次数不会超过树的深度 。
因此，在二叉排序树上进行检索的效率与树的形状有密切的联系。
在最坏的情况下，含有 n个结点的二叉排序树退化成一棵深度为 n的单支树（类似于单链表），它的平均查找长度与单链表上的顺序检索相同，即 ASL=
（ n+1） /2。在最好的情况下，二叉排序树形态比较匀称，对于含有 n个结点的二叉排序树，其深度不超过 log2n，此时的平均查找长度为 O（ log2n）。
60
40 70
30 50 65 80
46 55 75
30
40
46
50
55
60
65
70
75
80
（ a） （ b）
图 9.4两棵具有不同检索效率的二叉排序树例如,对于图 9.4中的两棵二叉排序树,其深度分别是 4和 10,在检索失败的情况下,在这两棵树上的最大比较次数分别是 4和 10；在检索成功的情况下,若检索每个结点的概率相等,则对于图 9.4
（ a） 所示的二叉排序树其平均查找长度为：
ASLa= =
对于图 9.4（ b） 所示的二叉排序树其平均查找长度为,ASLb=（ 1+2+3+4+5+6+7+8+9+10） /10=5.5
10
1i
iicp
310/)3443221(
二、基于二叉树的插入运算假设待插入的数据元素为 x，则二叉排序树的插入算法可以描述为：
若二叉排序树为空，则生成一个关键字为 x的新结点，并令其为二叉排序树的根结点；
否则，将待插入的关键字 x与根结点的关键字进行比较，若二者相等，则说明树中已有关键字 x，无须插入；
若 x小于根结点的关键字，则将 x插入到该树的左子树中，
否则将 x插入到该树的右子树中去。
将 x插入子树的方法与在整个树中的插入方法是相同的，如此进行下去，直到 x作为一个新的叶结点的关键字插入到二叉排序树中，或者直到发现树中已有此关键字为止。
/******************************************************/
/* 基于二叉排序树的结点插入算法 */
/* 文件名,t_insert.c 函数名,insertbstree() */
/******************************************************/
void insertbstree(bstree *t,datatype x)
{ bstree f,p;
p=*t;
while (p) /*查找插入位臵 */
{ if (x==p->key) return; /* 若二叉排序树 t中已有 key,则无需插入 */
f=p; /* f用于保存新结点的最终插入位臵 */
p=(x<p->key)? p->lchild:p->rchild;
}
p=(bstree) malloc(sizeof(bsnode)); /*生成待插入的新结点 */
p->key=x;
p->lchild=p->rchild=NULL;
if (*t==NULL) *t=p; /*原树为空 */
else
if (x<f->key)
f->lchild=p;
else f->rchild=p;
}
程序 9.5 基于二叉排序树的结点的插入算法建立二叉排序树的算法如下：
/******************************************************/
/* 二叉排序树的建立算法 */
/* 文件名,t_creat.c 函数名,creatbstree() */
/******************************************************/
bstree creatbstree(void)
{ /*根据输入的结点序列,建立一棵二叉排序树,并返回根结点的地址 */
bstree t=NULL;
datatype key;
printf("\n请输入一个以 -1为结束标记的结点序列,\n");
scanf("%d",&key); /*输入一个关键字 */
while (key!=-1)
{ insertbstree(&t,key); /*将 key插入二叉排序树 t*/
scanf("%d",&key);
}
return t; /*返回建立的二叉排序树的根指针 */
}
算法 9.6 生成一棵二叉排序树对于输入实例（ 30,20,40,10,25,45）,算法
9.6创建二叉排序树的过程如下：
（ a） 空树
30
（ b） 插入 30
30
20
（ c） 插入 20
30
20 40
（ d） 插入 40
30
20 40
10
（ e）插入 10
30
20 40
10 25
（ f）插入 25
30
20 40
10 25 45
（ g）插入 45
按照（ 30,20,10,25,40，
45）或（ 30,40,45,20,10，
25）的输入次序同样可生成图
9.5（ g）所示的二叉排序树。
但若按照（ 10,20,25，
30,40,45）或（ 45,40，
30,25,20,10）的次序输入，将分别生成只具有单个右分支和单个左分支的两棵二叉排序树。
结论：
二叉排序树的形态与数据的输入次序相关；
由无序序列输入建立二叉排序树，再对其进行中序遍历可得一个有序序列，这种方法便是树排序。
三、二叉排序树的删除从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，并且还要保证删除后所得的二叉树仍然满足 BST性质。
根据二叉排序树的结构特征,删除 *p可以分四种情况来考虑：
（ 1） 待删除结点为叶结点,则直接删除该结点即可 。
若该结点同时也是根结点,则删除后二叉排序树变为空树 。 图 9.6（ a） 给出了一个删除叶结点的例子 。
删除操作的一般步骤
(1) 进行查找查找时，令 p指向当前访问到的结点,parent指向其双亲 (其初值为 NULL)。若树中找不到被删结点则返回，否则被删结点是 *p。
(2) 删去 *p。
删 *p时，应将 *p的子树 (若有 )仍连接在树上且保持 BST性质不变。按 *p的孩子数目分三种情况进行处理。
60
40 70
30 50
36
80
45 7520
删除叶子结点
20和 75
60
40 70
30 50
36
80
45
（ 2）待删除结点 只有左子树，而无右子树 。根据二叉排序树的特点，可以直接将其左子树的根结点替代被删除结点的位臵。即如果被删结点为其双亲结点的左孩子，则将被删结点的唯一左孩子收为其双亲结点的左孩子，否则收为其双亲结点的右孩子。图 9.6（ b）
给出了一个例子。
60
40 70
30 50
36
80
45 7520
删除只有左子树的单孩子结点 50
（ 3）待删除结点只有右子树，而无左子树。与情况
（ 2）类似，可以直接将其右子树的根结点替代被删除结点的位臵。即如果被删结点为其双亲结点的左孩子，则将被删结点的唯一右孩子收为其双亲结点的左孩子，否则收为其双亲结点的右孩子。图 9.6（ c）给出了一个例子。
60
40 70
30 45
36
80
7520
60
40 70
30 50
36
80
45 7520
删除只有右子树的单孩子结点 70
（ 4） 待删除结点既有左子树又有右子树 。根据二叉排序树的特点，可以用被删除结点中序下的前趋结点（或其中序下的后继结点）代替被删除结点，同时删除其中序下的前趋结点（或中序下的后继结点）。而被删除结点的中序前趋无右子树，被删除结点的中序后继无左子树，因而问题转换为第（ 2）
种情况或第（ 3）种情况。
60
40 80
30 50
36 45
75
20
除此之外，还可以直接将被删结点的右子树代替被删除结点，同时将被删除结点的左子树收为被删结点右子树中序首点的左孩子。也可以直接将被删除结点的左子树代替被删除结点，同时将被删结点的右子树收为被删结点左子树中序尾点的右孩子。图 9.6（ d）
给出的示例是直接用被删结点的右子树代替被删结点。
60
40 70
30 50
36
80
45 7520
删除具有 2棵子树的结点 40
60
36 70
30 50 80
45 7520
45
36
50
30
36
45
20
30
50
36
45
20
/**************************************************/
/* 基于二叉排序树的结点删除算法 */
/* 文件名,t_dele.c 函数名,delbstree() */
/**************************************************/
bstree delbstree(bstree t,datatype x)
{ /*在二叉排序树 t中删除结点值为 x的结点 */
bstree p,q,child;
bssearch1(t,x,&p,&q); /*查找被删结点 */
if (q) /*找到了待删除结点 */
{ if (q->lchild==NULL && q->rchild==NULL) /*情况 1,待删结点为叶结点 */
{ if (p) /*待删除结点有双亲 */
{ if (p->lchild==q) p->lchild=NULL; else p->rchild=NULL;}
else t=NULL; /*待删结点为树根 */
free (q);
}
else /*情况 2,待删结点的左子树为空,用待删结点的右子树替代该结点 */
if (q->lchild==NULL)
{ if (p) /*待删结点的双亲结点不为空 */
{ if (p->lchild==q)
p->lchild=q->rchild; /*q是其双亲结点的左儿子 */
else p->rchild=q->rchild; /*q是其双亲结点的右儿子 */
}
else t=q->rchild;
free(q);
}
else /*情况 3,待删结点的右子树为空,用待删结点的左子树替代该结点 */
if (q->rchild==NULL)
{ if (p) /*待删结点的双亲结点不为空 */
{if (p->lchild==q)
p->lchild=q->lchild; /*q是其双亲结点的左儿子 */
else p->lchild=q->lchild; /*q是其双亲结点的右儿子 */
} else t=q->lchild;
free(q);
}
else /*情况 4,待删结点的左右子树均不为空,用右子树代替待删结点,同时将待删结点的左子树收为右子树中序首点的左儿子 */
{ child=q->rchild;
while (child->lchild) /*找待删结点右子树中的中序首点 */
child=child->lchild;
child->lchild=q->lchild; /*将待删结点的左子树收为
child的左孩子 */
if (p) /*待删结点不是树根 */
{ if (p->lchild==q)
p->lchild=q->rchild;
else p->rchild=q->rchild;
} else t=q->rchild; /*待删结点为树根 */
free(q);
}
}
return t;
}
算法 9.7 基于二叉排序树的结点删除二叉排序树中结点的删除操作的主要时间在于查找被删除结点及查找被删结点的右子树的中序首点上,
而这个操作的时间花费与树的深度密切相关 。 因此,
删除操作的平均时间亦为 O（ log2n） 。
9.2 设有关键码 A,B,C和 D,按照不同的输入顺序,
共可能组成多少不同的二叉排序树 。 请画出其中高度较小的 6种 。
9.3 已知序列 17,31,13,11,20,35,25,8,4,11，
24,40,27。 请画出由该输入序列构成的二叉排序树,
并分别给出下列操作后的二叉排序树 。
（ 1） 插入数据 9； （ 2） 删除结点 17； （ 3） 再删除结点 13
9.4 试写一算法判别给定的二叉树是否为二叉排序树,
设此二叉树以二叉链表为存储结构,且树中结点的关键字均不相同 。
习题
9.4丰满树和平衡树二叉排序树上实现的插入,删除和查找等基本操作的平均时间虽然为 O（ log2n）,但在最坏情况下,
二叉排序树退化成一个具有单个分支的单链表,此时树高增至 n,这将使这些操作的时间相应地增至 O
（ n） 。 为了避免这种情况发生,人们研究了许多种动态平衡的方法,包括如何建立一棵,好,的二叉排序树；如何保证往树中插入或删除结点时保持树的
,平衡,,使之既保持二叉排序树的性质又保证树的高度尽可能地为 O（ log2n） 。 本节将介绍两种特殊的二叉树,丰满树和平衡树 。
9.4.1丰满树设 T是一棵二叉树,ki和 kj是 T中孩子结点个数少于
2的任意两个结点,?k是结点 k的树枝长度,如果满足：
|?ki-?kj|
则称 T是一棵 丰满树 。
从上述概念可知，在丰满树中，任意两个非双孩子结点的高度之差的绝对值要小于等于 1，由于树的最下面一层为叶子结点，因此，在丰满树中，
子女结点个数少于 2的结点只出现在树的最低两层之中。图 9.7给出了一棵丰满树和一棵非丰满树。
（ a） 一棵丰满树 （ b） 一棵非丰满树图 9.7 丰满树与非丰满树示例对于 n个结点的任意序列,用 平分法 构造结点序列的丰满树的步骤是：
（ 1） 如果结点序列为空,则得到一棵空的二叉树；
（ 2） 如果序列中有 n1个结点 k1,k2,…,kn,那么令
m=?（ n+1） /2?,所求的树是由根 km,左子树 Tl和右子树 Tr组成 。 其中 Tl和 Tr分别是用平分法由 k1,k2,…,
km-1和 km+1,km+2,…,kn创建的丰满树 。
要用平分法构造丰满的二叉排序树，需保证 n个序列 k1,k2,…,kn是按升序排列的。根据有序数组创建丰满二叉排序树的算法见算法 9.8 。
/*****************************************************/
/* 丰满树构造算法 */
/* 文件名,creatfmt.c 函数名,creatfmt() */
/*****************************************************/
#include<stdio.h>
#include<stdlib.h>
typedef int datatype;
typedef struct node /*二叉树结点定义 */
{ datatype data;
struct node *lchild,*rchild;
} bintnode;
typedef bintnode *bintree;
/*---------平分法创建一棵丰满树 -------------*/
bintree creatfmt(int node[],int low,int high)
{ int mid; bintree s;
if (low<=high)
{ mid=(low+high)/2;
s=(bintree)malloc(sizeof(bintnode)); /*生成一个新结点 */
s->data=node[mid];
s->lchild=creatfmt(node,low,mid-1); /*平分法建左子树 */
s->rchild=creatfmt(node,mid+1,high); /*平分法建右子树 */
return s;
} else return NULL; }
算法 9.8 建立丰满树对于具有 n个结点的丰满二叉排序树,如果树中所有结点都具有相同的使用概率,那么其平均检索长度为：
ASL?log2n
但对动态的二叉排序树进行插入和删除等操作后，
丰满树很容易变为非丰满二叉排序树，并且将非丰满二叉排序树改造成丰满二叉排序树非常困难。因此，
实际应用中经常使用一种称为,平衡树” 的特殊二叉排序树。
9.4.2平衡二叉排序树平衡二叉树又称为 AVL树，它或是一棵空树，或是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树高度之差的绝对值不超过 1。
此处规定二叉树的高度是二叉树的树叶的最大层数,也就是从根结点到树叶的最大路径长度,空的二叉树的高度定义为 -1。
相应地,二叉树中某个结点的左子树高度与右子树高度之差称为该结点的平衡因子 （ 或平衡度 ） 。 由此可知,平衡二叉树 也就是树中任意结点的平衡因子的绝对值小于等于 1的二叉树 。
如果一棵二叉排序树满足平衡二叉树的定义便是一棵平衡的二叉排序树,平衡的二叉排序树又称为平衡查找树 。
研究平衡二叉树的目的在于如何动态地使一棵二叉排序树保持平衡,从而使它具有较高的检索效率 。
由丰满树和平衡树的定义可知，丰满树一定是平衡树，但平衡树却不一定是丰满树。
C
B
A D G
E1
0 1
-1
-1
F 0
0
D
B
A C G
E0
0 1
-1
-2
F 0
0
平衡非满树 非平衡二叉树
G.M.Adelson-Velskii和 E.M.Landis在 1962年提出了动态保持二叉排序树平衡的一个有效办法，后称为 Adelson方法。下面介绍 Adelson方法如何将一个新结点 k插入到一棵平衡二叉排序树 T中去。
Adelson方法由三个依次执行的过程 ——插入,调整平衡度和改组所组成：
（ 1）插入,不考虑结点的平衡度，使用在二叉排序树中插入新结点的方法，把结点 k插入树中，同时臵新结点的平衡度为 0。
（ 2）调整平衡度,假设 k0,k1,…,km=k是从根 k0
到插入点 k路径上的结点，由于插入了结点 k，就需要对这条路径上的结点的平衡度进行调整。
调整方法是,从结点 k开始,沿着树根的方向进行扫描,当首次发现某个结点 kj的平衡度不为零,或者 kj为根结点时,便对 kj与 km-1之间结点进行调整 。 令调整的结点为 ki（ j?i?m）,若 k在 ki的左子树中,则 ki的平衡度加 1；若 k在 ki的右子树中,则 ki的平衡度减 1；此时,
kj+1,kj+2,…,km-1结点不会失去平衡,唯一可能失去平衡的结点是 kj。 若 kj失去平衡,即 kj的平衡因子不是 -
1,0和 1时,便对以 kj为根的子树进行改组,且保证改组以后以 kj为根的子树与未插入结点 k之前的子树高度相同,这样,k0,k1,…,kj-1的平衡度将保持不变,
这就是为何不需要对这些结点进行平衡度调整的原因 。
反之,若 kj不失去平衡,则说明,新结点 k的加入并未改变以 kj为根的子树的高度,整棵树无需进行改组 。
（ 3） 改组：改组以 kj为根的子树除了满足新子树高度要和原来以 kj为根子树的高度相同外,还需使改造后的子树是一棵平衡二叉排序树 。
下面具体讨论 AVL树上因插入新结点而导致失去平衡时的调整方法 。
为叙述方便,假设在 AVL树上因插入新结点而失去平衡的最小子树的根结点为 A（ 即 A为距离插入结点最近的,平衡因子不是 -1,0和 1的结点 ） 。 失去平衡后的调整操作可依据失去平衡的原因归纳为下列四种情况分别进行 。
（ 1） LL型平衡旋转：由于在 A的左孩子的左子树上插入新结点,使 A的平衡度由 1增至 2,致使以 A为根的子树失去平衡,如图 9.9（ a） 所示 。 此时应进行一次顺时针旋转,,提升,B（ 即 A的左孩子 ） 为新子树的根结点,A下降为 B的右孩子,同时将 B原来的右子树 Br
调整为 A的左子树 。
A 2
B 1
BL Br
Ar h
hh
LL型
A 0
B 0
BL
Br Ar hh
h
图 9.9 (a)
（ 2） RR型平衡旋转：由于在 A的右孩子的右子树上插入新结点,使 A的平衡度由 -1变为 -2,致使以 A为根的子树失去平衡,如图 9.9（ b） 所示 。 此时应进行一次逆时针旋转,,提升,B（ 即 A的右孩子 ） 为新子树的根结点,A下降为 B的左孩子,同时将 B原来的左子树 BL调整为 A的右子树 。
图 9.9 (b)
A -2
B-1
BrBL
AL h
hh
RR型
A 0
B 0
Br
AL BL hh
h
（ 3） LR型平衡旋转：由于在 A的左孩子的右子树上插入新结点，使 A的平衡度由 1变成 2，致使以 A为根的子树失去平衡，如图 9.9（ c）所示。此时应进行两次旋转操作（先逆时针，后顺时针），即“提升” C（即 A
的左孩子的右孩子）为新子树的根结点； A下降为 C的右孩子； B变为 C的左孩子； C原来的左子树 CL调整为 B
现在的右子树； C原来的右子树 Cr调整为 A现在的左子树A 2
B -1
Ar h
BL h
LR型
C
CL h-1 Cr h-1
1
A -1B 0
Ar hBL h CL h-1 Cr h-1
C
0
图 9.9 (c)
（ 4） RL型平衡旋转：由于在 A的右孩子的左子树上插入新结点，使 A的平衡度由 -1变成 -2，致使以 A为根的子树失去平衡，如图 9.9（ d）所示。此时应进行两旋转操作（先顺时针，后逆时针），即,提升,C
（即 A的右孩子的左孩子）为新子树的根结点； A下降 C的左孩子； B变为 C的右孩子； C原来的左子树 CL
调整为 A现在的右子树； C原来的右子树 Cr调整为 B现在的左子树。
B -1A 0
Br hAL h CL h-1 Cr h-1
C
0
A -2
B 1
Br h
AL h RL型
CL h-1 Cr h-1
C
1
图 9.9 (d)
综上所述,在平衡的二叉排序树 t上插入一个新的数据元素 x的算法可描述如下：
（ 一 ） 若 AVL树 t为空树,则插入一个数据元素为 x的新结点作为 t的根结点,树的深度增 1；
（ 二 ） 若 x的关键字和 AVL树 t的根结点的关键字相等,
则不进行插入；
（三）若 x的关键字小于 AVL树 t的根结点的关键字，
则将 x插入在该树的左子树上，并且当插入之后的左子树深度增加 1时，分别就下列不同情况进行分情形处理：
（ 1）若 AVL树的根结点的平衡因子为 -1（右子树的深度大于左子树的深度），则将根结点的平衡因子调整为 0，并且树的深度不变；
（ 2） 若 AVL树的根结点的平衡因子为 0（ 左,右子树的深度相等 ）,则将根结点的平衡因子调整为 1,树的深度同时增 1；
（ 3）若 AVL树的根结点的平衡因子为 1（左子树的深度大于右子树的深度），则当该树的左子树的根结点的平衡因子为 1时需进行 LL型平衡旋转；当该树的左子树的根结点的平衡因子为 -1时需进行 LR型平衡旋转。
（四）若 x的关键字大于 AVL树 t的根结点的关键字，
则将 x插入在该树的右子树上，并且当插入之后的右子树深度增加 1时，需要分别就不同情况进行处理。
其处理操作和（三）中所述相对称，读者可以自行分析。
结点序列（ 120,80,30,90,45,60）逐个插入一棵空的 AVL树的过程如下：
120
0
120
1
80
0
120
2
80
1
30
0
120
0
80
0
30
0
120
1
80
-1
30
0
90
0
120
1
80
0
30
-1
90
0
45
0
120
1
80
0
30
-2
90
0
45
-1
60
0
120
1
80
0
30
0
90
0
45
0
60
0
为实现 Adelson方法,先定义 AVL树的存储结构如下：
/*********************************/
/* AVL树使用的头文件 */
/* 文件名,AVL.H */
/*********************************/
typedef int datatype;
typedef struct node
{ datatype key;
struct node *lchild,*rchild;
int bal; /*结点的平衡度 */
} bsnode;
typedef bsnode *bstree;
算法 9.9 给出了基于 AVL树的结点插入算法习题
9.6 含有 12个节点的平衡二叉树的最大深度是多少
（ 设根结点深度为 0）,并画出一棵这样的树 。
9.7 试用 Adelson插入方法依次把结点值为 60,40,30，
150,130,50,90,80,96,25的记录插入到初始为空的平衡二叉排序树中,使得在每次插入后保持该树仍然是平衡查找树 。 请依次画出每次插入后所形成的平衡查找树 。
9.5最佳二叉排序树和 Huffman树对于具有 n个结点的二叉排序树，在考虑每个结点查找概率的情况下，如何使得整棵树的平均检索效率最高，即使得比较的平均次数最少、代价最小，这与二叉排序树的形状密切相关。假定 n个结点的关键字序列为 k1,k2,…k n,ki对应的使用概率为 P（ ki），
树枝长度为?ki，则对 n个结点构成的二叉排序树其查找成功的平均比较次数为：
ASL= （ 9-9）?
n
i
ii kkp
1
)1)((?
当每个结点具有相同的使用概率，即 P（ ki） =1/n时，
ASL= = （ 9-10）?
n
i
ikn
1
)1(1? )1(1
1
n
i
ikn?
本节讨论如何构造 ASL最小的二叉排序树。
9.5.1扩充二叉树给定一棵二叉树,对树中不足两个孩子的结点
（ 包括叶子结点 ） 都添上附加结点,使每个结点都有两个孩子结点,所得的二叉树称为原二叉树的扩充二叉树,称那些附加的结点为 外部结点,称树中原来的结点为 内部结点 。 对于具有 n个内部结点的二叉树,
其外部结点数为 n+1个 。 图 9.11给出了一棵二叉树及其对应的扩充二叉树,图中圆圈表示内部结点,方框表示外部结点 。
（ a）一棵二叉树 t （ b） t的扩充二叉树对一棵二叉排序树进行扩充后便可得到一棵扩充的二叉排序树（又称为扩充查找树）。对扩充查找树进行中序遍历,最左外部结点 代表码值小于内部结点最小码值的可能结点集； 最右外部结点 代表码值大于内部结点最大码值的可能结点集；而其余外部结点代表码值处于原二叉排序树在中序序列下相邻结点码值之间的可能结点集。
最左外部结点最右外部结点在对扩充二叉查找树进行检索过程中,若检索到达外部结点,则表明相应码值的结点不在原二叉排序树中,故也称外部结点为失败结点 。
若一棵扩充二叉查找树中所有内部结点的树枝长度之和记为 I,所有外部结点的树枝长度之和记为 E。
则对于一个具有 n个内部结点的扩充二叉树,其内部树枝长度 In与外部树枝长度 En存在下列关系：
En=In+2n （ 9-11）
根据式 （ 9-11） 可知,在具有 n个结点的所有二叉树中,具有最大 （ 或最小 ） 内部路枝长度的二叉树也一定是具有最大 （ 或最小 ） 外部路枝长度的二叉树,反之亦然 。
当二叉树退化为线性表时,其内部路枝长度最大,
其值为 In=0+1+2+… +（ n-1） =n（ n-1） /2。 为了得到具有最小 In的二叉树,必须使内部结点尽量靠近根结点 。 由二叉树结构可知,根结点只有一个,路枝长度为 1的结点至多有两个,路枝长度为 2的结点至多为四个,路枝长度为 k的结点至多为 2k个 。 所以 In的最小值为：
In=1x0+2x1+4x2+8x3+…=
n
i
i
1
2log
9.4.1节介绍的平分法构造的丰满树具有最小内部路径长度 。
9.5.2最佳二叉排序树在一棵扩充的二叉排序树中,假设内部结点由序列
（ a1,a2,a3,…,ai,…,an ） 构成,且有
a1<a2<a3… <ai… <an。 外部结点由 （ b0,b1,b2,…,
bi,…,bn） 构成,且有 b0<b1<b2… <bi… <bn。 这里将内部结点 ai的检索概率记为 p（ ai）,简记为 pi
（ 1?i?n） ；外部结点 bi的检索概率记为 qi（ 0?i?n）,
它 们对 应的 树枝 长度分 别记 为 ai （ 1?i?n ） 和 bi
（ 0?i?n）,则成功查找所需的平均比较次数为：
n
i
n
i
iiii apap
1 1
)1()1(?的树枝长度而不成功查找所需的平均比较次数为：
n
i
n
i
iiii bqbq
0 0
)()(?的树枝长度不失一般性，一棵二叉排序树的平均查找长度（代价）为：
ASL= （ 9-18）
n
i
n
j
jjii bqap
1 0
))(())1((
对于 n个有序序列（ a1,a2,a3,…,ai,…,an）
作为内部结点和 n+1个有序序列（ b0,b1,b2,…,
bi,…,bn）作为外部结点构成的所有可能的扩充查找树中，具有最少平均比较次数，即式（ 9-18）取值最小的扩充二叉排序树称为最佳二叉排序树，或最优查找树。
当查找成功与查找失败具有相等概率，即
p1=p2=…=p n=q0=q1=…=1/ （ 2n+1）时，平均检索长度 ASL=
n
i
n
j
jjii bqap
1 0
))(())1((
))()1((12 1
1 0
n
i
n
j
ji ban
=
)(12 1 nn EnIn
)2(
12
1 nInI
n nn
)32(
12
1 nI
n n
=
=
= …… （ 9-19）
由式 （ 9-19） 可知,只要 In取最小值,ASL就达到最小 。
而平分法构造的丰满树具有最小内部路径长度。
In=?
n
i
i
1
2log )lo g()( lo g 22
nn nOn?
此时
ASL= = )32(
12
1 nI
n n )lo g( 2
nnO
所以,在检索成功和不成功具有相等概率的情况下,用平分法构造出来的丰满二叉排序树是最佳二叉排序树 。
现考虑查找概率不相等的情况下如何构造最佳二叉排序树。也就是对于给定的 n个内部结点 a1,a2，
a3,…,ai,…,an和 n+1个外部结点 b0,b1,b2,…,
bi,…,bn，它们对应的查找概率分别是 p1,p2，
p3,…,pi,…,pn及 q0,q1,…,qn，找使得
ASL=
n
i
n
j
jjii bqap
1 0
))(())1((
为最小的二叉排序树 （ 以下我们又称 ASL为二叉排序树的代价 （ 或花费 ）） 。
构造最佳二叉排序树时要满足以下两个要求：同一序列构造的不同二叉排序树应具有相同的中序遍历结果；一棵最佳二叉排序树的任何子树都是最佳二叉排序树 。 因此,构造一棵最佳二叉排序树可以先构造包括一个结点的最佳二叉排序树,再根据包括一个结点的最佳二叉排序树构造包括两个结点的最佳二叉排序树,…,如此进行下去,直到把所有的结点都包括进去 。
为描述构造最佳二叉排序树的算法,这里用 T[i,j]
表示 ai+1,…,aj（ i<j） 组成的一棵最佳二叉排序树,
规定当 0?i?n且 i=j时,T[i,j]为空树 （ 即内部结点为空 ） ；当 i>j时表示 T[i,j]无定义；用 C[i,j]表示查找树
T[i,j]的代价；用 rij表示 T[i,j]的根,用 W[i,j]表示 T[i，
j]的权值,它的值是 T[i,j]中内部结点和外部结点查找概率之和 。 即：
W[i,j]=qi+?
j
ik
kk qp
1
)(
根据最佳二叉排序树的构造要求,其构造过程可以按以下步骤进行：
（ 1） 构造包括一个结点的最佳二叉排序树,也就是
T[0,1],T[1,2],…,T[n-1,n]。
（ 2） 构造包括两个结点的最佳二叉排序树,也就是
T[0,2],T[1,3],…,T[n-2,n]。
（ 3）再构造包括三个，四个,…,n-1个结点的最佳二叉排序树，直到最后构造 T[0,n]。
用（ ai+1,ai+2,…,aj）作为内部结点构造最佳二叉排序树 T[i,j]的方法可如下进行：分别用 ai+1，
ai+2,…,aj为根，共考虑 j-i棵二叉排序树，以 ak为根的二叉排序树其左子树包括 ai+1,…,ak-1，而包括这些关键码为内部结点的最佳二叉排序树 T[i,k-1]已在前面的步骤确定,C[i,k-1]已求出，而以 ak为根的二叉排序树其右子树包括 ak+1,ak+2,…,aj，以这些关键码为内部结点的最佳二叉排序树 T[k,j]也已在前面的步骤确定,C[k,j]已求出。对于 i<k?j，找出使 C[i，
k-1]+C[k,j]最小的那个 k’，以 ak’为根,T[i,k’-1]为左子树,T[k’,j]为右子树的那棵二叉排序树就是所求的 T[i,j]。其花费 C[i,j]等于其根的左子树花费 C[i，
k’-1]加上右子树花费 C[k’,j]，再加上结点总的权 W[i，
j]，即 C[i,j]=W[i,j]+ C[i,k’-1]+ C[k’,j]。
综上所述,T[i,j]是最优查找树必须满足条件：
C[i,j]=W[i,j]+ （ C[i,k-1]+C[k,j]） （ 9-20）min
jki
假设 n=4，且（ a1,a2,a3,a4） =（ 10,18,26，
50）；（ p1,p2,p3,p4） =（ 1,4,3,2），（ q0，
q1,q2,q3,q4） =（ 1,2,3,3,1），试构造出有序序列 a1,a2,a3,a4所组成的最优查找树。
例首先根据式（ 9-20）构造包括一个内部结点的最佳二叉排序树，其花费的代价分别是 C[0,1]=4,C[1，
2]=9,C[2,3]=9和 C[3,4]=6，如图 9.12（ a）所示。
a1
b0
1
1 b
1
2
a2
b1
4
2 b
2
3
a3
b2
3
3 b
3
3
a4
b3
2
3 b
4
1
花费 C[0,1]=4 C[1,2]=9 C[2,3]=9 C[3,4]=6
总权 4 9 9 6
（ a）包括一个内部结点的最佳二叉排序树
a3
3
b3 3a2
b1
4
2 b
2
3
a3
b2
3
3 a
4
b3
2
3 b
4
1
a4 2
b4 1a3
b2
3
3 b
3
3
花费 24 C[2,4]=C[3,4]+12=18 21
总权 15 12 12
（ b）包括二个内部结点的最佳二叉排序树
a1
b0
1
1 a
2
b1
4
2 b
2
3
a2
4
b2 3a1
b0
1
1 b
1
2
a2
b1
4
2 a
3
b2
3
3 b
3
3
花费 20 C[0,2]=C[0,1]+11=15 C[1,3]=C[2,3]+15=24
总权 11 11 15
a1
b0
1
1 a
2
b1
4
2 a
3
b2
3
3 b
3
3
a2
4
a1
b0
1
1 b
1
2
a3
b2
3
3 b
3
3
a3
3
b3 3a2
4
b2 3a1
b0
1
1 b
1
2
花费 41 C[0,3]=C[0,1]+C[2,3]+17=30 32
总权 17 17 17
a2
b1
4
2 a
3
b2
3
3 a
4
b3
2
3 b
4
1
a3
3
a2
b1
4
2 b
2
3
a4
b3
2
3 b
4
1
a4
2
b4 1a2
b1
4
2 a
3
b2
3
3 b
3
3
花费 36 C[1,4]=C[1,2]+C[3,4]+18=33 42
总权 18 18 18
（ c）包括三个内部结点的最佳二叉排序树
a1
b0
1
1 a
3
3
a2
b1
4
2 b
2
3
a4
b3
2
3 b
4
1
a2
4
a1
b0
1
1 b
1
2
a3
b2
3
3 a
4
b3
2
3 b
4
1
花费 53 42
总权 20 20
a3
3
a24
b2 3a1
b0
1
1 b
1
2
a4
b3
2
3 b
4
1
a4
2
b4 1a2
4
a1
b0
1
1 b
1
2
a3
b2
3
3 b
3
3
花费 C[0,4]=C[0,2]+C[3,4]+20=41 50
总权 20 20
（ d）包括四个内部结点的最佳二叉排序树
9.8 结点关键字 k1,k2,k3,k4,k5为一个有序序列，
它们的相对使用频率分别为 p1=6,p2=8,p3=12，
p4=2,p5=16，外部结点的相对使用频率分别为 q0=4，
q1=9,q2=8,q3=12,q4=3,q5=2。试构造出有序序列 k1,k2,k3,k4,k5所组成的最优查找树。
习题对于包括 n个关键码的集合,构造最佳二叉排序树过程中需要进行 C[i,j]（ 0?i<j?n） 的计算次数为：
)(6)1( 3
1
1
0
3
nOnij
n
j
j
i
9.5.3 Huffman树给定 n个结点 k1,k2,…,kn,它们的权分别是 W（ ki）
（ 1?i?n）,现要利用这 n个结点作为外部结点 （ 叶子结点 ） 去构造一棵扩充二叉树,使得带权外部路径长度
n
i
iki kw
1
)(?WPL=
达到最小值，其中 wki为外部结点 ki的权值,?ki是从根结点到达外部结点 ki的树枝长度。具有最小带权外部路径长度的二叉树称为 Huffman树。
例如 4个结点 k1,k2,k3,k4，分别带权 10,16,20，
6。利用它们作为外部结点分别构造了以下三棵扩充二叉树（还有其它形式的扩充二叉树）如图 9.13所示。
（ a） （ b） （ c）
图 9.13 具有不同带权路径长度的扩充二叉树其带权路径长度分别为：
（ a） WPL=52?2=104
（ b） WPL=（ 16+20）?3+20?2+6?1=154
（ c） WPL=（ 10+6）?3+16?2+20?1=100
其中图 9.13（ c）所示的扩充二叉树带权外部路径长度最小，可以验证，它恰为 Huffman树。一般情况下，权越大的叶子离根越近，那么二叉树的带权外部路径长度就越小。在实际的应用中，分支程序的判断流程可用一棵 Huffman树来表示，如果出现概率越大的分枝（条件语句）离根越近，那么所需执行的判断语句就越少，这样便可提高程序的执行效率。
Huffman给出了求具有最小带权外部路径长度的扩充二叉树的方法,通常称为 Huffman算法,该算法可描述如下：
（ 1） 根据给定的 n个权值 {w1,w2,…,wn}构造 n棵二叉树的集合 F={T1,T2,…,Tn},其中每棵二叉树
Ti中只有一个带权为 wi的根结点,其左,右子树均为空 。
（ 2） 在 F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且臵新的二叉树的根结点权值为其左,右子树根结点的权值之和 。
（ 3） 在 F中用新得到的二叉树代替这两棵树 。
（ 4） 重复 （ 2）,（ 3） 过程,直到 F中只含有一棵树为止 。
root? 6? 10? 16? 20? 24? 30
具体实现可以采用有序链表存储结构例如：对于结点序列 10,16,20,6,30,24,构造 huffman树的过程如下：
（ 1）建立有序链表
（ 2）从链表中截取前面二棵根结点权值最小的树作为左右子树，生成一棵新的子树，并将新子树按其根的权值插入有序链表中去，如此循环，直到只剩一棵树为止。
root
6
16 20 24 30
10
161
root
6
16
20 24 30
10
16
322
root
6
16 20 24
30
10
16
32 443
root
6
16
20 24 30
10
16
32
44 624
root
6
16
20 24 30
10
16
32
44 62
1065
6
16
20 24 30
10
16
32
44 62
106
a b
c
d e f
0 1
1
1
1
10 0
0
0
Huffman 树的应用
1,Huffman编码各字符的二进制编码为：
a,1100 b,1101 c,111 d,00 e,01 f,10
从二叉树的根开始,用需要译码的二进制位串中的若干个相邻位与二叉树边上标的 0,1相匹配,确定一条到达树叶的路径,一旦到达树叶,则译出了一个字符,再回到树根,从二进制位串的下一位开始继续译码 。
2,huffman译码
9.10假设通讯电文中只用到 A,B,C,D,E,F六个字母，它们在电文中出现的相对频率分别为,8,3，
16,10,5,20，试为它们设计 Huffman编码。
习题
9.6 B-树前面所讨论的查找算法都是在内存中进行的,它们适用于较小的文件,而对较大的,存放在外存储器上的文件就不合适了 。
1972年 R.Bayer和 E.M.McCreight提出了一种称为 B-树的多路平衡查找树，它适合在磁盘等直接存取设备上组织动态的查找表。
9,6,1 B-树的定义
B-树是一种平衡的多路查找树,在文件系统中,已经成为索引文件的一种有效结构,并得到泛的应用 。
在此先介绍这种树的结构及其基本运算 。
一棵 m阶 （ m?3） B-树,或为空树,或为满足下列特性的 m叉树：
（ 1） 树中每个结点至多有 m棵子树；
（ 2） 若根结点不是叶子结点,则至少有两棵子树；
（ 3） 所有的非终端结点中包含下列信息
（ n,p0,k1,p1,k2,p2,…,kn,pn）
其中,ki（ 1?i?n） 为关键字,且 ki<ki+1（ 1?i?n） ； pj
（ 0?j?n） 为指向子树根结点的指针,且 pj（ 0?j<n） 所指子树中所有结点的关键字均小于 kj+1,pn所指子树中所有结点的关键字均大于 kn,n（?m/2?-1?n?m-1） 为关键字的个数 （ n+1为子树个数 ） 。
（ 4） 除根结点之外所有非终端结点至少有?m/2?棵子树,也即每个非根结点至少应有?m/2?-1个关键字；
（ 5） 所有的叶子结点都出现在同一层上,并且不带信息 （ 可以看作是外部结点或查找失败的结点,实际上这些结点不存在,指向这些结点的指针为空 ） 。
2 50 80
root
1^60^1^53^1^43^1^22^ 1^97^1^88^1^75^
2 20 40 2 55 70 1 90
2^10^19^
例,一棵 3阶的 B-树
9,6,2 B-树的基本操作一,基于 B-树的查找运算
2 50 80
root
1^60^1^53^1^43^1^22^ 1^97^1^88^1^75^
2 20 40 2 55 70 1 90
2^10^19^
二,基于 B-树的插入运算在 B-树中插入关键字 k的方法是：首先在树中查找
k，若找到则直接返回（假设不处理相同关键字的插入）；否则查找操作必失败于某个叶子结点上，利用函数 btree_search（）的返回值 *p及 *pos可以确定关键字 k的插入位臵，即将 k插入到 p所指的叶结点的第
pos个位臵上。若该叶结点原来是非满（结点中原有的关键字总数小于 m-1）的，则插入 k并不会破坏 B-树的性质，故插入 k后即完成了插入操作，例如，在图
9.17（ a）所示的 5阶 B-树的某结点（假设为 p结点）
中插入新的关键字 150时，可直接得到图 9.17（ b）所示的结果。
2 100 190 3 100 150 190
图 9.17在关键字个数不满的结点中插入关键字若 p所指示的叶结点原为满，则 k插入后 keynum=m，
破坏了 B-树的性质（ 1），故须调整使其维持 B-树的性质不变。调整的方法是将违反性质（ 1）的结点以中间位臵的关键字 key[?m/2?]为划分点，将该结点（即 p）
（ m,p0,k1,p1,…,km,pm）
分裂为两个结点，左边结点为（?m/2?-1,p0，
k1,…k?m/2?-1,p?m/2?-1），右边结点为（ m-?m/2?，
p?m/2?,k?m/2?+1,…,km,pm），同时把中间关键字
k?m/2?插入到双亲结点中。于是双亲结点中指向被插入结点的指针 pre改成 pre,k?m/2?,pre’三部分。指针 pre
指向分裂后的左边结点，指针 pre’指向分裂后的右边结点。由于将 k?m/2?插入双亲时，双亲结点亦可能原本为满，若如此，则需对双亲做分裂操作。分裂过程的例子如图 9.18所示。
2 … 80 220…
4 90 120 140 160
p
3 … 80 120 220 …
2 90 100 2 140 160
pre pre pre’
k?m/2?
插入 100
以前插入 100
以后如果初始时 B-树为空树，通过逐个向 B-树中插入新结点，可生成一棵 B-树。图 9.19说明了一棵 5阶 B-树的生长过程。
6 8 15 16
6 8
15
16 22 6 8 10
15
16 18 22 32
（ a）插入 6,8,15,16 （ b）插入 22 （ c）插入 10,18,32
6 8 10
15 20
16 18 22 32 6 8 10 12
15 20
16 18 19 22 32 40 50 6 8 10 12
15 20 40
16 18 19 22 32 50 56
（ d） 插入 20 （ e） 插入 12,19,40,50 （ f） 插入 56
6 8
9 15 20 40
16 18 19 22 26 32 36 50 52 55 5610 12 6 8
9 15
16 18 19 22 26 50 52 55 5610 12 36 38
20
32 40
（ g） 插入 9,26,36,52,55 （ h） 插入 38
三、基于 B-树的删除运算在 B-树上删除一个关键字，首先找到该关键字所在结点及其在结点中的位臵。具体可分为两种情况：
（ 1）若被删除结点 ki在最下层的非终端结点（即叶子结点的上一层）里，则应删除 ki及它右边的指针 pi。删除后若结点中关键字数目不少于?m/2?-1，则删除完成，否则要进行“合并”结点的操作。
（ 2）假若待删结点 ki是最下层的非终端结点以上某层的结点，根据 B-树的特性可知，可以用 ki右边指针 pi
所指子树中最小关键字 y代替 ki，然后在相应的结点中删除 y，或用 ki左边指针 pi-1所指子树中最大关键字 x代替 ki，然后在相应的结点中删除 x。例如删除图 9.20
（ a）所示 3阶 B-树中的关键字 50，可以用它右边指针所指子树中最小关键字 60代替 50，尔后转化为删除叶子上面一层的结点中的 60，删除后得到的 B-树如图
9.20（ b）所示。
90 1158 40
28
150 200
85 120
50
60 80
90 1158 40
28
150 200
85 120
60
80
3阶 B-树中删除 50
以 60代替 50
因此，下面主要讨论删除 B-树叶子上面一层结点中的关键字的方法，具体分三种情形：
1）被删关键字所在叶子上面一层结点中的关键字数目不小于?m/2?，则只需要从该结点中删去关键字 ki和相应的指针 pi，树的其它部分不变。
例：
908 40
28
150 200
85 120
50
80 90 11560 80
删除 60与
115
2）被删关键字所在叶子上面一层结点中的关键字数目等于?m/2?-1，而与该结点相邻的右兄弟结点（或左兄弟结点）中的关键字数目大于?m/2?-1，则需要将其右兄弟的最小关键字（或其左兄弟的最大关键字）移至双亲结点中，而将双亲结点中小于（或大于）该上移关键字的关键字下移至被删关键字所在的结点中。例如从图 9.21（ b）中删除关键字 90，结果如图 9.21（ c）所示。
1208 40
28
200
85 150
50
80 90 150 200
2
80
删除 90
3）被删关键字所在叶子上面一层结点中的关键字数和其相邻的兄弟结点中的关键字数目均等于?m/2?-1，
则第（ 2）种情况中采用的移动方法将不奏效，此时须将被删关键字所有结点与其左或右兄弟合并。不妨设该结点有右兄弟，但其右兄弟地址由双亲结点指针
pi所指，则在删除关键字之后，它所在结点中剩余的关键字和指针加上双亲结点中的关键字 ki一起合并到 pi
所指兄弟结点中（若没有右兄弟，则合并至左兄弟结点中）。
例如，从图 9.21（ c）中删去关键字 120，则应删去 120
所在结点，并将双亲结点中的 150与 200合并成一个结点，删除后的树如图 9.21（ d）所示。如果这一操作使双亲结点中的关键字数目小于?m/2?-1，则依同样方法进行调整，最坏的情况下，合并操作会向上传播至根，
当根中只有一个关键字时，合并操作将会使根结点及其两个孩子合并成一个新的根，从而使整棵树的高度减少一层。
1208 40
28
200
85 150
50
80
删除 120
150 200
85
例如，在图 9.21（ d）中删除关键字 8，此关键字所在结点无左兄弟，只检查其右兄弟，然而右兄弟关键字数目等于?m/2?-1，此时应检查其双亲结点关键字数目是否大于等于?m/2?-1，但此处其双亲结点的关键字数目等于?m/2?-1，从而进一步检查双亲结点兄弟结点关键字数目是否均等于?m/2?-1，这里关键字 28所在的结点的右兄弟结点关键字数目正好等于?m/2?-1，因此将
28和 40结合成一个结点,50和 85结合成一个结点，使得树变矮，删除结点 8后的结果如图 9.21（ e）所示。
8 40
28
150 200
85
50
80
删除 8
28 40 150 20080
50 85
习题
9.11含有 9个叶子结点的 3阶 B-树中至少有多少个非叶子结点？ 含有 10个叶子结点的 3阶 B-树中至少有多少个非叶子结点？
9.13用依次输入的关键字 23,30,51,29,2 7,15、
11,17和 16建一棵 3阶 B-树,画出建该树的变化过程示意图 （ 每插入一个结点至少有一张图 ） 。
9.7散列表检索在已经介绍过的线性表、树等数据结构中，记录存储在结构中的相对位臵是随机的，因而相应的检索是通过若干次的比较以寻找指定的记录。本节将介绍一种新的存储结构 ——散列存储，它既是一种存储方式，又是一种常见的检索方法。
9.7.1散列存储散列存储的基本思想是以关键码的值为自变量，
通过一定的函数关系（称为散列函数，或称 Hash
函数），计算出对应的函数值来，以这个值作为结点的存储地址，将结点存入计算得到的存储单元里去。
U
S
k1k
2
k3
k5
k4
0
H(k1)
H(k5)
H(k2)=H(k4)
H(k3)
H(km-1)
图 9.22 散列过程示例散列存储中经常会出现对于两个不同关键字 xi,xjS，
却有 H（ xi） =H（ xj），即对于不同的关键字具有相同的存放地址，这种现象称为冲突或碰撞。碰撞的两个（或多个）关键字称为同义词（相对于函数 H而言）。
“负载因子”?反映了散列表的装填程度，其定义为：
= 散列表中结点的数目基本区域能容纳的结点数当?>1时冲突是不可避免的 。 因此,散列存储必须考虑解决冲突的办法 。
综上所述,对于 Hash方法,需要研究下面两个主要问题：
（ 1） 选择一个计算简单,并且产生冲突的机会尽可能少的 Hash函数；
（ 2） 确定解决冲突的方法 。
9.7.2散列函数的构造
（ 1）除余法
H（ key） =key％ p
例如 S={5,21,65,22,69},若 m=7且 H（ x） =x %
7,则可以得到如表 9.1所示的 Hash表 。
0 1 2 3 4 5 6
21 22 65 5 69
表 9.1 散列表示例
（ 2）平方取中法取关键字平方后的中间几位为 Hash地址,所取的位数和 Hash地址位数相同 。 这是一种较常用的构造 Hash函数的方法 。 因为通常在选定 Hash函数时不一定能知道关键字的全部情况,难以决定取其中哪几位比较合适,而一个数平方后的中间几位数和数的每一位都相关,由此使随机每布的关键字得到的
Hash地址也是随机的 。
（ 3） 数字分析法对于关键字的位数比存储区域的地址码位数多的情况,可以采取对关键字的各位进行分析,丢掉分布不均匀的位留下分布均匀的位作为 Hash地址,这种方法称为数字分析法 。
Key H（ key）
0 1 9 4 2 8 3 2 432
0 1 5 7 9 8 8 5 785
0 1 9 5 9 0 1 3 513
0 1 2 8 1 5 3 8 838
0 1 9 2 1 8 2 7 227
0 1 7 1 1 8 4 6 146
（ 4） 折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）
作为 Hash地址，称为折叠法。关键字位数很多且关键字中每一位上数字分布大致均匀时，可以采用折叠法得到 Hash地址。
在折叠法中数位叠加可以有移位叠加和间界叠加两种方法 。 移位叠加是将分割后的每一部分的最低位对齐,然后相加；间界叠加是从一端向另一端沿分割界来回折迭,然后对齐相加 。 如关键码为 7-302-
03806-6,若 Hash地址取 4位,则此关键字的 Hash地址采用折叠法得到如图 9.23所示的结果 。
8006 8006
0203 3020
+ ) 073 +) 073
8282 11099
H（ key） =8282 H（ key） =1099
（ a） 移位叠加 （ b） 间界叠加图 9.23 由折叠法求得 Hash地址
（ 5） 直接地址法取关键字或关键字的某个线性函数值为哈希地址,即：
H（ key） =key或 H（ key） =a·key+b
9.7.3冲突处理
1,开放定址法开放定址法的基本做法是在发生冲突时,按照某种方法继续探测基本表中的其它存储单元,直到找到一个开放的地址 （ 即空位臵 ） 为止 。 显然这种方法需要用某种标记区分空单元与非空单元 。
开放定址法的一般形式可表示为：
Hi（ k） =（ H（ k） +di） mod m（ i=1,2,…,k（ k?m-1））
其中,H（ k） 为键字为 k的直接哈希地址,m为哈希表长,di为每次再探测时的地址增量 。
当 di=1,2,3,…,m-1时,称为线性探测再散列；
当 di=12,-12,22,-22,…,k2,-k2（ k?m/2） 时,称为二次探测再散列；当 di=随机数序列时,称为随机探测再散列 。
例如，有数据（ 654,638,214,357,376,854，
662,392），现采用数字分析法，取得第二位数作为哈希地址，将数据逐个存放入大小为 10的散列表
（此处为顺序表）中。若采用线性探测法解决地址冲突，则 8个数据全部插入完成后，散列表的状态如表 9.2所示。
392 214 638 654 357 376 854 662
0 1 2 3 4 5 6 7 8 9
2,再哈希法采用再哈希法解决冲突的做法是当待存入散列表的某个元素 k在原散列函数 H（ k）的映射下与其它数据发生碰撞时，采用另外一个 Hash函数 Hi（ k）（ i=1，
2,…,n）计算 k的存储地址（ Hi均是不同的 Hash函数），这种计算直到冲突不再发生为止。
3,拉链法拉链法解决冲突的做法是，将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为
m，则可将散列表定义为一个由 m个头指针组成的指针数组 T[0..m-1]，凡是散列地址为 i的结点，均插入到以 T[i]为头指针的单链表中。
拉链法的缺点主要是指针需要用额外的空间,故当结点规模较小时,开放定址法较为节省空间 。
例如,关键字集合为 {1,13,20,5,14,33}，
散列表长度 m=5,现采用除余法为哈希函数并采用拉链法解决地址冲突,所创建的 Hash链表如图 9.24所示 。
t[0]
t[1]
t[2]
t[3]
t[4]
5
1 ^
20 ^
33 13 ^
14 ^
^
除了上述三种方法外,还有差值法可解决地址冲突 。
这种方法在发生冲突时,处理原则以现在的数据地址加上一个固定的差值,当数据地址超出数据大小时,
则让数据地址采用循环的方式处理 。 另外,还可以建立一个公共溢出区的方法去解决冲突 。 即 m个 Hash地址用数组 t[0..m-1]表示,称此表为基本表,每一个分量存放一个关键字,另外设立一个数组 v[0..n]为溢出表 。
若关键字和基本表中关键字为同义词,不管它由 Hash
函数得到的 Hash地址是什么,一旦发生冲突,都填入溢出表 。
假设负载系数为?,则：
（ 1） 如果用开放定址线性探测再散列法解决冲突,
Hash表查找成功和查找不成功的平均查找长度 Sn和 Un
分别为：
Sn Un
)1 11(21 ))1( 11(21 2
（ 2） 如果用二次探测再散列解决冲突,Hash查找成功和查找不成功的平均查找长度 Sn和 Un分别为：
)1ln (1
)1(
1
Sn Un
（ 2） 如果用拉链法解决冲突,Hash表查找成功和查找不成功的平均查找长度 Sn和 Un分别为：
2
1
e
Sn Un
习题
9.14设散列表长度为 11,散列函数 H（ x） =x % 11，
给定的关键字序列为,1,13,12,34,38,33,27，
22。 试画出分别用拉链法和线性探测法解决冲突时所构造的散列表,并求出在等概率的情况下,这两种方法查找成功和失败时的平均查找长度 。
9.15设散列表为 T[0..12],即表的大小 m=13。 现采用再哈希法 （ 双散列法 ） 解决冲突 。 散列函数和再散列函数分别为：
H0（ k） =k % 13、
Hi=（ Hi-1+REV（ k+1） %11+1） %13； i=1,2,…,m-1
其中,函数 REV（ x） 表示颠倒 10进制数的各位,如
REV（ 37） =73,REV（ 1） =1等 。 若插入的关键码序列为 {2,8,31,20,19,18,53,27}。
（ 1） 试画出插入这 8个关键码后的散列表 。
（ 2） 计算检索成功的平均查找长度 ASL。
