1
第 8 章 检索结构
2
§ 8.1 概述
? 检索也称查找
– 检索是指在数据元素（记录）集合中求出满足某给定条件的
记录
– 数据元素（记录）中确定某特定数据字段的值与给定值相匹
配的记录
? 关键字字段（简称关键字）
? 检索成功与不成功
? 在某此问题中，当检索不成功时要插入不存在的数据
记录，或在某种情况下删除所找到的记录
§ 8.1,1 检索的概念
3
? 检索算法（方法）,
– 按检索操作是否全部在内存进行：
? 内检索
? 外检索
– 按是否增删元素
? 静态检索
? 动态检索
§ 8.1,1 检索的概念
4
? 检索算法（方法）,
– 按是否进行比较操作
? 比较式检索
? 非比较式检索
– 按关键字是否变化
? 原词检索
? 变词检索
§ 8.1,1 检索的概念
5
? 为了提高检索效率，要专门为检索操作设置数
据结构
? 若按数据元素集合中元素间结构关系分类
– 线性结构（含线性链结构）
– 线性索引结构
– 树形结构
– 散列（杂凑）结构
§ 8.1,2 检索结构
6
? 按检索结构中数据元素是否会增加或减少分类
– 静态检索结构：操作中不增加或减少元素
– 动态检索结构：操作中可能增加元素或减少元素
§ 8.1,2 检索结构
7
? 检索算法的空间复杂度分析
– 在现有结构上进行检索的算法
– 实现检索算法而构造专门的数据结构的算法
? 检索算法的时间复杂度分析
– 以关键字的比较次数为主度量算法的时间复杂度
§ 8.1,3 检索算法的时间与空间复杂
度分析
8
? 待查关键字的位置对算法本身而言是个随机量，
所以要综合测定算法的检索次数，需使用检索
次数的数学期望
? 将检索算法的检索次数的数学期望称为平均检
索长度 ASL（ Average Search Length）
? 对检索成功（关键字在表中）情况其计算式为：
ASL=
§ 8.1,3 检索算法的时间与空间复杂
度分析
?
?
n
i
iicp
1
9
? 检索不成功的情况（关键字不在数据元素集
中），平均检索长度即为检索失败对应的比较
次数。
? 检索算法的总的平均检索长度应为检索成功与
失败两种情况的平均检索长度的数学期望。
§ 8.1,3 检索算法的时间与空间复杂
度分析
10
? 判定树中每个结点表示被查数据元素集中的一个元素
（常用元素编号表示）
? 从树根到某一结点的路径，就表示检索该结点所经历
的过程，路径上各结点为检索中测试（比较）过的结
点
? 树结点的各个儿子，表示从该结点起下步检索的各选
择分枝
? 对无儿子结点，表示检索过程进行到它（即与它比较）
后，不能继续进行，应终止
§ 8.1.4 检索算法的判定树
11
? 判定树的构造方法
– 若某检索算法 A在数据元素集 D上进行检索，则 A对 D的（检索）
判定树定义为：
– 若 D=空，则 A对 D的判定树为空
– 若第 1次是与元素 i1比较（测试），则令 i1为判定树的根
– 若与 i1比较后，下一步的检索操作是在数据集 D1,...,Dm 之一中
进行（即可能在 D1,...,Dm中任意一个上进行），则令算法 A的
其余部分对 D1,...,Dm的判定树（子树）为根结点 i1的各子树，
这里,D1,...,Dm应为 (D-{i1})的一个划分。 （即 D1∪,..∪ Dm=D-
{i1}，且 Dj∩ Dk=空,j≠ k,j,k∈ {1,...,m}）
§ 8.1.4 检索算法的判定树
12
1 2 3 4 5 6 7 8 9
（ a）顺序查找判定树
5
2 7
1 3 6 8
4 9
（ b）折半查找判定树
5
2 7
1 3 6 8
4 9
（ c）折半查找判定树 (带外结点
)
图 - 判定树
13
? 判定树的深度就表示检索算法的最大比较次数
? 树的分枝数越大（即数据集分块越多），树深
度就越小
? 检索某结的比较次数，就是从树根到该结点的
路径上的结点个数
? 外结点
? 增设了外结点的判定树为完全二叉树
§ 8.1.4 检索算法的判定树
14
? 增设了外结点的判定树为完全二叉树
? 判定树的 内路径 长定义为该树中各内结点的路径长
（从根到某结点的路径长定义为该结点的内径长）之和
? 外路径 长定义为树中各外结点的路径长之和
?设 I与 E分别代表判定树的内与外路径长, 则有
E=I+2n
这里 n为内结点数目
§ 8.1.4 检索算法的判定树
15
§ 8.1.4 检索算法的判定树
? 实际中，各关键被查概率可能不同，为此，引入加权
内外路径长
? 设 wi与 li分别为结点 i的权值与在树中的层次数（即结点
i的路径长），则定义 wi与 li的积为 i的加权路径长
? 加权内路径长 I=
? 加权外路径长 E=
i
n
i
ilw?
?1
i
n
i
ilw?
?
?
12
1
16
§ 8.2 线性结构的检索
? 属于静态检索
? 算法简单，但速度不高
? 主要用在对小型数据集的检索
? 一般的线性表有两种存贮结构：连续式与链式
? 对它们的检索，一般采用顺序搜索的方式 ── 称为顺
序查找
? 若元素已按关键字排序，则可采用更高效的检索法
── 折半查找
17
§ 8.2.1 无序表的检索
(一 )算法
long SeqSearch(int a[],long n,int key)
{ /*连续存储结构的线性表的顺序查找
a[ ]——输入量,一维数组, 充当线性表, n为元素个数 。
序号为 0的位置不使用
key——待查关键字
返回 ——成功时返回 key在表中的序号, 否则返回 0*/
long i;
a[0]=key; //设置监视哨
i=n;;
while(a[i]!=key) i--;
return i;
}
18
§ 8.2.1 无序表的检索
(二 )平均检索长度
? 检索成功时的平均检索长度
ASL=∑ 1/n(n-i+1)=1/n (n-i+1)=(n+1)/2=O(n)
ASL总 =q0(n+1)+q1(n+1)/2
? 若它们是等概率的
ASL总 =1/2(n+1)+1/2·(n+1)/2=3/4(n+1)
19
§ 8.2.1 无序表的检索
(三 )线性链表的顺序检索
? 在链表中检索关键字值为 key的结点的过程为：
p=pHead;
while (p!=NULL && p→key!=key) p=p→next ;
return p; //p为 NULL时失败，否则 p指向所查到的结点
20
§ 8.2.2 有序表的折半检索
(一 )折半检索算法
? 基本思想
– 先找出有序表中点位置上的元素 （ 表空时无中点, 表示检索
不成功 ）, 用待查关键字与它比较
– 若相等, 则已查到, 结束
– 否则, 若它小于待查关键字, 则下步在有序表的前半部 （ 值
小于中点元素的部分 ） 中按类似方法检索, 若它的值大于待
查关键字, 则在表的后半部按类似方法检索
21
§ 8.2.2 有序表的折半检索
(一 )折半检索算法
longBinSearch(int a[],long n,int key)
{/*有序表 （ 升序 ） 的折半查找的非递归算发
a[]——输入量, 一维数组, 充当有序线形表 （ 连续结构 ）, 表中
元素按关键字 key的升序排列, 0号位置空置
key——输入量, 待查关键字
返回 ——返回所找到的关键字的位置号, 找不到时返回 0
*/
long low,high,mid;
low=1;high=pL-last;
22
§ 8.2.2 有序表的折半检索
(一 )折半检索算法
while(low<=high)
{
mid=(low+high)/2; //求中点
if (key==a[mid] ) return mid;
else
if ( key < a[mid]) high=mid-1; //下次在前半部分查找
else low=mid+1; //下次在后半部分查找
}
return 0; /*查找失败 */
}/BinSearch
23
§ 8.2.2 有序表的折半检索
(一 )折半检索算法
long BinSearch2(int a[],long low,long high,int key)
{/*有序线形表 （ 连续存储结构 ） 的折半查找的递归算法
a[]----同前
long,high——输入量，指定查找范围，分别为有序表的查找范围的低端
和高端的序号
返回 ——同前
*/
long mid;
24
§ 8.2.2 有序表的折半检索
(一 )折半检索算法
if(low>high) return 0; //查不到
mid=(low+high)/2;
if(key==a[mid]) return mid;
if(key<a[mid]) return BinSearch2(a,low,mid-1,key); //在前半部分查找
else return BinSearch2(a,mid+1,high,key); //在后半部查找
}//inSearch2
25
§ 8.2.2 有序表的折半检索
(二 )判定树
? 折半检索判定树具有下列性质：
① 任一结点的左右子树中的结点数目最多相差 1
② 任意两棵折半检索判定树, 若它们的结点数目相同, 则它们的
结构完全等同 （ 全等 ）
③ 具有 n个结点的折半检索判定树的深度为 「 log2n」 +1,即深度
与同结点数目的顺序二叉树相同 。
④ 折半检索判定树是平衡二叉树, 即任一结点的左右子树的深度
最多相差 1。
⑤折半检索判定树中任两个叶子所处层次号之差不超过 1
26
5
2 7
1 3 6 8
4 9
（ b）折半查找判定树
27
§ 8.3 线性索引结构
? 索引是为了加快检索速度而引进的一种数据结构
? 索引技术中的关键对象是索引
? 索引项的结构为
? 若索引中的索引项按关键字有序，则称这种索引为线
性索引（也称索引表）
? 多级索引
§ 8.3.1 概述
关键字 关键字所在记录的位置的指示器
28
? 线性索引技术分为稠密索引与非稠密索引（非稠密索
引常为分块索引 ── 索引顺序结构）
? 若索引组织的好，则可显著提高检索速度
? 索引技术除涉及检索操作外，还涉及索引的创建与维
护问题
? 索引项可以组织成多种结构，一般有线性结构与树形
结构
§ 8.3.1 概述
29
? 如果数据元素集中的每个元素对应一个索引项，则这
种索引称为稠密索引
§ 8.3.2 稠密索引
8
20
35
65
70
90
100
100
100
20
8
35
90
100
65
70
线性稠密索引的例子
30
? 假定数据集为连续存贮结构的线性表
? 创建索引相当于一个排序过程
? 以枚举排序为例说明稠密索引的创建
/*定义常量 ListSize,类型 tKey,tElem,tLinearList见程序 8.2-1*/
typedef struct
{tKey key; /*索引项中的关键字字段 */
long ip; /*索引项中记录位置指示器, 这里假定该字
段存放数组下标 */
}/*索引项类型 */
§ 8.3.2 稠密索引
31
tIndexItem *CreateIndex(tlinearList *pL)
{/*借用枚举排序法为线性表 （ 连续存储结构 ） pL建立稠密索引
pL—输入量, 待创建稠密索引的线性表
返回值 —所创建的索引表的首地址
*/
long i,j;
tIndexItem *pII;
pII=(tindexitem )malloc(sizeof(tIndexItem)*pL->last+1);
/*为索引表申请存储区 */
if(pII==null) return NULL; /*不能分配空间, 失败返回 */
for(i=0;i<=pL->last;i++) pII[i].ip=1;
/*索引表中记录指示器初始化，在下面的步骤中,pII充当计数器，
pII[i ]的值为关键字 key大于或等于 pL-room[i].key的记录数目加 1*/
§ 8.3.2 稠密索引
32
for(i= pL->last;i>0;i--)
for(j=i-1;j>0;j--)
if(pL->room[j[.key>pL->room[i].key]
pII[j].ip++;
else pII[i].ip++;
return pII;
}/*CreateIndex*/
33
§ 8.3.3 分块索引（索引顺序检索）
(1)分块索引结构
? 分块有序是指：对任意两块 B1和 B2，若 B1在逻辑上位
于 B2之前，则 B1中任一元素的关键字也在逻辑上位于
B2中任一元素之前
? 分块有序并不要求块内一定有序
? 每块对应一个索引项，每个索引项的结构为：
最大或最小关键字值 块首地址或尾地址
34
§ 8.3.3 分块索引（索引顺序检索）
8 101 210
0 4 9
10 8 35 70 101 180 120 140 130 280 290 210 220
0 1 2 3 4 5 6 7 8 9 10 11 12
35
§ 8.3.3 分块索引（索引顺序检索）
(1)分块索引结构
? 若数据集为一维数组 data，则为它生成一个名为 index 的索引表
的过程为（假定块长为 BlockSize,索引中存块内最小关键字与
块首元素下标,数据集长为 N）：
numBlock=N/BlockSize+N%BlockSize;
/*求出块数目 numBlock*/
posBlock=0;
for(i=1;i<=numBlock;i++)
{index[i].ip=posBlock;
index[i].key=data[posBlock];
posBlock=posBlock+BlockSize;
}
36
§ 8.3.3 分块索引（索引顺序检索）
(1)索引顺序检索
? 分两个步骤：
– ①在索引表中确定关键字所在块；
– ②在块中检索关键字。
? 分块检索的平均检索长度 ASL应为
ASL=ASLi+ASLb
= 1/bj+ 1/sj
=(b+1)/2+(s+1)/2
=1/2(n/s+s)+1
37
§ 8.4 树形检索结构（树目录）
? 树中的每一结点是一个索引项
? 树结构的检索一般也快于线性结构
? 树目录也常常用于驻留在外存上的数据集
? 树目录多用作动态结构
§ 8.4.1 概述
38
? 二叉排序树是一种基本的树目录，由它可导出最优
（次优）二叉排序树与平衡二叉树。然后导出各种 B树。
? B树可用来实现高效的外部文件索引，广泛地应用于数
据库实现中
? 对树目录，由于检索就在树目录上进行，所以树目录
的检索判定树就是树目录本身
§ 8.4.1 概述
39
(一 )基本概念
?二叉排序树 （ 也称二叉检索树 ） 是这样一种结点含关键
字的二叉树, 它或为空二叉树, 或满足下列性质：
(i)若它的左子树不空, 则其左子树上所有结点的关键字
均分别小于它的根结点关键字；
(ii)若它的右子树不空, 则右子树上所有结点的关键字均
分别大于它的根结点的关键字 。
(iii)它的左右子树亦分别为二叉排序树 。
§ 8.4.2 二叉排序树
40
§ 8.4.2 二叉排序树
50
30 80
10 70 90
20 55
ifelse
for
charr while
case
图 - 二叉排序树
(a) (b)
41
(一 )基本概念
?前面讨论的折半检索与 Fibonacii检索判定树均为二叉排序树
?对二叉排序树进行中序遍历就会得到一个结点 （ 关键字 ） 的升序序
列
?若给二叉排序树添加外结点, 则外结点就可有具体的含意：某外结
点代表这么一个值的集合, 该集合中的值的大小由开区间 (a,b)确定,
这里 a与 b 分别为该外结点在该二叉排序树 （ 带外结点 ） 的中序遍历
序列中的前趋结点与后继结点的关键字值
§ 8.4.2 二叉排序树
42
(一 )基本概念
?C++ 描述
template <class TElem>
struct TBinTreeNode
{
TElem info;
……
TElem *lc,*rc;
}
§ 8.4.2 二叉排序树
43
(二 )二叉排序树的检索
?二叉树检索的递归程序为：
TBinTreeNode *SearchBinSortTree(TBinTree *root,TElem key)
{//root为被检索的树的根指针
if (root==NULL) return NULL;
if (root->info == key) return root;
if (key <root->info) return SearchBinSortTree(roo->lc,key);
return SearchBinSortTree(roo->rc,key);
}
§ 8.4.2 二叉排序树
44
(二 )二叉排序树的检索
?二叉树检索的非递归程序为：
TBinTreeNode *SearchBinSortTree2(TBinTree*root,TElem key)
{//root为被检索的树的根指针
TBinTreeNode *p;
p = root;
while (p!=NULL)
{
if (key ==p->info) return p;
if (key <p->info) p = p->lc;
else p = p->rc;
}
return p;
}
§ 8.4.2 二叉排序树
45
(二 )二叉排序树的检索
?有时候, 需要找到某关键字对应的结点的父亲, 实现程序如下：
TBinTreeNode *SearchFatheBinSortTree(TBinTree *root,TElem key,
char &isLeft)
{//root为被检索的树的根指针,检索 key,若找到, 则返回其父结点的
指针,
//并且, 当 key在左儿子中时, 置 isLeft为 1,否则置 isLeft为 0。
//找不到 key时返回 NULL
TBinTreeNode *p,*p0;
isLeft=0;
p0=NULL;
p = root;
§ 8.4.2 二叉排序树
46
(二 )二叉排序树的检索
while (p!=NULL)
{
if (key ==p->info) return p0;
p0 = p;
if (key <p->info) {p = p->lc; isLeft=1;}
else {p = p->rc; isLeft=0; }
}
return p0;
}
§ 8.4.2 二叉排序树
47
(三 )二叉排序树的插入
TBinTreeNode *InsertBinTree(TBinTreeNode * &root,
TBinTreeNode *pNode,char &isLeft)
{ //将 pNode所指结点插入到以 root为根的二叉排序树中, 返回插入后
pNode的父亲,
//isLeft指示 pNode是否是左儿子 。
//如果 root为空, 则 pNode被作为树根, root直接指向 pNode
TBinTreeNode *p;
§ 8.4.2 二叉排序树
48
(三 )二叉排序树的插入
if (root==NULL) {root=pNode; return NULL;}
p = SearchFatherBinSortTree(root,pNode->info,isLeft);
if （ isLeft） p->lc=pNode;
else p->rc=pNode;
return p;
}
§ 8.4.2 二叉排序树
49
70
10
70
30
20 80
10
70
30
20 80
50
9010
70
30
20 80
50
9010
70
30
20 80
50
55
70
20
70
30
20
10
70
30
20
(a)初态 (b)插入 70 (c)插入 20 (d)插入 30 (e)插入 10
（ 空 ）
(f)插入 80 (g)插入 50 (h)插入 90 (i)插入 55
图 - 建立二叉排序过程示例
50
(三 )二叉排序树的插入
利用该程序, 也可根据原始数据生成二叉排序树：
TBinTreeNode *CreateBinTree(int a[],long n)
{//根据一维数组 a[]中的原始数据, 创建二叉排序树, 返回其树根 。
long k;
TBinTreeNode *root,*p;
char isLeft;
root=NULL:
for (k=0; k<n; k++)
{
p = new TBinTreeNode;
p->info=a[k];
InsertBinSortTree(root,p,isLeft)
}
}
§ 8.4.2 二叉排序树
51
(三 )二叉排序树的插入
?显然, 读入关键字的次序不同, 所建二叉树的形式也不
同
§ 8.4.2 二叉排序树
5
4
3
2
1
5
4
3
2
1
图 - 插入次序不同，树结构也不同
52
(四 )二叉排序树的删除
?(1) 若 p无左子树, 则用 p的右子树 （ 若有的话 ） 的根代替 p
if(p==f→lc)
f→lc=p→rc ; //p是 f的左儿子
else f→rc=p→rc ;
return p;
§ 8.4.2 二叉排序树
53
(四 )二叉排序树的删除
?(2) 若 p有左子树, 但 p无右子树, 则用 p的左子树代替 p
（ 见图 8-0b） 。 实现方法为：
if (f→lc==p)
f→lc=p→lc ;
else f→rc=p→lc ;
return p;
§ 8.4.2 二叉排序树
54
p
PR
f
p
PR
f
(a)p无左子树
p
PL
f
p
PL
f
(b)p有左子树, 但无右
子树
55
(四 )二叉排序树的删除
?(3) 若 p有左子树, 也有右子树, 则用 p的中序前驱 （ 中序
序列中 p的直接前趋 ） q代替 p,并将 q的左子树转让给 q的父
亲 （ 注,q必无右子树 ）
q=p→lc ;
r=p; //使 r一直为 q的父亲
while (q->rc!=NULL)
{
r = q ;
q=q→rc ;
}
§ 8.4.2 二叉排序树
56
(四 )二叉排序树的删除
//用 q的左子树置换 q
// r等于 p时, q就是 p的左儿子, 也是将 q 的左子树挂接在 p的左链
r→rc=q→lc ;
//下面用 q置换 p
q→lc=p→lc ;
q→rc=p→rc ;
if (f→lc=p) f→lc=q ;
elsef→rc=q ;
retrun p;
§ 8.4.2 二叉排序树
57
f
Q
PR
S
SL R
RL
QL
左图
(d)删除 p的另一方法 (用 p左儿
置换 p,p 的右子树挂接到 p 的
直接前趋的右链 )
P
PR
f
p
S
SL R
RL
r
Q
QL
q
Q
PR
f
q
S
SL R
RL
r
QL
(c)p有左, 右子树
图 - 二叉排序树中删除 p
58
typedef int tKey; /*关键字类型 */
typedef struct tSBTreeNode
{tKey key; /*关键字字段 */
······ /*这里可定义其他字段 */
struct TSBTreeNode *lc,*rc; /*左右儿子域 */
}tSBTreeNode;
tSBTreeNode *SBtreeSearch(tSBTreeNode *root,tKey key,tSBTreeNode
**f)
{/*二叉排序树查找子程序 （ 递归 ）
root——输入量, 为待查二叉排序树的根指针
key——输入量, 待查关键字
*f——指向被查接点的父亲, 用树根调用此函数时, 变量 f为空
指针的地址
返回值 ——树中第一个关键字等于 key的结点的指针, 若树中五
此结点, 则返回 nuul
*/
59
if(root==NULL||root->key==key)
return root;
*f=root;
if(key<root.key)
return SBTreeSearch(root->lc,key,f);
else return SBTReeSearch(root->rc,key,f);
}/*SBTreeSearch*/
60
tSBTreeNode *SBTreeSearchPos(tSBTreeNode *root,tKey
key,char *isl)
{/*在二叉排序树中查找插入位置 （ 递归 ）
root——待查二叉排序树的根指针
key—— 输入量, 待查关键字
*isl——输入量, 说明见下
返回值 ——返回以 *root为根的二叉排序树中的 key应
出现的位置的父指针 。 若位置为他父亲懂得左儿子,
则置 *isl为 1,否则置为 0
注：若树中已有与 key相同的关键字结点, 则认为 key 小
于它们
*/
61
if(root==NULL) return NULL; /*为提高速度，此行可取消，但调用该
函数时不能用空树调用（ *root不为 NULL） */
if(roor-rc==NULL)
{*isl=1;
return root;
}
else return SBTreeSearchPos(root->lc,key,isl);
}
else
{if(roo->rc==NULL)
{*isl=0;
return root;
}
else return SBTreeSearchPos(root->rc,key,isl);
}
}/*SBTreeSearchPos*/
62
tSBTreeNode * SBTreeIns(tSBTreeNode **root,tKey,key)
{/* 在二叉排序树中插入一个关键字结点
*root——输入量, 指向二叉排序树的根
key——输入量, 为待插入的关键字值
返回 ——返回插入的结点的指针
*/
tSBTreeNode *p,*q;
char isl;
q=(tSBTreeNode )malloc (sizeof(tSBTreeNode)); /*申请一
个结点 */
q->key=key;q->lc=NULL,q->rc=NULL;
63
if(*root==NULL)
*root=NULL; /*对空树, 将新结点作为树根 */
else
{ p=SBTreeSearchPos(*root,key,&isl); /* 找插入位置 */
if(isl)
p->lc=q;
else p-<rc=q;
}
return q;
}/*SBTreeSearchPos*/
64
tSBTreeNode
SBTreeDelNode(tSBTreeNode*p,tSBTreeNode **f)
{/*删除二叉排序树中由 p所指向结点, 并令 *f指向删除 p
后由 p子树中剩余部分构成的新子树的根 。 （ 注：本算
法删除 p后, 仍使 p子树剩余部分保持在同一子树中 ）,
返回被删除结点
*/
tSBTreeNode *q,*r,*p0;
p0=p; /* d当 *f==p时, 下面的操作将改变 p,故应保存 */
65
if(p->lc==NULL)
*f=p->rc;
else
if(p->rc==NULL)
*f=p->lc;
else /*p 的左右子树均不为空 */
{q=p->lc;
r=p; /*使 r一直为 q之父结点指针 */
while(q->rc!=NULL) /*找 p的直接前驱 q*/
{r=q;q=q->rc;}
if(r!=p)
r->rc=q-lc; /*用 q的左子树代替 q的位置 */
else /* r等于 q时, q就是 p 的左儿子, 故应将 q 的左子树挂接到 p
的左链 */
r->lc=q->lc;
66
/*下面用 q置换 p*/
q->lc=p->lc;
q->rc=p->rc;
*f=q;
}/*if(p->rc==NULL)… else… */
return p0;
}/*SBTreeDelNode*/
67
tSBTreNode * SBTreeDelKey(tSBTreeNode **root,tKey,key)
{/*从二叉排序树中摘除指定关键字所在的第一个结点
*root——指向二叉排序树的根
key——待删除关键字值
返回 ——被删除结点的指针
*/
tSBTreeNode *p,*f;
68
if(key==*root->key)
return SBTreeDelNode(*root,root);/*删根 */
else
{p=SBTreeSearch(*root,key,&f); /*找 key所在结点 p及其父亲 f*/
if(p==NULL) return NULL ; /*找不到 key*/
if(p==f->lc)
return SBTreeDelNode(p,&(f->lc)); /*删 p,用 f的左链代管 p子树的剩
余部分 */
else return SBTreeDelNode(p,&(f->rc));
}
}/*SBTreeDelKey*/
69
(五 )二叉排序树的分析与最优二叉排序树
?只需分析二叉排序树的检索算法
?检索算法的效率与树的结构相关, 而树结构又与关键字进
入树中的次序有关
§ 8.4.2 二叉排序树
80
60 85
20 90
(b) 关键字输入次序为 (80,60,20,85,90)
所对应的二叉排序树
20
60
80
85
90
(关键字输入次序为 (20,60,80,85,90)
所对应的二叉排序树
70
(五 )二叉排序树的分析与最优二叉排序树
?给定 n个关键字与它们的 n个检索概率值, 能否存在一棵平
均检索长度 （ 即加权内外路径长度, 见 § 8.1.4） 最小的二
叉排序树呢？ 回答是肯定的 。 这种树称为最优二叉排序树 。
?对于经常进行插入与删除的二叉排序, 较好的选择是平衡
二叉排序树, 它是二叉排序树与最优二叉排序树之间的一
种折衷 。
§ 8.4.2 二叉排序树
71
(一 )概念
?高度平衡二叉树 （ height Balanced binary tree）,或是一棵空树, 或是
具有下列性质的二叉树：它的左右子树均为平衡二叉树, 且它们二者
的深度之差不超过 1。 在不至于产生混淆的情况下, 我们常称其高度平
衡二叉树为平衡二叉树或平衡树 。
?平衡因子：二叉树中的结点的平衡因子定义为该结点的左子树的深度
与右子树深度之差 。
?平衡二叉排序树：若二叉排序树为平衡二叉树, 则称为平衡二叉排序
树 。 在本节中, 常以平衡二叉树称平衡二叉排序树 。
§ 8.4.3 平衡二叉排序树的性质
72
(二 )若干性质
① 平衡树中任一结点的平衡因子均为 -1,0,1三者之一, 这是
显然的 。 因为任一结点的左右子树深度之差不超过 1。
② 任一棵二叉排序树, 都可以转化为一棵平衡二叉排序树 。
③ （ A e c oHBe ck,H c 1962） 一棵具有 n 个 （ 内部 ） 结
点的平衡二叉树, 其高度 h满足
log2(n+1)≤ h≤ 1.4404log2(n+2)-0.328
§ 8.4.3 平衡二叉排序树的性质
73
(一 )插入平衡调整
设 p 是一棵平衡二叉树 （ p为根 ）, 则将某一结点插入它中后, 有下列
情况
( i)p的平衡因子为 -1（ p左重 ）, 结点插入到 p的左子树, 并使 p左子树
升高, 则 p变为左超重 （ p平衡因子变为 -2）, 此时需进行平衡调整 。
(ii)p的平衡因子为 1（ p右重 ）, 结点插入到 p的右子树, 并使 p 右子树
升高, 则 p变为右超重, 需进行平衡调整 。
(iii)其它情况均不需进行平衡调整 。 即 p平衡因子 0,或 p左重, 但结点
插入到 p的右子树, 或 p右重, 但结点插入到 p左子树 。
§ 8.4.4 平衡二叉树局部平衡调整算法
74
(一 )插入平衡调整
§ 8.4.4 平衡二叉树局部平衡调整算法
A
B A
B
图 - 二叉排序树变换
左 右：以 B为轴顺时针旋转 （ 父变左子之右子 ）
右 左：以 A为轴递时针旋转 （ 父变右子之左子 ）
75
(a)
-1/-2
P
0/-1
P1
h h-1
P1l
×
P1r h-1
插入结点
P1r h-1或 h-2
0
P
0/1
P
h
P1l
×
Pr h-1P1r h-1或 h-2
LL
76
插入结点
P2r h-2或 h-3
-1/-2
P
0/1或 1/2P1
h-1h-2
P2l
×
Pr h-1
0/-1或 -1/-2P2P1l
h-1或 h-2
P2r
P
P1
P2l
×
PrP2
P1l
P2r
1或 2P
P2l
×
PrP1l
0或 1P1
0P2
LR
(b)
77
1/2
P
0/1或 1/2P1
hh-1
P1r
×
h-1 Pl
P1lh-1或 h-2
RR
0
P1
0/-1
P P1r
×
P1lPl
(c)
78
RL
插入结点
1/2
P
Plh-1 0/1或 -1/-2P1
0/-1或 -1/-2P1 P1r h-1或 h-2
P2r h-2或 h-3
h-1 h-2
P2l
×
P1r
P
P1P1l
×
Pl P2
P2r
P2r
1或 0或 2P1
P2l
×
P1rPl
0P
P2
(d)
图 - 在平衡二叉排序树中，插入接点后的平衡调整（结点内标住的 x/y表示
插 入前与插入后的平衡因子分别为 x/y。图中，圆圈表示结点，方框表示子
树
79
（ 空树 ） 插入结点 10 10 插入 6 10
6
插入 3
对子树 10LL
10
6
3
插入结点 2,5
10
6
3
52
插入 4
10
63
5
2 4
对子树 6LR
10
6
3
52
4
插入 16
16
10
63
5
2 4
对 6RR
16
10
6
3
5
2 4
插入结点 18,20
80
16
10
6
3
5
2 4
18
20
对 16RR 插入 17
18
16
10
6
3
5
2 4
20
18
16
10
6
3
5
2 4
20
17
对 10RL
18
16
10
6
3
5
2 4
2017
图 - 平衡二叉树的插入与平衡 （ 箭头所指结点为最小不平衡
子树的根 ）
81
(二 )删除平衡调整
设 p是一棵平衡二叉排序树 （ 子树 ）, 则当 p的某子树高度
被降低 1后, 仅在下列情况下, p才需进行平衡调整：
(i)p右轻 （ 即左重 ）, 且 p右子树高度被降低
(ii)p左轻 （ 即右重 ）, 且 p左子树高度被降低
§ 8.4.4 平衡二叉树局部平衡调整算法
82
(a)LL型
LL
-1/-2
P
0/-1
P1
h-1
h-2Pr
×
P1lh-1 P1r h-1或 h-2
1或 0P1
-1或 0
P
P1l
P1r Pr
×
83
删除 28
30
20
10
6 16 26 40
4 8 18 22 28
217
45
30
20
10
6 16 26 40
4 8 18 22
217
45
8
26
30
18
10
22 40
21 45
对 26进行 LL 删除 4,6,16,20
26
30
20
10
6 16 22 40
4 8 18 21
7
45
84
删除 45
8
26
30
18
10
22 40
21
删除 8
26
30
18
10
22 40
21
2110
30
22
18
26 40
对 18进行 RL
图 - 平衡二叉排序树的删除平衡调整
85
1970年 R.Bayer和 E.Mccrerght提出了一种适合用于外查找的树，它是
一种平衡的多叉树，其特点是插入、删除时易于平衡，外查找效
率高，适合于组织磁盘文件的动态索引结构，这就是我们将要讨
论的 B-树。
1)B-树的定义
一 棵 m阶的 B-树满,或为空树，或为满 足下列条件 的 m叉树,
(1)每个结点至多有 m棵子树 ；
(2)若 根结点 不 是 叶结点,则 至少有 2棵子树；
(3)除根之外的所有非终端结点 至少有 ?m/2?棵子树 ；
8.5 B-树
86
(4)所有的非终端结点所包含的信息：
（ n,A0,K1,A1,K2,A2,…,KN,AN)
其中 Ki(i=1,..,n)为关键字，且 Ki<=Ki+1;
Ai(i=0,..,n)为指向子树根结点的指针，且指针 Ai-1的指子树中所有结点的
关键字昀小于 Ki(I=1,..,n),An的指子树中所有结点的关键字均大于 Kn，
n(?m/2?-1<=n<=m-1)为关键字的个数（或 n+1为子树个数）。
(5)的有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结
点或查找失败的结点，实际上这些结点不存在，掼向这些结点的指针为
空）。
B-树
书 P239图
87
1 35
1 18
1 11 1 391 27
3 47 53 64
1 99
2 43 78
t
F F F F F F
F F F F
F F
4阶的 B树，深度为 4
88
#define m 3 //B树的阶
typedef struct BTNode {
int keynum; //结点中关键字个数，即结点的大小
struct BTNode *parent; //指向双亲结点
KeyType key[m+1]; // 关键字向量,0号单元未用
struct BTNode *ptr[m+1]; //子树指针向量
Record *recptr[m+1]; //记录指针向量,0号单元未用
} BTNode,*Btree; //B树结点和 B树的类型
typedef struct {
BTNode *pt; //指向找到的结点
int i; //1..m,在结点中的关键字序号
int tag; //1：查找成功,0：查找失败
} Result; //B树的查找结果类型
B树查找算法
89
Result SearchBTree ( Btree T,KeyType K)
//在 m阶 B树上查找关键字 K，返回结果 (pt,i,tag)。若查找成功，则特
//征值 tag = 1,指针 pt所指结点中第 I个关键字等于 K；否则特征值 tag= 0，
//等于 K的关键字应插入在指针 pt所指结点中第 i和第 i+1个关键字之间
p = T; q = NULL; found = FALSE; i = 0;
//初始化,p指向待查结点,q指向 p的双亲
while ( p && !found ) {
n = p->keynum; i = Search ( p,K);
//在 p->key[1..keynum]中查找,i使得,p->key[i]<=K<p->key[i+1]
if ( i>0 && p->key[i] == K) found = TRUE; //找到待查关键字
else ( q = p; p = p->ptr[i]; }
}
if ( found ) return ( p,i,1); //查找成功
else return ( q,i,0); //查找不成功，返回 K的插入位置信息
}// SearchBTree
90
B-树的 插入和删除
? B- 树的插入
首先在最低层的某个非终端结点中添加一个关键字，若该结点的
关键字个数不超过 m-1，则插入完成，否则要产生结点的“分
裂”。
? B- 树的删除
首先应找到该关键字所在结点，并从中删除之，若该结点为最下
层的非终端结点，且其中的关键字数目不少于 ?m/2?,则删除完成，
否则要进行, 合并, 结点的操作。
91
45
53 9024
3 12 37 50 61 70 100
bt
b
c d f g h
a
e
(a) 一棵 2-3树
45
53 9024
3 12 30 37 50 61 70 100
bt
b
c d f g h
a
e
(b) 插入 30之后
92
45
53 9024
3 12 26 30 37 50 61 70 100
bt
b
c d f g h
a
e
(c)
45
53 9024 30
3 12 37 50 61 70 100
bt
b
c d' f g h
a
e
(d) 插入 26之后
26d
93
(e)
45 70
5324 30
3 12 37 50 61 100
bt
b
c d' f g h
a
e
插入 85之后
26
45
53 9024 30
3 12 37 50 61 70 85 100
bt
b
c d' f g h
a
e
26
45
53 70 9024 30
3 12 37 50 61 100
bt
b
c d' f g h
a
e
26
(g)
85
g'
90
85
g'
d
d
d
(f)
94
(h)
45 70
7 24 30
3 37
bt
b
c d'
a
26
24 45 70
7
37
bt
b
d'
a
26
d
d
(i)
12c'
53
50 61 100
f g h
90
85
g'
30b' 53
50 61 100
f g h
90
85
g'
e e'
e'e
3
c
12c'
95
70
7
37
bt
b
d'
a
26d
30b' 53
50 61 100
f g h
90
85
g'
e e'
c
12c'
插入 7之后
24
a'
45
m
3
96
Status InsertBTree ( Btree *T,KeyType K,Btree q,int i) {
//在 m阶 B树 T上结点 *q的 key[i]与 key[i+1]之间插入关键字 K。
//若引起结点过大，则沿双亲链进行必要的结点分裂调整，使 T仍是 m阶 B树。
x = K; ap = NULL; finished = FALSE;
while ( q && !finished ) {
Insert ( q,i,x,ap); //将 x和 ap分别插入到 q->key[i+1]和 q->ptr[i+1]
if ( q->keynum < m) finished = TRUE; //插入完成
else { //分裂结点 *q
s = ?m/2?; split ( q,ap); x = q->key[s];
//将 q->key[s+1..m],q->ptr[s..m]和 q->recptr[s+1..m]移入新结点 *ap
q = q->parent;
if ( q) i = Search (q,x); //在双亲结点 *q中查找 x的插入位置
} //else
} //while
if ( !finished ) //T是空树 (参数 q的初值为 NULL)或者根结点已分裂为结点 *q和 *ap
NewRoot (T,q,x,ap); //生成含信息（ T,x,ap)的新根结点 *T，原 T和 ap为子树指针
}
97
B树的删除过程
45
53 9024
3 37 50 61 70 100
bt
b
c d f g h
a
e
45
61 9024
3 37 53 70 100
bt
b
c d f g h
a
e
98
B树的删除
45
9024
3 37 61 70 100
bt
b
c d g h
a
e
45 90
1003 24
bt
c
a
h61 70g
99
? B+树是应文件系统所需的一种 B- 树的变型树。 m阶的 B+树和 m阶的 B-树的
差别在于：
（ 1）有 n棵子树的结点中含有 n个关键字；
（ 2）所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录
的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
（ 3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）
中的最大（或最小）关键字。
B+ 树
100
B+ 树
59 97
15 44 59
21 37 44
72 97
63 72 85 91 9751 5910 15
root
sqt
101
? 通常在 B+树上有两个头指针，一个指向根结点，另一个指向关键字最小的
叶子结点。
? B+树的查找运算有两种：
– 从最小关键字起顺序查找
– 从根结点开始，进行随机查找。
? 在 B+树上进行随机查找、插入和删除的过程基本上与 B-树类似。
? 在查找时，若非终端结点上的关键字等于给定值，并不终止，而是继续向
下直到叶子结点。
B+ 树
102
8.6 哈希 表
9.4.1 哈希 表（ Hash Table,散列表 )
散列 (Hashing)基本思想：以结点的关键字 K为自变量，通过
一个确定的函数关系 f, 计算出对应的函数值 f(K),把这个值解
释为结点的存储地址，将结点存入 f(K)所指的存储位置上。查找
时再根据要查找的关键字用同样的函数计算地址，然后到相应的
单元里去取要找的结点。因此散列法又称关键字 -地址转换法。用
散列法存储的线性表叫散列表 (Hash Table),上述的函数 f称为散
列函数,f(K)称为散列地址。
103
编号 地区名 总人口 汉族 回族,..
C[ 1..30 ]
散列函数：
（ 1） f(key) = key,key 是编号
（ 2） f(key)=关键字中第一个字母在字母表中的编号。
Key 为地区名的拼音。
（ 3） f(key)=关键字中第一个和最后一个字母在字母表中
的序号之和，此和若比 30大，则减去 30。 Key的含义同
上。
104
(1)若散列函数是一对一的函数，则在查找时，只需根据散列函数对给定
值进行某种运算，即可得到待查结点的存储位置；
(2)设散列表的空间大小为 m,填入表中的结点数是 n,则称 n/m为散列表的
装填因子 。实用中常取 α =0.65为宜。
(3)散列函数的选取原则是：运算尽量简单；函数的值域必须在表长的范
围内；尽可能使关键字不同时，其散列函数值亦不相同。
(4)若某个散列函数 H对于不相等的关键字 Key1和 Key2得到相同的散列地址
(即 H(Key1)=H(Key2),则该现象称为 冲突 (Collision),而发生冲突的这
两个关键字则称为 H的 同义词 (Synonym)。
散列法查找必须研究下面的两个主要问题：
（ 1）选择一个计算简单且冲突尽量少的, 均匀, 的散列函数
（ 2）一个解决冲突的方法，即寻找一种方法存储产生冲突的同义词。
哈希表的讨论
105
9.4.1 散列函数的构造方法
1） 数字选择法,若事先知道关键字集合，且关键字的位数比散列表的地址位
数多，则可选取数字分布比较均匀的若干位作为散列地址。
2） 平方取中法,即先通过求关键字的平方值扩大差别，然后再取中间的几
位或其组合作为散列地址。因为一个乘积的中间几位数和乘数的每一位
都相关，故由此产生的散列地址较为均匀。所取位数由散列表的表长决
定。
3） 折叠法,若关键字位数较多，也可以将关键字分割成位数相同的几段
（最后一段的位数可以不同），段的长度取决于散列表的地址位数，然
后将各段的叠加和（舍去进位）作为散列地址。折叠法又分移位叠加和
间 界叠加两种。移位叠加是将各段的最低位对齐，然后相加； 间 界叠加
则是两个相邻的段沿边界来回折叠，然后对齐相加。
详见书 P254-256
106
4） 除余法：选择一个适当的正整数 P,用 P去除关键字，取所得余数作为散
列地址。
5）基数转换法：把关键字看成是另一个进制上的数后，再把它转换为原来
进制上的数，取其中的若干位作为散列地址。
6）随机数法：选择一个随机函数，取关键字的随机函数值为它的散列地址。
107
8.6.2 冲突的处理方法
在 处理冲突的过程中可能得到一个地址序列 Hi,I=1,2,…,k (Hi?[0,n-1])
若 H1仍然发生冲突，再求下一个地址 H2,…,直到 Hk不发生冲突为止。
1）开放地址法
Hi = ( H (key) + di ) MOD m i = 1,2,…,k (k<=m -1)
di为增量序列，有三种取法：
（ 1）线性探 测再散列。 di=1,2,3,…,m-1
（ 2） 二次探 测再散列。 di=12,-12,22,-22,32,…,?k2,(k<=m/2)
（ 3） 伪随机探测再散列。 di=伪随机数序列
书 P257
108
2） 再哈希法
Hi = RHi(key) i= 1,2,…,k
Rhi均是不同的哈希函数。不易产生聚集，但增加了计算时间
3）链 地址 法
将所有关键字为同 义 词的结点链接在同一个单链表中。
与开放地址相比,链地址法有如下几个优点,链地址法不会产生堆积现象，
因而平均查找长度较短；由于 链地址法中各单链表上的结点空间是动态申
请的，故它更适合造表前无法确定表长的 情 况；在用 链地址法构造的散列
表中，删除结点操作易于实现，只要简单地删去链表上的相应结点即可。
而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置
为空、否则将截断在它之后填入散列表的同义词结点的查找路径。因此在
用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上作删
除标记，而不能真正删除结点。
109
8.6.3 散列表的查找及分析
#define Nil 0 /*空结点标记 */
#define M 18 /*表长 */
typedef struct
{ KeyType Key;
DataType Other;
} HashTable;
HashTable TH[M];
110
int LinSrch(HashTable *HT,KeyType K )
/*在散列表 HT[M]中查找关键字为 K的结点，查找成功时函数 值 为结点在表
中的位置，查找不成功时函数值为失败时的位置 */
{ int D,I=0;
D = H(K); /*D为散列地址,I为冲突时的地址增量 */
/* 线性探查法 */
while ((I < M) && (HT[D].Key != K) && (HT[D].Key != Nil))
{ I++; D = (D+I) % M;}
return D; /*HT[D] == K,则查找成功，否则失败。 I==M时表满 */
}; /*LinSrch*/
111
void LinSert(HashTable *HT,HashTable S)
/*将结点 S插入散列表 HT[M]中 */
{ int D;
D = LinSrch (HT,S.Key); /*查找 S的插入位置 */
if (HT[D].Key == Nil) HT[D] = S ; ； /*D为开放地址，插入 S*/
else printf ("Error")
/* HT[D].Key == S.Key 该结点已存在 */
/* HT[D].Key != S.Key 表已满 */
} /*LinSert*/
112
typedef struct NodeType
{ KeyType Key;
DataType Other;
struct NodeType *Next;
} ChainHash;
ChainHash *HTC[M];
ChainHash *ChnSrch(ChainHash **HTC,KeyType K )
/*散列表 HTC[M]中查找关键字为 K的结点，查找成功时返回指向结点的指
针；否则返回空指针 Nil */
{ ChainHash *P;
P = HTC[H(K)]; /*取 K所在链表的头指针 */
while((P!=Nil) && (P->Key != K)) /*顺序查找 */
P = P->Next;
return P;
}; /*ChnSrch */
113
void CinSert(ChainHash *HTC[],ChainHash *S)
/*将结点 *S插入散列表 HTC[M]中 */
{ int D;
P = ChnSrch(HTC,S->Key);/*查找表中有无待插结点 */
if (P != Nil) printf("表中已有该结点 ");
else /*将 *S插在相应链表的头上 */
{ D =H(S->Key); S->Next = HT[D]; HT[D] = S; }
}; /*CinSert */
114
解决冲突方法 平均查找长度
成功的查找 不成功的查找
线性探 测 法 (1+1/(1-α ))/2 (1+1/(1-α )2)/2
二次探 测,随机探 测
或 再哈希 法 -ln(1-α )/α 1/(1-α )
链地址法 1+α /2 α +exp(-α )
散列表平均查找长度不是结点个数 n的长度，而是装填因子 α 的函数。
查找分析
第 8 章 检索结构
2
§ 8.1 概述
? 检索也称查找
– 检索是指在数据元素（记录）集合中求出满足某给定条件的
记录
– 数据元素（记录）中确定某特定数据字段的值与给定值相匹
配的记录
? 关键字字段（简称关键字）
? 检索成功与不成功
? 在某此问题中，当检索不成功时要插入不存在的数据
记录，或在某种情况下删除所找到的记录
§ 8.1,1 检索的概念
3
? 检索算法（方法）,
– 按检索操作是否全部在内存进行：
? 内检索
? 外检索
– 按是否增删元素
? 静态检索
? 动态检索
§ 8.1,1 检索的概念
4
? 检索算法（方法）,
– 按是否进行比较操作
? 比较式检索
? 非比较式检索
– 按关键字是否变化
? 原词检索
? 变词检索
§ 8.1,1 检索的概念
5
? 为了提高检索效率，要专门为检索操作设置数
据结构
? 若按数据元素集合中元素间结构关系分类
– 线性结构（含线性链结构）
– 线性索引结构
– 树形结构
– 散列（杂凑）结构
§ 8.1,2 检索结构
6
? 按检索结构中数据元素是否会增加或减少分类
– 静态检索结构：操作中不增加或减少元素
– 动态检索结构：操作中可能增加元素或减少元素
§ 8.1,2 检索结构
7
? 检索算法的空间复杂度分析
– 在现有结构上进行检索的算法
– 实现检索算法而构造专门的数据结构的算法
? 检索算法的时间复杂度分析
– 以关键字的比较次数为主度量算法的时间复杂度
§ 8.1,3 检索算法的时间与空间复杂
度分析
8
? 待查关键字的位置对算法本身而言是个随机量，
所以要综合测定算法的检索次数，需使用检索
次数的数学期望
? 将检索算法的检索次数的数学期望称为平均检
索长度 ASL（ Average Search Length）
? 对检索成功（关键字在表中）情况其计算式为：
ASL=
§ 8.1,3 检索算法的时间与空间复杂
度分析
?
?
n
i
iicp
1
9
? 检索不成功的情况（关键字不在数据元素集
中），平均检索长度即为检索失败对应的比较
次数。
? 检索算法的总的平均检索长度应为检索成功与
失败两种情况的平均检索长度的数学期望。
§ 8.1,3 检索算法的时间与空间复杂
度分析
10
? 判定树中每个结点表示被查数据元素集中的一个元素
（常用元素编号表示）
? 从树根到某一结点的路径，就表示检索该结点所经历
的过程，路径上各结点为检索中测试（比较）过的结
点
? 树结点的各个儿子，表示从该结点起下步检索的各选
择分枝
? 对无儿子结点，表示检索过程进行到它（即与它比较）
后，不能继续进行，应终止
§ 8.1.4 检索算法的判定树
11
? 判定树的构造方法
– 若某检索算法 A在数据元素集 D上进行检索，则 A对 D的（检索）
判定树定义为：
– 若 D=空，则 A对 D的判定树为空
– 若第 1次是与元素 i1比较（测试），则令 i1为判定树的根
– 若与 i1比较后，下一步的检索操作是在数据集 D1,...,Dm 之一中
进行（即可能在 D1,...,Dm中任意一个上进行），则令算法 A的
其余部分对 D1,...,Dm的判定树（子树）为根结点 i1的各子树，
这里,D1,...,Dm应为 (D-{i1})的一个划分。 （即 D1∪,..∪ Dm=D-
{i1}，且 Dj∩ Dk=空,j≠ k,j,k∈ {1,...,m}）
§ 8.1.4 检索算法的判定树
12
1 2 3 4 5 6 7 8 9
（ a）顺序查找判定树
5
2 7
1 3 6 8
4 9
（ b）折半查找判定树
5
2 7
1 3 6 8
4 9
（ c）折半查找判定树 (带外结点
)
图 - 判定树
13
? 判定树的深度就表示检索算法的最大比较次数
? 树的分枝数越大（即数据集分块越多），树深
度就越小
? 检索某结的比较次数，就是从树根到该结点的
路径上的结点个数
? 外结点
? 增设了外结点的判定树为完全二叉树
§ 8.1.4 检索算法的判定树
14
? 增设了外结点的判定树为完全二叉树
? 判定树的 内路径 长定义为该树中各内结点的路径长
（从根到某结点的路径长定义为该结点的内径长）之和
? 外路径 长定义为树中各外结点的路径长之和
?设 I与 E分别代表判定树的内与外路径长, 则有
E=I+2n
这里 n为内结点数目
§ 8.1.4 检索算法的判定树
15
§ 8.1.4 检索算法的判定树
? 实际中，各关键被查概率可能不同，为此，引入加权
内外路径长
? 设 wi与 li分别为结点 i的权值与在树中的层次数（即结点
i的路径长），则定义 wi与 li的积为 i的加权路径长
? 加权内路径长 I=
? 加权外路径长 E=
i
n
i
ilw?
?1
i
n
i
ilw?
?
?
12
1
16
§ 8.2 线性结构的检索
? 属于静态检索
? 算法简单，但速度不高
? 主要用在对小型数据集的检索
? 一般的线性表有两种存贮结构：连续式与链式
? 对它们的检索，一般采用顺序搜索的方式 ── 称为顺
序查找
? 若元素已按关键字排序，则可采用更高效的检索法
── 折半查找
17
§ 8.2.1 无序表的检索
(一 )算法
long SeqSearch(int a[],long n,int key)
{ /*连续存储结构的线性表的顺序查找
a[ ]——输入量,一维数组, 充当线性表, n为元素个数 。
序号为 0的位置不使用
key——待查关键字
返回 ——成功时返回 key在表中的序号, 否则返回 0*/
long i;
a[0]=key; //设置监视哨
i=n;;
while(a[i]!=key) i--;
return i;
}
18
§ 8.2.1 无序表的检索
(二 )平均检索长度
? 检索成功时的平均检索长度
ASL=∑ 1/n(n-i+1)=1/n (n-i+1)=(n+1)/2=O(n)
ASL总 =q0(n+1)+q1(n+1)/2
? 若它们是等概率的
ASL总 =1/2(n+1)+1/2·(n+1)/2=3/4(n+1)
19
§ 8.2.1 无序表的检索
(三 )线性链表的顺序检索
? 在链表中检索关键字值为 key的结点的过程为：
p=pHead;
while (p!=NULL && p→key!=key) p=p→next ;
return p; //p为 NULL时失败，否则 p指向所查到的结点
20
§ 8.2.2 有序表的折半检索
(一 )折半检索算法
? 基本思想
– 先找出有序表中点位置上的元素 （ 表空时无中点, 表示检索
不成功 ）, 用待查关键字与它比较
– 若相等, 则已查到, 结束
– 否则, 若它小于待查关键字, 则下步在有序表的前半部 （ 值
小于中点元素的部分 ） 中按类似方法检索, 若它的值大于待
查关键字, 则在表的后半部按类似方法检索
21
§ 8.2.2 有序表的折半检索
(一 )折半检索算法
longBinSearch(int a[],long n,int key)
{/*有序表 （ 升序 ） 的折半查找的非递归算发
a[]——输入量, 一维数组, 充当有序线形表 （ 连续结构 ）, 表中
元素按关键字 key的升序排列, 0号位置空置
key——输入量, 待查关键字
返回 ——返回所找到的关键字的位置号, 找不到时返回 0
*/
long low,high,mid;
low=1;high=pL-last;
22
§ 8.2.2 有序表的折半检索
(一 )折半检索算法
while(low<=high)
{
mid=(low+high)/2; //求中点
if (key==a[mid] ) return mid;
else
if ( key < a[mid]) high=mid-1; //下次在前半部分查找
else low=mid+1; //下次在后半部分查找
}
return 0; /*查找失败 */
}/BinSearch
23
§ 8.2.2 有序表的折半检索
(一 )折半检索算法
long BinSearch2(int a[],long low,long high,int key)
{/*有序线形表 （ 连续存储结构 ） 的折半查找的递归算法
a[]----同前
long,high——输入量，指定查找范围，分别为有序表的查找范围的低端
和高端的序号
返回 ——同前
*/
long mid;
24
§ 8.2.2 有序表的折半检索
(一 )折半检索算法
if(low>high) return 0; //查不到
mid=(low+high)/2;
if(key==a[mid]) return mid;
if(key<a[mid]) return BinSearch2(a,low,mid-1,key); //在前半部分查找
else return BinSearch2(a,mid+1,high,key); //在后半部查找
}//inSearch2
25
§ 8.2.2 有序表的折半检索
(二 )判定树
? 折半检索判定树具有下列性质：
① 任一结点的左右子树中的结点数目最多相差 1
② 任意两棵折半检索判定树, 若它们的结点数目相同, 则它们的
结构完全等同 （ 全等 ）
③ 具有 n个结点的折半检索判定树的深度为 「 log2n」 +1,即深度
与同结点数目的顺序二叉树相同 。
④ 折半检索判定树是平衡二叉树, 即任一结点的左右子树的深度
最多相差 1。
⑤折半检索判定树中任两个叶子所处层次号之差不超过 1
26
5
2 7
1 3 6 8
4 9
（ b）折半查找判定树
27
§ 8.3 线性索引结构
? 索引是为了加快检索速度而引进的一种数据结构
? 索引技术中的关键对象是索引
? 索引项的结构为
? 若索引中的索引项按关键字有序，则称这种索引为线
性索引（也称索引表）
? 多级索引
§ 8.3.1 概述
关键字 关键字所在记录的位置的指示器
28
? 线性索引技术分为稠密索引与非稠密索引（非稠密索
引常为分块索引 ── 索引顺序结构）
? 若索引组织的好，则可显著提高检索速度
? 索引技术除涉及检索操作外，还涉及索引的创建与维
护问题
? 索引项可以组织成多种结构，一般有线性结构与树形
结构
§ 8.3.1 概述
29
? 如果数据元素集中的每个元素对应一个索引项，则这
种索引称为稠密索引
§ 8.3.2 稠密索引
8
20
35
65
70
90
100
100
100
20
8
35
90
100
65
70
线性稠密索引的例子
30
? 假定数据集为连续存贮结构的线性表
? 创建索引相当于一个排序过程
? 以枚举排序为例说明稠密索引的创建
/*定义常量 ListSize,类型 tKey,tElem,tLinearList见程序 8.2-1*/
typedef struct
{tKey key; /*索引项中的关键字字段 */
long ip; /*索引项中记录位置指示器, 这里假定该字
段存放数组下标 */
}/*索引项类型 */
§ 8.3.2 稠密索引
31
tIndexItem *CreateIndex(tlinearList *pL)
{/*借用枚举排序法为线性表 （ 连续存储结构 ） pL建立稠密索引
pL—输入量, 待创建稠密索引的线性表
返回值 —所创建的索引表的首地址
*/
long i,j;
tIndexItem *pII;
pII=(tindexitem )malloc(sizeof(tIndexItem)*pL->last+1);
/*为索引表申请存储区 */
if(pII==null) return NULL; /*不能分配空间, 失败返回 */
for(i=0;i<=pL->last;i++) pII[i].ip=1;
/*索引表中记录指示器初始化，在下面的步骤中,pII充当计数器，
pII[i ]的值为关键字 key大于或等于 pL-room[i].key的记录数目加 1*/
§ 8.3.2 稠密索引
32
for(i= pL->last;i>0;i--)
for(j=i-1;j>0;j--)
if(pL->room[j[.key>pL->room[i].key]
pII[j].ip++;
else pII[i].ip++;
return pII;
}/*CreateIndex*/
33
§ 8.3.3 分块索引（索引顺序检索）
(1)分块索引结构
? 分块有序是指：对任意两块 B1和 B2，若 B1在逻辑上位
于 B2之前，则 B1中任一元素的关键字也在逻辑上位于
B2中任一元素之前
? 分块有序并不要求块内一定有序
? 每块对应一个索引项，每个索引项的结构为：
最大或最小关键字值 块首地址或尾地址
34
§ 8.3.3 分块索引（索引顺序检索）
8 101 210
0 4 9
10 8 35 70 101 180 120 140 130 280 290 210 220
0 1 2 3 4 5 6 7 8 9 10 11 12
35
§ 8.3.3 分块索引（索引顺序检索）
(1)分块索引结构
? 若数据集为一维数组 data，则为它生成一个名为 index 的索引表
的过程为（假定块长为 BlockSize,索引中存块内最小关键字与
块首元素下标,数据集长为 N）：
numBlock=N/BlockSize+N%BlockSize;
/*求出块数目 numBlock*/
posBlock=0;
for(i=1;i<=numBlock;i++)
{index[i].ip=posBlock;
index[i].key=data[posBlock];
posBlock=posBlock+BlockSize;
}
36
§ 8.3.3 分块索引（索引顺序检索）
(1)索引顺序检索
? 分两个步骤：
– ①在索引表中确定关键字所在块；
– ②在块中检索关键字。
? 分块检索的平均检索长度 ASL应为
ASL=ASLi+ASLb
= 1/bj+ 1/sj
=(b+1)/2+(s+1)/2
=1/2(n/s+s)+1
37
§ 8.4 树形检索结构（树目录）
? 树中的每一结点是一个索引项
? 树结构的检索一般也快于线性结构
? 树目录也常常用于驻留在外存上的数据集
? 树目录多用作动态结构
§ 8.4.1 概述
38
? 二叉排序树是一种基本的树目录，由它可导出最优
（次优）二叉排序树与平衡二叉树。然后导出各种 B树。
? B树可用来实现高效的外部文件索引，广泛地应用于数
据库实现中
? 对树目录，由于检索就在树目录上进行，所以树目录
的检索判定树就是树目录本身
§ 8.4.1 概述
39
(一 )基本概念
?二叉排序树 （ 也称二叉检索树 ） 是这样一种结点含关键
字的二叉树, 它或为空二叉树, 或满足下列性质：
(i)若它的左子树不空, 则其左子树上所有结点的关键字
均分别小于它的根结点关键字；
(ii)若它的右子树不空, 则右子树上所有结点的关键字均
分别大于它的根结点的关键字 。
(iii)它的左右子树亦分别为二叉排序树 。
§ 8.4.2 二叉排序树
40
§ 8.4.2 二叉排序树
50
30 80
10 70 90
20 55
ifelse
for
charr while
case
图 - 二叉排序树
(a) (b)
41
(一 )基本概念
?前面讨论的折半检索与 Fibonacii检索判定树均为二叉排序树
?对二叉排序树进行中序遍历就会得到一个结点 （ 关键字 ） 的升序序
列
?若给二叉排序树添加外结点, 则外结点就可有具体的含意：某外结
点代表这么一个值的集合, 该集合中的值的大小由开区间 (a,b)确定,
这里 a与 b 分别为该外结点在该二叉排序树 （ 带外结点 ） 的中序遍历
序列中的前趋结点与后继结点的关键字值
§ 8.4.2 二叉排序树
42
(一 )基本概念
?C++ 描述
template <class TElem>
struct TBinTreeNode
{
TElem info;
……
TElem *lc,*rc;
}
§ 8.4.2 二叉排序树
43
(二 )二叉排序树的检索
?二叉树检索的递归程序为：
TBinTreeNode *SearchBinSortTree(TBinTree *root,TElem key)
{//root为被检索的树的根指针
if (root==NULL) return NULL;
if (root->info == key) return root;
if (key <root->info) return SearchBinSortTree(roo->lc,key);
return SearchBinSortTree(roo->rc,key);
}
§ 8.4.2 二叉排序树
44
(二 )二叉排序树的检索
?二叉树检索的非递归程序为：
TBinTreeNode *SearchBinSortTree2(TBinTree*root,TElem key)
{//root为被检索的树的根指针
TBinTreeNode *p;
p = root;
while (p!=NULL)
{
if (key ==p->info) return p;
if (key <p->info) p = p->lc;
else p = p->rc;
}
return p;
}
§ 8.4.2 二叉排序树
45
(二 )二叉排序树的检索
?有时候, 需要找到某关键字对应的结点的父亲, 实现程序如下：
TBinTreeNode *SearchFatheBinSortTree(TBinTree *root,TElem key,
char &isLeft)
{//root为被检索的树的根指针,检索 key,若找到, 则返回其父结点的
指针,
//并且, 当 key在左儿子中时, 置 isLeft为 1,否则置 isLeft为 0。
//找不到 key时返回 NULL
TBinTreeNode *p,*p0;
isLeft=0;
p0=NULL;
p = root;
§ 8.4.2 二叉排序树
46
(二 )二叉排序树的检索
while (p!=NULL)
{
if (key ==p->info) return p0;
p0 = p;
if (key <p->info) {p = p->lc; isLeft=1;}
else {p = p->rc; isLeft=0; }
}
return p0;
}
§ 8.4.2 二叉排序树
47
(三 )二叉排序树的插入
TBinTreeNode *InsertBinTree(TBinTreeNode * &root,
TBinTreeNode *pNode,char &isLeft)
{ //将 pNode所指结点插入到以 root为根的二叉排序树中, 返回插入后
pNode的父亲,
//isLeft指示 pNode是否是左儿子 。
//如果 root为空, 则 pNode被作为树根, root直接指向 pNode
TBinTreeNode *p;
§ 8.4.2 二叉排序树
48
(三 )二叉排序树的插入
if (root==NULL) {root=pNode; return NULL;}
p = SearchFatherBinSortTree(root,pNode->info,isLeft);
if （ isLeft） p->lc=pNode;
else p->rc=pNode;
return p;
}
§ 8.4.2 二叉排序树
49
70
10
70
30
20 80
10
70
30
20 80
50
9010
70
30
20 80
50
9010
70
30
20 80
50
55
70
20
70
30
20
10
70
30
20
(a)初态 (b)插入 70 (c)插入 20 (d)插入 30 (e)插入 10
（ 空 ）
(f)插入 80 (g)插入 50 (h)插入 90 (i)插入 55
图 - 建立二叉排序过程示例
50
(三 )二叉排序树的插入
利用该程序, 也可根据原始数据生成二叉排序树：
TBinTreeNode *CreateBinTree(int a[],long n)
{//根据一维数组 a[]中的原始数据, 创建二叉排序树, 返回其树根 。
long k;
TBinTreeNode *root,*p;
char isLeft;
root=NULL:
for (k=0; k<n; k++)
{
p = new TBinTreeNode;
p->info=a[k];
InsertBinSortTree(root,p,isLeft)
}
}
§ 8.4.2 二叉排序树
51
(三 )二叉排序树的插入
?显然, 读入关键字的次序不同, 所建二叉树的形式也不
同
§ 8.4.2 二叉排序树
5
4
3
2
1
5
4
3
2
1
图 - 插入次序不同，树结构也不同
52
(四 )二叉排序树的删除
?(1) 若 p无左子树, 则用 p的右子树 （ 若有的话 ） 的根代替 p
if(p==f→lc)
f→lc=p→rc ; //p是 f的左儿子
else f→rc=p→rc ;
return p;
§ 8.4.2 二叉排序树
53
(四 )二叉排序树的删除
?(2) 若 p有左子树, 但 p无右子树, 则用 p的左子树代替 p
（ 见图 8-0b） 。 实现方法为：
if (f→lc==p)
f→lc=p→lc ;
else f→rc=p→lc ;
return p;
§ 8.4.2 二叉排序树
54
p
PR
f
p
PR
f
(a)p无左子树
p
PL
f
p
PL
f
(b)p有左子树, 但无右
子树
55
(四 )二叉排序树的删除
?(3) 若 p有左子树, 也有右子树, 则用 p的中序前驱 （ 中序
序列中 p的直接前趋 ） q代替 p,并将 q的左子树转让给 q的父
亲 （ 注,q必无右子树 ）
q=p→lc ;
r=p; //使 r一直为 q的父亲
while (q->rc!=NULL)
{
r = q ;
q=q→rc ;
}
§ 8.4.2 二叉排序树
56
(四 )二叉排序树的删除
//用 q的左子树置换 q
// r等于 p时, q就是 p的左儿子, 也是将 q 的左子树挂接在 p的左链
r→rc=q→lc ;
//下面用 q置换 p
q→lc=p→lc ;
q→rc=p→rc ;
if (f→lc=p) f→lc=q ;
elsef→rc=q ;
retrun p;
§ 8.4.2 二叉排序树
57
f
Q
PR
S
SL R
RL
QL
左图
(d)删除 p的另一方法 (用 p左儿
置换 p,p 的右子树挂接到 p 的
直接前趋的右链 )
P
PR
f
p
S
SL R
RL
r
Q
QL
q
Q
PR
f
q
S
SL R
RL
r
QL
(c)p有左, 右子树
图 - 二叉排序树中删除 p
58
typedef int tKey; /*关键字类型 */
typedef struct tSBTreeNode
{tKey key; /*关键字字段 */
······ /*这里可定义其他字段 */
struct TSBTreeNode *lc,*rc; /*左右儿子域 */
}tSBTreeNode;
tSBTreeNode *SBtreeSearch(tSBTreeNode *root,tKey key,tSBTreeNode
**f)
{/*二叉排序树查找子程序 （ 递归 ）
root——输入量, 为待查二叉排序树的根指针
key——输入量, 待查关键字
*f——指向被查接点的父亲, 用树根调用此函数时, 变量 f为空
指针的地址
返回值 ——树中第一个关键字等于 key的结点的指针, 若树中五
此结点, 则返回 nuul
*/
59
if(root==NULL||root->key==key)
return root;
*f=root;
if(key<root.key)
return SBTreeSearch(root->lc,key,f);
else return SBTReeSearch(root->rc,key,f);
}/*SBTreeSearch*/
60
tSBTreeNode *SBTreeSearchPos(tSBTreeNode *root,tKey
key,char *isl)
{/*在二叉排序树中查找插入位置 （ 递归 ）
root——待查二叉排序树的根指针
key—— 输入量, 待查关键字
*isl——输入量, 说明见下
返回值 ——返回以 *root为根的二叉排序树中的 key应
出现的位置的父指针 。 若位置为他父亲懂得左儿子,
则置 *isl为 1,否则置为 0
注：若树中已有与 key相同的关键字结点, 则认为 key 小
于它们
*/
61
if(root==NULL) return NULL; /*为提高速度，此行可取消，但调用该
函数时不能用空树调用（ *root不为 NULL） */
if(roor-rc==NULL)
{*isl=1;
return root;
}
else return SBTreeSearchPos(root->lc,key,isl);
}
else
{if(roo->rc==NULL)
{*isl=0;
return root;
}
else return SBTreeSearchPos(root->rc,key,isl);
}
}/*SBTreeSearchPos*/
62
tSBTreeNode * SBTreeIns(tSBTreeNode **root,tKey,key)
{/* 在二叉排序树中插入一个关键字结点
*root——输入量, 指向二叉排序树的根
key——输入量, 为待插入的关键字值
返回 ——返回插入的结点的指针
*/
tSBTreeNode *p,*q;
char isl;
q=(tSBTreeNode )malloc (sizeof(tSBTreeNode)); /*申请一
个结点 */
q->key=key;q->lc=NULL,q->rc=NULL;
63
if(*root==NULL)
*root=NULL; /*对空树, 将新结点作为树根 */
else
{ p=SBTreeSearchPos(*root,key,&isl); /* 找插入位置 */
if(isl)
p->lc=q;
else p-<rc=q;
}
return q;
}/*SBTreeSearchPos*/
64
tSBTreeNode
SBTreeDelNode(tSBTreeNode*p,tSBTreeNode **f)
{/*删除二叉排序树中由 p所指向结点, 并令 *f指向删除 p
后由 p子树中剩余部分构成的新子树的根 。 （ 注：本算
法删除 p后, 仍使 p子树剩余部分保持在同一子树中 ）,
返回被删除结点
*/
tSBTreeNode *q,*r,*p0;
p0=p; /* d当 *f==p时, 下面的操作将改变 p,故应保存 */
65
if(p->lc==NULL)
*f=p->rc;
else
if(p->rc==NULL)
*f=p->lc;
else /*p 的左右子树均不为空 */
{q=p->lc;
r=p; /*使 r一直为 q之父结点指针 */
while(q->rc!=NULL) /*找 p的直接前驱 q*/
{r=q;q=q->rc;}
if(r!=p)
r->rc=q-lc; /*用 q的左子树代替 q的位置 */
else /* r等于 q时, q就是 p 的左儿子, 故应将 q 的左子树挂接到 p
的左链 */
r->lc=q->lc;
66
/*下面用 q置换 p*/
q->lc=p->lc;
q->rc=p->rc;
*f=q;
}/*if(p->rc==NULL)… else… */
return p0;
}/*SBTreeDelNode*/
67
tSBTreNode * SBTreeDelKey(tSBTreeNode **root,tKey,key)
{/*从二叉排序树中摘除指定关键字所在的第一个结点
*root——指向二叉排序树的根
key——待删除关键字值
返回 ——被删除结点的指针
*/
tSBTreeNode *p,*f;
68
if(key==*root->key)
return SBTreeDelNode(*root,root);/*删根 */
else
{p=SBTreeSearch(*root,key,&f); /*找 key所在结点 p及其父亲 f*/
if(p==NULL) return NULL ; /*找不到 key*/
if(p==f->lc)
return SBTreeDelNode(p,&(f->lc)); /*删 p,用 f的左链代管 p子树的剩
余部分 */
else return SBTreeDelNode(p,&(f->rc));
}
}/*SBTreeDelKey*/
69
(五 )二叉排序树的分析与最优二叉排序树
?只需分析二叉排序树的检索算法
?检索算法的效率与树的结构相关, 而树结构又与关键字进
入树中的次序有关
§ 8.4.2 二叉排序树
80
60 85
20 90
(b) 关键字输入次序为 (80,60,20,85,90)
所对应的二叉排序树
20
60
80
85
90
(关键字输入次序为 (20,60,80,85,90)
所对应的二叉排序树
70
(五 )二叉排序树的分析与最优二叉排序树
?给定 n个关键字与它们的 n个检索概率值, 能否存在一棵平
均检索长度 （ 即加权内外路径长度, 见 § 8.1.4） 最小的二
叉排序树呢？ 回答是肯定的 。 这种树称为最优二叉排序树 。
?对于经常进行插入与删除的二叉排序, 较好的选择是平衡
二叉排序树, 它是二叉排序树与最优二叉排序树之间的一
种折衷 。
§ 8.4.2 二叉排序树
71
(一 )概念
?高度平衡二叉树 （ height Balanced binary tree）,或是一棵空树, 或是
具有下列性质的二叉树：它的左右子树均为平衡二叉树, 且它们二者
的深度之差不超过 1。 在不至于产生混淆的情况下, 我们常称其高度平
衡二叉树为平衡二叉树或平衡树 。
?平衡因子：二叉树中的结点的平衡因子定义为该结点的左子树的深度
与右子树深度之差 。
?平衡二叉排序树：若二叉排序树为平衡二叉树, 则称为平衡二叉排序
树 。 在本节中, 常以平衡二叉树称平衡二叉排序树 。
§ 8.4.3 平衡二叉排序树的性质
72
(二 )若干性质
① 平衡树中任一结点的平衡因子均为 -1,0,1三者之一, 这是
显然的 。 因为任一结点的左右子树深度之差不超过 1。
② 任一棵二叉排序树, 都可以转化为一棵平衡二叉排序树 。
③ （ A e c oHBe ck,H c 1962） 一棵具有 n 个 （ 内部 ） 结
点的平衡二叉树, 其高度 h满足
log2(n+1)≤ h≤ 1.4404log2(n+2)-0.328
§ 8.4.3 平衡二叉排序树的性质
73
(一 )插入平衡调整
设 p 是一棵平衡二叉树 （ p为根 ）, 则将某一结点插入它中后, 有下列
情况
( i)p的平衡因子为 -1（ p左重 ）, 结点插入到 p的左子树, 并使 p左子树
升高, 则 p变为左超重 （ p平衡因子变为 -2）, 此时需进行平衡调整 。
(ii)p的平衡因子为 1（ p右重 ）, 结点插入到 p的右子树, 并使 p 右子树
升高, 则 p变为右超重, 需进行平衡调整 。
(iii)其它情况均不需进行平衡调整 。 即 p平衡因子 0,或 p左重, 但结点
插入到 p的右子树, 或 p右重, 但结点插入到 p左子树 。
§ 8.4.4 平衡二叉树局部平衡调整算法
74
(一 )插入平衡调整
§ 8.4.4 平衡二叉树局部平衡调整算法
A
B A
B
图 - 二叉排序树变换
左 右：以 B为轴顺时针旋转 （ 父变左子之右子 ）
右 左：以 A为轴递时针旋转 （ 父变右子之左子 ）
75
(a)
-1/-2
P
0/-1
P1
h h-1
P1l
×
P1r h-1
插入结点
P1r h-1或 h-2
0
P
0/1
P
h
P1l
×
Pr h-1P1r h-1或 h-2
LL
76
插入结点
P2r h-2或 h-3
-1/-2
P
0/1或 1/2P1
h-1h-2
P2l
×
Pr h-1
0/-1或 -1/-2P2P1l
h-1或 h-2
P2r
P
P1
P2l
×
PrP2
P1l
P2r
1或 2P
P2l
×
PrP1l
0或 1P1
0P2
LR
(b)
77
1/2
P
0/1或 1/2P1
hh-1
P1r
×
h-1 Pl
P1lh-1或 h-2
RR
0
P1
0/-1
P P1r
×
P1lPl
(c)
78
RL
插入结点
1/2
P
Plh-1 0/1或 -1/-2P1
0/-1或 -1/-2P1 P1r h-1或 h-2
P2r h-2或 h-3
h-1 h-2
P2l
×
P1r
P
P1P1l
×
Pl P2
P2r
P2r
1或 0或 2P1
P2l
×
P1rPl
0P
P2
(d)
图 - 在平衡二叉排序树中，插入接点后的平衡调整（结点内标住的 x/y表示
插 入前与插入后的平衡因子分别为 x/y。图中，圆圈表示结点，方框表示子
树
79
（ 空树 ） 插入结点 10 10 插入 6 10
6
插入 3
对子树 10LL
10
6
3
插入结点 2,5
10
6
3
52
插入 4
10
63
5
2 4
对子树 6LR
10
6
3
52
4
插入 16
16
10
63
5
2 4
对 6RR
16
10
6
3
5
2 4
插入结点 18,20
80
16
10
6
3
5
2 4
18
20
对 16RR 插入 17
18
16
10
6
3
5
2 4
20
18
16
10
6
3
5
2 4
20
17
对 10RL
18
16
10
6
3
5
2 4
2017
图 - 平衡二叉树的插入与平衡 （ 箭头所指结点为最小不平衡
子树的根 ）
81
(二 )删除平衡调整
设 p是一棵平衡二叉排序树 （ 子树 ）, 则当 p的某子树高度
被降低 1后, 仅在下列情况下, p才需进行平衡调整：
(i)p右轻 （ 即左重 ）, 且 p右子树高度被降低
(ii)p左轻 （ 即右重 ）, 且 p左子树高度被降低
§ 8.4.4 平衡二叉树局部平衡调整算法
82
(a)LL型
LL
-1/-2
P
0/-1
P1
h-1
h-2Pr
×
P1lh-1 P1r h-1或 h-2
1或 0P1
-1或 0
P
P1l
P1r Pr
×
83
删除 28
30
20
10
6 16 26 40
4 8 18 22 28
217
45
30
20
10
6 16 26 40
4 8 18 22
217
45
8
26
30
18
10
22 40
21 45
对 26进行 LL 删除 4,6,16,20
26
30
20
10
6 16 22 40
4 8 18 21
7
45
84
删除 45
8
26
30
18
10
22 40
21
删除 8
26
30
18
10
22 40
21
2110
30
22
18
26 40
对 18进行 RL
图 - 平衡二叉排序树的删除平衡调整
85
1970年 R.Bayer和 E.Mccrerght提出了一种适合用于外查找的树，它是
一种平衡的多叉树，其特点是插入、删除时易于平衡，外查找效
率高，适合于组织磁盘文件的动态索引结构，这就是我们将要讨
论的 B-树。
1)B-树的定义
一 棵 m阶的 B-树满,或为空树，或为满 足下列条件 的 m叉树,
(1)每个结点至多有 m棵子树 ；
(2)若 根结点 不 是 叶结点,则 至少有 2棵子树；
(3)除根之外的所有非终端结点 至少有 ?m/2?棵子树 ；
8.5 B-树
86
(4)所有的非终端结点所包含的信息：
（ n,A0,K1,A1,K2,A2,…,KN,AN)
其中 Ki(i=1,..,n)为关键字，且 Ki<=Ki+1;
Ai(i=0,..,n)为指向子树根结点的指针，且指针 Ai-1的指子树中所有结点的
关键字昀小于 Ki(I=1,..,n),An的指子树中所有结点的关键字均大于 Kn，
n(?m/2?-1<=n<=m-1)为关键字的个数（或 n+1为子树个数）。
(5)的有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结
点或查找失败的结点，实际上这些结点不存在，掼向这些结点的指针为
空）。
B-树
书 P239图
87
1 35
1 18
1 11 1 391 27
3 47 53 64
1 99
2 43 78
t
F F F F F F
F F F F
F F
4阶的 B树，深度为 4
88
#define m 3 //B树的阶
typedef struct BTNode {
int keynum; //结点中关键字个数，即结点的大小
struct BTNode *parent; //指向双亲结点
KeyType key[m+1]; // 关键字向量,0号单元未用
struct BTNode *ptr[m+1]; //子树指针向量
Record *recptr[m+1]; //记录指针向量,0号单元未用
} BTNode,*Btree; //B树结点和 B树的类型
typedef struct {
BTNode *pt; //指向找到的结点
int i; //1..m,在结点中的关键字序号
int tag; //1：查找成功,0：查找失败
} Result; //B树的查找结果类型
B树查找算法
89
Result SearchBTree ( Btree T,KeyType K)
//在 m阶 B树上查找关键字 K，返回结果 (pt,i,tag)。若查找成功，则特
//征值 tag = 1,指针 pt所指结点中第 I个关键字等于 K；否则特征值 tag= 0，
//等于 K的关键字应插入在指针 pt所指结点中第 i和第 i+1个关键字之间
p = T; q = NULL; found = FALSE; i = 0;
//初始化,p指向待查结点,q指向 p的双亲
while ( p && !found ) {
n = p->keynum; i = Search ( p,K);
//在 p->key[1..keynum]中查找,i使得,p->key[i]<=K<p->key[i+1]
if ( i>0 && p->key[i] == K) found = TRUE; //找到待查关键字
else ( q = p; p = p->ptr[i]; }
}
if ( found ) return ( p,i,1); //查找成功
else return ( q,i,0); //查找不成功，返回 K的插入位置信息
}// SearchBTree
90
B-树的 插入和删除
? B- 树的插入
首先在最低层的某个非终端结点中添加一个关键字，若该结点的
关键字个数不超过 m-1，则插入完成，否则要产生结点的“分
裂”。
? B- 树的删除
首先应找到该关键字所在结点，并从中删除之，若该结点为最下
层的非终端结点，且其中的关键字数目不少于 ?m/2?,则删除完成，
否则要进行, 合并, 结点的操作。
91
45
53 9024
3 12 37 50 61 70 100
bt
b
c d f g h
a
e
(a) 一棵 2-3树
45
53 9024
3 12 30 37 50 61 70 100
bt
b
c d f g h
a
e
(b) 插入 30之后
92
45
53 9024
3 12 26 30 37 50 61 70 100
bt
b
c d f g h
a
e
(c)
45
53 9024 30
3 12 37 50 61 70 100
bt
b
c d' f g h
a
e
(d) 插入 26之后
26d
93
(e)
45 70
5324 30
3 12 37 50 61 100
bt
b
c d' f g h
a
e
插入 85之后
26
45
53 9024 30
3 12 37 50 61 70 85 100
bt
b
c d' f g h
a
e
26
45
53 70 9024 30
3 12 37 50 61 100
bt
b
c d' f g h
a
e
26
(g)
85
g'
90
85
g'
d
d
d
(f)
94
(h)
45 70
7 24 30
3 37
bt
b
c d'
a
26
24 45 70
7
37
bt
b
d'
a
26
d
d
(i)
12c'
53
50 61 100
f g h
90
85
g'
30b' 53
50 61 100
f g h
90
85
g'
e e'
e'e
3
c
12c'
95
70
7
37
bt
b
d'
a
26d
30b' 53
50 61 100
f g h
90
85
g'
e e'
c
12c'
插入 7之后
24
a'
45
m
3
96
Status InsertBTree ( Btree *T,KeyType K,Btree q,int i) {
//在 m阶 B树 T上结点 *q的 key[i]与 key[i+1]之间插入关键字 K。
//若引起结点过大，则沿双亲链进行必要的结点分裂调整，使 T仍是 m阶 B树。
x = K; ap = NULL; finished = FALSE;
while ( q && !finished ) {
Insert ( q,i,x,ap); //将 x和 ap分别插入到 q->key[i+1]和 q->ptr[i+1]
if ( q->keynum < m) finished = TRUE; //插入完成
else { //分裂结点 *q
s = ?m/2?; split ( q,ap); x = q->key[s];
//将 q->key[s+1..m],q->ptr[s..m]和 q->recptr[s+1..m]移入新结点 *ap
q = q->parent;
if ( q) i = Search (q,x); //在双亲结点 *q中查找 x的插入位置
} //else
} //while
if ( !finished ) //T是空树 (参数 q的初值为 NULL)或者根结点已分裂为结点 *q和 *ap
NewRoot (T,q,x,ap); //生成含信息（ T,x,ap)的新根结点 *T，原 T和 ap为子树指针
}
97
B树的删除过程
45
53 9024
3 37 50 61 70 100
bt
b
c d f g h
a
e
45
61 9024
3 37 53 70 100
bt
b
c d f g h
a
e
98
B树的删除
45
9024
3 37 61 70 100
bt
b
c d g h
a
e
45 90
1003 24
bt
c
a
h61 70g
99
? B+树是应文件系统所需的一种 B- 树的变型树。 m阶的 B+树和 m阶的 B-树的
差别在于：
（ 1）有 n棵子树的结点中含有 n个关键字；
（ 2）所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录
的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
（ 3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）
中的最大（或最小）关键字。
B+ 树
100
B+ 树
59 97
15 44 59
21 37 44
72 97
63 72 85 91 9751 5910 15
root
sqt
101
? 通常在 B+树上有两个头指针，一个指向根结点，另一个指向关键字最小的
叶子结点。
? B+树的查找运算有两种：
– 从最小关键字起顺序查找
– 从根结点开始，进行随机查找。
? 在 B+树上进行随机查找、插入和删除的过程基本上与 B-树类似。
? 在查找时，若非终端结点上的关键字等于给定值，并不终止，而是继续向
下直到叶子结点。
B+ 树
102
8.6 哈希 表
9.4.1 哈希 表（ Hash Table,散列表 )
散列 (Hashing)基本思想：以结点的关键字 K为自变量，通过
一个确定的函数关系 f, 计算出对应的函数值 f(K),把这个值解
释为结点的存储地址，将结点存入 f(K)所指的存储位置上。查找
时再根据要查找的关键字用同样的函数计算地址，然后到相应的
单元里去取要找的结点。因此散列法又称关键字 -地址转换法。用
散列法存储的线性表叫散列表 (Hash Table),上述的函数 f称为散
列函数,f(K)称为散列地址。
103
编号 地区名 总人口 汉族 回族,..
C[ 1..30 ]
散列函数：
（ 1） f(key) = key,key 是编号
（ 2） f(key)=关键字中第一个字母在字母表中的编号。
Key 为地区名的拼音。
（ 3） f(key)=关键字中第一个和最后一个字母在字母表中
的序号之和，此和若比 30大，则减去 30。 Key的含义同
上。
104
(1)若散列函数是一对一的函数，则在查找时，只需根据散列函数对给定
值进行某种运算，即可得到待查结点的存储位置；
(2)设散列表的空间大小为 m,填入表中的结点数是 n,则称 n/m为散列表的
装填因子 。实用中常取 α =0.65为宜。
(3)散列函数的选取原则是：运算尽量简单；函数的值域必须在表长的范
围内；尽可能使关键字不同时，其散列函数值亦不相同。
(4)若某个散列函数 H对于不相等的关键字 Key1和 Key2得到相同的散列地址
(即 H(Key1)=H(Key2),则该现象称为 冲突 (Collision),而发生冲突的这
两个关键字则称为 H的 同义词 (Synonym)。
散列法查找必须研究下面的两个主要问题：
（ 1）选择一个计算简单且冲突尽量少的, 均匀, 的散列函数
（ 2）一个解决冲突的方法，即寻找一种方法存储产生冲突的同义词。
哈希表的讨论
105
9.4.1 散列函数的构造方法
1） 数字选择法,若事先知道关键字集合，且关键字的位数比散列表的地址位
数多，则可选取数字分布比较均匀的若干位作为散列地址。
2） 平方取中法,即先通过求关键字的平方值扩大差别，然后再取中间的几
位或其组合作为散列地址。因为一个乘积的中间几位数和乘数的每一位
都相关，故由此产生的散列地址较为均匀。所取位数由散列表的表长决
定。
3） 折叠法,若关键字位数较多，也可以将关键字分割成位数相同的几段
（最后一段的位数可以不同），段的长度取决于散列表的地址位数，然
后将各段的叠加和（舍去进位）作为散列地址。折叠法又分移位叠加和
间 界叠加两种。移位叠加是将各段的最低位对齐，然后相加； 间 界叠加
则是两个相邻的段沿边界来回折叠，然后对齐相加。
详见书 P254-256
106
4） 除余法：选择一个适当的正整数 P,用 P去除关键字，取所得余数作为散
列地址。
5）基数转换法：把关键字看成是另一个进制上的数后，再把它转换为原来
进制上的数，取其中的若干位作为散列地址。
6）随机数法：选择一个随机函数，取关键字的随机函数值为它的散列地址。
107
8.6.2 冲突的处理方法
在 处理冲突的过程中可能得到一个地址序列 Hi,I=1,2,…,k (Hi?[0,n-1])
若 H1仍然发生冲突，再求下一个地址 H2,…,直到 Hk不发生冲突为止。
1）开放地址法
Hi = ( H (key) + di ) MOD m i = 1,2,…,k (k<=m -1)
di为增量序列，有三种取法：
（ 1）线性探 测再散列。 di=1,2,3,…,m-1
（ 2） 二次探 测再散列。 di=12,-12,22,-22,32,…,?k2,(k<=m/2)
（ 3） 伪随机探测再散列。 di=伪随机数序列
书 P257
108
2） 再哈希法
Hi = RHi(key) i= 1,2,…,k
Rhi均是不同的哈希函数。不易产生聚集，但增加了计算时间
3）链 地址 法
将所有关键字为同 义 词的结点链接在同一个单链表中。
与开放地址相比,链地址法有如下几个优点,链地址法不会产生堆积现象，
因而平均查找长度较短；由于 链地址法中各单链表上的结点空间是动态申
请的，故它更适合造表前无法确定表长的 情 况；在用 链地址法构造的散列
表中，删除结点操作易于实现，只要简单地删去链表上的相应结点即可。
而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置
为空、否则将截断在它之后填入散列表的同义词结点的查找路径。因此在
用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上作删
除标记，而不能真正删除结点。
109
8.6.3 散列表的查找及分析
#define Nil 0 /*空结点标记 */
#define M 18 /*表长 */
typedef struct
{ KeyType Key;
DataType Other;
} HashTable;
HashTable TH[M];
110
int LinSrch(HashTable *HT,KeyType K )
/*在散列表 HT[M]中查找关键字为 K的结点，查找成功时函数 值 为结点在表
中的位置，查找不成功时函数值为失败时的位置 */
{ int D,I=0;
D = H(K); /*D为散列地址,I为冲突时的地址增量 */
/* 线性探查法 */
while ((I < M) && (HT[D].Key != K) && (HT[D].Key != Nil))
{ I++; D = (D+I) % M;}
return D; /*HT[D] == K,则查找成功，否则失败。 I==M时表满 */
}; /*LinSrch*/
111
void LinSert(HashTable *HT,HashTable S)
/*将结点 S插入散列表 HT[M]中 */
{ int D;
D = LinSrch (HT,S.Key); /*查找 S的插入位置 */
if (HT[D].Key == Nil) HT[D] = S ; ； /*D为开放地址，插入 S*/
else printf ("Error")
/* HT[D].Key == S.Key 该结点已存在 */
/* HT[D].Key != S.Key 表已满 */
} /*LinSert*/
112
typedef struct NodeType
{ KeyType Key;
DataType Other;
struct NodeType *Next;
} ChainHash;
ChainHash *HTC[M];
ChainHash *ChnSrch(ChainHash **HTC,KeyType K )
/*散列表 HTC[M]中查找关键字为 K的结点，查找成功时返回指向结点的指
针；否则返回空指针 Nil */
{ ChainHash *P;
P = HTC[H(K)]; /*取 K所在链表的头指针 */
while((P!=Nil) && (P->Key != K)) /*顺序查找 */
P = P->Next;
return P;
}; /*ChnSrch */
113
void CinSert(ChainHash *HTC[],ChainHash *S)
/*将结点 *S插入散列表 HTC[M]中 */
{ int D;
P = ChnSrch(HTC,S->Key);/*查找表中有无待插结点 */
if (P != Nil) printf("表中已有该结点 ");
else /*将 *S插在相应链表的头上 */
{ D =H(S->Key); S->Next = HT[D]; HT[D] = S; }
}; /*CinSert */
114
解决冲突方法 平均查找长度
成功的查找 不成功的查找
线性探 测 法 (1+1/(1-α ))/2 (1+1/(1-α )2)/2
二次探 测,随机探 测
或 再哈希 法 -ln(1-α )/α 1/(1-α )
链地址法 1+α /2 α +exp(-α )
散列表平均查找长度不是结点个数 n的长度，而是装填因子 α 的函数。
查找分析
