第九章查找
9.1.基本概念
9.2顺序表
9.2.1顺序查找
9.2.2二分法查找
9.2.3分块查找
9.3散列表
9.3.1概述
9.3.2散列函数的构造方法
9.3.3处理冲突的方法
9.3.4散列表的性能分析
9.4,树表
9.4.1 二叉排序树
9.4.2 平衡的二叉排序树
9.4.3 B－树
小结
◆ 查找表,由同一类型的数据元素（记录）组成的集合，
可以由任意的数据结构实现 。
9.1 基本概念
◆ 查找表的操作：（ 1）查询某个“特定的”数据元素
是否在查找表中；（ 2）查找某个“特定的”数据元素的
属性；（ 3）在查找表中插入一个数据元素；（ 4）从查找
表中删除某个数据元素。
◆ 静态查找表,若对查找表只作前两种操作，此类查找表
称静态查找表。
◆ 动态查找表,若在查找过程中同时插入查找表中不存在
的数据元素，或者从查找表中删除已经存在的某个数据元
素,此类查找表为动态查找表。
◆ 关键字：数据元素中某个数据项的值，用它可以标
示查找表中的一个数据元素。主关键字可以唯一地标
识一个记录，次关键字用以识别若干记录。
◆ 查找：就是根据给定的关键字值，在特定的查找表
中确定一个其关键字与给定值相同的数据元素，并返
回该数据元素在查找表中的位置。如果找到数据元素，
则称查找成功，否则查找失败。
◆ 平均查找长度, 为了确定数据元素在查找表中的位
置需要和给定值进行比较的关键字个数期望值，称为
查找算法在查找成功时的平均查找长度。
?对于长度为 n的查找表，查找成功的平均查找长度为：
?其中 Pi为查找表中第 i个数据元素的概率,Ci为找到
查找表中第 i个元素时，已经进行的比较次数。由于
查找算法的基本元素是关键字之间的比较操作，所以
可以平均查找长度来衡量查找算法的性能。
9.2顺序表
顺序表中相邻的两个记录 Ri和 Ri+1在存储器中
的物理位置也是相邻的，因此存储结构采用的
是顺序结构。
顺序结构有关 C++语言描述的数据类型定义,
（为了简单起见，我们假设记录的排序码为整
型，在本章以后讨论的顺序表中均采用这样的
向量存储结构）
?顺序表的查找方法分为顺序查找法、二分法
（折半）查找法以及分块（索引）查找法。
#define maxn 30 // 文件中最大记录数
typedef struct
{ int key; // 假设记录排序码为整数
char *other; // 记录中其它信息域，暂不用
} record;
typedef record recordfile[maxn];
9.2.1顺序查找
顺序查找（ sequential search)用待查的关键字值与线
性表里各结点的关键字值逐个比较，
?查找第 n个元素,比较次数 1 查找第 n-1个元素,比较次数 2
………,查找第 1个元素,比较次数 n
查找第 i个元素,比较次数 n+1-i 查找失败, 比较次数 n+1
443211237669875676
0 1 2 3 4 5 6 7 8
监视哨
查
找
76 ↑i↑i↑i↑i
↑i
查找次数＝ 5
int seqserch(recordfile r,int k,int n)
//k为给定值,n为表长 ;
//返回 0表明查找不成功,否则返回关键字等于 k的
记录在表 r中的序号,
{ int i=n;
r[0].key=k;
while(r[i].key!=k) i--;
return i;}
顺序查找的算法,查找前对结点之间并没有排序
要求,用 C++语言描述的顺序查找算法如下,
在此算法中，查找之前，先对 r[0]的关键字赋值
为 k，目的在于免去查找过程中每一步都要检测
整个表是否查找完毕。在此 r[0]起了监视哨的作
用
这种改进能使顺序查找在 n≥1000 时进行一次查
找所需要的平均时间几乎减少一半，从而提高查
找效率。
?顺序查找方法的 ASL：
??有 n个记录的表，查找成功时的平均查找长度为
??假设每个记录的平均查找概率相等即,Pi = 1/n 。
。
在顺序查找时,ci取决于所查记录在表中的位
置。如查找记录 r[n]时，仅需比较一次，而查
找记录 r[1]时，则需比较 n次。一般地,ci=n-
i+1。故顺序查找的平均查找长度为,
ASL = np1 +(n-1)p2 + … + 2p n-1 + pn 。
顺序查找法和后面将要讨论的其它查找法相比,
其缺点是平均查找长度较大, 特别是当 n 很大时,
查找效率低 。 然而, 它有很大的优点：算法简单
且适用面广 。 它对表的结构无任何要求, 无论记
录是否按关键字有序均可应用, 而且上述所有讨
论对线性链表也同样适用 。
算法 的评价
9.2.2二分法查找
查找过程：每次将待查记录所在区间缩小一半，
适用条件：采用顺序存储结构的有序表
?算法实现,
设表长为 n,low,high和 mid分别指向待查元素所在区间的上
界、下界和中点,k为给定值
初始时，令 low=1,up=n,mid=?(low+up)/2?
让 k与 mid指向的记录比较
若 k==r[mid].key,查找成功
若 k<r[mid].key,则 up=mid-1
若 k>r[mid].key,则 low=mid+1
重复上述操作，直至 low>up时，查找失败
958980756356342119155
1 2 3 4 5 6 7 8 9 10 11
例：查找 21
↑low ↑up↑mid
?(1+11)/2?=6
958980756356342119155
1 2 3 4 5 6 7 8 9 10 11
↑low ↑mid
?(1+5)/2?=3
↑up
958980756356342119155
1 2 3 4 5 6 7 8 9 10 11
low ↑↑mid
?(4+5)/2?=4
↑up
958980756356342119155
1 2 3 4 5 6 7 8 9 10 11
例：查找 83
↑low ↑up↑mid
?(7+11)/2?=9
958980756356342119155
1 2 3 4 5 6 7 8 9 10 11
low↑↑mid
?(10+11)/2?=10
↑up
958980756356342119155
1 2 3 4 5 6 7 8 9 10 11
↑ lowup ↑
Up <low 查找
失败
int bins(recordfile r,int K,int n) //二分查找
{ int l=1,u=n,m; // 置区间初值
while(l<=u)
{ m=(l+u)/2;
if(K>r[m].key) l=m+1; // 修改下界 l 值
else if(K<r[m].key) u=m-1; // 修改上界 u值
else return m; // 查找成功
}
return 0; // 脱离 while,则 l>u 查找不成功
}
二分查找的算法用 C++语言描述如下
判定树：描述查找过程的二叉树叫判定树。有 n个结点
的判定树的深度为 ?log2n?+1 ； 二分查找成功时比较次
数最多不超过树的深度 ；二分查找在查找不成功时和关
键字比较的次数最多不超过 ?log2n? +1；
算法查找的性能
二分 查找的 ASL
表的长度为,n=2h-1(h=log2(n+1))
每个元素的查找概率相等 Pi=1/n
平均查找长度,
二分查找的效率比顺序查找高, 但二分查找只能适用于
有序表, 且存储结构仅限于向量 （ 对线性链表无法进行
折半查找 ）, 当表经常需要插入或删除一个元素时, 就
需要来回移动元素 。 因此, 折半查找方法适用于不经常
变动而查找频繁的有序列表 。
算法 的评价
将查找表分成若干个块（子表）块内无序，但块与块
之间应有序构造一个索引表。其中每个索引项对应一
个块并记录每个块的起始位置，以及每块中的最大关
键字（或最小关键字）。索引表按关键字有序排列
9.2.3分块查找
查找过程：先根据索引表确定待查记录所在块，再在
块内顺序查找
适用条件：分块有序表
例：查找 37
754522
477558614826374542330809151222
查找表
索引表
平均查找长度为,
Lb为查找索引表确定所在块的平均查找长度,Lw为在块
中查找元素的平均查找长度 。
长度为 n的表分成 b块，每块含有 s个记录，即 b= n/s ；
表中每个记录的查找概率相等，则每块查找的概率为 1/b，
块中每个记录的查找概率为 1/s
用顺序查找确定所在块，则平均查找长度为：
用二分查找确定所在块，则查找长度为：
分块查找的优点是,在线性表中插入或删除一个结点时,
只要找到该结点应属的块, 然后在块内进行插入和删除
运算, 由于块内结点的存放是任意的, 所以插入或删除
比较容易, 不需要移动大量的结点 。 分块查找的主要代
价是增加一个辅助数组的存储空间和将初始线性表分块
排序的运算 。 另外当大量的插入和删除运算使块中的结
点数分布不均匀时, 查找速度会下降 。
算法 的评价
基本思想：在记录的存储地址和它的关键字之间建立
一个确定的对应关系；这样，不经过比较，一次存取
就能得到所查元素的查找方法。
9.3散列表
9.3.1 概述
散列表定义：
记录的存储位置和它的关键字之间建立一个确定的对
应关系 h，使每个关键字和结构中一个唯一的存储位置
相对应。查找时，根据 h找到给定值 k的映象 h(k)，若
结构中存在关键字和 k相等的记录，则必定在 h(k)的存
储位置上。我们称这个对应关系 h为散列（ Hash）函
数用散列函数建立的表称为散列表。
例如, 一张全国各地区的各民族人口统计表
上海2
北京1
·······回族汉族总人数地区名编号 满族
以编号作关键字，
构造 哈希函数,H(key)=key
H(1)=1
H(2)=2
特征位抽取法
构造：抽取关键字中某几位随机性较好的数位，然后把
这些数位拼接起来作为散列地址。
9.3.2 散列函数的构造方法
直接定址法
构造：取关键字或关键字的某个线性函数作哈希地址，
即 H(key)=key 或 H(key)=a·key+b
特点：直接定址法所得地址集合与关键字集合大小相等，
不会发生冲突。实际中能用这种哈希函数的情况很少。
分析,?只取 8
?只取 1
?只取 3,4
?只取 2,7、
5
????数字
分布近乎随机
所以：取 ????任
意两位或两位
与另两位的
叠加作散列
地址
平方取中法
构造：取关键字平方后中间几位作哈希地址适用
于当无法确定关键字中哪几位分布比较均匀时
K的内部编码为 11,E的内部编码为 05,Y的内部编码
为 25,A的内部编码为 01,B的内部编码为 02。关键字
,KEYA‖的内部代码为 11052501，同理得到关键字
,KYAB‖、,AKEY‖的内部编码，然后进行对关键
字平方运算，取出第 7到第 9位作为该关键字的散列地
址
关 键 字 内 部 编 码 内 部 编 码 的 平 方 值 散 列 地 址
K E Y A 1 1 0 5 2 5 0 1 1 2 2 1 5 7 7 7 8 3 5 5 0 0 1 7 7 8
K Y A B 1 1 2 5 0 1 0 2 1 2 6 5 6 4 7 9 5 0 1 0 4 0 4 7 9 5
A K E Y 0 1 1 1 0 5 2 5 0 0 1 2 3 3 2 6 5 7 7 5 6 2 5 2 6 5
表 9, 2 平 方 取 中 法 的 散 列 地 址
折叠法构造：
将关键字分割成位数相同的几部分，然后取这几部分的
叠加和（舍去进位）做散列地址移位叠加：将分割后的
几部分低位对齐相加间界叠加：从一端沿分割界来回折
送，然后对齐相加适于关键字位数很多，且每一位上数
字分布大致均匀情况如国际标准图书编号 0-442-20586-
4采用这两种折叠法求得的散列地址分别如下所示：
5 8 6 4
4 2 2 0
0 4
1 0 0 8 8
H(key)=0088
移位叠加
5 8 6 4
0 2 2 4
0 4
6 0 9 2
H(key)=6092
间界叠
加
除留余数法构造：
取关键字被某个不大于散列表表长 m的数 p除后所得余数
作散列地址，即 H(key)=key MOD p,m特点：简单、
常用，可与上述几种方法结合使用
表 （ 18,75,60,43,54,90,46） m=p=13
0 1 2 3 4 5 6 7 8 9 10 11 12
18 75604354 9046
H（ 18）＝ 18 ％ 13＝ 5 H（ 75）＝ 75 ％ 13＝ 10
H（ 60）＝ 60 ％ 13＝ 8 H（ 43）＝ 43 ％ 13＝ 4
H（ 54）＝ 54 ％ 13＝ 2 H（ 90）＝ 90 ％ 13＝ 12
H（ 46）＝ 46 ％ 13＝ 7
随机数法
构造：取关键字的随机函数值作散列地址，即
H(key)=random(key)
适于关键字长度不等的情况
选取散列函数，考虑以下因素：
⑴ 计算散列函数所需的时间 ( 包括硬件指令的因素 )；
⑵ 关键字的长度；
⑶ 散列表的大小；
⑷ 关键字的分布情况；
⑸ 记录的查找频率
1、开放定址法：
方法：当冲突发生时，形成一个探查序列；沿此序列逐
个地址探查，直到找到一个空位置（开放的地址），将
发生冲突的记录放到该地址中，即 Hi=(H(key)+di)MOD
m,i=1,2,……k(k m-1)
其中,H(key)——散列函数 m——散列表表长 di——增量序列
9.3,3 处理冲突的方法
分类：
线性探测再散列,di=1,2,3,……m -1
二次探测再散列,di=12,-12,22,-22,32,…… ± k2(k≤m/2)
伪随机探测再散列,di=伪随机数序列
例 表长为 16的散列表中已填有关键字为 19,70,33和 38
的记录,H(key)=key MOD 13,
现有第五个记录，其关键字为 25,H(25)=12
38331970
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
冲突
25
不冲突线性探测再散列
插入第六个记录，其关键字为 18,H(18)=5
冲突
线性探测再散列
冲突 冲突 不冲突
18
用二次探测
再散列
不冲突
伪随机探测
再散列
不冲突
1818
2、再散列法
方法：构造若干个散列函数，当发生冲突时，计算下一
个散列地址，即,Hi=Rhi(key) i=1,2,……k
其中,Rhi——不同的散列函数。
特点：计算时间增加。
3、链地址法：
方法：将所有关键字为同义词的记录存储在同一线性链
表中并用一维数组存放头指针
用链地址法解决冲突的散列造表算法,
#include <iostream.h>
#define listlen 13
struct record
{ int key;
record *next;
};
typedef record RECF[listlen];
int modh (int ); //Hash函数 (除留余数法 )
void chainh(int,RECF,int (*hash)(int ));
prhashlist(RECF ); //输出散列表
void main(void)
{ int i,x; RECF r;
for(i=0;i<listlen;i++){ r[i].key=0; r[i].next=NULL; }
cin>>x;
while(x){ chainh(x,r,modh); cin>>x; }
prhashlist(r);
}
// 其中参数 int(*hash)(int)是指向函数的指针，它返回一
个整数（散列地址）
//用链地址法解决冲突的散列造表算法
//根据 (*hash)函数造散列表
void chainh(int k,RECF r,int (*hash)(int))
{ int addr; record *p,*q; //用链地址法解决冲突
addr=(*hash)(k);
if (!r[addr].key)r[addr].key=k;
else if(r[addr].key!=k)
{p=r[addr].next; q=&r[addr];
while(p && p->key!=k) { q=p; p=p->next; }
if(!p){ p=new record; p->key=k; p->next=NULL;
q->next=p; }
}
}
int modh (int k) //Hash函数 (除留余数法 )
{ return(k % listlen); }
prhashlist(RECF r) //输出散列表
{ int i; record *p;
cout<<"no.\tkey\t link\n";
for(i=0;i<listlen;i++)
{ if(!r[i].key) cout<<i<<"\t\t^\n";
else{ cout<<i<<"\t"<<r[i].key<<"\t-->";
p=r[i].next;
while(p){ cout<<p->key<<"-->"; p=p->next; }
cout<<"^"<<endl; }}}
Λ
Λ
Λ
Λ
Λ
Λ
0
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
4 0
4 2 Λ
1 6
5 3
3 2
7 1 Λ
4 6 Λ
3 6
2 4 Λ
6 4 Λ
2 7 Λ
4 9 Λ
比 较 次 数 1 2 3
图 9, 7 链 地 址 法 处 理 冲 突 时 的 散 列 表
例：已知一组关键字（ 32,40,36,53,16,46,71,27,42，
24,49,64），散列表表长为 13，散列函数为 H（ key）＝ key％
13，则用链地址法处理冲突的结果
散列查找过程仍是一个给定值与关键字进行比较的过程
评价散列查找效率仍要用 ASL
散列查找过程与给定值进行比较的关键字的个数取决于：
1、散列函数
2、处理冲突的方法
3、散列表的填满因子 ?=表中填入的记录数 /散列表长度
9.3.4 散列表性能分析
已有散列表 a[16]如图所示（上面是地址，最下一行是插
入 /查找某记录所需的关键字比较次数）,Hash函数
H(key)=key ? 13，处理冲突用二次探测再散列
27 14 01 68 55 84 19 20 10 23 11 79
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
3 1 2 1 2 3 1 1 3 1 1 5
图 9,8 散列表 a [ 1 6 ]
下
标
检索次数
平均查找长度分别为, ASL=(1*6+2*2+3*3+5)/12=2
用链地址法处理冲突的散列表
平均查找长度为, ASL=(1*7+2*4+3)/12=1.5
Λ
Λ
Λ
Λ
Λ
Λ
0
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
4 0
4 2 Λ
1 6
5 3
3 2
7 1 Λ
4 6 Λ
3 6
2 4 Λ
6 4 Λ
2 7 Λ
4 9 Λ
比 较 次 数 1 2 3
图 9, 7 链 地 址 法 处 理 冲 突 时 的 散 列 表
α =表中的记录数 /表长
直观地看,α 越小，发生冲突的可能性就越小； α 越大，
即表越满，发生冲突的可能性就越大，查找时所用的比
较次数就越多。因此散列表查找成功的平均查找长度 Sn
和 α 有关。
在线性探测再散列时,Snl≈(1+1/(1-α))/2
在伪随机探测再散列，二次探测再散列及再散列时：
Snr≈-Ln(1-α)/α
在链地址法中,Snc≈1+α/2
二叉排序树又称为二叉查找树，它是一种特殊结构的
二叉树，其定义为：二叉排序树或者是一个空树，
或是具有下面性质的二叉树
1、若它的左子树非空，则左子树上所有结点的值均小
于根结点的值；
2、若它的右子树非空，则右子树上所有结点的值均大
于根结点的值；
3、它的左右子树也分别为二叉排序树。
9.4 树表
9.4.1 二叉排序树
二叉排序树的一个重要性质：中序遍历一个二叉排序树
时可以得到一个递增有序序列。上图所示二叉树是个二
叉排序树。若中序遍历，得到一个递增的有序序列,1，
2,3,4,5,6,7,8,9。
6
8
5
2
7
41
9
3
(a )关键 字为整数的二叉排序树
二叉排序树的操作中，使用二叉链表作为存储结构，其
结点说明如下：
//treenode.h
#define NULL 0
template<class T> class TreeNode //声明二叉树结点类
{public:
T data;
TreeNode<T>* lchild;
TreeNode<T>* rchild;
TreeNode(){} //缺省构造函数
TreeNode(const T& item,TreeNode<T>
*lptr=NULL,TreeNode<T> *rptr=NULL);
void FreeTreeNode(TreeNode<T> *p){delete p;} //释放二
叉树的一个结点存储空间
};
template<class T> TreeNode<T>:,// 构造函
数
TreeNode(const T& item,TreeNode<T>
*lptr,TreeNode<T> *rptr)
:data(item),lchild(lptr),rchild(rptr){ }
用 C++描述二叉排序树如下
#include <iostream.h>
#include "treenode.h"
#define endmark –999 // 输入 -999则表示结束本次建立
二叉排序树的输入
template<class T> class SortBinTree:public
TreeNode<T>
{ public:
TreeNode<T>* root; //二叉排序树根结点指针
TreeNode<T>* f; //二叉排序树某结点的双亲结点指针
SortBinTree():root(NULL),f(NULL){}
void ins_bs(TreeNode<T>*,TreeNode<T>* &); //向二叉
排序树中插入结点
void ins_bs_nr(TreeNode<T>*,TreeNode<T>* &); //插入
结点的非递归算法
void creat_bst(TreeNode<T>* &r); //从空树出发，依次
插入结点建立二叉排序树
void del_bst(TreeNode<T>* p); //二叉排序树删除结点
//二叉排序树中查找关键字为 K的结点,
TreeNode<T>* Search_bst(TreeNode<T>* t,T K);
void inorder(TreeNode<T>* r ); // 中序遍历以 r为根结点
指针的二叉排序树 };
二叉排序树的插入
插入原则：若二叉排序树为空，则插入结点应为新的根
结点；否则，继续在其左、右子树上查找，直至某个叶
子结点的左子树或右子树为空为止，则插入结点应为该
叶子结点的左孩子或右孩子
template<class T> // 将 s所指结点插入到以 t为根结点指针的二叉
排序树中
void SortBinTree<T>::ins_bs(TreeNode<T>* s,TreeNode<T>* &t)
{ if(t==NULL) t=s; //s所指结点插入到“空”二叉排序树中
else if(s->data<t->data)ins_bs(s,t->lchild); // s所指结点插入到左
子树中 else ins_bs(s,t->rchild); // s所指结点插入到右子树中
}
二叉排序树的生成
整棵树的构成只要从空树出发，依次插入结点即可。例
如，已知序列 45,24,53,12,28,90 整棵树的构造
过程,
45
24( a ) 空树
53
90
45
24
28
12
45
53
45
24
53
45
24
12
53
45
24
28
12
φ
( b ) 插入4 5
( c ) 插入2 4
( d ) 插入5 3
( e ) 插入1 2
( f ) 插入2 8
( g ) 插入9 0
图 9.10 二叉排序树的构造过程
二叉排序树的删除：
要删除二叉排序树中的 p结点，分三种情况：
1,p为叶子结点，修改 p双亲 f的指针 f-
>lchild=NULL
或 f->rchild=NULL
2,p只有左子树或右子树：
p只有左子树，用 p的左孩子代替 p
p只有右子树，用 p的右孩子代替 p
3,p左、右子树均非空
在删除 P之前，中序遍历该二叉树得到的序列为 { ?
ClC ? Q lQSlSPPrF ? },在删除 P之后，为保持其它元
素之间的相对位置不变，可以有两种做法：其一是令 P
的左子树为 F 的左子树，而 P的右子树为 S的右子树，如
图 (c)所示 ；其二是令 P的直接前驱（或直接后继）替
代 P，然后再从二叉排序树中删除它的直接前驱（或直
接后继），图 (d)所示 。
P l P r C l
P r
Q l
S l
f
f
p
q
s
p
c
f
p
c
q
P r
C l
S l
f
C
F
Q
S
F
P
C
F
Q
S
C
S
F
( a ) 以 F 为 根 的 子 树
（ b ) 删 除 P 之 前
（ d ) 删 除 P 之 后 以 S 替 换 P 的 情 况
（ c ) 删 除 P 之 后 以 P
r
作 为 替 换 S 的
右 子 树
图 9, 1 1 在 二 叉 排 序 树 中 删 除 P
Q l
C l
S l
P r
P
c
s
删除算法如下所示,
template<class T> //二叉排序树中删除结点
void SortBinTree<T>::del_bst(TreeNode<T>* p)
// p指向二叉排序树上将被删除结点，数据成员 f为 p所指
结点的双亲结点指针
{ TreeNode<T>* s;
if(p->lchild==NULL) // *p无左子树
if(f==NULL)root=p->rchild; // *p是根结点
else if(f->lchild==p)f->lchild=p->rchild; // *p是 *f的左孩
子
else f->rchild=p->rchild; // *p是 *f的右孩子
else if(p->rchild==NULL) // *p有左子树，但无右子树
if(f==NULL)root=p->lchild; // *p是根结点
else if(f->lchild==p)f->lchild=p->lchild;
else f->rchild=p->lchild;
else // *p既有左子树，也有右子树
{ s=p->lchild; //令 s指向 p的左子树中最大结点
while(s->rchild!=NULL) s=s->rchild;
if(f==NULL){ root=p->lchild; s->rchild=p->rchild; }
else if(f->lchild==p){f->lchild=p->lchild;
s->rchild=p->rchild;}
else{f->rchild=p->lchild; s->rchild=p->rchild; }}
FreeTreeNode(p);}
二叉排序树的查找
查找过程：
首先将待查关键字 k与根结点关键字 t进行比较，如果：
(1)k=t，则返回根结点地址；
(2)k<t，则进一步查找左子树；
(3)否则，进一步查找右子树；
二叉排序树的查找的递归算法：
template<class T> //二叉排序树中查找关键字为 K的结点,
// 若查找成功，数据成员 f是所查得结点的双亲结点指针
TreeNode<T>* SortBinTree<T>::Search_bst(TreeNode<T>* t,T K)
// 在以 t为根指针的二叉排序树中检索关键字为 K的结点，返回结
点指针
{ TreeNode<T>*p;
p=t;
if(p==NULL||p->data==K)return p; // 此处返回“空”则查找
不成功
else{ f=p;
if(K<p->data)p=Search_bst(p->lchild,K); // 到左子树中查找
else p=Search_bst(p->rchild,K); // 到右子树中查找
}}
在二叉排序树上进行查找的平均查找长度和二叉排序树
的形态有关
a,ASL＝（ 1+2+2+3+3+3） / 6＝ 14/6
b:ASL＝（ 1+2+3+4+5+6） / 6＝ 21/6 4 5
9 3
5 3
2 8
5 3
4 5
2 4
9 3
1 2
2 8
2 4
1 2
( a )
( b )
图 9, 1 2 不 同 形 态 的 二 叉 排 序 树
在最坏情况下，二叉排序树是为一棵深度为 n的单支树，
它的平均查找长度是（ n+1） /2。
在最好的情况下，二叉排序树是一棵形态与二分查找的
判定树形似，此时他的平均查找长度大约是 log2n。
考虑 n个结点有 n！种二叉排序树（其中有形态相同的）
可能，可以证明，对这些二叉排序树的查找长度进行平
均，得到的平均查找长度仍然是 O(log2n)
起因：提高查找速度，避免最坏情况出现。虽然完全
二叉树的树型最好，但构造困难。常使用平衡二叉树。
9.4.2平衡的二叉排序树 (AVL树 )
定义：平衡二叉排序树（又称 AVL树），或者是一棵
空树，或者是具有下列性质的二叉树：它的左子树和
右子树都是平衡二叉树，且左子树和右子树的深度之
差的绝对值不超过 1。
平衡因子定义：该结点的左子树的深度减去它的右子
树的深度 。
平衡二叉树上所有结点的平衡因子只可能是 -1,0和 1
一般情况下，假设由于在二叉排序树上插入结点而失
去了平衡的最小子树的根结点指针为 A（即 A是离插
入键最近，且平衡因子绝对值超过 1的祖先结点），
则失去平衡之后进行调整的规律可以归纳为下列四种
情况：（结点外的值是该结点的平衡因子）
LL型：
如图在 A的左子树 B的左子树插入新结点 S，由于 A
的平衡因子由 1增加到 2，导致失衡。为了恢复二叉
排序树的平衡性，需要进行一次顺时针的旋转操作
平衡二叉树失衡的情况和相应的调整方法
LL型失衡特点为,A－ >bf＝ 2,B－ >bf＝ 1。 相应调
整操作可用如下语句完成：
B＝ A－ >lchild； A－ >lchild＝ B－ >rchild； B－ >rchild＝ A；
A－ >bf＝ 0； B－ >bf＝ 0；
A
B A
B
BL
BL
BR
AR
S
AR
S
(b)调整后恢复平衡(a)插入新结点 S后失去平衡
二叉排序树的 LL型平衡旋转
2
1
0
0
H-1
H-1
H BR
最后, 将调整后的二叉排序树的根结点 B―接到, A处 。
令 A原来的父指针为 FA如果 FA非空, 则用 B代替 A做
FA的左子树或者右子树；否则原来 A就是根结点, 此
时应该令根指针 t指向 B。 相应调整操作可用如下语句
if(FA==NULL) t＝ B；
else if (A==FA－ >lchild) FA－ >lchild＝ B；
else FA—>rchild＝ B；
LR型,
由于在 A的左子树的 B的右子树上插入结点，使 A的
平衡因子由 1增至 2而失去了平衡，需进行两次旋转
操作（先逆时针，后顺时针），如图所示。
A
B
A R
S
( b ) 调 整 后 恢 复 平 衡
( a ) 插 入 新 结 点 S 后 失 去 平 衡
二 叉 排 序 树 的 L R 型 平 衡 旋 转
C
B L
C L
C R
A
B
C
C R
A R
C L
S
B L
1
- 1
0
- 1
2
0
H - 1
H - 2
H - 1
H - 1
LR型失衡特点为,A－ >bf＝ 2,B－ >bf＝ -1。相应调
整操作可用如下语句完成：
B＝ A－ >lchild； C＝ B－ >rchild；
B－ >rchild＝ C－ >lchild； A－ >lchild＝ C－ >rchild；
C－ >rchild＝ A； C－ >lchild＝ B；
新结点 S的插入位置有三种情况,1、在 CL下插入 S。 2、
在 CR下插入 S。 3,B 的右子树为空,C本身就是插入
的新的结点 S。针对上述三种不同情况，修改 A,B,C
的平衡因子：
最后，将调整后的二叉排序树的根结点 C接到 A处。令
A原来的父指针为 FA如果 FA非空，则用 C代替 A做
FA的左子树或者右子树；否则原来 A就是根结点，
此时应该令根指针 t指向 C：
if (FA == NULL) t＝ C； else if (A == FA－ >lchild) FA－
>lchild＝ C； else FA—>rchild＝ C；
if(S->key < C->key) //在 CL下面插入 S
{ A－ >bf＝－ 1； B－ >bf＝ 0； C－ >bf＝ 0}
if(S->key > C->key) // 在 CR下面插入 S
{ A－ >bf＝ 0； B－ >bf＝ 1； C－ >bf＝ 0}
if(S->key == C->key) //C是新的插入结点 S { A－ >bf＝ 0；
B－ >bf＝ 0； }
RR 型：
由于在 a的右子树的右子树上插入结点，使 a的平衡
因子由 -1减至 -2而失去平衡，需进行一次逆时针
旋转操作。如图所示。
A
B
A
B
BL
BL
BR
BR
AL
S
AL
S
( b ) 调整后恢复平衡
( a ) 插入新结点S 后失去平衡
二叉排序树的R R 型平衡旋转
-1
-2 0
0
H-1
H
H-1
RL 型：
由于在 a的右子树的左子树上插入结点，使 a的平衡
因子由 -1 减至 -2而失去平衡，需进行两次旋转操
作（先顺时针，后逆时针）。如图所示。
A
B
A L
S
( b ) 调 整 后 恢 复 平 衡
( a ) 插 入 新 结 点 S 后 失 去 平 衡
二 叉 排 序 树 的 R L 型 平 衡 旋 转
C
B L
C L
C R
A
B
C
C R
B R
C L
S
A L
- 1
1
1
0
0
- 2
H - 1
H - 1
H - 1
H - 2
综上所述插入一个新的结点 S时，主要包括以下三步：
1）查找应该插入位置，同时记录距离插入位置最近的
可能失衡结点 A（ A的平衡 因子不等于 0）。
2）插入新的结点 S，并修改从 A到 S路径上各个结点的
平衡因子。
3）根据 A,B的平衡因子，判断是否失衡以及失衡类
型，并做相应的处理。
LL型与 RR型对称,LR型与 RL型对称
平衡树结点类 (AVL_NODE) 及平衡树类 (AVLtree)的声明：
#define NULL 0
template<class T> class AVL_Node //平衡树 (AVL)结点类
的定义 (AVLnode.h)
{ public:T data; int bf;
AVL_Node<T> *lchild,*rchild;
AVL_Node(){} //缺省构造函数
AVL_Node(const T& item,int b=0,AVL_Node<T>
*lptr=NULL,AVL_Node<T>
*rptr=NULL):data(item),bf(b),lchild(lptr),rchild(rptr){
}};
//AVL树根结点指针
template<class T> class AVLtree:public AVL_Node<T>
{ public:
AVL_Node<T>* root;
AVLtree():root(NULL){ };
void inorder(AVL_Node<T>* t); // 中序遍历 AVL树
void LL_rotation(AVL_Node<T>*,AVL_Node<T>*); //
LL型旋转
void LR_rotation(AVL_Node<T>*&,AVL_Node<T>*); //
LR型旋转
void RR_rotation(AVL_Node<T>*,AVL_Node<T>*); //
RR型旋转
void RL_rotation(AVL_Node<T>*&,AVL_Node<T>*); //
RL型旋转
void AVL_ins(AVL_Node<T>*,AVL_Node<T>*&); // 在
平衡树上插入结点
void creat_AVL(AVL_Node<T>* &r); // 建立平衡树的算
法
};
RR型旋转
void RL_rotation(AVL_Node<T>*&,AVL_Node<T>*); //
RL型旋转
void AVL_ins(AVL_Node<T>*,AVL_Node<T>*&); // 在
平衡树上插入结点
void creat_AVL(AVL_Node<T>* &r); // 建立平衡树的算
法
};
创建 AVL树算法：
template<class T> void
AVLtree<T>::creat_AVL(AVL_Node<T>* &r) // 创建
一棵 AVL树 { AVL_Node<T> *s; T x; r=NULL;
cin>>x;while(x!=in_end) // in_end代表输入终止的符号
{ s=new AVL_Node<T>(x); // 为插入结点申请空间
AVL_ins(s,r); // 逐个插入结点并令保持平衡 cin>>x;}}
B- 树定义9.4.3B－树
一棵 m阶的 B-树，或为空树，或满足下列特性的 m叉树：
1、每个结点至多有 m棵子树；
2、除根结点和叶结点外其它个结点至少有 ?m/2?棵子树；
3、除非根结点为最低层非终端结点否则至少有两子树；
4、所有非终端结点中包含有下列信息：
（ n,A0,K1,A1,K2,A2,…, Kn,An）
其中,Ki（ 1? i ?n）为关键字，且 Ki<Ki+1（ 1?i <n），
Ai（ 0? i ?n）为指向子树根结点的指针，且指针 Ai
（ 0? i<n）所指子树中所有结点的关键字均小于 Ki+1，
指针 An 所指子树中的关键字均大于 Kn,n（ ?m/2?-1 ?
n ? m-1）为关键字的个数；
5、缩有的叶子结点都出现在同一层上，并且不带信
息（可以看作是外部结点或查失败的结点,实际上这
些结点不存在,指向这些结点的指针为空）
1 3 5
1 1 1
1 3 9
2 4 3 7 8
3 4 7 5 3 6 3
1 1 8
1 2 7 1 9 9
F
FF F
F
F
F F F F FF
一 棵 4 阶 的 B - 树
A
B C
D E
F G
H
设查找一个给定值 K，首先从根开始，若根结点中有 K，
则查找成功，否则必是下述三种情况之一：
① ki<K<ki+1,(1? i<n)。继续到 Ai 所指结点中去查
找；
② K>kn，则到 An所指结点继续查找；
③ K<k1，则转到 A0所指结点中去查找。
重复上述过程，直到查找成功或下一个要查找结点的
指针 Ai（ 0?i ?n）为“空”（或指向叶子结点 F），
则查找失败，关键字为 K的记录不在树中。
B-树的查找
在 B-树上进行查找所需时间取决于两个因素：
① 等于给定值的关键字所在结点的层次；
② 结点中关键字的数目。当结点中关键字数目较大
时可采用折半查找以提高效率。
例如：上面查找图的 4阶 B-树的 53的过程如下：
首先由根指针找到根结点 A，因为 53>35，所以找到
结点 C，又因为 43<53<78，所以找到结点 G，最后在
结点 G中找到 53。
深度为 L+1的 m阶 B-树具有的最少结点数,
B- 树的定义，第一层至少有 1个结点，第二层至少有
2个结点。由于除根之外的每个非终端结点至少有
?m/2?棵子树，则第三层至少有 2*「 m/2?个结点，依次
类推 ?,第 L+1层至少有 2*(?m/2?)i-1个结点。而
L+1层的结点为叶子结点（外部结点），若 m 阶 B-树
中具有 N个关
B－树的插入：
30
35 38
20
10 15 25
40
45 50
30
20
10 15
35 38 45 50
a
a
b
b
c
c
d
d
e
e
f
f
gg
( 1 ) 一棵3 阶B树
（2）插入 2 3 后
（3）插入 5 5,结点g需要分 裂
（4）结点 g 分裂后
（5）插入 结点3 7,结点f需要分 裂
（6）结点 f 分裂，结点c需要分 裂
23 25
40
30
20
10 15
35 38
45 50 55
a
e f
23 25
40
30
20
10 15 35 38 4523 25
40 50
55
30
20
10 15 35 37 38
45
23 25
40 50
55
30
20
10 15
35
45
23 25
37 40 50
5538
a
a a
b b
b b
c c
c c
d d
d
d
e
e e
f
f
f
f'
g
g
g
g g'g'
g'
B－树的插入：
（7）结点 c 分裂后
30 40
20
10 15 35
45
23 25
50
5538
37
30 40
20
10 15 18 35 4523 25
50
5538
37
30 40
15 20
10 35 4523 25
50
55
38
37
18
（8）插入 结点1 8 结点d 需要分裂
30 40
15 20
10 35 4523 25 28
50
5538
37
18
（9）结点 d 分裂后
a
a
a a
b
b
b
b
c c
c c
C'C'
C' C'
d
d
d d d'd'
e
e
e e
f
f
f f f'f'
f'
f'
g
g
g
g g'
g'
g'
g'
（10 ）插入结点28 后e结点需 要分裂
B－树的插入：
30 40
15 20 25
10 35 4523
50
5538
37
18 28
20 30 40
15
10 35 45
23
50
5538
37
18
28
25
20
15
10 35 4523
50
55
38
37
18 28
25
30
40
a
a
a
b b
b
c
c C'
C'
d
d
d
d'
d'
d'
e
e
e e'
e'
e'
f
f
f f'
f'
f'
g
g
g
g'
g'
g'
a'
m
（1 3 ）根结点分裂后
（1 2 ）结点b 分裂后根结点需要分裂
（1 1 ）结点b 需要分裂
b'
b'
在B - 树中插入的实例
c
C'
B-树的创建,
3 7
3 7 7 0
1 2 3 7 7 0
3 7
1 2 7 0
3 7
1 2 4 5 7 0
3 7
1 2 4 5 7 0 9 0
3 7 7 0 3 7 7 0
1 2 4 5 9 0 3 1 2 4 5 9 0
3 7 7 0
3 1 2 2 4 4 5 9 0
1 2 3 7 7 0
3 2 4 4 5
3 7
1 2 7 0
3 2 4 4 5 9 0
9 0
( 1 ) 空 树
( 2 ) 插 入 3 7 ( 3 ) 插 入 7 0
( 4 ) 插 入 1 2
分 裂
分 裂
分 裂
分 裂
( 5 ) 插 入 4 5
( 6 ) 插 入 9 0
( 7 ) 插 入 3
( 8 ) 插 入 2 4
从 空 树 开 始, 插 入 关 键 字, 创 建 一 棵 3 阶 B - 树
B-树的删除,在最下面结点中删除一个关键字
18
11 13 27 47 53 64
43 78
39 99
35
18
13 27 47 53 64
43 78
39 99
35
18
13 27 47 64
43 78
39 99
35
18
13 27 64
47 78
43 99
35
35 35
(1)一棵4阶B-树
(2)删除11后
（3)删除53后
（4)删除39后
18
13 27 78 99
47
43
35
13 18 78 99
47
43
35
35 47
13 18 78 9943
43
35 47
13 18 78 99
（3 ) 删除5 3 后
（4 ) 删除3 9 后
（5 ) 删除6 4 后
（6 ) 删除2 7 后将剩余信息与父结
点中的1 8 并入左兄弟
（7 ) 将父结点剩余信息与祖父结
点中3 5 并入4 7 左端
（8 ) 删除2 7 后最终结果
在B －树最下层结点中删除关键字
B-树的删除,在非最下层结点中删除一个关键字
1 8
1 1 1 3 2 7
4 7 5 3 6 4
4 3 7 8
3 9 9 9
3 5
1 8
1 1 1 3 2 7
5 3 6 4
4 7 7 8
3 9 9 9
3 5
1 8
1 1 1 3 2 7
5 3 6 4
4 7 7 8
3 9 9 9
2 7
1 3
1 3 1 8
5 3 6 4
4 7 7 8
3 9
9 9
2 7
( 1 ) 一 棵 4 阶 B - 树
( 2 ) 删 除 4 3 后
（ 3 ) 删 除 3 5 后, 先 用 2 7 代 替 3 5
（ 4 ) 删 除 原 2 7 后
在 B － 树 非 最 下 层 结 点 中 删 除 关 键 字
B+ 树
B+树和 m阶的 B-树差异在于：（这儿不再考虑外
部结点，而直接称最低层内部结点为叶结点）
① 有 n棵子树的结点中含有 n个关键字；
② 所有的叶子结点中包含了全部关键字的
信息及指向相应记录的指针，且叶结点本身依关
键字的大小自小而大顺序链接。
③ 所有的非终端结点可以看成是索引部分，
结点中仅含有其子树的最大（或最小）关键字。
小结
本章介绍了顺序表的三种查找方法：顺序查找,
二分法查找, 分块查找, 散列表的查找, 以及树
表：二叉排序树, AVL树, 以及 B-树的定义, 特点
和存储结构 。 并且讨论了各种查找方法的效率
―― 平均查找长度 。
9.1.基本概念
9.2顺序表
9.2.1顺序查找
9.2.2二分法查找
9.2.3分块查找
9.3散列表
9.3.1概述
9.3.2散列函数的构造方法
9.3.3处理冲突的方法
9.3.4散列表的性能分析
9.4,树表
9.4.1 二叉排序树
9.4.2 平衡的二叉排序树
9.4.3 B－树
小结
◆ 查找表,由同一类型的数据元素（记录）组成的集合，
可以由任意的数据结构实现 。
9.1 基本概念
◆ 查找表的操作：（ 1）查询某个“特定的”数据元素
是否在查找表中；（ 2）查找某个“特定的”数据元素的
属性；（ 3）在查找表中插入一个数据元素；（ 4）从查找
表中删除某个数据元素。
◆ 静态查找表,若对查找表只作前两种操作，此类查找表
称静态查找表。
◆ 动态查找表,若在查找过程中同时插入查找表中不存在
的数据元素，或者从查找表中删除已经存在的某个数据元
素,此类查找表为动态查找表。
◆ 关键字：数据元素中某个数据项的值，用它可以标
示查找表中的一个数据元素。主关键字可以唯一地标
识一个记录，次关键字用以识别若干记录。
◆ 查找：就是根据给定的关键字值，在特定的查找表
中确定一个其关键字与给定值相同的数据元素，并返
回该数据元素在查找表中的位置。如果找到数据元素，
则称查找成功，否则查找失败。
◆ 平均查找长度, 为了确定数据元素在查找表中的位
置需要和给定值进行比较的关键字个数期望值，称为
查找算法在查找成功时的平均查找长度。
?对于长度为 n的查找表，查找成功的平均查找长度为：
?其中 Pi为查找表中第 i个数据元素的概率,Ci为找到
查找表中第 i个元素时，已经进行的比较次数。由于
查找算法的基本元素是关键字之间的比较操作，所以
可以平均查找长度来衡量查找算法的性能。
9.2顺序表
顺序表中相邻的两个记录 Ri和 Ri+1在存储器中
的物理位置也是相邻的，因此存储结构采用的
是顺序结构。
顺序结构有关 C++语言描述的数据类型定义,
（为了简单起见，我们假设记录的排序码为整
型，在本章以后讨论的顺序表中均采用这样的
向量存储结构）
?顺序表的查找方法分为顺序查找法、二分法
（折半）查找法以及分块（索引）查找法。
#define maxn 30 // 文件中最大记录数
typedef struct
{ int key; // 假设记录排序码为整数
char *other; // 记录中其它信息域，暂不用
} record;
typedef record recordfile[maxn];
9.2.1顺序查找
顺序查找（ sequential search)用待查的关键字值与线
性表里各结点的关键字值逐个比较，
?查找第 n个元素,比较次数 1 查找第 n-1个元素,比较次数 2
………,查找第 1个元素,比较次数 n
查找第 i个元素,比较次数 n+1-i 查找失败, 比较次数 n+1
443211237669875676
0 1 2 3 4 5 6 7 8
监视哨
查
找
76 ↑i↑i↑i↑i
↑i
查找次数＝ 5
int seqserch(recordfile r,int k,int n)
//k为给定值,n为表长 ;
//返回 0表明查找不成功,否则返回关键字等于 k的
记录在表 r中的序号,
{ int i=n;
r[0].key=k;
while(r[i].key!=k) i--;
return i;}
顺序查找的算法,查找前对结点之间并没有排序
要求,用 C++语言描述的顺序查找算法如下,
在此算法中，查找之前，先对 r[0]的关键字赋值
为 k，目的在于免去查找过程中每一步都要检测
整个表是否查找完毕。在此 r[0]起了监视哨的作
用
这种改进能使顺序查找在 n≥1000 时进行一次查
找所需要的平均时间几乎减少一半，从而提高查
找效率。
?顺序查找方法的 ASL：
??有 n个记录的表，查找成功时的平均查找长度为
??假设每个记录的平均查找概率相等即,Pi = 1/n 。
。
在顺序查找时,ci取决于所查记录在表中的位
置。如查找记录 r[n]时，仅需比较一次，而查
找记录 r[1]时，则需比较 n次。一般地,ci=n-
i+1。故顺序查找的平均查找长度为,
ASL = np1 +(n-1)p2 + … + 2p n-1 + pn 。
顺序查找法和后面将要讨论的其它查找法相比,
其缺点是平均查找长度较大, 特别是当 n 很大时,
查找效率低 。 然而, 它有很大的优点：算法简单
且适用面广 。 它对表的结构无任何要求, 无论记
录是否按关键字有序均可应用, 而且上述所有讨
论对线性链表也同样适用 。
算法 的评价
9.2.2二分法查找
查找过程：每次将待查记录所在区间缩小一半，
适用条件：采用顺序存储结构的有序表
?算法实现,
设表长为 n,low,high和 mid分别指向待查元素所在区间的上
界、下界和中点,k为给定值
初始时，令 low=1,up=n,mid=?(low+up)/2?
让 k与 mid指向的记录比较
若 k==r[mid].key,查找成功
若 k<r[mid].key,则 up=mid-1
若 k>r[mid].key,则 low=mid+1
重复上述操作，直至 low>up时，查找失败
958980756356342119155
1 2 3 4 5 6 7 8 9 10 11
例：查找 21
↑low ↑up↑mid
?(1+11)/2?=6
958980756356342119155
1 2 3 4 5 6 7 8 9 10 11
↑low ↑mid
?(1+5)/2?=3
↑up
958980756356342119155
1 2 3 4 5 6 7 8 9 10 11
low ↑↑mid
?(4+5)/2?=4
↑up
958980756356342119155
1 2 3 4 5 6 7 8 9 10 11
例：查找 83
↑low ↑up↑mid
?(7+11)/2?=9
958980756356342119155
1 2 3 4 5 6 7 8 9 10 11
low↑↑mid
?(10+11)/2?=10
↑up
958980756356342119155
1 2 3 4 5 6 7 8 9 10 11
↑ lowup ↑
Up <low 查找
失败
int bins(recordfile r,int K,int n) //二分查找
{ int l=1,u=n,m; // 置区间初值
while(l<=u)
{ m=(l+u)/2;
if(K>r[m].key) l=m+1; // 修改下界 l 值
else if(K<r[m].key) u=m-1; // 修改上界 u值
else return m; // 查找成功
}
return 0; // 脱离 while,则 l>u 查找不成功
}
二分查找的算法用 C++语言描述如下
判定树：描述查找过程的二叉树叫判定树。有 n个结点
的判定树的深度为 ?log2n?+1 ； 二分查找成功时比较次
数最多不超过树的深度 ；二分查找在查找不成功时和关
键字比较的次数最多不超过 ?log2n? +1；
算法查找的性能
二分 查找的 ASL
表的长度为,n=2h-1(h=log2(n+1))
每个元素的查找概率相等 Pi=1/n
平均查找长度,
二分查找的效率比顺序查找高, 但二分查找只能适用于
有序表, 且存储结构仅限于向量 （ 对线性链表无法进行
折半查找 ）, 当表经常需要插入或删除一个元素时, 就
需要来回移动元素 。 因此, 折半查找方法适用于不经常
变动而查找频繁的有序列表 。
算法 的评价
将查找表分成若干个块（子表）块内无序，但块与块
之间应有序构造一个索引表。其中每个索引项对应一
个块并记录每个块的起始位置，以及每块中的最大关
键字（或最小关键字）。索引表按关键字有序排列
9.2.3分块查找
查找过程：先根据索引表确定待查记录所在块，再在
块内顺序查找
适用条件：分块有序表
例：查找 37
754522
477558614826374542330809151222
查找表
索引表
平均查找长度为,
Lb为查找索引表确定所在块的平均查找长度,Lw为在块
中查找元素的平均查找长度 。
长度为 n的表分成 b块，每块含有 s个记录，即 b= n/s ；
表中每个记录的查找概率相等，则每块查找的概率为 1/b，
块中每个记录的查找概率为 1/s
用顺序查找确定所在块，则平均查找长度为：
用二分查找确定所在块，则查找长度为：
分块查找的优点是,在线性表中插入或删除一个结点时,
只要找到该结点应属的块, 然后在块内进行插入和删除
运算, 由于块内结点的存放是任意的, 所以插入或删除
比较容易, 不需要移动大量的结点 。 分块查找的主要代
价是增加一个辅助数组的存储空间和将初始线性表分块
排序的运算 。 另外当大量的插入和删除运算使块中的结
点数分布不均匀时, 查找速度会下降 。
算法 的评价
基本思想：在记录的存储地址和它的关键字之间建立
一个确定的对应关系；这样，不经过比较，一次存取
就能得到所查元素的查找方法。
9.3散列表
9.3.1 概述
散列表定义：
记录的存储位置和它的关键字之间建立一个确定的对
应关系 h，使每个关键字和结构中一个唯一的存储位置
相对应。查找时，根据 h找到给定值 k的映象 h(k)，若
结构中存在关键字和 k相等的记录，则必定在 h(k)的存
储位置上。我们称这个对应关系 h为散列（ Hash）函
数用散列函数建立的表称为散列表。
例如, 一张全国各地区的各民族人口统计表
上海2
北京1
·······回族汉族总人数地区名编号 满族
以编号作关键字，
构造 哈希函数,H(key)=key
H(1)=1
H(2)=2
特征位抽取法
构造：抽取关键字中某几位随机性较好的数位，然后把
这些数位拼接起来作为散列地址。
9.3.2 散列函数的构造方法
直接定址法
构造：取关键字或关键字的某个线性函数作哈希地址，
即 H(key)=key 或 H(key)=a·key+b
特点：直接定址法所得地址集合与关键字集合大小相等，
不会发生冲突。实际中能用这种哈希函数的情况很少。
分析,?只取 8
?只取 1
?只取 3,4
?只取 2,7、
5
????数字
分布近乎随机
所以：取 ????任
意两位或两位
与另两位的
叠加作散列
地址
平方取中法
构造：取关键字平方后中间几位作哈希地址适用
于当无法确定关键字中哪几位分布比较均匀时
K的内部编码为 11,E的内部编码为 05,Y的内部编码
为 25,A的内部编码为 01,B的内部编码为 02。关键字
,KEYA‖的内部代码为 11052501，同理得到关键字
,KYAB‖、,AKEY‖的内部编码，然后进行对关键
字平方运算，取出第 7到第 9位作为该关键字的散列地
址
关 键 字 内 部 编 码 内 部 编 码 的 平 方 值 散 列 地 址
K E Y A 1 1 0 5 2 5 0 1 1 2 2 1 5 7 7 7 8 3 5 5 0 0 1 7 7 8
K Y A B 1 1 2 5 0 1 0 2 1 2 6 5 6 4 7 9 5 0 1 0 4 0 4 7 9 5
A K E Y 0 1 1 1 0 5 2 5 0 0 1 2 3 3 2 6 5 7 7 5 6 2 5 2 6 5
表 9, 2 平 方 取 中 法 的 散 列 地 址
折叠法构造：
将关键字分割成位数相同的几部分，然后取这几部分的
叠加和（舍去进位）做散列地址移位叠加：将分割后的
几部分低位对齐相加间界叠加：从一端沿分割界来回折
送，然后对齐相加适于关键字位数很多，且每一位上数
字分布大致均匀情况如国际标准图书编号 0-442-20586-
4采用这两种折叠法求得的散列地址分别如下所示：
5 8 6 4
4 2 2 0
0 4
1 0 0 8 8
H(key)=0088
移位叠加
5 8 6 4
0 2 2 4
0 4
6 0 9 2
H(key)=6092
间界叠
加
除留余数法构造：
取关键字被某个不大于散列表表长 m的数 p除后所得余数
作散列地址，即 H(key)=key MOD p,m特点：简单、
常用，可与上述几种方法结合使用
表 （ 18,75,60,43,54,90,46） m=p=13
0 1 2 3 4 5 6 7 8 9 10 11 12
18 75604354 9046
H（ 18）＝ 18 ％ 13＝ 5 H（ 75）＝ 75 ％ 13＝ 10
H（ 60）＝ 60 ％ 13＝ 8 H（ 43）＝ 43 ％ 13＝ 4
H（ 54）＝ 54 ％ 13＝ 2 H（ 90）＝ 90 ％ 13＝ 12
H（ 46）＝ 46 ％ 13＝ 7
随机数法
构造：取关键字的随机函数值作散列地址，即
H(key)=random(key)
适于关键字长度不等的情况
选取散列函数，考虑以下因素：
⑴ 计算散列函数所需的时间 ( 包括硬件指令的因素 )；
⑵ 关键字的长度；
⑶ 散列表的大小；
⑷ 关键字的分布情况；
⑸ 记录的查找频率
1、开放定址法：
方法：当冲突发生时，形成一个探查序列；沿此序列逐
个地址探查，直到找到一个空位置（开放的地址），将
发生冲突的记录放到该地址中，即 Hi=(H(key)+di)MOD
m,i=1,2,……k(k m-1)
其中,H(key)——散列函数 m——散列表表长 di——增量序列
9.3,3 处理冲突的方法
分类：
线性探测再散列,di=1,2,3,……m -1
二次探测再散列,di=12,-12,22,-22,32,…… ± k2(k≤m/2)
伪随机探测再散列,di=伪随机数序列
例 表长为 16的散列表中已填有关键字为 19,70,33和 38
的记录,H(key)=key MOD 13,
现有第五个记录，其关键字为 25,H(25)=12
38331970
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
冲突
25
不冲突线性探测再散列
插入第六个记录，其关键字为 18,H(18)=5
冲突
线性探测再散列
冲突 冲突 不冲突
18
用二次探测
再散列
不冲突
伪随机探测
再散列
不冲突
1818
2、再散列法
方法：构造若干个散列函数，当发生冲突时，计算下一
个散列地址，即,Hi=Rhi(key) i=1,2,……k
其中,Rhi——不同的散列函数。
特点：计算时间增加。
3、链地址法：
方法：将所有关键字为同义词的记录存储在同一线性链
表中并用一维数组存放头指针
用链地址法解决冲突的散列造表算法,
#include <iostream.h>
#define listlen 13
struct record
{ int key;
record *next;
};
typedef record RECF[listlen];
int modh (int ); //Hash函数 (除留余数法 )
void chainh(int,RECF,int (*hash)(int ));
prhashlist(RECF ); //输出散列表
void main(void)
{ int i,x; RECF r;
for(i=0;i<listlen;i++){ r[i].key=0; r[i].next=NULL; }
cin>>x;
while(x){ chainh(x,r,modh); cin>>x; }
prhashlist(r);
}
// 其中参数 int(*hash)(int)是指向函数的指针，它返回一
个整数（散列地址）
//用链地址法解决冲突的散列造表算法
//根据 (*hash)函数造散列表
void chainh(int k,RECF r,int (*hash)(int))
{ int addr; record *p,*q; //用链地址法解决冲突
addr=(*hash)(k);
if (!r[addr].key)r[addr].key=k;
else if(r[addr].key!=k)
{p=r[addr].next; q=&r[addr];
while(p && p->key!=k) { q=p; p=p->next; }
if(!p){ p=new record; p->key=k; p->next=NULL;
q->next=p; }
}
}
int modh (int k) //Hash函数 (除留余数法 )
{ return(k % listlen); }
prhashlist(RECF r) //输出散列表
{ int i; record *p;
cout<<"no.\tkey\t link\n";
for(i=0;i<listlen;i++)
{ if(!r[i].key) cout<<i<<"\t\t^\n";
else{ cout<<i<<"\t"<<r[i].key<<"\t-->";
p=r[i].next;
while(p){ cout<<p->key<<"-->"; p=p->next; }
cout<<"^"<<endl; }}}
Λ
Λ
Λ
Λ
Λ
Λ
0
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
4 0
4 2 Λ
1 6
5 3
3 2
7 1 Λ
4 6 Λ
3 6
2 4 Λ
6 4 Λ
2 7 Λ
4 9 Λ
比 较 次 数 1 2 3
图 9, 7 链 地 址 法 处 理 冲 突 时 的 散 列 表
例：已知一组关键字（ 32,40,36,53,16,46,71,27,42，
24,49,64），散列表表长为 13，散列函数为 H（ key）＝ key％
13，则用链地址法处理冲突的结果
散列查找过程仍是一个给定值与关键字进行比较的过程
评价散列查找效率仍要用 ASL
散列查找过程与给定值进行比较的关键字的个数取决于：
1、散列函数
2、处理冲突的方法
3、散列表的填满因子 ?=表中填入的记录数 /散列表长度
9.3.4 散列表性能分析
已有散列表 a[16]如图所示（上面是地址，最下一行是插
入 /查找某记录所需的关键字比较次数）,Hash函数
H(key)=key ? 13，处理冲突用二次探测再散列
27 14 01 68 55 84 19 20 10 23 11 79
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
3 1 2 1 2 3 1 1 3 1 1 5
图 9,8 散列表 a [ 1 6 ]
下
标
检索次数
平均查找长度分别为, ASL=(1*6+2*2+3*3+5)/12=2
用链地址法处理冲突的散列表
平均查找长度为, ASL=(1*7+2*4+3)/12=1.5
Λ
Λ
Λ
Λ
Λ
Λ
0
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
4 0
4 2 Λ
1 6
5 3
3 2
7 1 Λ
4 6 Λ
3 6
2 4 Λ
6 4 Λ
2 7 Λ
4 9 Λ
比 较 次 数 1 2 3
图 9, 7 链 地 址 法 处 理 冲 突 时 的 散 列 表
α =表中的记录数 /表长
直观地看,α 越小，发生冲突的可能性就越小； α 越大，
即表越满，发生冲突的可能性就越大，查找时所用的比
较次数就越多。因此散列表查找成功的平均查找长度 Sn
和 α 有关。
在线性探测再散列时,Snl≈(1+1/(1-α))/2
在伪随机探测再散列，二次探测再散列及再散列时：
Snr≈-Ln(1-α)/α
在链地址法中,Snc≈1+α/2
二叉排序树又称为二叉查找树，它是一种特殊结构的
二叉树，其定义为：二叉排序树或者是一个空树，
或是具有下面性质的二叉树
1、若它的左子树非空，则左子树上所有结点的值均小
于根结点的值；
2、若它的右子树非空，则右子树上所有结点的值均大
于根结点的值；
3、它的左右子树也分别为二叉排序树。
9.4 树表
9.4.1 二叉排序树
二叉排序树的一个重要性质：中序遍历一个二叉排序树
时可以得到一个递增有序序列。上图所示二叉树是个二
叉排序树。若中序遍历，得到一个递增的有序序列,1，
2,3,4,5,6,7,8,9。
6
8
5
2
7
41
9
3
(a )关键 字为整数的二叉排序树
二叉排序树的操作中，使用二叉链表作为存储结构，其
结点说明如下：
//treenode.h
#define NULL 0
template<class T> class TreeNode //声明二叉树结点类
{public:
T data;
TreeNode<T>* lchild;
TreeNode<T>* rchild;
TreeNode(){} //缺省构造函数
TreeNode(const T& item,TreeNode<T>
*lptr=NULL,TreeNode<T> *rptr=NULL);
void FreeTreeNode(TreeNode<T> *p){delete p;} //释放二
叉树的一个结点存储空间
};
template<class T> TreeNode<T>:,// 构造函
数
TreeNode(const T& item,TreeNode<T>
*lptr,TreeNode<T> *rptr)
:data(item),lchild(lptr),rchild(rptr){ }
用 C++描述二叉排序树如下
#include <iostream.h>
#include "treenode.h"
#define endmark –999 // 输入 -999则表示结束本次建立
二叉排序树的输入
template<class T> class SortBinTree:public
TreeNode<T>
{ public:
TreeNode<T>* root; //二叉排序树根结点指针
TreeNode<T>* f; //二叉排序树某结点的双亲结点指针
SortBinTree():root(NULL),f(NULL){}
void ins_bs(TreeNode<T>*,TreeNode<T>* &); //向二叉
排序树中插入结点
void ins_bs_nr(TreeNode<T>*,TreeNode<T>* &); //插入
结点的非递归算法
void creat_bst(TreeNode<T>* &r); //从空树出发，依次
插入结点建立二叉排序树
void del_bst(TreeNode<T>* p); //二叉排序树删除结点
//二叉排序树中查找关键字为 K的结点,
TreeNode<T>* Search_bst(TreeNode<T>* t,T K);
void inorder(TreeNode<T>* r ); // 中序遍历以 r为根结点
指针的二叉排序树 };
二叉排序树的插入
插入原则：若二叉排序树为空，则插入结点应为新的根
结点；否则，继续在其左、右子树上查找，直至某个叶
子结点的左子树或右子树为空为止，则插入结点应为该
叶子结点的左孩子或右孩子
template<class T> // 将 s所指结点插入到以 t为根结点指针的二叉
排序树中
void SortBinTree<T>::ins_bs(TreeNode<T>* s,TreeNode<T>* &t)
{ if(t==NULL) t=s; //s所指结点插入到“空”二叉排序树中
else if(s->data<t->data)ins_bs(s,t->lchild); // s所指结点插入到左
子树中 else ins_bs(s,t->rchild); // s所指结点插入到右子树中
}
二叉排序树的生成
整棵树的构成只要从空树出发，依次插入结点即可。例
如，已知序列 45,24,53,12,28,90 整棵树的构造
过程,
45
24( a ) 空树
53
90
45
24
28
12
45
53
45
24
53
45
24
12
53
45
24
28
12
φ
( b ) 插入4 5
( c ) 插入2 4
( d ) 插入5 3
( e ) 插入1 2
( f ) 插入2 8
( g ) 插入9 0
图 9.10 二叉排序树的构造过程
二叉排序树的删除：
要删除二叉排序树中的 p结点，分三种情况：
1,p为叶子结点，修改 p双亲 f的指针 f-
>lchild=NULL
或 f->rchild=NULL
2,p只有左子树或右子树：
p只有左子树，用 p的左孩子代替 p
p只有右子树，用 p的右孩子代替 p
3,p左、右子树均非空
在删除 P之前，中序遍历该二叉树得到的序列为 { ?
ClC ? Q lQSlSPPrF ? },在删除 P之后，为保持其它元
素之间的相对位置不变，可以有两种做法：其一是令 P
的左子树为 F 的左子树，而 P的右子树为 S的右子树，如
图 (c)所示 ；其二是令 P的直接前驱（或直接后继）替
代 P，然后再从二叉排序树中删除它的直接前驱（或直
接后继），图 (d)所示 。
P l P r C l
P r
Q l
S l
f
f
p
q
s
p
c
f
p
c
q
P r
C l
S l
f
C
F
Q
S
F
P
C
F
Q
S
C
S
F
( a ) 以 F 为 根 的 子 树
（ b ) 删 除 P 之 前
（ d ) 删 除 P 之 后 以 S 替 换 P 的 情 况
（ c ) 删 除 P 之 后 以 P
r
作 为 替 换 S 的
右 子 树
图 9, 1 1 在 二 叉 排 序 树 中 删 除 P
Q l
C l
S l
P r
P
c
s
删除算法如下所示,
template<class T> //二叉排序树中删除结点
void SortBinTree<T>::del_bst(TreeNode<T>* p)
// p指向二叉排序树上将被删除结点，数据成员 f为 p所指
结点的双亲结点指针
{ TreeNode<T>* s;
if(p->lchild==NULL) // *p无左子树
if(f==NULL)root=p->rchild; // *p是根结点
else if(f->lchild==p)f->lchild=p->rchild; // *p是 *f的左孩
子
else f->rchild=p->rchild; // *p是 *f的右孩子
else if(p->rchild==NULL) // *p有左子树，但无右子树
if(f==NULL)root=p->lchild; // *p是根结点
else if(f->lchild==p)f->lchild=p->lchild;
else f->rchild=p->lchild;
else // *p既有左子树，也有右子树
{ s=p->lchild; //令 s指向 p的左子树中最大结点
while(s->rchild!=NULL) s=s->rchild;
if(f==NULL){ root=p->lchild; s->rchild=p->rchild; }
else if(f->lchild==p){f->lchild=p->lchild;
s->rchild=p->rchild;}
else{f->rchild=p->lchild; s->rchild=p->rchild; }}
FreeTreeNode(p);}
二叉排序树的查找
查找过程：
首先将待查关键字 k与根结点关键字 t进行比较，如果：
(1)k=t，则返回根结点地址；
(2)k<t，则进一步查找左子树；
(3)否则，进一步查找右子树；
二叉排序树的查找的递归算法：
template<class T> //二叉排序树中查找关键字为 K的结点,
// 若查找成功，数据成员 f是所查得结点的双亲结点指针
TreeNode<T>* SortBinTree<T>::Search_bst(TreeNode<T>* t,T K)
// 在以 t为根指针的二叉排序树中检索关键字为 K的结点，返回结
点指针
{ TreeNode<T>*p;
p=t;
if(p==NULL||p->data==K)return p; // 此处返回“空”则查找
不成功
else{ f=p;
if(K<p->data)p=Search_bst(p->lchild,K); // 到左子树中查找
else p=Search_bst(p->rchild,K); // 到右子树中查找
}}
在二叉排序树上进行查找的平均查找长度和二叉排序树
的形态有关
a,ASL＝（ 1+2+2+3+3+3） / 6＝ 14/6
b:ASL＝（ 1+2+3+4+5+6） / 6＝ 21/6 4 5
9 3
5 3
2 8
5 3
4 5
2 4
9 3
1 2
2 8
2 4
1 2
( a )
( b )
图 9, 1 2 不 同 形 态 的 二 叉 排 序 树
在最坏情况下，二叉排序树是为一棵深度为 n的单支树，
它的平均查找长度是（ n+1） /2。
在最好的情况下，二叉排序树是一棵形态与二分查找的
判定树形似，此时他的平均查找长度大约是 log2n。
考虑 n个结点有 n！种二叉排序树（其中有形态相同的）
可能，可以证明，对这些二叉排序树的查找长度进行平
均，得到的平均查找长度仍然是 O(log2n)
起因：提高查找速度，避免最坏情况出现。虽然完全
二叉树的树型最好，但构造困难。常使用平衡二叉树。
9.4.2平衡的二叉排序树 (AVL树 )
定义：平衡二叉排序树（又称 AVL树），或者是一棵
空树，或者是具有下列性质的二叉树：它的左子树和
右子树都是平衡二叉树，且左子树和右子树的深度之
差的绝对值不超过 1。
平衡因子定义：该结点的左子树的深度减去它的右子
树的深度 。
平衡二叉树上所有结点的平衡因子只可能是 -1,0和 1
一般情况下，假设由于在二叉排序树上插入结点而失
去了平衡的最小子树的根结点指针为 A（即 A是离插
入键最近，且平衡因子绝对值超过 1的祖先结点），
则失去平衡之后进行调整的规律可以归纳为下列四种
情况：（结点外的值是该结点的平衡因子）
LL型：
如图在 A的左子树 B的左子树插入新结点 S，由于 A
的平衡因子由 1增加到 2，导致失衡。为了恢复二叉
排序树的平衡性，需要进行一次顺时针的旋转操作
平衡二叉树失衡的情况和相应的调整方法
LL型失衡特点为,A－ >bf＝ 2,B－ >bf＝ 1。 相应调
整操作可用如下语句完成：
B＝ A－ >lchild； A－ >lchild＝ B－ >rchild； B－ >rchild＝ A；
A－ >bf＝ 0； B－ >bf＝ 0；
A
B A
B
BL
BL
BR
AR
S
AR
S
(b)调整后恢复平衡(a)插入新结点 S后失去平衡
二叉排序树的 LL型平衡旋转
2
1
0
0
H-1
H-1
H BR
最后, 将调整后的二叉排序树的根结点 B―接到, A处 。
令 A原来的父指针为 FA如果 FA非空, 则用 B代替 A做
FA的左子树或者右子树；否则原来 A就是根结点, 此
时应该令根指针 t指向 B。 相应调整操作可用如下语句
if(FA==NULL) t＝ B；
else if (A==FA－ >lchild) FA－ >lchild＝ B；
else FA—>rchild＝ B；
LR型,
由于在 A的左子树的 B的右子树上插入结点，使 A的
平衡因子由 1增至 2而失去了平衡，需进行两次旋转
操作（先逆时针，后顺时针），如图所示。
A
B
A R
S
( b ) 调 整 后 恢 复 平 衡
( a ) 插 入 新 结 点 S 后 失 去 平 衡
二 叉 排 序 树 的 L R 型 平 衡 旋 转
C
B L
C L
C R
A
B
C
C R
A R
C L
S
B L
1
- 1
0
- 1
2
0
H - 1
H - 2
H - 1
H - 1
LR型失衡特点为,A－ >bf＝ 2,B－ >bf＝ -1。相应调
整操作可用如下语句完成：
B＝ A－ >lchild； C＝ B－ >rchild；
B－ >rchild＝ C－ >lchild； A－ >lchild＝ C－ >rchild；
C－ >rchild＝ A； C－ >lchild＝ B；
新结点 S的插入位置有三种情况,1、在 CL下插入 S。 2、
在 CR下插入 S。 3,B 的右子树为空,C本身就是插入
的新的结点 S。针对上述三种不同情况，修改 A,B,C
的平衡因子：
最后，将调整后的二叉排序树的根结点 C接到 A处。令
A原来的父指针为 FA如果 FA非空，则用 C代替 A做
FA的左子树或者右子树；否则原来 A就是根结点，
此时应该令根指针 t指向 C：
if (FA == NULL) t＝ C； else if (A == FA－ >lchild) FA－
>lchild＝ C； else FA—>rchild＝ C；
if(S->key < C->key) //在 CL下面插入 S
{ A－ >bf＝－ 1； B－ >bf＝ 0； C－ >bf＝ 0}
if(S->key > C->key) // 在 CR下面插入 S
{ A－ >bf＝ 0； B－ >bf＝ 1； C－ >bf＝ 0}
if(S->key == C->key) //C是新的插入结点 S { A－ >bf＝ 0；
B－ >bf＝ 0； }
RR 型：
由于在 a的右子树的右子树上插入结点，使 a的平衡
因子由 -1减至 -2而失去平衡，需进行一次逆时针
旋转操作。如图所示。
A
B
A
B
BL
BL
BR
BR
AL
S
AL
S
( b ) 调整后恢复平衡
( a ) 插入新结点S 后失去平衡
二叉排序树的R R 型平衡旋转
-1
-2 0
0
H-1
H
H-1
RL 型：
由于在 a的右子树的左子树上插入结点，使 a的平衡
因子由 -1 减至 -2而失去平衡，需进行两次旋转操
作（先顺时针，后逆时针）。如图所示。
A
B
A L
S
( b ) 调 整 后 恢 复 平 衡
( a ) 插 入 新 结 点 S 后 失 去 平 衡
二 叉 排 序 树 的 R L 型 平 衡 旋 转
C
B L
C L
C R
A
B
C
C R
B R
C L
S
A L
- 1
1
1
0
0
- 2
H - 1
H - 1
H - 1
H - 2
综上所述插入一个新的结点 S时，主要包括以下三步：
1）查找应该插入位置，同时记录距离插入位置最近的
可能失衡结点 A（ A的平衡 因子不等于 0）。
2）插入新的结点 S，并修改从 A到 S路径上各个结点的
平衡因子。
3）根据 A,B的平衡因子，判断是否失衡以及失衡类
型，并做相应的处理。
LL型与 RR型对称,LR型与 RL型对称
平衡树结点类 (AVL_NODE) 及平衡树类 (AVLtree)的声明：
#define NULL 0
template<class T> class AVL_Node //平衡树 (AVL)结点类
的定义 (AVLnode.h)
{ public:T data; int bf;
AVL_Node<T> *lchild,*rchild;
AVL_Node(){} //缺省构造函数
AVL_Node(const T& item,int b=0,AVL_Node<T>
*lptr=NULL,AVL_Node<T>
*rptr=NULL):data(item),bf(b),lchild(lptr),rchild(rptr){
}};
//AVL树根结点指针
template<class T> class AVLtree:public AVL_Node<T>
{ public:
AVL_Node<T>* root;
AVLtree():root(NULL){ };
void inorder(AVL_Node<T>* t); // 中序遍历 AVL树
void LL_rotation(AVL_Node<T>*,AVL_Node<T>*); //
LL型旋转
void LR_rotation(AVL_Node<T>*&,AVL_Node<T>*); //
LR型旋转
void RR_rotation(AVL_Node<T>*,AVL_Node<T>*); //
RR型旋转
void RL_rotation(AVL_Node<T>*&,AVL_Node<T>*); //
RL型旋转
void AVL_ins(AVL_Node<T>*,AVL_Node<T>*&); // 在
平衡树上插入结点
void creat_AVL(AVL_Node<T>* &r); // 建立平衡树的算
法
};
RR型旋转
void RL_rotation(AVL_Node<T>*&,AVL_Node<T>*); //
RL型旋转
void AVL_ins(AVL_Node<T>*,AVL_Node<T>*&); // 在
平衡树上插入结点
void creat_AVL(AVL_Node<T>* &r); // 建立平衡树的算
法
};
创建 AVL树算法：
template<class T> void
AVLtree<T>::creat_AVL(AVL_Node<T>* &r) // 创建
一棵 AVL树 { AVL_Node<T> *s; T x; r=NULL;
cin>>x;while(x!=in_end) // in_end代表输入终止的符号
{ s=new AVL_Node<T>(x); // 为插入结点申请空间
AVL_ins(s,r); // 逐个插入结点并令保持平衡 cin>>x;}}
B- 树定义9.4.3B－树
一棵 m阶的 B-树，或为空树，或满足下列特性的 m叉树：
1、每个结点至多有 m棵子树；
2、除根结点和叶结点外其它个结点至少有 ?m/2?棵子树；
3、除非根结点为最低层非终端结点否则至少有两子树；
4、所有非终端结点中包含有下列信息：
（ n,A0,K1,A1,K2,A2,…, Kn,An）
其中,Ki（ 1? i ?n）为关键字，且 Ki<Ki+1（ 1?i <n），
Ai（ 0? i ?n）为指向子树根结点的指针，且指针 Ai
（ 0? i<n）所指子树中所有结点的关键字均小于 Ki+1，
指针 An 所指子树中的关键字均大于 Kn,n（ ?m/2?-1 ?
n ? m-1）为关键字的个数；
5、缩有的叶子结点都出现在同一层上，并且不带信
息（可以看作是外部结点或查失败的结点,实际上这
些结点不存在,指向这些结点的指针为空）
1 3 5
1 1 1
1 3 9
2 4 3 7 8
3 4 7 5 3 6 3
1 1 8
1 2 7 1 9 9
F
FF F
F
F
F F F F FF
一 棵 4 阶 的 B - 树
A
B C
D E
F G
H
设查找一个给定值 K，首先从根开始，若根结点中有 K，
则查找成功，否则必是下述三种情况之一：
① ki<K<ki+1,(1? i<n)。继续到 Ai 所指结点中去查
找；
② K>kn，则到 An所指结点继续查找；
③ K<k1，则转到 A0所指结点中去查找。
重复上述过程，直到查找成功或下一个要查找结点的
指针 Ai（ 0?i ?n）为“空”（或指向叶子结点 F），
则查找失败，关键字为 K的记录不在树中。
B-树的查找
在 B-树上进行查找所需时间取决于两个因素：
① 等于给定值的关键字所在结点的层次；
② 结点中关键字的数目。当结点中关键字数目较大
时可采用折半查找以提高效率。
例如：上面查找图的 4阶 B-树的 53的过程如下：
首先由根指针找到根结点 A，因为 53>35，所以找到
结点 C，又因为 43<53<78，所以找到结点 G，最后在
结点 G中找到 53。
深度为 L+1的 m阶 B-树具有的最少结点数,
B- 树的定义，第一层至少有 1个结点，第二层至少有
2个结点。由于除根之外的每个非终端结点至少有
?m/2?棵子树，则第三层至少有 2*「 m/2?个结点，依次
类推 ?,第 L+1层至少有 2*(?m/2?)i-1个结点。而
L+1层的结点为叶子结点（外部结点），若 m 阶 B-树
中具有 N个关
B－树的插入：
30
35 38
20
10 15 25
40
45 50
30
20
10 15
35 38 45 50
a
a
b
b
c
c
d
d
e
e
f
f
gg
( 1 ) 一棵3 阶B树
（2）插入 2 3 后
（3）插入 5 5,结点g需要分 裂
（4）结点 g 分裂后
（5）插入 结点3 7,结点f需要分 裂
（6）结点 f 分裂，结点c需要分 裂
23 25
40
30
20
10 15
35 38
45 50 55
a
e f
23 25
40
30
20
10 15 35 38 4523 25
40 50
55
30
20
10 15 35 37 38
45
23 25
40 50
55
30
20
10 15
35
45
23 25
37 40 50
5538
a
a a
b b
b b
c c
c c
d d
d
d
e
e e
f
f
f
f'
g
g
g
g g'g'
g'
B－树的插入：
（7）结点 c 分裂后
30 40
20
10 15 35
45
23 25
50
5538
37
30 40
20
10 15 18 35 4523 25
50
5538
37
30 40
15 20
10 35 4523 25
50
55
38
37
18
（8）插入 结点1 8 结点d 需要分裂
30 40
15 20
10 35 4523 25 28
50
5538
37
18
（9）结点 d 分裂后
a
a
a a
b
b
b
b
c c
c c
C'C'
C' C'
d
d
d d d'd'
e
e
e e
f
f
f f f'f'
f'
f'
g
g
g
g g'
g'
g'
g'
（10 ）插入结点28 后e结点需 要分裂
B－树的插入：
30 40
15 20 25
10 35 4523
50
5538
37
18 28
20 30 40
15
10 35 45
23
50
5538
37
18
28
25
20
15
10 35 4523
50
55
38
37
18 28
25
30
40
a
a
a
b b
b
c
c C'
C'
d
d
d
d'
d'
d'
e
e
e e'
e'
e'
f
f
f f'
f'
f'
g
g
g
g'
g'
g'
a'
m
（1 3 ）根结点分裂后
（1 2 ）结点b 分裂后根结点需要分裂
（1 1 ）结点b 需要分裂
b'
b'
在B - 树中插入的实例
c
C'
B-树的创建,
3 7
3 7 7 0
1 2 3 7 7 0
3 7
1 2 7 0
3 7
1 2 4 5 7 0
3 7
1 2 4 5 7 0 9 0
3 7 7 0 3 7 7 0
1 2 4 5 9 0 3 1 2 4 5 9 0
3 7 7 0
3 1 2 2 4 4 5 9 0
1 2 3 7 7 0
3 2 4 4 5
3 7
1 2 7 0
3 2 4 4 5 9 0
9 0
( 1 ) 空 树
( 2 ) 插 入 3 7 ( 3 ) 插 入 7 0
( 4 ) 插 入 1 2
分 裂
分 裂
分 裂
分 裂
( 5 ) 插 入 4 5
( 6 ) 插 入 9 0
( 7 ) 插 入 3
( 8 ) 插 入 2 4
从 空 树 开 始, 插 入 关 键 字, 创 建 一 棵 3 阶 B - 树
B-树的删除,在最下面结点中删除一个关键字
18
11 13 27 47 53 64
43 78
39 99
35
18
13 27 47 53 64
43 78
39 99
35
18
13 27 47 64
43 78
39 99
35
18
13 27 64
47 78
43 99
35
35 35
(1)一棵4阶B-树
(2)删除11后
（3)删除53后
（4)删除39后
18
13 27 78 99
47
43
35
13 18 78 99
47
43
35
35 47
13 18 78 9943
43
35 47
13 18 78 99
（3 ) 删除5 3 后
（4 ) 删除3 9 后
（5 ) 删除6 4 后
（6 ) 删除2 7 后将剩余信息与父结
点中的1 8 并入左兄弟
（7 ) 将父结点剩余信息与祖父结
点中3 5 并入4 7 左端
（8 ) 删除2 7 后最终结果
在B －树最下层结点中删除关键字
B-树的删除,在非最下层结点中删除一个关键字
1 8
1 1 1 3 2 7
4 7 5 3 6 4
4 3 7 8
3 9 9 9
3 5
1 8
1 1 1 3 2 7
5 3 6 4
4 7 7 8
3 9 9 9
3 5
1 8
1 1 1 3 2 7
5 3 6 4
4 7 7 8
3 9 9 9
2 7
1 3
1 3 1 8
5 3 6 4
4 7 7 8
3 9
9 9
2 7
( 1 ) 一 棵 4 阶 B - 树
( 2 ) 删 除 4 3 后
（ 3 ) 删 除 3 5 后, 先 用 2 7 代 替 3 5
（ 4 ) 删 除 原 2 7 后
在 B － 树 非 最 下 层 结 点 中 删 除 关 键 字
B+ 树
B+树和 m阶的 B-树差异在于：（这儿不再考虑外
部结点，而直接称最低层内部结点为叶结点）
① 有 n棵子树的结点中含有 n个关键字；
② 所有的叶子结点中包含了全部关键字的
信息及指向相应记录的指针，且叶结点本身依关
键字的大小自小而大顺序链接。
③ 所有的非终端结点可以看成是索引部分，
结点中仅含有其子树的最大（或最小）关键字。
小结
本章介绍了顺序表的三种查找方法：顺序查找,
二分法查找, 分块查找, 散列表的查找, 以及树
表：二叉排序树, AVL树, 以及 B-树的定义, 特点
和存储结构 。 并且讨论了各种查找方法的效率
―― 平均查找长度 。
