,数据结构,
第九章 查找第九章 查找第 2页第九章 查 找内容和要求查找的概念，顺序查找、二分法查找、分块查找的概念和方法，二叉排序树、平衡二叉树的查找，哈希表查找。要求获得有关静态和动态环境下几种基本的查找方法和技术知识。掌握顺序、二分法和分块查找的方法；了解哈希表是一种基本的存储结构、哈希表的背景和基本思路。掌握哈希表处理冲突的方法。
重点二分法查找方法；哈希表的动态查找。
第九章 查找第 3页
查找表 由同一类型的数据元素（或记录）构成 的集合基本概念
静态查找表 仅作查询与检索（统称为查找）工作的查找表。
动态查找表 除作查询与检索之外，还需作诸如插入、删除之类更新操作的查找表。
查找 在一个含有众多数据元素（或记录）的查找表中找出某个
“特定的”数据元素（或记录）的过程。
关键字 能够标识一个数据元素（或记录）的某个数据项的值。
当数据元素只有一个数据项时，其关键字即为该数据元素的值。
主关键字 能唯一地标识一个记录的关键字。
给定一个值 k，在含有 n个记录 (或数据元素 )的表中找出关键字等于给定值 k的记录，若找到，则 查找成功,查找结果为给出整个记录的信息，或指示该记录在查找表中的位置；若找不到，则 查找不成功,查找结果为 NULL值或值 0。
第九章 查找第 4页查找操作主要是关键字的比较,故通常把查找过程中对关键字需要执行的 平均比较次数 （亦称 平均查找长度 ）作为衡量一个 查找算法效率优劣的标准 。
基本概念
平均查找长度 为了确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值 (平均值 )称为查找算法在查找 成功时 的平均查找长度 (Average Search Length)。
对于含有 n个记录的表，查找成功时的平均查找长度为
(9-1)
其中
Pi：表中第 i个记录被查找的概率，有 ；
Ci：找到表中其关键字与给定值相等的第 i个记录时，所需要的比较次数。
若无特别声明，均认为表中每个记录的概率均相等，即第九章 查找第 5页约定和宏定义宏定义
#define EQ( a,b ) ((a) == (b))
#define LT( a,b ) ((a) < (b))
#define LQ( a,b ) ((a) <= (b))
注,宏定义随不同的数据类型，有所不同 。
第九章 查找第 6页
1、静 态 查 找 表静态查找表的 ADT
静态查找表是一种最简单的查找表。
Specification ADT Static_Search_Table
Elements,查找表中的数据元素类型相同，每一数据元素都 存在一个能唯一标识该元素的关键字
Structure,查找表中的 n个数据元素具有相同类型，属于同一集合 。数据元素之间不存在结构关系
Operation：
Create(ST,n) 生成操作,产生一个含用户给定的 n个数据元素的表 ST。
Search(ST,K) 查找函数,若表 ST中存在其关键字等于给定值 K的数据元素，则函数值为该元素在表中的位置；否则函数值为“空”。
Traverse(ST) 输出操作,按某种次序输出表 ST中所有数据元素。
第九章 查找第 7页顺序 (线性 )表的查找 —— 顺序查找顺序（线性）表的查找是一种最简单的查找方法。它的算法基本思想是,
从表的一端开始,顺序地扫描线性表,依次将扫描到的关键字和给定值相比较，若当前扫描到的记录的关键字与给定值相等，则查找成功，找到所查记录；若直至扫描结束，仍未找到其关键字与给定值相等的记录，
则查找不成功。
既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。若使用单链表作存储结构时，扫描必须从第一个结点开始。若以向量作存储结构，则可从前往后或从后往前进行扫描。
第九章 查找第 8页顺序表的查找算法描述
typedef struct {
ElemType elem[];
int Length;
}SSTable;
顺序（线性）表的查找
int seqsearch( SSTable st,keytype k )
{/*K为给定值，返回 i为关键字等于 K的记录在表 st中的序号,i值为零表明查找不成功 */
st.elem[0].key = K; //设置监视哨
for( i = st.length; !EQ( st.elem[i].key,key ); i--)
//从表尾开始向前扫描
return i; //返回找到的位置
} //算法 9.1
第九章 查找第 9页算法性能分析
nnSS PPPnnPA S L 121 2)1(?
若查找每个记录时是等概率，则有 ASLss=(n+1)/2
顺序（线性）表的查找
(9-2)
第九章 查找第 10页如果考虑到不成功的查找，则 查找算法的平均查找长度 应是查找成功时的平均长度与查找不成功时的平均查找长度之和 。若假设查找成功与不成功的可能性相同，对每个记录的查找概率也相等，即 。由于查找不成功的比较次数总是 n+1，故顺序查找的平均查找长度为顺序（线性）表的查找第九章 查找第 11页
(2) 当表中各个记录的查找概率互不相等时，为了提高查找效率，宜将诸记录先按查找概率由小到大进行排列（式 (9-2)在
P1≤P2≤···≤Pn-1≤Pn时达到极小值）；
说明：
(1) 顺序查找算法简单，且对表的结构无任何要求（无论按向量还是链表结构，无论记录间是否按关键字有序排列），故此算法适应面广。但当 n>>1时,查找效率随 n越大而越低 。
顺序（线性）表的查找
(3) 在很多实际应用的情况下，各记录的查找概率无法事先确定，则可以采用“自组织”形式的顺序查找表。
第九章 查找第 12页有序表的查找 —— 折半查找折半查找又称二分查找（ Binary Search），它是一种效率高的查找方法。
折半查找的 前提是静态查找表是有序表,即表中记录按关键字有序排列，且需使用 向量作为表的存储结构 。不妨设有序表是递增有序的。
折半查找的算法思想：
先确定待查记录所在的范围（区间），然后以处于区间中间位置记录的关键字和给定值 K相比较,（ 1） 若相等，则查找成功； （ 2） 若不等，则缩小范围，继续按此法查找，
直至新的区间位置记录的关键字等于给定值 K，或者查找区间的大小等于零（表明查找不成功）时为止。
猜数游戏的方法第九章 查找第 13页有序表的折半算法描述
int Search_Bin( SSTable st,KeyType key )
{ //在有序表 st中折半查找关健字等于给定值 key的记录
int mid;
low = 1; hig = st.Length; //置区间初值
while( low ≤ hig ) //判别查找区间大小
{ mid = ( low + hig ) / 2;
switch{
case K ＞ st.elem[mid].key,low = mid+1;
case K == st.elem[mid].key,return mid;
case K ＜ st.elem[mid].key,hig = mid-1;
}
}
return( 0 ); //查找不成功
} // 算法 9.2
有序表的查找 —— 折半查找第九章 查找第 14页算法性能分析
6
3 9
7 I041
52 8 11
56
80
64 88
92753713
05
19
21
这棵二叉树并非完全二叉树，但其叶结点所在层次之差至多为 1。因此，该二叉树深度与一根完全二叉树相同，
为 。 这里 n是二叉树结点的个数,亦即有序表中数据元素的个数。
折半查找过程中可用二叉树来描述（ 判定树 ）。树根为表的中间记录。根的左子树关键字均小于根的关键字，根的右子树关键字均大于根的关键字。
56 8064 88 9275371305 19 21
示例 1,以下 11个数据元素为例，可画出二叉树有序表的查找 —— 折半查找第九章 查找第 15页结论,折半查找法在查找 成功时 进行比较的关键字个数最多不超过树的深度，即问题：查找不成功的情况如何？
示例 2 对于如示例 1所给数据，描述折半查找过程加上 外部结点 的判定树和查找关健字为 85的结点，示意如下
6
3 9
7 I0
56
80
64 8805
19
211 4
I19-1086-713 53-4 372-1
10-11 11-1-2 2-3 4-5 5-6 7-8 8-9
75 92
图 9.3 加上外部结点的判定树和查找 85的过程结论,折半查找在查找不成功时和给定值进行比较的关健字个数最多不超过有序表的查找 —— 折半查找第九章 查找第 16页折半查找的平均查找长度的计算：
记 h=log2(n+1),即有 n=2h-1，则描述折半查找的判定树是深度为 h的 满二叉树 。设表中每个记录的查找概率均相等（ Pi=1/n），
则查找成功时折半查找的平均查找长度其中 j为层数,2j-1为该层结点数。
记,则故有因为当 n>>1时，有有序表的查找 —— 折半查找第九章 查找第 17页说明：
折半查找的效率比顺序查找高。
有序表的查找 —— 折半查找而排序本身是一种很费时的操作，即使采用高效率的排序方法也要花费 O(nlog2n) 的时间代价 。
另外，折半查找仅适用于顺序存储结构，为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。故折半查找特别适用于那些一经建立就很少改动，而又经常需要查找的线性表,而对那此查找少而又经常需要改动的线性表，可采用链表作存储结构，进行 顺序查找 ；
第九章 查找第 18页索引顺序表的查找 —— 分块查找以索引顺序表表示静态查找表时，可采用分块查找（
Blocking Search） 方法来进行查找。
分块查找又称索引顺序查找，它是一种性能介于顺序查找和折半查找之间的方法。
分块查找法要求按如下的索引方式来存储一个线性表,
将表 R[1..n] 均分为 b块,前 b-1块中结点个数为,第
b块的结点数小于或等于 S。 每一块中的关键字不一定有序,但前一块中的最大关键字必须小于后一块中的最小关键字，即要求表是,分块有序” 的 。抽取各块中的最大关键字及起始位置，构成一个索引表 ID[1..b]。 由于表 R是分块有序的，所以索引表应是一个递增有序表。
第九章 查找第 19页示例 3 分块有序表的索引存储表示分块查找的算法思想：
(1) 查找索引表，确定待查关键字所在的块（子表）。 由于索引表是按记录关健字有序，故宜采用 折半查找法 ；
(2) 在所确定的块中查找是否存在关键字与给定值相同的记录 。此时需采用 顺序查找法 。
故分块查找的算法实际上是折半查找算法和顺序查找算法的简单合成。
22 48 86
1 7 13
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53
索引表最大关键字起始地址子表 1 子表 2 子表 3
索引顺序表的查找 —— 分块查找图 9.6 表及其索引表第九章 查找第 20页分块查找的算法分析分块查找实际上是两次查找过程，故整个算法的平均查找长度是两次查找的平均查找长度之和，即
ASLbs=Lb+Lw，
其中
Lb：查找索引表所在子表的平均查找长度
Lw：在子表中顺序查找记录的平均查找长度设将表均匀分布成 b个子表，每个子表包含 s个记录 （最后一个子表可能不足 s个记录）,并设表中每个记录的查找概率均相等，即每个子表的查找概率为 1/b，子表中每个记录的查找概率为 1/s。
(1) 若用顺序查找确定所在块，则索引顺序表的查找 —— 分块查找与表长 n有关，
与块中记录个数 s有关第九章 查找第 21页
(2) 若用折半查找法确定所在块，则示例 4 若表中有 n=10000个记录，取 即将该表分成 100块，每块中含 100个记录。则用顺序查找确定块的分块查找平均需要做 101次比较，而若用折半查找确定所在块，
则最多需做约 57次比较。
若使用顺序查找，平均需做约 5000次比较，而使用折半查找，则最多需做约 14次比较。
故分块查找算法的效率介于顺序查找和折半查找算法之间。
索引顺序表的查找 —— 分块查找第九章 查找第 22页说明：
(1) 分块查找的优点是，在表中插入或删除一个记录时，
只要找到该记录应当所属的块，然后在块内进行插入和删除运算。因为块内记录的存放是任意的，所以插入或删除比较容易
，不需要移动大量记录。分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的操作；
索引顺序表的查找 —— 分块查找
(2) 在实用中，分块查找不一定要将线性表分成大小相等的若干块，而应该根据表的特征进行分块。例如，一个学校的学生登记表，可按系号或班号分块。此外，各块中的记录也不一定要存放在同一个向量中，可将各块放在不同的向量中，也可将每一块存放在同一个单链表中。
第九章 查找第 23页动 态 查 找 表当用线性表作为表的组织形式时，可采用顺序查找、折半查找、分块查找等查找方法，其中以折半查找效率最高。
但折半查找要求表中结点按关健字有序，且不能使用链表作存储结构。因此，当表的插入或删除操作频繁时，为了维护表的有序性，势必要移动表中很多结点，引起额外的时间开销，从而抵消了折半查找的优点。
希望采用既具有如折半查找那样的查找效率、又易于进行诸如插入、删除结点操作的表的组织方式。这就是动态查找表。
动态查找表的 ADT
第九章 查找第 24页动态查找表既具有顺序表那样较高的检索效率，又具有链表那样插入、删除的灵活性。它可有不同的表示方法，但较典型的是 采用特殊的树或二叉树作为动态查找表的一种组织方式，可 统称为树表 。
动态查找表的特点,表结构本身是在查找过程中动态生成的，即对于给定值 K，若表中存在其关健字等于 K的结点（记录），则查找成功返回，否则插入关健字等于 K的结点（记录）。 在动态查找表中亦允许删除表中结点。
动 态 查 找 表动态查找表的 ADT
第九章 查找第 25页
Specification ADT Dynamic_Search_Table
Elements,表中各结点都含有一个类型相同的关健字，并且该关健字可唯一地识别结点
Structure,n个结点具有查同属性，同属一个集合动态查找表的 ADT
Operation：
Initialize(DT) 初始化操作,设置一个空的动态查找表 DT。
Search(DT,K) 查找函数,若表 DT中存在其关键字等于给定值 K的结点，则函数值为该结点或它在表中的位置；否则函数值为“空”。
Insert(DT,K) 插入操作,若表 DT中存在其关键字等于给定值 K的结点，则空操作；否则插入其关键字等于 K的结点。
Delete(DT,K) 删除操作,若表中存在其关键字等于给定值 K
的结点，则删除之；否则空操作。
Traverse(DT) 输出操作 按某种次序输出表 DT中所有结点。
第九章 查找第 26页二叉排序树及其查找过程二叉排序树（ Binary Sort Tree） 又称为二叉查找树或二叉搜索树（ Binary Search Tree）。它是一种特殊结构的二叉树。
动 态 查 找 表?
定义,二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：
(1) 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值；
(2) 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值；
(3) 它的左、右子树也分别为二叉排序树 。
显见。关于二叉树排序树的这一定义是递归的。
第九章 查找第 27页示例 1 如下是两棵二叉排序树
45
12
3
24
53
61
10037
90
78
(a) 图 9.7 二叉排序树示例 (b)
二叉排序树的一个重要性质：
性质 对二叉排序树按中序遍历该树所得到的中序序列是一个递增有序序列 。
故一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
CAO
ZHAO
DING
CHEN WANG
MA
DU
XIA
LI
二叉排序树及其查找过程第九章 查找第 28页二叉排序树的查找算法描述
BiTree bstsrch( BiTree t,KeyType K )
{ //在指针 t所指的二叉排序树上查找其关健字等于给定值 K的记录，当查找成功时，返回指向该记录结点的指针，否则返回空指针
if(( t == NULL )||(t->data.key == K ))
return t;
else
if( t->data.key < K )
return bstsrch( t->rchild,k );
else
return bstsrch( t->lchild,k );
} //算 法 9.4(a)
第九章 查找第 29页二叉排序树的插入和生成二叉排序树是一种 动态树表 。其特点是，树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。
动 态 查 找 表?
在二叉排序树中插入新结点，需保证插入后仍符合二叉排序树的定义。
在二叉排序树中插入新结点，需保证插入后仍符合二叉排序树的定义。
插入的前提,查找不成功插入的位置,若二叉排序树为空，则插入结点成为新的根结点；否则，沿左子树或右子树继续查找，直至某结点的左子树或右子树为空为止，插入结点作为一个新的叶结点并成为该结点的左孩子或右孩子结点。
第九章 查找第 30页二叉排序树查找算法的修正算法
Status SearchBST( BiTree t,KeyType K,BiTree f,BiTree &p )
/*在查找指针为 t的二叉树上查找关键字等于 K的结点，若存在，则 p返回指向该结点的指针；否则返回指向查找路径上最后一个结点的指针，以指示插入位置,f的初始调用值为 NULL，指向 t的双亲 */
{ if( t == NULL ) //查找不成功
{ p = f; return false }
else if( t->data.key == K ) //查找成功
{ p = t; return true; }
else if( K< t->data.key ) //继续在左子树上进行查找
SearchBST(t->lchild,key,t,p )
else //继续在右子树上进行查找
SearchBST(t->rchild,key,t,p )
} //算 法 9.4(b)
参数 f的作用？
第九章 查找第 31页二叉排序树的插入算法
Status ins_bstree( BiTree &t,Elemtype e )
/*在根指针为 t 的二叉排序树上插入关键字为 e.key 的结点，若树空，
则插入结点为新的根结点，否则根据 K 小于（或大于）结点 f 中关键字而插入为 f 的左子树（或右子树）的根 */
{
if( !SearchBST( t,e.key,NULL,p )) {
s = new( BiTreeNode );
s->data = e; s->lchild = s->rchild = NULL;
if( p == NULL ) t = s;
else if( e.key < p->data.key ) p->lchild = s;
else p->rchild = s;
return true;
}
else
return false;
} //算 法 9.5
第九章 查找第 32页从二叉排序树的生成过程可以看到，它经历了若干次插入新结点的操作。 每次插入的新结点都是二叉排序树上新的叶子结点,则在进行插入操作时，不必移动其它结点，仅需改动某个结点的指针
，由空变为非空即可。它表明，二叉排序树既有类似于折半查找的特性，又采用了链表作存储结构，因此是动态查找表的一种适宜表示。
示例 2 设从空树出发，对于输入关键字序列
{45,24,53,12,37,93}，经过一序列的查找、插入操作，可陆续生成一棵二叉排序树,45
24 53
12 37 93
图 9.8 二叉排序树的构造过程二叉排序树的插入初始问题：如何实现在一个二叉排序树上删除某个结点？
第九章 查找第 33页二叉排序树的删除从二叉排序树上删除一个结点，不能把以该结点为根的子树都删去,而只能删掉该结点自身,并且还要保证删除后所得的二叉树仍然满足二叉排序树的性质。
也就是说，在二叉排序树中删去一个结点，相当于删去有序序列中的一个结点。
删除操作必须进行查找，以确定被删结点是否在二叉排序树中。若不在，则不做任何事情；若在，则设法删除之。
动 态 查 找 表?
第九章 查找第 34页
(3) p结点既有左子树又有右子树，即 p结点的左、右子树均不空。
此时不能作简单处理，而需对 p结点的左、右子树进行细化,目的是将 p的左、右子树链接到合适的位置，并保持二叉排序树的特性
。
假设在二叉排序树上被删结点为 p，其双亲结点为 f，且不失一般性，可设 p 是 f 的左指针
(2) p结点只有左子树 pL或右子树 pR，则令 pL或 pR直接成为 f结点的左子树即可 ;
F
P
f
p
二叉排序树的删除分三种情况进行讨论删除操作
(1) p结点为叶结点，即 pL和 pR均为空树。
则可令 f->lchild = NULL;
F
P
f
p
F
P
f
p
第九章 查找第 35页设删除结点 p之前二叉排序树的形状如下（细化 PL）
按中序遍历所得序列为
{···CLC···QLQSLSPPRF ···}
若欲删去结点 p，且保持二叉排序树的特性，则所指指针改变而获得的新二叉树排序树，经按中序遍历所得序列应为
{···CLC···QLQSLSPRF ···}
P
C
p
c
Ff
Q
S
q
s
可采用两种做法实现之做法一 令 p的左子树为 f的左子树，而 p的右子树为 s的右子树做法二 令 p的直接前驱（或者接后继）替代 p，然后再从二叉排序树中删去它的直接前驱（或直接后继）
二叉排序树的删除第九章 查找第 36页做法一 令 p 的左子树为 f 的左子树，而 p 的右子树为 s 的右子树
f->lchild = p->lchild;
s->rchild = p->rchild;
P
C
p
c
Ff
Q
S
q
s
Cc
Ff
Q
S
q
s
二叉排序树的删除第九章 查找第 37页做法二 令 p 的直接前驱（或者接后继）替代 p，然后再从二叉排序树中删去它的直接前驱（或直接后继）
q = p; s = p->lchild;
while( s->rchild ≠ NULL )
{ q = s; s = s->rchild };
p->data = s->data; //替代
if( q ≠ p ) q->rchild = s->lchild;
else q->lchild = s->lchild; //删 s
free(s);
q≠p情形
q=p情形
P
C
p
c
Ff
Q
S
q
s
S
Pp
Ff
Ss
q
Pp
Ff
S
q
S
首先查找 s与 q
s即为 p 的左孩子结点二叉排序树的删除第九章 查找第 38页二叉排序树的查找分析示例 3 设输入关键字序列分别为 {45,24,53,12,37,93}以及
{12,24,37,45,53,93}，则将生成两棵不同形态的二叉排序树图 9.10不同形态的二叉查找树
(a) 关键字序列为 {45,24,53,12,37,93}的二叉排序树
(b) 关键字序列为 {12,24,37,45,53,93}的单支树当先后插入的关键字有序时，所构成的二叉排序树蜕变为单支树。
12
24
37
45
53
93
45
53
93
24
3712
(a) (b)
含有 n个结点的二叉排序树的平均查找长度和树的形态有关。
第九章 查找第 39页二叉排序树的平均查找长度
(1) 最佳情况二叉排序树的形态和折半查找的判定树相同
ASL=log2(n+1)-1
(2) 最差情况二叉排序树蜕变为单支树
ASL=（ n+1） /2
(3) 随机情况
ASL≤1+4log2n
二叉排序树的查找分析?
就平均性能而言，二叉排序树上的查找和折半查找相差不大，并且二叉排序树的插入和删除结点十分方便，无需移动大量结点。因此，对于需要经常做插入、删除和查找操作的表，
拟采用二叉排序树结构。
第九章 查找第 40页平衡二叉树二叉排序树的查找效率取决于树的形态，而构造一棵形态匀称的二叉排序树与插入的先后次序往往不是随人的意志而定的，这就要求找到一种动态平衡的方法，对于任意给定的关健字序列都能构造一棵形态 匀称 的二叉排序树。也就是说，需在构成二叉排序树的过程中进行,平衡化,处理，成为平衡的二叉排序树。
把形态匀称的二叉树称为平衡二叉树（ Balanced Binary Tree）
定义 平衡二叉树 或者是一棵空树，或者是任何结点的左子树和右子树 深度最多相差 1的二叉树。
定义 二叉树上任一结点的左子树深度减去右子树深度之差称为该结点的 平衡因子 （ Balance Factor）
问题：如何构造出一棵平衡的二叉排序树？
Adelson_Velskii和 Landis提出了一个方法。
所以平衡的二叉排序树也简称为 AVL树 。
第九章 查找第 41页示例 4 平衡二叉树、不平衡二叉树以及树中诸结点的平衡因子示例如下
1
1
(a)
-1
-1
1
1
0
(b) 0
0
0
0
图 9.11 平衡与不平衡的二叉树及结点的平衡因子
(a)(b) 平衡二叉树； (c)(d) 不平衡的二叉树
2
-1
1
(c)
-1
-2
100
(d)
0
0
0
0
0
平衡二叉树?
第九章 查找第 42页如何使构成的二叉树成为平衡树平衡调整规律,假设由于在二叉排序树上插入结点而失去平衡的最小子树的根结点指针为 a（ 即 a是离插入结点最近，且平衡因子绝对值超过 1的祖先结点 ），则失去平衡后进行调整规律可归纳为下列四种情况：
45
50
60
30
48
0
0
00
1
200
LL
插入前 插入 20 调整后
(1) LL型平衡旋转原因：在 A的左子树的左子树上插入结点使 A的平衡因子由 1增至 2
调整：进行一次顺时针旋转操作示例：
50
60
48
45
1
0
0
0
30 0
50
60
48
45
2
0
0
1
30 1
20 0
第九章 查找第 43页
(2) RR型平衡旋转原因：在 A的右子树的右子树上插入结点，使 A的平衡因子由
-1减至 -2
调整：进行一次逆时针旋转操作
RR型：
b = a->rchild;
a->rchild = b->lchild; a->bf = 0;
b->lchild = a; b->bf = 0; //b为子树新根如何使构成的二叉树成为平衡树
13
24
(c)
-1
0 13
24
37
(d)
-2
-1
0
a→
b→
24
3713
(e)
0
0
0a→
b→
示例：
第九章 查找第 44页
(3) LR型平衡旋转原因：在 A的左子树的右子树上插入结点，使 A的平衡因子由
1增至 2
调整：进行先逆时针、后顺时针共两次旋转操作
21
24
18
13
2
0
-1
-1
11 0
19
a→
b→
c→ 0
如何使构成的二叉树成为平衡树
21
2418
13
2
0
1
1
11 0
19
a→
b→
c→ 0 21
24
18
13
0
0
0
1
11 0 19
a
b→
c→
0
示例,21
24
18
13
1
0
0
0
11 0
a→
b→
c→插入前插入 19 先逆时针旋转再顺时针旋转第九章 查找第 45页
LR 型,b = a->lchild; c = b->rchild;
a->lchild = c->rchild; b->rchild = c->lchild;
c->rchild = a; c->lchild = b; //c为子树新根
switch{ //插入之前 c->bf 为零，插入之后有三种情况
case c->bf == 1,{ a->bf = -1; b->bf = 0};
case c->bf == -1,{ a->bf = 0; b->bf = 1 };
case c->bf == 0,{ a->bf = 0; b->bf = 0 };
};
c->bf = 0; b = c; //旋转变换以后，用 c指向新树根如何使构成的二叉树成为平衡树
21
24
18
13
2
0
-1
-1
11 0
19
a→
b→
c→ 0
21
24
18
13
0
0
0
1
11 0 19
a
b→
c→
0
第九章 查找第 46页
(4) RL 型平衡旋转原因：在 A的右子树的左子树上插入结点，使 A的平衡因子由 -1减至 -2
调整：进行先顺时针、后逆时针共两次旋转操作如何使构成的二叉树成为平衡树
24
70
37
13
-1
0
0
0
示例：
53
0
a→
b→
c→
24
70
90
13
-2
1
0
0
70
0
a→
b→
c→
24
37
90
13
-2
-2
0
0
900
c→
a→
b37
70
53
24
0
0
0
1
90
0
37-1
53 0 13
0
第九章 查找第 47页
RL 型,b = a->rchild; c = b->lchild;
a->rchild = c->lchild; b->lchild = c->rchild;
c->rchild = b; c->lchild = a;
switch{
case c->bf == 1:{ a->bf = 0; b->bf = -1};
case c->bf == -1:{ a->bf = 1; b->bf = 0 };
case c->bf == 0:{ a->bf = 0; b->bf = 0 };
};
c->bf = 0; b = c;
如何使构成的二叉树成为平衡树
53
0
a→
b→
c→
24
70
90
13
-2
1
0
0
900
c→
a→
b37
70
53
24
0
0
0
1
37-1 130
第九章 查找第 48页在平衡树上插入一个结点的算法描述平衡旋转是当二叉排序树在插入结点后产生不平衡时进行的。为了使得到的二叉排序树为平衡树，需对插入算法
ins_bstree(t,k,s)作如下修改为此，需要做到
(1) 在查找 s 结点的插入位置的过程中，记下离 s 结点最近且平衡因子不等于零的结点，令指针 a 指向该结点；
(1) 判别插入结点之后是否产生不平衡；
(2) 找到失去平衡的最小子树；
(3) 判别旋转类型并作相应调整处理。
(2) 修改自 a 至 s 路径上所有结点的平衡因子值；
(3) 判别树是否失去平衡，即在插入结点之后,a 结点的平衡因子绝对值是否大于 1。若是，则需判别旋转类型并作相应处理，否则插入过程结束。
第九章 查找第 49页平衡树查找的分析
(1) 在平衡树的查找过程中，与给定值进行比较的关键字个数不超过树的深度，这与排序树相同
(2) 含有 n 个结点的 AVL树其最大深度与 log2n 同数量级（
最大深度 ）；
(3) 由于在 AVL 树上查找时，和关键字比较的次数不超过树的深度，且不再出现蜕变为单支树的情形，因此 AVL 树上查找的时间复杂度是 O(log2n)
(4) 因为动态平衡过程仍需花费不少时间，故在实际应用中
，是否采用 AVL 树要根据具体情况而定。一般情况下，
项结点关键字是随机分布的，并且系统对平均查找长度没有苛求，则使用二叉排序树即可。
第九章 查找第 50页
B- 树和 B+ 树以前所讨论的算法都是内查找算法，被查找的数据都保存在内存中。它们适用于组织较小的、内存中记录的文件。对于较大的、存放在外存储器上的文件，它们就不合适了。
1972年,R.Bayer 和 E.McCreight 提出了一种适用于外查找的树，它是一种 平衡的多叉树,其特点是插入、删除时易于平衡，外查找效率高，适用于组织磁盘文件的动态索引结构。这就是 B- 树。
例如,当用平衡二叉树作为磁盘文件的索引组织时，若以结点作为内、外存交换的单位，则查找到需要的关键字之前，平均要对磁盘进行 log2n 次访问，这是很费时间的。
B- 树定义第九章 查找第 51页
B-树 致力于解决实现基于磁盘的检索树时遇到的所有问题：
B- 树和 B+ 树?
B- 树定义
(1) B- 树总是高度平衡的，所有叶结点都在同一层；
(2) 更新和检索操作只影响一些磁盘页，因此性能很好；
(3) B- 树把相关的记录放在同一个磁盘页中，从而利用了访问局部性原理；
(4) B- 树保证树中至少有一定比例的结点是满的。这样能够改进空间的利用率，同时在检索和更新期间减少需要的磁盘读取数目。
第九章 查找第 52页定义 (B- 树 ),一棵 m 阶的 B- 树，或为空树，或为满足下列特性的 m 叉树：
B- 树定义
(1) 树中每个结点至多有 m 棵子树；
(3) 根结点至少有两棵子树（唯一例外的是只包含一个根结点的
B- 树）；
(4) 所有的叶结点均在同一层，且叶结点不包含任何关键字信息；
(5) 有 j 棵子树的非叶结点恰好包含 j-1 个关键字。
B- 树的一个包含 j 个关键字,j+1 个指针的结点的一般形式为,
j A0 K1 A1 K2 ··· Aj-1 Kj Aj
Ki(i=1,2,···,j) 为关键字，且 Ki<Ki+1(i=1,2,···,j-1);
其中,Ai(i=0,1,··,j) 为指向子树根结点的指针；
且指针 Ai-1 所指子树中所有结点的关键字均小于 Ki(i=1,2,···,j)，
Aj 所指子树中所有结点的关键字均大于 Kj； j 为关键字个数（或
j+1 为子树个数）。
(2) 除根结点和叶结点外，其它每个结点至少有 棵子树；
第九章 查找第 53页
1 35
1 18
b c
d e f g h
t
图 9.14 一棵 4阶的 B- 树在 B- 树中每个结点的关键字从小到大排列。因为叶结点不包含关键字，故可把叶结点看成在树中 实际上并不存在的外部结点 。 叶结点的总数正好等于树中所包含的关键字总个数加 1。
B- 树定义
1 11 1 27
a
2 43 78
1 39 3 47 53 64 1 99
F F F F F F F F F F F F
示例 1
第九章 查找第 54页示例 2 下图为一棵 6阶的 B- 树（简化形式）
注,m=6。每个非叶结点的子树个数在 6/2(=3)和 6之间，
从而它们所包含的关键字个数可以不等，取 2,3,4或 5。
B- 树定义第九章 查找第 55页
B- 树的查找在 B- 树上进行查找的过程和二叉树的查找类似。
在 B- 树上查找给定的关键字的方法是：
首先取根结点，在根结点所包含的关键字 K1,K2,···,Kj 中查找给定值，若找到等于给定值的关键字，则查找成功 ;
否则，可以确定要查的关键字是在某个 Ki 和 Ki+1 之间（因为在结点内部的关键字是排序的），故可取 Ai 所指向的结点继续查找如此重复下去，直至找到，或指针 Ai 为 NULL 时，查找失败。
可见，在 B- 树上进行查找的过程是一个顺指针查找结点和在结点的关键字中进行查找交叉进行的过程。
第九章 查找第 56页
2 47 53 64
2 43 78
A0 A1 A2
1 35A0 A1
示例 3,承示例 1，在一棵 4阶 B- 树上查找图 9.14 一棵 4阶的 B- 树
1 18
b c
d e f g h
t
1 11 1 27
a
1 39 1 99
F F F F F F F F F F
B- 树的查找
(1) 查找关键字 47 (2) 查找关键字 23查找成功
F F
查找失败在 B- 树中查找与所给关键字相等的结点的算法思想：
(1) 在 B- 树中根据关键字找结点； (2) 在结点中找关键字。
第九章 查找第 57页
B- 树结点类型说明
#define m 3
typedef struct BTNode{
int keynum;
struct BTNode *parent; //父结点指针
KeyType key[m+1]; //关键字,m 个 (0未用 )
struct BTNode *ptr[m+1]; //指向子树的指针,m+1个
Record *recptr[m+1]; //指向记录的指针 (0未用 )
} BTNode,*BTree;
typedef struct{
BTNode *pt;
int i; //关键字序号
int tag; //0-查找不成功,1-查找成功
} Result;
B- 树的查找第九章 查找第 58页
Result SearchBTree( Btree T,KeyType K)
/*在根结点指针为 T 的 m阶 B- 树上查找关键字 K，返回记录
(pt,i,tag)。若查找成功，则特征位 tag=1，等于 K 的关键字即为指针 pt 所指结点的第 i个关键字；若查找不成功，则特征位 tag=0，等于 K 的关键字应插入到指针 pt 所指结点第 i 个和第 i+1 个关键字之间 */
{ p = T; q = NULL; found = false; i = 0;
//初始化,p 指向待查结点,q 指向 p 的双亲结点
while( p≠NULL && !found )
{ n = p->keynum; i = Search( p,K );
//在 p->key[1..n] 中进行查找，
//直至 p->key[i]≤K<p->key[i+1]止,0 ≤ i ≤ n
if( i > 0 && p->key[i] == K )
found = true;
else { q = p; p = p->ptr[i] }
}; //while
if( found )
return(p,i,1) //查找成功
else return(q,i,0) //查找不成功，返回插入位置信息
} //算法 9.7
第九章 查找第 59页性能分析：通常 B- 树 存储在外存上。在 B- 树中查找结点涉及内、外存交换，而结点中查找关键字是在内存进行的，后者可采用折半查找，效率很高。 因此,B- 树的查找效率主要取决于如何在树中找结点，即需与磁盘交换，而这一操作又与 B- 树的层次数（深度）有关，所以，算法的效率取决于树的高度，（最大层次数）。
B- 树的查找分析第九章 查找第 60页假设 B- 树有 N 个关键字，因此共有 N+1 个树叶，且设树叶均在 l+1 层。
根据 B- 树定义，
第一层有一个结点（根），
第二层至少有 2个结点，
第三层至少有 个结点,·····，
第 l+1 层至少有 个结点。
由于叶结点 数为 N+1，因此，有即
B- 树的查找分析
2*（ ）
2*（ ） l-1
l 这意味着若 N=1,999,998,m=199，则 l
至多等于 4。显然其查找效率非常之高。
第九章 查找第 61页
B- 树的插入
B- 树的生成也是从 空 树起，逐个插入关键字而得。 但 B-
树的插入与一般树的插入有所不同。一般树的插入是将树 往下延伸,而 B- 树的插入却是 往上“蔓延” 的。
对于叶结点处于第 L+1 层的 B- 树，插入的关键字总是进入第 L 层的结点。
在 m阶 B- 树中插入一个关键字：
由于 m阶 B- 树结点中的关键字个数必须,
因此，每次插入一个关键字不是在树中添加一个叶结点，而是首先在最低层的某个 非终端结点 中添加一个关键字，若该结点的关键字个数不超过 m-1，则插入完成；
否则（ 关键字个数等于 m）要对结点进行,分裂”。
第九章 查找第 62页
B- 树的插入怎样对结点进行,分裂”？
令 f=
m-f >=
m A0 K1 A1 K2 ··· Af-1 Kf Af Kf+1Af+1Kf+2 ··· Am-1 Km Am
结点如下所示：P
f A0 K1 A1 K2 ··· Af-1 Kf Af
p
m-f-1 Af+1Kf+2 ··· Am-1 Km Am
P`
把关键字 Kf+1和指针 p`一起插入到 P的双亲结点中，当然这有可能会导致双亲结点的“分裂”，甚至产生连锁反应。
第九章 查找第 63页示例 4,下列图示给出了一棵 3阶 B- 树依次插入关键字 30,26,85
和 7时，整个 B- 树和结点的变化过程
(a) 一棵 2-3 树 45
24 53 90
3 12 61 7037 50 100
b
c d f g h
e
bt
B- 树的插入
a
(1) 插入关键字 30：首先查找插入位置 (37之前 )； 进行插入，并检查
45
24 53 90
3 12 61 7037 50 100
b
d f g h
e
bta
c
30
第九章 查找第 64页
45
24 53 90
3 12 61 7030 37 50 100
b
c d f g h
e
bt
插入 26之后，结点 d需分裂,30向上插入到双亲结点中。
B- 树的插入
a
(2) 继续插入关键字 26：首先查找插入位置 (30之前 )；
进行插入，并检查插入后结点关键字数目大于 2。
c
bt
45
24 53 90
3 12 61 7050 100
b
d f g h
e
a
30 3726 26 30 37
d`
30
第九章 查找第 65页插入 85之后，结点 g需分裂,70向上插入到双亲结点 e中。
B- 树的插入
(3) 继续插入关键字 85：首先查找插入位置 (70之后 )；
进行插入，并检查插入后结点关键字数目大于 2。
c
bt
45
24 30 53 90
3 12 61 7050 100
b
d f g h
e
a
26 37
d`
c
bt
45
24 30 53 90
3 12 61 7050 100
b
d f g h
e
a
26 37
d`
61 70 85
第九章 查找第 66页插入 85之后，结点 g需分裂,70向上插入到双亲结点 e中。
B- 树的插入
c
bt
45
24 30 53 90
3 12 50 100
b
d f g h
e
a
26 37
d`
61 70 85
结点 g需分裂。 bt
45
24 30 53 90
3 12 50 100
b
d f g
h
e
a
26 37
d`
61
c
70 85
70
g`
e分裂,70上插
70
e`
第九章 查找第 67页
B- 树的插入
bt
45 70
24 30
3 12 50 100
b
d f g h
e
a
26 37
d`
61
c
85
g`
c分裂,7上插
e`
(4) 继续插入关键字 7：首先查找插入位置 (3之后 )；
进行插入，并检查插入后结点关键字数目大于 2。
53 90
bt
45 70
24 30
3 7 12 50 100
b
d f g h
e
a
26 37
d`
61
c
85
g`
e`
53 90
第九章 查找第 68页
B- 树的插入
bt
45 70
7 24 30
3 50 100
b
d f g h
e
a
26 37
d`
61
c
85
g`
e`
c分裂,7上插
53 90
12
c`
bt
45 7024 45 70
3 50 100
b
d f g h
e
a
26 37
d`
61
c
85
g`
e`
b分裂,24上插
53 90
12
c`
7 30
a分裂,45上插第九章 查找第 69页
B- 树的插入
a分裂,45上插
24 45 70
3 50 100
b
d f g h
e
26 37
d`
61
c
85
g`
e`
53 90
12
c`
7 30
bt
a
bt
45
70
a a`
第九章 查找第 70页
Status InsertBtree( BTree &t,KeyType K,Btree q,int i )
/*在以 t 所指 m 阶 B- 树上插入等于 K 的关键字，若树为空则插入根结点，否则插入在 q->key[i] 和 q->key[i+1] 之间 */
(x,ap) = (K,NULL ); finished = false;
while( q≠ NULL && !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 = ; split(q,ap); //生成新结点，
且将 q->key[s+1..m] 和 q->ptr[s..m] 移至结点 ap中
x = q->key[s]; //组成一对新的插入信息
q = q->parent;
if( q≠NULL ) i = Search( q,x )
//继续在双亲结点 q中查找 x 的插入位置
}; //else
}; //while
在 B- 树一插入关键字的算法描述第九章 查找第 71页续上页
if( !finished )
Newroot(t,t,x,ap) //生成新的含信息 (t,x,ap)的根 t，其中 t 和 ap
为指向其子树根的指针
}// 算法 9.8
在 B- 树一插入关键字的算法描述第九章 查找第 72页删除操作过程与插入操作相类似，但要稍复杂些。若欲在 B-
树上删除一个关键字，则首先应找到该关键字所在结点，并从中删除之。若该结点为最下层的非终端结点，且其中的关键字数目不小于,则删除完成；
B- 树的删除否则要进行“合并”结点的操作。这里可能发生多种情况，
甚至合并会一直往上蔓延，传到根结点。更有甚者，还有可能发生根结点与它两个孩子进行合并，形成新的根结点，从而使整棵
B- 树减少了一层。
可分三种情况加以讨论：
（ 1）被删结点的关键字数目不小于
（ 2）被删结点的关键字数目等于,而其左或右兄弟结点中关键字数目不小于
（ 3）被删结点和其左或右兄弟结点中关键字数目等于第九章 查找第 73页
B- 树的删除可分三种情况加以讨论：
（ 1）被删结点的关键字数目不小于
（ 2）被删结点的关键字数目等于,而其右 (或左 )兄弟结点中关键字数目不小于删除关键字 Ki和相应指针 Ai
则需将其右兄弟结点中的最小（或最大）的关键字上移至双亲结点，
而将双亲结点中小于该上移关键字的关键字下移至被删关键字所在结点。如删除以下关键字 50
45
24 53 90
3 12 61 7037 50 100
b
d f g h
e
bta
c
70
53 61 9061 90
53
第九章 查找第 74页
B- 树的删除
（ 3）被删结点和其左或右兄弟结点中关键字数目等于不妨设右兄弟结点存在，且由双亲结点中的 Ai指针所指，则在删除关键字后，把剩余的关键字和指针，加上双亲结点中的关键字
Ki一起，合并至于 Ai指针所指兄弟结点中。
45
24
3 12 37 100
b
d f g h
e
bta
c
70
61 90
53
例如：删除关键字 53
第九章 查找第 75页
B+ 树
B+ 树是 B- 树的一种变型树。
一棵 m 阶的 B+ 树和 m 阶的 B- 树的差异在于
(1) 有 n 棵子树的结点中含有 n 个关键字 (n≤m)； {B- 树为
n-1 个 }
(2) 所有的叶结点包含了全部关键字的信息以及指向包含这些关键字的信息以及指向包含这些关键字记录的指针，叶结点本身依关键字由小到大顺序链接，从而既可从根开始随机查找，又可从叶结点顺序查找；
(3) 所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。
示例 8 下图为一棵 3阶的 B+ 树
59 97
72 97
63 7251 5910 15
15 44 59
21 37 44 85 91 97
root
sqt
图 9.18 一棵 3阶的 B+ 树第九章 查找第 76页说明：
(1) B+ 树与 B- 树的相同之处在于
a,根结点（非叶）最少有两棵子树
b,所有非终端结点（除根外）至少有 棵子树；
c,叶结点均在同一层次
(2) B+ 树的查找、插入、删除等操作与 B- 树类似。需强调的是,B+ 树查找时，若非终端结点上的关键字等于给定值时，并不终止，而是继续向下直到叶结点。因此，对 B+ 树，不管查找成功与否，每次查找都是走上了一条从根到叶结点的路径；
(3) 通常在 B+ 树上有两个头指针，一个指向根结点。因此，可以对 B+ 树进行两种查找操作。
B+ 树第九章 查找第 77页哈希表（散列表）
前面所介绍的查找方法是建立在“比较”的基础之上进行的，目标都是尽量减少“比较”的次数。
更希望不经过任何比较，一次存取就能得到所查记录。
哈希函数、哈希表
—— 提出了哈希表。思想：
通过在关键字和它的记录存贮位置之间建立一个确定的对应关系 f,使每个关键字和结构中一个唯一的有效位置相对应。 因而在查找时，只要根据这个对应关系 f 找到给定值 k 的映象 f (k)，
若结构中存在关键字和 k 相等的记录，则必定在 f(k) 的存贮位置上。
这个对应关系 f为 哈希函数,根据这种思想建立的表称为哈希表 。
第九章 查找第 78页通常对于一个给定的关键字集合,设计一个函数 。这个函数将关键字映射到 M个连续的整数集合中,且把这些整数解释成向量 V元素的标号，这个向量称为关键字集合的 Hash向量，向量的长为 M。
哈希函数、哈希表例如 假设每个标记符由 2个字母构成，并将标识符视为关键字，
则这种关键字共有 26× 26=676个，若接收这些关键字就会要
M=676个的存贮向量，按字典序把 26个字母赋予代码 1~26，
则编码为,
aa,ab,…,az,ba,…,bz,…,zz （标识符）
1,2,…,26,27,…,52,…,676 （编码）
2121 )1(26)( LLLLH显然可定义函数此函数可将标识映射到一个长为 676的向量中。
第九章 查找第 79页哈希函数、哈希表但在实际应用中，程序一般不会把所有两上字母组合的词都用作标识符（关键字），因此这样做虽能唯一确定标识符位置，
却浪费的空间 。若每个标识符（关键字）全由不多于 5个字母组成，
则有,265＋ 264＋ 263＋ 262＋ 26=12356630 种组合，这就是说要构造能容纳这么大的符号表（ Hash表），这是无法忍受的，
通常 Hash向量长度总是有限的,如果放弃上述一一对应的形式，并放弃不同的关键字一定要映射到存贮向量的不同位置上，则很容易找到能够把变化范围很广的关键字，映射到存贮向量的合适位置的一个函数。
所以我们设计的哈希函数应是一个 压缩映象 。
第九章 查找第 80页哈希函数、哈希表当几个关键字映射到存贮向量的同一位置时,就出现了 冲突 （ Collision）,即 k1≠k2,但 f(k1)=f(k2),k1与 k2
互为 同义词 。
所以建造哈希表时，应：
① 选择一个好的哈希函数，尽量减少冲突的发生。
② 因冲突一般是难免的，应设定一种处理冲突的方法。
第九章 查找第 81页哈希函数的构造方法判定 Hash函数好坏的标准，主要有两条：
① 随机性好指 Hash函数应当尽可能均匀地把关键字映射到 Hash向量的元素中；
哈希表（散列表）?
② 尽可能避免冲突指尽量使得关键字不共享 Hash向量同一元素,显然,随机分布越好,冲突的可能性也越小 。
常用的构造 Hash函数的方法有：
1,直接定址法取关键字或关键字的某些 线性值 为 Hash地址，即 H(key)=key或
H(key)=a?key+b 其中 a和 b为常数。
这种方法所得地址集合与关键字集合的大小相同，因此不会发生冲突。但实际很少采用。
第九章 查找第 82页哈希函数的构造方法
2,数字分析法假设关键字以 r为基的数,并且 Hash表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址 。
选取若干位的原则是使得到的哈希地址尽量避免产生冲突，前提是对关键字作深入分析。一般要求选择的若干位应具有比较好的随机性，这样可以减少冲突发生的可能。
例如：对英文单词进行散列，就不应当按第一个字符的值进行散列。
3,平方取中法取关键字平方后中间几位为哈希地址，这是一种常用的方法 。
通常在选 Hash函数时不一定知道关键字的全部情况，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，因此使随机分布的关键字得到的 Hash地址也是随机的,取的位数由表长决定。一般若表长为 2r,则取中间 r位。
第九章 查找第 83页哈希函数的构造方法
4,折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为 Hash地址，
该方法称折叠法（ folding）。
当关键字位数很多，而且每一位上数字分布大致均匀时，可以采用折叠法回到哈希地址。
如图书编号，身份证号码等。
5,除留余数法取关键字被某个不大于哈希表表长 m的数除后的余数作为地址。
H(key) = key MOD p ( p <= m )
次方法最简单，最常用。
第九章 查找第 84页哈希函数的构造方法总之,构造 Hash函数的方法可以很多,要考虑的因素有：
计算 Hash函数所需时间
关键字长度及分布情况
Hash的表的大小
记录的查找频率
6,随机数法选择一个随机函数，取关键字的随机函数值作为 Hash地址。
H( key ) = random( key )
此方法在关键字长度不等时可采用。
第九章 查找第 85页冲突处理由于冲突 不可避免,因此如何处理冲突是 Hash查找中的关键之一,假定 Hash向量的地址为 0~m－ 1（ 长度为 m）,冲突 是指由关键字得到的 Hash地址为 j(0≤j≤m－ 1)的位置上已存在记录,
则,处理冲突,就是为该关键字的记录找到另一个,空,的
Hash地址 。 在处理冲突的过程中可能得到一个地址序列 。 即在处理 Hash地址的冲突时,若得到的另一个哈希地址仍然发生冲突,则再求下一个地址,若仍然冲突,再求,依此类推,直到不发生冲突为止,则为记录在 Hash向量中的地址 。
冲突解决方法分为两类,闭散列方法和开散列方法哈希表（散列表）?
闭散列方法把所有记录直接存储在散列表中。 每个记录 i有一个基位置是 h(ki)，如果要插入一个记录 R，而另一个记录已经占据了 R位置，那么就把 R存储在散列表其他位置上，这个位置由冲突处理方法计算而得。
开散列方法并不把记录直接存储在散列表中，散列表中存储的是指向各个链表的表头指针。记录便存储在这些链表的结点中。
第九章 查找第 86页
)2(,,,2,2,1,1 222222 mkkkd i
冲突处理闭散列冲突处理
1,开放地址法发生冲突时,采用下列公式其中,H(key)为哈希函数； m为步长,为增量序列
1),称为线性探测再散列；
2),称二次探测再散列
3) di =伪随机数序列,称伪随机探测再散列上述方法实际上是根据 di找,下一个空位,
)1(,,2,1))(( mkkjmM O Ddk eyHH ii?
1,,2,1 md i?
第九章 查找第 87页冲突处理闭散列冲突处理,1,开放地址法例如 1,在长度为 11的 Hash表中已填关键字为 17,60,29
现在加入关键字为 38的记录，显然，产生冲突
11 )( M ODkeykeyH?
60 17 29
1 2 3 4 5 6 7 8 9 100
511 38)38( M ODH
(1) 采用线性探测再散列方法处理冲突：
得到下一个地址为 6，仍冲突，再求为 7仍冲突，直到 Hash地址为 8
时出现“空”位，插入记录，得到
60 17 29
1 2 3 4 5 6 7 8 9 100
38
优点,只要散列表不空，总能找到位置插入记录；
缺点,容易产生“二次聚集” —— 非同义词之间地址冲突。
第九章 查找第 88页冲突处理闭散列冲突处理
2、再散列当出现冲突时，采用不同的 Hash函数计算另一个 Hash函数地址，直到冲突不再发生。
即这种方法不易产生“聚焦”，但增加了计算时间。
缺点,增加了计算优点,不容易产生“二次聚集”；
kikeyRHH ii,,2,1)(
3,建立公共溢出区假设 Hash向量值域为 [0m－ 1]，则称向量 Hashtable[0m－ 1]为基本表，每个分量存一个记录，另建立向量 Overtable[0v]为溢出表。一旦发生冲突，都放入溢出表。
第九章 查找第 89页冲突处理开散列 冲突处理 —— 链地址法散列表中存储的是指向各个链表的表头指针。记录便存储在这些链表的结点中。 将所有关键字为同义词的记录存贮在同一线性关键表中。
例如，已知一组关键字为 (19,14,23,01,68,20,84,27,55,11,10,29)，则按和链地址法处理冲突得到的 Hash表如下所示：
13 )( M ODk e yk e yH?
0 ∧
1
2 ∧
3
4 ∧
5 ∧
6
7
8 ∧
9 ∧
10
11
12 ∧
01 14 27 79 ∧
55 68 ∧
19 84 ∧
10 23 ∧
11 ∧
20 ∧
第九章 查找第 90页
Hash表的查找及分析
Hash表的查找与其构造过程类似。算法思想如下：
哈希表（散列表）?
给定 K值,根据 Hash函数求得 Hash地址,若表中此位置上没有记录,则查找不成功,进行插入操作；
否则 比较 关键字,若与给定值 k相等,则查找成功；
否则根据处理冲突的方法找,下一位置,地址,直至哈希表中某个位置为,空,或者表中所填记录的关键字等于给定值为止 。
Hash表的初衷是通过“计算”，不用“比较”直接查找记录。
但从上述思想可知，只要创建表时存在“冲突”，查找时就难免要多次“比较”。
第九章 查找第 91页
Hash表的查找及分析下列算法为以开放定址法处理冲突的 Hash查找过程 （ 不考虑插入 ）
Status HashSearch( HashTable H,KeyType K,int &p,int &c )
{
p = Hash(K); //计算 hash地址
while( H.elem[p].key != NULLKEY &&
!EQ( K,H.elem[p].key ) //有记录且关键字不等
collision( p,++c );
if( EQ( K,H.elem[p].key )
return OK;
return Faliure
}
数据结构,int hashsize[] = {997,…}; //Hash容量表
typedef struct {
ElemType elem[]; //存储元素，动态分配
int count; //元素个数
int sizeindex; //容量大小
} HashTable;
第九章 查找第 92页
Hash表的查找及分析由查找过程可知：
1)显然 Hash其在关键字与记录的存贮位置之间建立了直接映象,
但由于冲突的产生,使得其查找过程仍然是一个给定值 k与关键字的比较过程 。 因此,仍需以平均查找长度作为 Hash表查找效率的尺度；
2)D.E.Knuth在程序设计技巧第三卷,Data Sorting and Data
Searching”中提出； 为了查找一个关键字或插入一个新关键字,
其平均查找长度取决于负载因子?。
M
N
H a s h
H a s h
表长度表中已填入记录数?
标志 Hash表的装满程度，一般情况下,?越小，发生的冲突可能性越小，反之则反。
第九章 查找第 93页
Hash表的查找及分析以开放定址冲突处理法的伪随机探测再散列为例,推导平均查找长度：
发现基位置被占的可能为,? = N/M
)1),,,(1(
)1),,,(1(
iMMM
iNNN
发现第 i次冲突的可能为,
发现下一位置被占的可能为,
)1(
)1(
MM
NN
若 N和 M>>1,那么可简化为,
i
M
N?
平均查找长度为,
)1/(1
1
1
i
M
N
i
第九章 查找第 94页
Hash表的查找及分析可以证明，不同的冲突处理方法其平均查找长度为,
线性探测再数列,
成功查找,?
1
1
1
2
1
l
A S L 不成功查找,
2
1
1
1
2
1
随机探测再数列，二次再数列和再哈希；
成功查找,
1ln
2
1
r
A S L
不成功查找,
1
1
链 地址法,
成功查找：
2
1
c
A S L
不成功查找：
e
第九章 查找第 95页删除当从散列表中删除记录的时候，有两点需要重点考虑：
哈希表（散列表）?
1,删除一个记录一定不能影响后面的检索 。
即删除之后，查找过程必须仍然能够通过新清空的位置。因此，删除过程不能简单地清空，这样会隔离探查序列后面的记录。
2,删除一个记录后,空出的位置能再利用一般的方法是,在删除记录的位置上设置一个特殊标记 —— 墓碑 。
第九章 查找第 96页内容提要
掌握静态查找：顺序查找、二分法查找、分块查找的概念和方法，熟悉平均查找长度的计算；
了解二叉排序树、平衡二叉树,B-树的动态查找过程 ；
理解哈希表的散列思想、冲突处理及查找过程。
掌握各种查找方法的应用场合。
第九章 查找 小结
第九章 查找第九章 查找第 2页第九章 查 找内容和要求查找的概念，顺序查找、二分法查找、分块查找的概念和方法，二叉排序树、平衡二叉树的查找，哈希表查找。要求获得有关静态和动态环境下几种基本的查找方法和技术知识。掌握顺序、二分法和分块查找的方法；了解哈希表是一种基本的存储结构、哈希表的背景和基本思路。掌握哈希表处理冲突的方法。
重点二分法查找方法；哈希表的动态查找。
第九章 查找第 3页
查找表 由同一类型的数据元素（或记录）构成 的集合基本概念
静态查找表 仅作查询与检索（统称为查找）工作的查找表。
动态查找表 除作查询与检索之外，还需作诸如插入、删除之类更新操作的查找表。
查找 在一个含有众多数据元素（或记录）的查找表中找出某个
“特定的”数据元素（或记录）的过程。
关键字 能够标识一个数据元素（或记录）的某个数据项的值。
当数据元素只有一个数据项时，其关键字即为该数据元素的值。
主关键字 能唯一地标识一个记录的关键字。
给定一个值 k，在含有 n个记录 (或数据元素 )的表中找出关键字等于给定值 k的记录，若找到，则 查找成功,查找结果为给出整个记录的信息，或指示该记录在查找表中的位置；若找不到，则 查找不成功,查找结果为 NULL值或值 0。
第九章 查找第 4页查找操作主要是关键字的比较,故通常把查找过程中对关键字需要执行的 平均比较次数 （亦称 平均查找长度 ）作为衡量一个 查找算法效率优劣的标准 。
基本概念
平均查找长度 为了确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值 (平均值 )称为查找算法在查找 成功时 的平均查找长度 (Average Search Length)。
对于含有 n个记录的表，查找成功时的平均查找长度为
(9-1)
其中
Pi：表中第 i个记录被查找的概率，有 ；
Ci：找到表中其关键字与给定值相等的第 i个记录时，所需要的比较次数。
若无特别声明，均认为表中每个记录的概率均相等，即第九章 查找第 5页约定和宏定义宏定义
#define EQ( a,b ) ((a) == (b))
#define LT( a,b ) ((a) < (b))
#define LQ( a,b ) ((a) <= (b))
注,宏定义随不同的数据类型，有所不同 。
第九章 查找第 6页
1、静 态 查 找 表静态查找表的 ADT
静态查找表是一种最简单的查找表。
Specification ADT Static_Search_Table
Elements,查找表中的数据元素类型相同，每一数据元素都 存在一个能唯一标识该元素的关键字
Structure,查找表中的 n个数据元素具有相同类型，属于同一集合 。数据元素之间不存在结构关系
Operation：
Create(ST,n) 生成操作,产生一个含用户给定的 n个数据元素的表 ST。
Search(ST,K) 查找函数,若表 ST中存在其关键字等于给定值 K的数据元素，则函数值为该元素在表中的位置；否则函数值为“空”。
Traverse(ST) 输出操作,按某种次序输出表 ST中所有数据元素。
第九章 查找第 7页顺序 (线性 )表的查找 —— 顺序查找顺序（线性）表的查找是一种最简单的查找方法。它的算法基本思想是,
从表的一端开始,顺序地扫描线性表,依次将扫描到的关键字和给定值相比较，若当前扫描到的记录的关键字与给定值相等，则查找成功，找到所查记录；若直至扫描结束，仍未找到其关键字与给定值相等的记录，
则查找不成功。
既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。若使用单链表作存储结构时，扫描必须从第一个结点开始。若以向量作存储结构，则可从前往后或从后往前进行扫描。
第九章 查找第 8页顺序表的查找算法描述
typedef struct {
ElemType elem[];
int Length;
}SSTable;
顺序（线性）表的查找
int seqsearch( SSTable st,keytype k )
{/*K为给定值，返回 i为关键字等于 K的记录在表 st中的序号,i值为零表明查找不成功 */
st.elem[0].key = K; //设置监视哨
for( i = st.length; !EQ( st.elem[i].key,key ); i--)
//从表尾开始向前扫描
return i; //返回找到的位置
} //算法 9.1
第九章 查找第 9页算法性能分析
nnSS PPPnnPA S L 121 2)1(?
若查找每个记录时是等概率，则有 ASLss=(n+1)/2
顺序（线性）表的查找
(9-2)
第九章 查找第 10页如果考虑到不成功的查找，则 查找算法的平均查找长度 应是查找成功时的平均长度与查找不成功时的平均查找长度之和 。若假设查找成功与不成功的可能性相同，对每个记录的查找概率也相等，即 。由于查找不成功的比较次数总是 n+1，故顺序查找的平均查找长度为顺序（线性）表的查找第九章 查找第 11页
(2) 当表中各个记录的查找概率互不相等时，为了提高查找效率，宜将诸记录先按查找概率由小到大进行排列（式 (9-2)在
P1≤P2≤···≤Pn-1≤Pn时达到极小值）；
说明：
(1) 顺序查找算法简单，且对表的结构无任何要求（无论按向量还是链表结构，无论记录间是否按关键字有序排列），故此算法适应面广。但当 n>>1时,查找效率随 n越大而越低 。
顺序（线性）表的查找
(3) 在很多实际应用的情况下，各记录的查找概率无法事先确定，则可以采用“自组织”形式的顺序查找表。
第九章 查找第 12页有序表的查找 —— 折半查找折半查找又称二分查找（ Binary Search），它是一种效率高的查找方法。
折半查找的 前提是静态查找表是有序表,即表中记录按关键字有序排列，且需使用 向量作为表的存储结构 。不妨设有序表是递增有序的。
折半查找的算法思想：
先确定待查记录所在的范围（区间），然后以处于区间中间位置记录的关键字和给定值 K相比较,（ 1） 若相等，则查找成功； （ 2） 若不等，则缩小范围，继续按此法查找，
直至新的区间位置记录的关键字等于给定值 K，或者查找区间的大小等于零（表明查找不成功）时为止。
猜数游戏的方法第九章 查找第 13页有序表的折半算法描述
int Search_Bin( SSTable st,KeyType key )
{ //在有序表 st中折半查找关健字等于给定值 key的记录
int mid;
low = 1; hig = st.Length; //置区间初值
while( low ≤ hig ) //判别查找区间大小
{ mid = ( low + hig ) / 2;
switch{
case K ＞ st.elem[mid].key,low = mid+1;
case K == st.elem[mid].key,return mid;
case K ＜ st.elem[mid].key,hig = mid-1;
}
}
return( 0 ); //查找不成功
} // 算法 9.2
有序表的查找 —— 折半查找第九章 查找第 14页算法性能分析
6
3 9
7 I041
52 8 11
56
80
64 88
92753713
05
19
21
这棵二叉树并非完全二叉树，但其叶结点所在层次之差至多为 1。因此，该二叉树深度与一根完全二叉树相同，
为 。 这里 n是二叉树结点的个数,亦即有序表中数据元素的个数。
折半查找过程中可用二叉树来描述（ 判定树 ）。树根为表的中间记录。根的左子树关键字均小于根的关键字，根的右子树关键字均大于根的关键字。
56 8064 88 9275371305 19 21
示例 1,以下 11个数据元素为例，可画出二叉树有序表的查找 —— 折半查找第九章 查找第 15页结论,折半查找法在查找 成功时 进行比较的关键字个数最多不超过树的深度，即问题：查找不成功的情况如何？
示例 2 对于如示例 1所给数据，描述折半查找过程加上 外部结点 的判定树和查找关健字为 85的结点，示意如下
6
3 9
7 I0
56
80
64 8805
19
211 4
I19-1086-713 53-4 372-1
10-11 11-1-2 2-3 4-5 5-6 7-8 8-9
75 92
图 9.3 加上外部结点的判定树和查找 85的过程结论,折半查找在查找不成功时和给定值进行比较的关健字个数最多不超过有序表的查找 —— 折半查找第九章 查找第 16页折半查找的平均查找长度的计算：
记 h=log2(n+1),即有 n=2h-1，则描述折半查找的判定树是深度为 h的 满二叉树 。设表中每个记录的查找概率均相等（ Pi=1/n），
则查找成功时折半查找的平均查找长度其中 j为层数,2j-1为该层结点数。
记,则故有因为当 n>>1时，有有序表的查找 —— 折半查找第九章 查找第 17页说明：
折半查找的效率比顺序查找高。
有序表的查找 —— 折半查找而排序本身是一种很费时的操作，即使采用高效率的排序方法也要花费 O(nlog2n) 的时间代价 。
另外，折半查找仅适用于顺序存储结构，为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。故折半查找特别适用于那些一经建立就很少改动，而又经常需要查找的线性表,而对那此查找少而又经常需要改动的线性表，可采用链表作存储结构，进行 顺序查找 ；
第九章 查找第 18页索引顺序表的查找 —— 分块查找以索引顺序表表示静态查找表时，可采用分块查找（
Blocking Search） 方法来进行查找。
分块查找又称索引顺序查找，它是一种性能介于顺序查找和折半查找之间的方法。
分块查找法要求按如下的索引方式来存储一个线性表,
将表 R[1..n] 均分为 b块,前 b-1块中结点个数为,第
b块的结点数小于或等于 S。 每一块中的关键字不一定有序,但前一块中的最大关键字必须小于后一块中的最小关键字，即要求表是,分块有序” 的 。抽取各块中的最大关键字及起始位置，构成一个索引表 ID[1..b]。 由于表 R是分块有序的，所以索引表应是一个递增有序表。
第九章 查找第 19页示例 3 分块有序表的索引存储表示分块查找的算法思想：
(1) 查找索引表，确定待查关键字所在的块（子表）。 由于索引表是按记录关健字有序，故宜采用 折半查找法 ；
(2) 在所确定的块中查找是否存在关键字与给定值相同的记录 。此时需采用 顺序查找法 。
故分块查找的算法实际上是折半查找算法和顺序查找算法的简单合成。
22 48 86
1 7 13
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53
索引表最大关键字起始地址子表 1 子表 2 子表 3
索引顺序表的查找 —— 分块查找图 9.6 表及其索引表第九章 查找第 20页分块查找的算法分析分块查找实际上是两次查找过程，故整个算法的平均查找长度是两次查找的平均查找长度之和，即
ASLbs=Lb+Lw，
其中
Lb：查找索引表所在子表的平均查找长度
Lw：在子表中顺序查找记录的平均查找长度设将表均匀分布成 b个子表，每个子表包含 s个记录 （最后一个子表可能不足 s个记录）,并设表中每个记录的查找概率均相等，即每个子表的查找概率为 1/b，子表中每个记录的查找概率为 1/s。
(1) 若用顺序查找确定所在块，则索引顺序表的查找 —— 分块查找与表长 n有关，
与块中记录个数 s有关第九章 查找第 21页
(2) 若用折半查找法确定所在块，则示例 4 若表中有 n=10000个记录，取 即将该表分成 100块，每块中含 100个记录。则用顺序查找确定块的分块查找平均需要做 101次比较，而若用折半查找确定所在块，
则最多需做约 57次比较。
若使用顺序查找，平均需做约 5000次比较，而使用折半查找，则最多需做约 14次比较。
故分块查找算法的效率介于顺序查找和折半查找算法之间。
索引顺序表的查找 —— 分块查找第九章 查找第 22页说明：
(1) 分块查找的优点是，在表中插入或删除一个记录时，
只要找到该记录应当所属的块，然后在块内进行插入和删除运算。因为块内记录的存放是任意的，所以插入或删除比较容易
，不需要移动大量记录。分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的操作；
索引顺序表的查找 —— 分块查找
(2) 在实用中，分块查找不一定要将线性表分成大小相等的若干块，而应该根据表的特征进行分块。例如，一个学校的学生登记表，可按系号或班号分块。此外，各块中的记录也不一定要存放在同一个向量中，可将各块放在不同的向量中，也可将每一块存放在同一个单链表中。
第九章 查找第 23页动 态 查 找 表当用线性表作为表的组织形式时，可采用顺序查找、折半查找、分块查找等查找方法，其中以折半查找效率最高。
但折半查找要求表中结点按关健字有序，且不能使用链表作存储结构。因此，当表的插入或删除操作频繁时，为了维护表的有序性，势必要移动表中很多结点，引起额外的时间开销，从而抵消了折半查找的优点。
希望采用既具有如折半查找那样的查找效率、又易于进行诸如插入、删除结点操作的表的组织方式。这就是动态查找表。
动态查找表的 ADT
第九章 查找第 24页动态查找表既具有顺序表那样较高的检索效率，又具有链表那样插入、删除的灵活性。它可有不同的表示方法，但较典型的是 采用特殊的树或二叉树作为动态查找表的一种组织方式，可 统称为树表 。
动态查找表的特点,表结构本身是在查找过程中动态生成的，即对于给定值 K，若表中存在其关健字等于 K的结点（记录），则查找成功返回，否则插入关健字等于 K的结点（记录）。 在动态查找表中亦允许删除表中结点。
动 态 查 找 表动态查找表的 ADT
第九章 查找第 25页
Specification ADT Dynamic_Search_Table
Elements,表中各结点都含有一个类型相同的关健字，并且该关健字可唯一地识别结点
Structure,n个结点具有查同属性，同属一个集合动态查找表的 ADT
Operation：
Initialize(DT) 初始化操作,设置一个空的动态查找表 DT。
Search(DT,K) 查找函数,若表 DT中存在其关键字等于给定值 K的结点，则函数值为该结点或它在表中的位置；否则函数值为“空”。
Insert(DT,K) 插入操作,若表 DT中存在其关键字等于给定值 K的结点，则空操作；否则插入其关键字等于 K的结点。
Delete(DT,K) 删除操作,若表中存在其关键字等于给定值 K
的结点，则删除之；否则空操作。
Traverse(DT) 输出操作 按某种次序输出表 DT中所有结点。
第九章 查找第 26页二叉排序树及其查找过程二叉排序树（ Binary Sort Tree） 又称为二叉查找树或二叉搜索树（ Binary Search Tree）。它是一种特殊结构的二叉树。
动 态 查 找 表?
定义,二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：
(1) 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值；
(2) 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值；
(3) 它的左、右子树也分别为二叉排序树 。
显见。关于二叉树排序树的这一定义是递归的。
第九章 查找第 27页示例 1 如下是两棵二叉排序树
45
12
3
24
53
61
10037
90
78
(a) 图 9.7 二叉排序树示例 (b)
二叉排序树的一个重要性质：
性质 对二叉排序树按中序遍历该树所得到的中序序列是一个递增有序序列 。
故一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
CAO
ZHAO
DING
CHEN WANG
MA
DU
XIA
LI
二叉排序树及其查找过程第九章 查找第 28页二叉排序树的查找算法描述
BiTree bstsrch( BiTree t,KeyType K )
{ //在指针 t所指的二叉排序树上查找其关健字等于给定值 K的记录，当查找成功时，返回指向该记录结点的指针，否则返回空指针
if(( t == NULL )||(t->data.key == K ))
return t;
else
if( t->data.key < K )
return bstsrch( t->rchild,k );
else
return bstsrch( t->lchild,k );
} //算 法 9.4(a)
第九章 查找第 29页二叉排序树的插入和生成二叉排序树是一种 动态树表 。其特点是，树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。
动 态 查 找 表?
在二叉排序树中插入新结点，需保证插入后仍符合二叉排序树的定义。
在二叉排序树中插入新结点，需保证插入后仍符合二叉排序树的定义。
插入的前提,查找不成功插入的位置,若二叉排序树为空，则插入结点成为新的根结点；否则，沿左子树或右子树继续查找，直至某结点的左子树或右子树为空为止，插入结点作为一个新的叶结点并成为该结点的左孩子或右孩子结点。
第九章 查找第 30页二叉排序树查找算法的修正算法
Status SearchBST( BiTree t,KeyType K,BiTree f,BiTree &p )
/*在查找指针为 t的二叉树上查找关键字等于 K的结点，若存在，则 p返回指向该结点的指针；否则返回指向查找路径上最后一个结点的指针，以指示插入位置,f的初始调用值为 NULL，指向 t的双亲 */
{ if( t == NULL ) //查找不成功
{ p = f; return false }
else if( t->data.key == K ) //查找成功
{ p = t; return true; }
else if( K< t->data.key ) //继续在左子树上进行查找
SearchBST(t->lchild,key,t,p )
else //继续在右子树上进行查找
SearchBST(t->rchild,key,t,p )
} //算 法 9.4(b)
参数 f的作用？
第九章 查找第 31页二叉排序树的插入算法
Status ins_bstree( BiTree &t,Elemtype e )
/*在根指针为 t 的二叉排序树上插入关键字为 e.key 的结点，若树空，
则插入结点为新的根结点，否则根据 K 小于（或大于）结点 f 中关键字而插入为 f 的左子树（或右子树）的根 */
{
if( !SearchBST( t,e.key,NULL,p )) {
s = new( BiTreeNode );
s->data = e; s->lchild = s->rchild = NULL;
if( p == NULL ) t = s;
else if( e.key < p->data.key ) p->lchild = s;
else p->rchild = s;
return true;
}
else
return false;
} //算 法 9.5
第九章 查找第 32页从二叉排序树的生成过程可以看到，它经历了若干次插入新结点的操作。 每次插入的新结点都是二叉排序树上新的叶子结点,则在进行插入操作时，不必移动其它结点，仅需改动某个结点的指针
，由空变为非空即可。它表明，二叉排序树既有类似于折半查找的特性，又采用了链表作存储结构，因此是动态查找表的一种适宜表示。
示例 2 设从空树出发，对于输入关键字序列
{45,24,53,12,37,93}，经过一序列的查找、插入操作，可陆续生成一棵二叉排序树,45
24 53
12 37 93
图 9.8 二叉排序树的构造过程二叉排序树的插入初始问题：如何实现在一个二叉排序树上删除某个结点？
第九章 查找第 33页二叉排序树的删除从二叉排序树上删除一个结点，不能把以该结点为根的子树都删去,而只能删掉该结点自身,并且还要保证删除后所得的二叉树仍然满足二叉排序树的性质。
也就是说，在二叉排序树中删去一个结点，相当于删去有序序列中的一个结点。
删除操作必须进行查找，以确定被删结点是否在二叉排序树中。若不在，则不做任何事情；若在，则设法删除之。
动 态 查 找 表?
第九章 查找第 34页
(3) p结点既有左子树又有右子树，即 p结点的左、右子树均不空。
此时不能作简单处理，而需对 p结点的左、右子树进行细化,目的是将 p的左、右子树链接到合适的位置，并保持二叉排序树的特性
。
假设在二叉排序树上被删结点为 p，其双亲结点为 f，且不失一般性，可设 p 是 f 的左指针
(2) p结点只有左子树 pL或右子树 pR，则令 pL或 pR直接成为 f结点的左子树即可 ;
F
P
f
p
二叉排序树的删除分三种情况进行讨论删除操作
(1) p结点为叶结点，即 pL和 pR均为空树。
则可令 f->lchild = NULL;
F
P
f
p
F
P
f
p
第九章 查找第 35页设删除结点 p之前二叉排序树的形状如下（细化 PL）
按中序遍历所得序列为
{···CLC···QLQSLSPPRF ···}
若欲删去结点 p，且保持二叉排序树的特性，则所指指针改变而获得的新二叉树排序树，经按中序遍历所得序列应为
{···CLC···QLQSLSPRF ···}
P
C
p
c
Ff
Q
S
q
s
可采用两种做法实现之做法一 令 p的左子树为 f的左子树，而 p的右子树为 s的右子树做法二 令 p的直接前驱（或者接后继）替代 p，然后再从二叉排序树中删去它的直接前驱（或直接后继）
二叉排序树的删除第九章 查找第 36页做法一 令 p 的左子树为 f 的左子树，而 p 的右子树为 s 的右子树
f->lchild = p->lchild;
s->rchild = p->rchild;
P
C
p
c
Ff
Q
S
q
s
Cc
Ff
Q
S
q
s
二叉排序树的删除第九章 查找第 37页做法二 令 p 的直接前驱（或者接后继）替代 p，然后再从二叉排序树中删去它的直接前驱（或直接后继）
q = p; s = p->lchild;
while( s->rchild ≠ NULL )
{ q = s; s = s->rchild };
p->data = s->data; //替代
if( q ≠ p ) q->rchild = s->lchild;
else q->lchild = s->lchild; //删 s
free(s);
q≠p情形
q=p情形
P
C
p
c
Ff
Q
S
q
s
S
Pp
Ff
Ss
q
Pp
Ff
S
q
S
首先查找 s与 q
s即为 p 的左孩子结点二叉排序树的删除第九章 查找第 38页二叉排序树的查找分析示例 3 设输入关键字序列分别为 {45,24,53,12,37,93}以及
{12,24,37,45,53,93}，则将生成两棵不同形态的二叉排序树图 9.10不同形态的二叉查找树
(a) 关键字序列为 {45,24,53,12,37,93}的二叉排序树
(b) 关键字序列为 {12,24,37,45,53,93}的单支树当先后插入的关键字有序时，所构成的二叉排序树蜕变为单支树。
12
24
37
45
53
93
45
53
93
24
3712
(a) (b)
含有 n个结点的二叉排序树的平均查找长度和树的形态有关。
第九章 查找第 39页二叉排序树的平均查找长度
(1) 最佳情况二叉排序树的形态和折半查找的判定树相同
ASL=log2(n+1)-1
(2) 最差情况二叉排序树蜕变为单支树
ASL=（ n+1） /2
(3) 随机情况
ASL≤1+4log2n
二叉排序树的查找分析?
就平均性能而言，二叉排序树上的查找和折半查找相差不大，并且二叉排序树的插入和删除结点十分方便，无需移动大量结点。因此，对于需要经常做插入、删除和查找操作的表，
拟采用二叉排序树结构。
第九章 查找第 40页平衡二叉树二叉排序树的查找效率取决于树的形态，而构造一棵形态匀称的二叉排序树与插入的先后次序往往不是随人的意志而定的，这就要求找到一种动态平衡的方法，对于任意给定的关健字序列都能构造一棵形态 匀称 的二叉排序树。也就是说，需在构成二叉排序树的过程中进行,平衡化,处理，成为平衡的二叉排序树。
把形态匀称的二叉树称为平衡二叉树（ Balanced Binary Tree）
定义 平衡二叉树 或者是一棵空树，或者是任何结点的左子树和右子树 深度最多相差 1的二叉树。
定义 二叉树上任一结点的左子树深度减去右子树深度之差称为该结点的 平衡因子 （ Balance Factor）
问题：如何构造出一棵平衡的二叉排序树？
Adelson_Velskii和 Landis提出了一个方法。
所以平衡的二叉排序树也简称为 AVL树 。
第九章 查找第 41页示例 4 平衡二叉树、不平衡二叉树以及树中诸结点的平衡因子示例如下
1
1
(a)
-1
-1
1
1
0
(b) 0
0
0
0
图 9.11 平衡与不平衡的二叉树及结点的平衡因子
(a)(b) 平衡二叉树； (c)(d) 不平衡的二叉树
2
-1
1
(c)
-1
-2
100
(d)
0
0
0
0
0
平衡二叉树?
第九章 查找第 42页如何使构成的二叉树成为平衡树平衡调整规律,假设由于在二叉排序树上插入结点而失去平衡的最小子树的根结点指针为 a（ 即 a是离插入结点最近，且平衡因子绝对值超过 1的祖先结点 ），则失去平衡后进行调整规律可归纳为下列四种情况：
45
50
60
30
48
0
0
00
1
200
LL
插入前 插入 20 调整后
(1) LL型平衡旋转原因：在 A的左子树的左子树上插入结点使 A的平衡因子由 1增至 2
调整：进行一次顺时针旋转操作示例：
50
60
48
45
1
0
0
0
30 0
50
60
48
45
2
0
0
1
30 1
20 0
第九章 查找第 43页
(2) RR型平衡旋转原因：在 A的右子树的右子树上插入结点，使 A的平衡因子由
-1减至 -2
调整：进行一次逆时针旋转操作
RR型：
b = a->rchild;
a->rchild = b->lchild; a->bf = 0;
b->lchild = a; b->bf = 0; //b为子树新根如何使构成的二叉树成为平衡树
13
24
(c)
-1
0 13
24
37
(d)
-2
-1
0
a→
b→
24
3713
(e)
0
0
0a→
b→
示例：
第九章 查找第 44页
(3) LR型平衡旋转原因：在 A的左子树的右子树上插入结点，使 A的平衡因子由
1增至 2
调整：进行先逆时针、后顺时针共两次旋转操作
21
24
18
13
2
0
-1
-1
11 0
19
a→
b→
c→ 0
如何使构成的二叉树成为平衡树
21
2418
13
2
0
1
1
11 0
19
a→
b→
c→ 0 21
24
18
13
0
0
0
1
11 0 19
a
b→
c→
0
示例,21
24
18
13
1
0
0
0
11 0
a→
b→
c→插入前插入 19 先逆时针旋转再顺时针旋转第九章 查找第 45页
LR 型,b = a->lchild; c = b->rchild;
a->lchild = c->rchild; b->rchild = c->lchild;
c->rchild = a; c->lchild = b; //c为子树新根
switch{ //插入之前 c->bf 为零，插入之后有三种情况
case c->bf == 1,{ a->bf = -1; b->bf = 0};
case c->bf == -1,{ a->bf = 0; b->bf = 1 };
case c->bf == 0,{ a->bf = 0; b->bf = 0 };
};
c->bf = 0; b = c; //旋转变换以后，用 c指向新树根如何使构成的二叉树成为平衡树
21
24
18
13
2
0
-1
-1
11 0
19
a→
b→
c→ 0
21
24
18
13
0
0
0
1
11 0 19
a
b→
c→
0
第九章 查找第 46页
(4) RL 型平衡旋转原因：在 A的右子树的左子树上插入结点，使 A的平衡因子由 -1减至 -2
调整：进行先顺时针、后逆时针共两次旋转操作如何使构成的二叉树成为平衡树
24
70
37
13
-1
0
0
0
示例：
53
0
a→
b→
c→
24
70
90
13
-2
1
0
0
70
0
a→
b→
c→
24
37
90
13
-2
-2
0
0
900
c→
a→
b37
70
53
24
0
0
0
1
90
0
37-1
53 0 13
0
第九章 查找第 47页
RL 型,b = a->rchild; c = b->lchild;
a->rchild = c->lchild; b->lchild = c->rchild;
c->rchild = b; c->lchild = a;
switch{
case c->bf == 1:{ a->bf = 0; b->bf = -1};
case c->bf == -1:{ a->bf = 1; b->bf = 0 };
case c->bf == 0:{ a->bf = 0; b->bf = 0 };
};
c->bf = 0; b = c;
如何使构成的二叉树成为平衡树
53
0
a→
b→
c→
24
70
90
13
-2
1
0
0
900
c→
a→
b37
70
53
24
0
0
0
1
37-1 130
第九章 查找第 48页在平衡树上插入一个结点的算法描述平衡旋转是当二叉排序树在插入结点后产生不平衡时进行的。为了使得到的二叉排序树为平衡树，需对插入算法
ins_bstree(t,k,s)作如下修改为此，需要做到
(1) 在查找 s 结点的插入位置的过程中，记下离 s 结点最近且平衡因子不等于零的结点，令指针 a 指向该结点；
(1) 判别插入结点之后是否产生不平衡；
(2) 找到失去平衡的最小子树；
(3) 判别旋转类型并作相应调整处理。
(2) 修改自 a 至 s 路径上所有结点的平衡因子值；
(3) 判别树是否失去平衡，即在插入结点之后,a 结点的平衡因子绝对值是否大于 1。若是，则需判别旋转类型并作相应处理，否则插入过程结束。
第九章 查找第 49页平衡树查找的分析
(1) 在平衡树的查找过程中，与给定值进行比较的关键字个数不超过树的深度，这与排序树相同
(2) 含有 n 个结点的 AVL树其最大深度与 log2n 同数量级（
最大深度 ）；
(3) 由于在 AVL 树上查找时，和关键字比较的次数不超过树的深度，且不再出现蜕变为单支树的情形，因此 AVL 树上查找的时间复杂度是 O(log2n)
(4) 因为动态平衡过程仍需花费不少时间，故在实际应用中
，是否采用 AVL 树要根据具体情况而定。一般情况下，
项结点关键字是随机分布的，并且系统对平均查找长度没有苛求，则使用二叉排序树即可。
第九章 查找第 50页
B- 树和 B+ 树以前所讨论的算法都是内查找算法，被查找的数据都保存在内存中。它们适用于组织较小的、内存中记录的文件。对于较大的、存放在外存储器上的文件，它们就不合适了。
1972年,R.Bayer 和 E.McCreight 提出了一种适用于外查找的树，它是一种 平衡的多叉树,其特点是插入、删除时易于平衡，外查找效率高，适用于组织磁盘文件的动态索引结构。这就是 B- 树。
例如,当用平衡二叉树作为磁盘文件的索引组织时，若以结点作为内、外存交换的单位，则查找到需要的关键字之前，平均要对磁盘进行 log2n 次访问，这是很费时间的。
B- 树定义第九章 查找第 51页
B-树 致力于解决实现基于磁盘的检索树时遇到的所有问题：
B- 树和 B+ 树?
B- 树定义
(1) B- 树总是高度平衡的，所有叶结点都在同一层；
(2) 更新和检索操作只影响一些磁盘页，因此性能很好；
(3) B- 树把相关的记录放在同一个磁盘页中，从而利用了访问局部性原理；
(4) B- 树保证树中至少有一定比例的结点是满的。这样能够改进空间的利用率，同时在检索和更新期间减少需要的磁盘读取数目。
第九章 查找第 52页定义 (B- 树 ),一棵 m 阶的 B- 树，或为空树，或为满足下列特性的 m 叉树：
B- 树定义
(1) 树中每个结点至多有 m 棵子树；
(3) 根结点至少有两棵子树（唯一例外的是只包含一个根结点的
B- 树）；
(4) 所有的叶结点均在同一层，且叶结点不包含任何关键字信息；
(5) 有 j 棵子树的非叶结点恰好包含 j-1 个关键字。
B- 树的一个包含 j 个关键字,j+1 个指针的结点的一般形式为,
j A0 K1 A1 K2 ··· Aj-1 Kj Aj
Ki(i=1,2,···,j) 为关键字，且 Ki<Ki+1(i=1,2,···,j-1);
其中,Ai(i=0,1,··,j) 为指向子树根结点的指针；
且指针 Ai-1 所指子树中所有结点的关键字均小于 Ki(i=1,2,···,j)，
Aj 所指子树中所有结点的关键字均大于 Kj； j 为关键字个数（或
j+1 为子树个数）。
(2) 除根结点和叶结点外，其它每个结点至少有 棵子树；
第九章 查找第 53页
1 35
1 18
b c
d e f g h
t
图 9.14 一棵 4阶的 B- 树在 B- 树中每个结点的关键字从小到大排列。因为叶结点不包含关键字，故可把叶结点看成在树中 实际上并不存在的外部结点 。 叶结点的总数正好等于树中所包含的关键字总个数加 1。
B- 树定义
1 11 1 27
a
2 43 78
1 39 3 47 53 64 1 99
F F F F F F F F F F F F
示例 1
第九章 查找第 54页示例 2 下图为一棵 6阶的 B- 树（简化形式）
注,m=6。每个非叶结点的子树个数在 6/2(=3)和 6之间，
从而它们所包含的关键字个数可以不等，取 2,3,4或 5。
B- 树定义第九章 查找第 55页
B- 树的查找在 B- 树上进行查找的过程和二叉树的查找类似。
在 B- 树上查找给定的关键字的方法是：
首先取根结点，在根结点所包含的关键字 K1,K2,···,Kj 中查找给定值，若找到等于给定值的关键字，则查找成功 ;
否则，可以确定要查的关键字是在某个 Ki 和 Ki+1 之间（因为在结点内部的关键字是排序的），故可取 Ai 所指向的结点继续查找如此重复下去，直至找到，或指针 Ai 为 NULL 时，查找失败。
可见，在 B- 树上进行查找的过程是一个顺指针查找结点和在结点的关键字中进行查找交叉进行的过程。
第九章 查找第 56页
2 47 53 64
2 43 78
A0 A1 A2
1 35A0 A1
示例 3,承示例 1，在一棵 4阶 B- 树上查找图 9.14 一棵 4阶的 B- 树
1 18
b c
d e f g h
t
1 11 1 27
a
1 39 1 99
F F F F F F F F F F
B- 树的查找
(1) 查找关键字 47 (2) 查找关键字 23查找成功
F F
查找失败在 B- 树中查找与所给关键字相等的结点的算法思想：
(1) 在 B- 树中根据关键字找结点； (2) 在结点中找关键字。
第九章 查找第 57页
B- 树结点类型说明
#define m 3
typedef struct BTNode{
int keynum;
struct BTNode *parent; //父结点指针
KeyType key[m+1]; //关键字,m 个 (0未用 )
struct BTNode *ptr[m+1]; //指向子树的指针,m+1个
Record *recptr[m+1]; //指向记录的指针 (0未用 )
} BTNode,*BTree;
typedef struct{
BTNode *pt;
int i; //关键字序号
int tag; //0-查找不成功,1-查找成功
} Result;
B- 树的查找第九章 查找第 58页
Result SearchBTree( Btree T,KeyType K)
/*在根结点指针为 T 的 m阶 B- 树上查找关键字 K，返回记录
(pt,i,tag)。若查找成功，则特征位 tag=1，等于 K 的关键字即为指针 pt 所指结点的第 i个关键字；若查找不成功，则特征位 tag=0，等于 K 的关键字应插入到指针 pt 所指结点第 i 个和第 i+1 个关键字之间 */
{ p = T; q = NULL; found = false; i = 0;
//初始化,p 指向待查结点,q 指向 p 的双亲结点
while( p≠NULL && !found )
{ n = p->keynum; i = Search( p,K );
//在 p->key[1..n] 中进行查找，
//直至 p->key[i]≤K<p->key[i+1]止,0 ≤ i ≤ n
if( i > 0 && p->key[i] == K )
found = true;
else { q = p; p = p->ptr[i] }
}; //while
if( found )
return(p,i,1) //查找成功
else return(q,i,0) //查找不成功，返回插入位置信息
} //算法 9.7
第九章 查找第 59页性能分析：通常 B- 树 存储在外存上。在 B- 树中查找结点涉及内、外存交换，而结点中查找关键字是在内存进行的，后者可采用折半查找，效率很高。 因此,B- 树的查找效率主要取决于如何在树中找结点，即需与磁盘交换，而这一操作又与 B- 树的层次数（深度）有关，所以，算法的效率取决于树的高度，（最大层次数）。
B- 树的查找分析第九章 查找第 60页假设 B- 树有 N 个关键字，因此共有 N+1 个树叶，且设树叶均在 l+1 层。
根据 B- 树定义，
第一层有一个结点（根），
第二层至少有 2个结点，
第三层至少有 个结点,·····，
第 l+1 层至少有 个结点。
由于叶结点 数为 N+1，因此，有即
B- 树的查找分析
2*（ ）
2*（ ） l-1
l 这意味着若 N=1,999,998,m=199，则 l
至多等于 4。显然其查找效率非常之高。
第九章 查找第 61页
B- 树的插入
B- 树的生成也是从 空 树起，逐个插入关键字而得。 但 B-
树的插入与一般树的插入有所不同。一般树的插入是将树 往下延伸,而 B- 树的插入却是 往上“蔓延” 的。
对于叶结点处于第 L+1 层的 B- 树，插入的关键字总是进入第 L 层的结点。
在 m阶 B- 树中插入一个关键字：
由于 m阶 B- 树结点中的关键字个数必须,
因此，每次插入一个关键字不是在树中添加一个叶结点，而是首先在最低层的某个 非终端结点 中添加一个关键字，若该结点的关键字个数不超过 m-1，则插入完成；
否则（ 关键字个数等于 m）要对结点进行,分裂”。
第九章 查找第 62页
B- 树的插入怎样对结点进行,分裂”？
令 f=
m-f >=
m A0 K1 A1 K2 ··· Af-1 Kf Af Kf+1Af+1Kf+2 ··· Am-1 Km Am
结点如下所示：P
f A0 K1 A1 K2 ··· Af-1 Kf Af
p
m-f-1 Af+1Kf+2 ··· Am-1 Km Am
P`
把关键字 Kf+1和指针 p`一起插入到 P的双亲结点中，当然这有可能会导致双亲结点的“分裂”，甚至产生连锁反应。
第九章 查找第 63页示例 4,下列图示给出了一棵 3阶 B- 树依次插入关键字 30,26,85
和 7时，整个 B- 树和结点的变化过程
(a) 一棵 2-3 树 45
24 53 90
3 12 61 7037 50 100
b
c d f g h
e
bt
B- 树的插入
a
(1) 插入关键字 30：首先查找插入位置 (37之前 )； 进行插入，并检查
45
24 53 90
3 12 61 7037 50 100
b
d f g h
e
bta
c
30
第九章 查找第 64页
45
24 53 90
3 12 61 7030 37 50 100
b
c d f g h
e
bt
插入 26之后，结点 d需分裂,30向上插入到双亲结点中。
B- 树的插入
a
(2) 继续插入关键字 26：首先查找插入位置 (30之前 )；
进行插入，并检查插入后结点关键字数目大于 2。
c
bt
45
24 53 90
3 12 61 7050 100
b
d f g h
e
a
30 3726 26 30 37
d`
30
第九章 查找第 65页插入 85之后，结点 g需分裂,70向上插入到双亲结点 e中。
B- 树的插入
(3) 继续插入关键字 85：首先查找插入位置 (70之后 )；
进行插入，并检查插入后结点关键字数目大于 2。
c
bt
45
24 30 53 90
3 12 61 7050 100
b
d f g h
e
a
26 37
d`
c
bt
45
24 30 53 90
3 12 61 7050 100
b
d f g h
e
a
26 37
d`
61 70 85
第九章 查找第 66页插入 85之后，结点 g需分裂,70向上插入到双亲结点 e中。
B- 树的插入
c
bt
45
24 30 53 90
3 12 50 100
b
d f g h
e
a
26 37
d`
61 70 85
结点 g需分裂。 bt
45
24 30 53 90
3 12 50 100
b
d f g
h
e
a
26 37
d`
61
c
70 85
70
g`
e分裂,70上插
70
e`
第九章 查找第 67页
B- 树的插入
bt
45 70
24 30
3 12 50 100
b
d f g h
e
a
26 37
d`
61
c
85
g`
c分裂,7上插
e`
(4) 继续插入关键字 7：首先查找插入位置 (3之后 )；
进行插入，并检查插入后结点关键字数目大于 2。
53 90
bt
45 70
24 30
3 7 12 50 100
b
d f g h
e
a
26 37
d`
61
c
85
g`
e`
53 90
第九章 查找第 68页
B- 树的插入
bt
45 70
7 24 30
3 50 100
b
d f g h
e
a
26 37
d`
61
c
85
g`
e`
c分裂,7上插
53 90
12
c`
bt
45 7024 45 70
3 50 100
b
d f g h
e
a
26 37
d`
61
c
85
g`
e`
b分裂,24上插
53 90
12
c`
7 30
a分裂,45上插第九章 查找第 69页
B- 树的插入
a分裂,45上插
24 45 70
3 50 100
b
d f g h
e
26 37
d`
61
c
85
g`
e`
53 90
12
c`
7 30
bt
a
bt
45
70
a a`
第九章 查找第 70页
Status InsertBtree( BTree &t,KeyType K,Btree q,int i )
/*在以 t 所指 m 阶 B- 树上插入等于 K 的关键字，若树为空则插入根结点，否则插入在 q->key[i] 和 q->key[i+1] 之间 */
(x,ap) = (K,NULL ); finished = false;
while( q≠ NULL && !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 = ; split(q,ap); //生成新结点，
且将 q->key[s+1..m] 和 q->ptr[s..m] 移至结点 ap中
x = q->key[s]; //组成一对新的插入信息
q = q->parent;
if( q≠NULL ) i = Search( q,x )
//继续在双亲结点 q中查找 x 的插入位置
}; //else
}; //while
在 B- 树一插入关键字的算法描述第九章 查找第 71页续上页
if( !finished )
Newroot(t,t,x,ap) //生成新的含信息 (t,x,ap)的根 t，其中 t 和 ap
为指向其子树根的指针
}// 算法 9.8
在 B- 树一插入关键字的算法描述第九章 查找第 72页删除操作过程与插入操作相类似，但要稍复杂些。若欲在 B-
树上删除一个关键字，则首先应找到该关键字所在结点，并从中删除之。若该结点为最下层的非终端结点，且其中的关键字数目不小于,则删除完成；
B- 树的删除否则要进行“合并”结点的操作。这里可能发生多种情况，
甚至合并会一直往上蔓延，传到根结点。更有甚者，还有可能发生根结点与它两个孩子进行合并，形成新的根结点，从而使整棵
B- 树减少了一层。
可分三种情况加以讨论：
（ 1）被删结点的关键字数目不小于
（ 2）被删结点的关键字数目等于,而其左或右兄弟结点中关键字数目不小于
（ 3）被删结点和其左或右兄弟结点中关键字数目等于第九章 查找第 73页
B- 树的删除可分三种情况加以讨论：
（ 1）被删结点的关键字数目不小于
（ 2）被删结点的关键字数目等于,而其右 (或左 )兄弟结点中关键字数目不小于删除关键字 Ki和相应指针 Ai
则需将其右兄弟结点中的最小（或最大）的关键字上移至双亲结点，
而将双亲结点中小于该上移关键字的关键字下移至被删关键字所在结点。如删除以下关键字 50
45
24 53 90
3 12 61 7037 50 100
b
d f g h
e
bta
c
70
53 61 9061 90
53
第九章 查找第 74页
B- 树的删除
（ 3）被删结点和其左或右兄弟结点中关键字数目等于不妨设右兄弟结点存在，且由双亲结点中的 Ai指针所指，则在删除关键字后，把剩余的关键字和指针，加上双亲结点中的关键字
Ki一起，合并至于 Ai指针所指兄弟结点中。
45
24
3 12 37 100
b
d f g h
e
bta
c
70
61 90
53
例如：删除关键字 53
第九章 查找第 75页
B+ 树
B+ 树是 B- 树的一种变型树。
一棵 m 阶的 B+ 树和 m 阶的 B- 树的差异在于
(1) 有 n 棵子树的结点中含有 n 个关键字 (n≤m)； {B- 树为
n-1 个 }
(2) 所有的叶结点包含了全部关键字的信息以及指向包含这些关键字的信息以及指向包含这些关键字记录的指针，叶结点本身依关键字由小到大顺序链接，从而既可从根开始随机查找，又可从叶结点顺序查找；
(3) 所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。
示例 8 下图为一棵 3阶的 B+ 树
59 97
72 97
63 7251 5910 15
15 44 59
21 37 44 85 91 97
root
sqt
图 9.18 一棵 3阶的 B+ 树第九章 查找第 76页说明：
(1) B+ 树与 B- 树的相同之处在于
a,根结点（非叶）最少有两棵子树
b,所有非终端结点（除根外）至少有 棵子树；
c,叶结点均在同一层次
(2) B+ 树的查找、插入、删除等操作与 B- 树类似。需强调的是,B+ 树查找时，若非终端结点上的关键字等于给定值时，并不终止，而是继续向下直到叶结点。因此，对 B+ 树，不管查找成功与否，每次查找都是走上了一条从根到叶结点的路径；
(3) 通常在 B+ 树上有两个头指针，一个指向根结点。因此，可以对 B+ 树进行两种查找操作。
B+ 树第九章 查找第 77页哈希表（散列表）
前面所介绍的查找方法是建立在“比较”的基础之上进行的，目标都是尽量减少“比较”的次数。
更希望不经过任何比较，一次存取就能得到所查记录。
哈希函数、哈希表
—— 提出了哈希表。思想：
通过在关键字和它的记录存贮位置之间建立一个确定的对应关系 f,使每个关键字和结构中一个唯一的有效位置相对应。 因而在查找时，只要根据这个对应关系 f 找到给定值 k 的映象 f (k)，
若结构中存在关键字和 k 相等的记录，则必定在 f(k) 的存贮位置上。
这个对应关系 f为 哈希函数,根据这种思想建立的表称为哈希表 。
第九章 查找第 78页通常对于一个给定的关键字集合,设计一个函数 。这个函数将关键字映射到 M个连续的整数集合中,且把这些整数解释成向量 V元素的标号，这个向量称为关键字集合的 Hash向量，向量的长为 M。
哈希函数、哈希表例如 假设每个标记符由 2个字母构成，并将标识符视为关键字，
则这种关键字共有 26× 26=676个，若接收这些关键字就会要
M=676个的存贮向量，按字典序把 26个字母赋予代码 1~26，
则编码为,
aa,ab,…,az,ba,…,bz,…,zz （标识符）
1,2,…,26,27,…,52,…,676 （编码）
2121 )1(26)( LLLLH显然可定义函数此函数可将标识映射到一个长为 676的向量中。
第九章 查找第 79页哈希函数、哈希表但在实际应用中，程序一般不会把所有两上字母组合的词都用作标识符（关键字），因此这样做虽能唯一确定标识符位置，
却浪费的空间 。若每个标识符（关键字）全由不多于 5个字母组成，
则有,265＋ 264＋ 263＋ 262＋ 26=12356630 种组合，这就是说要构造能容纳这么大的符号表（ Hash表），这是无法忍受的，
通常 Hash向量长度总是有限的,如果放弃上述一一对应的形式，并放弃不同的关键字一定要映射到存贮向量的不同位置上，则很容易找到能够把变化范围很广的关键字，映射到存贮向量的合适位置的一个函数。
所以我们设计的哈希函数应是一个 压缩映象 。
第九章 查找第 80页哈希函数、哈希表当几个关键字映射到存贮向量的同一位置时,就出现了 冲突 （ Collision）,即 k1≠k2,但 f(k1)=f(k2),k1与 k2
互为 同义词 。
所以建造哈希表时，应：
① 选择一个好的哈希函数，尽量减少冲突的发生。
② 因冲突一般是难免的，应设定一种处理冲突的方法。
第九章 查找第 81页哈希函数的构造方法判定 Hash函数好坏的标准，主要有两条：
① 随机性好指 Hash函数应当尽可能均匀地把关键字映射到 Hash向量的元素中；
哈希表（散列表）?
② 尽可能避免冲突指尽量使得关键字不共享 Hash向量同一元素,显然,随机分布越好,冲突的可能性也越小 。
常用的构造 Hash函数的方法有：
1,直接定址法取关键字或关键字的某些 线性值 为 Hash地址，即 H(key)=key或
H(key)=a?key+b 其中 a和 b为常数。
这种方法所得地址集合与关键字集合的大小相同，因此不会发生冲突。但实际很少采用。
第九章 查找第 82页哈希函数的构造方法
2,数字分析法假设关键字以 r为基的数,并且 Hash表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址 。
选取若干位的原则是使得到的哈希地址尽量避免产生冲突，前提是对关键字作深入分析。一般要求选择的若干位应具有比较好的随机性，这样可以减少冲突发生的可能。
例如：对英文单词进行散列，就不应当按第一个字符的值进行散列。
3,平方取中法取关键字平方后中间几位为哈希地址，这是一种常用的方法 。
通常在选 Hash函数时不一定知道关键字的全部情况，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，因此使随机分布的关键字得到的 Hash地址也是随机的,取的位数由表长决定。一般若表长为 2r,则取中间 r位。
第九章 查找第 83页哈希函数的构造方法
4,折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为 Hash地址，
该方法称折叠法（ folding）。
当关键字位数很多，而且每一位上数字分布大致均匀时，可以采用折叠法回到哈希地址。
如图书编号，身份证号码等。
5,除留余数法取关键字被某个不大于哈希表表长 m的数除后的余数作为地址。
H(key) = key MOD p ( p <= m )
次方法最简单，最常用。
第九章 查找第 84页哈希函数的构造方法总之,构造 Hash函数的方法可以很多,要考虑的因素有：
计算 Hash函数所需时间
关键字长度及分布情况
Hash的表的大小
记录的查找频率
6,随机数法选择一个随机函数，取关键字的随机函数值作为 Hash地址。
H( key ) = random( key )
此方法在关键字长度不等时可采用。
第九章 查找第 85页冲突处理由于冲突 不可避免,因此如何处理冲突是 Hash查找中的关键之一,假定 Hash向量的地址为 0~m－ 1（ 长度为 m）,冲突 是指由关键字得到的 Hash地址为 j(0≤j≤m－ 1)的位置上已存在记录,
则,处理冲突,就是为该关键字的记录找到另一个,空,的
Hash地址 。 在处理冲突的过程中可能得到一个地址序列 。 即在处理 Hash地址的冲突时,若得到的另一个哈希地址仍然发生冲突,则再求下一个地址,若仍然冲突,再求,依此类推,直到不发生冲突为止,则为记录在 Hash向量中的地址 。
冲突解决方法分为两类,闭散列方法和开散列方法哈希表（散列表）?
闭散列方法把所有记录直接存储在散列表中。 每个记录 i有一个基位置是 h(ki)，如果要插入一个记录 R，而另一个记录已经占据了 R位置，那么就把 R存储在散列表其他位置上，这个位置由冲突处理方法计算而得。
开散列方法并不把记录直接存储在散列表中，散列表中存储的是指向各个链表的表头指针。记录便存储在这些链表的结点中。
第九章 查找第 86页
)2(,,,2,2,1,1 222222 mkkkd i
冲突处理闭散列冲突处理
1,开放地址法发生冲突时,采用下列公式其中,H(key)为哈希函数； m为步长,为增量序列
1),称为线性探测再散列；
2),称二次探测再散列
3) di =伪随机数序列,称伪随机探测再散列上述方法实际上是根据 di找,下一个空位,
)1(,,2,1))(( mkkjmM O Ddk eyHH ii?
1,,2,1 md i?
第九章 查找第 87页冲突处理闭散列冲突处理,1,开放地址法例如 1,在长度为 11的 Hash表中已填关键字为 17,60,29
现在加入关键字为 38的记录，显然，产生冲突
11 )( M ODkeykeyH?
60 17 29
1 2 3 4 5 6 7 8 9 100
511 38)38( M ODH
(1) 采用线性探测再散列方法处理冲突：
得到下一个地址为 6，仍冲突，再求为 7仍冲突，直到 Hash地址为 8
时出现“空”位，插入记录，得到
60 17 29
1 2 3 4 5 6 7 8 9 100
38
优点,只要散列表不空，总能找到位置插入记录；
缺点,容易产生“二次聚集” —— 非同义词之间地址冲突。
第九章 查找第 88页冲突处理闭散列冲突处理
2、再散列当出现冲突时，采用不同的 Hash函数计算另一个 Hash函数地址，直到冲突不再发生。
即这种方法不易产生“聚焦”，但增加了计算时间。
缺点,增加了计算优点,不容易产生“二次聚集”；
kikeyRHH ii,,2,1)(
3,建立公共溢出区假设 Hash向量值域为 [0m－ 1]，则称向量 Hashtable[0m－ 1]为基本表，每个分量存一个记录，另建立向量 Overtable[0v]为溢出表。一旦发生冲突，都放入溢出表。
第九章 查找第 89页冲突处理开散列 冲突处理 —— 链地址法散列表中存储的是指向各个链表的表头指针。记录便存储在这些链表的结点中。 将所有关键字为同义词的记录存贮在同一线性关键表中。
例如，已知一组关键字为 (19,14,23,01,68,20,84,27,55,11,10,29)，则按和链地址法处理冲突得到的 Hash表如下所示：
13 )( M ODk e yk e yH?
0 ∧
1
2 ∧
3
4 ∧
5 ∧
6
7
8 ∧
9 ∧
10
11
12 ∧
01 14 27 79 ∧
55 68 ∧
19 84 ∧
10 23 ∧
11 ∧
20 ∧
第九章 查找第 90页
Hash表的查找及分析
Hash表的查找与其构造过程类似。算法思想如下：
哈希表（散列表）?
给定 K值,根据 Hash函数求得 Hash地址,若表中此位置上没有记录,则查找不成功,进行插入操作；
否则 比较 关键字,若与给定值 k相等,则查找成功；
否则根据处理冲突的方法找,下一位置,地址,直至哈希表中某个位置为,空,或者表中所填记录的关键字等于给定值为止 。
Hash表的初衷是通过“计算”，不用“比较”直接查找记录。
但从上述思想可知，只要创建表时存在“冲突”，查找时就难免要多次“比较”。
第九章 查找第 91页
Hash表的查找及分析下列算法为以开放定址法处理冲突的 Hash查找过程 （ 不考虑插入 ）
Status HashSearch( HashTable H,KeyType K,int &p,int &c )
{
p = Hash(K); //计算 hash地址
while( H.elem[p].key != NULLKEY &&
!EQ( K,H.elem[p].key ) //有记录且关键字不等
collision( p,++c );
if( EQ( K,H.elem[p].key )
return OK;
return Faliure
}
数据结构,int hashsize[] = {997,…}; //Hash容量表
typedef struct {
ElemType elem[]; //存储元素，动态分配
int count; //元素个数
int sizeindex; //容量大小
} HashTable;
第九章 查找第 92页
Hash表的查找及分析由查找过程可知：
1)显然 Hash其在关键字与记录的存贮位置之间建立了直接映象,
但由于冲突的产生,使得其查找过程仍然是一个给定值 k与关键字的比较过程 。 因此,仍需以平均查找长度作为 Hash表查找效率的尺度；
2)D.E.Knuth在程序设计技巧第三卷,Data Sorting and Data
Searching”中提出； 为了查找一个关键字或插入一个新关键字,
其平均查找长度取决于负载因子?。
M
N
H a s h
H a s h
表长度表中已填入记录数?
标志 Hash表的装满程度，一般情况下,?越小，发生的冲突可能性越小，反之则反。
第九章 查找第 93页
Hash表的查找及分析以开放定址冲突处理法的伪随机探测再散列为例,推导平均查找长度：
发现基位置被占的可能为,? = N/M
)1),,,(1(
)1),,,(1(
iMMM
iNNN
发现第 i次冲突的可能为,
发现下一位置被占的可能为,
)1(
)1(
MM
NN
若 N和 M>>1,那么可简化为,
i
M
N?
平均查找长度为,
)1/(1
1
1
i
M
N
i
第九章 查找第 94页
Hash表的查找及分析可以证明，不同的冲突处理方法其平均查找长度为,
线性探测再数列,
成功查找,?
1
1
1
2
1
l
A S L 不成功查找,
2
1
1
1
2
1
随机探测再数列，二次再数列和再哈希；
成功查找,
1ln
2
1
r
A S L
不成功查找,
1
1
链 地址法,
成功查找：
2
1
c
A S L
不成功查找：
e
第九章 查找第 95页删除当从散列表中删除记录的时候，有两点需要重点考虑：
哈希表（散列表）?
1,删除一个记录一定不能影响后面的检索 。
即删除之后，查找过程必须仍然能够通过新清空的位置。因此，删除过程不能简单地清空，这样会隔离探查序列后面的记录。
2,删除一个记录后,空出的位置能再利用一般的方法是,在删除记录的位置上设置一个特殊标记 —— 墓碑 。
第九章 查找第 96页内容提要
掌握静态查找：顺序查找、二分法查找、分块查找的概念和方法，熟悉平均查找长度的计算；
了解二叉排序树、平衡二叉树,B-树的动态查找过程 ；
理解哈希表的散列思想、冲突处理及查找过程。
掌握各种查找方法的应用场合。
第九章 查找 小结
