页数：148页文件大小：1.06 MB来源： 数据结构ppt课件
本课件系统讲解各类查找方法，从无序表与有序表的顺序查找讲起，介绍对半查找、一致对半查找、斐波那契查找与插值查找及二叉判定树分析，进而讨论二叉查找树的查找、插入与删除、最优二叉查找树、高度平衡树的插入与调整，以及 B 树、B+ 树与散列函数的构造和冲突调节。
第八章查找
查找---即在某种数据结构中找出满足条件的结点。查找表：是由同一类型的数据元素构成的集合。查找结果：成功、失败。平均查找长度——查找一个结点所作的平均比较次数（衡量一个查找算法优劣的主要标准）。
查找算法的四个特征：内外有别：分为内查找和外查找。静态动态：静态查找时，表的内容不变；动态查找时，表中的内容不断地变化。原词变词：原词系指用原来的关键词，变词系指使用经过变换的关键词。数字文字：指进行比较的时候，是否用数字的性质。
一、线性表的查找8.1.1无序表的顺序查找8.1.2有序表的顺序查找8.2.1对半查找8.2.2一致对半查找8.2.3斐波那契查找8.2.4插值查找二、树形结构的查找三、散列
一、线性表的查找8.1.1无序表的顺序查找现实生活中顺序查找的例子很多。比如，在一个班级的名册中查找某个学生的名字。通常的做法是，顺序比较名册中的每个名字。这就是顺序查找。顺序查找的基本思想：从线性表的起始结点开始，逐个检查每个结点，或者找到关键词Ki=K，或者以i>n(i为表中记录的下标，n为线性表的元素个数)查找失败告终。
顺序查找很简单、明显，该方法是讨论查找问题的一个有用的起点，因为许多错综复杂的查找算法都是以它为基础的。
算法S(N，R，K.i)S1.[初始化]置i←1.S2.[比较关键词]如果K=Ki，则算法成功结束.S3.[推进i]置i←i+1.S4.[i≤N?]若i≤N，则返回步骤S2；
否则此算法以查找失败告终.▐
算法S(N，R，K.i)S1[初始化]i←1．S2[比较关键词]WHILE((i≤N)&&(K≠Ki))DOi←i+1.▌
在表中引入一个“虚拟”记录RN+1，能提高算法S的效率。算法Q(N，R，K.i)Q1.[初始化]置i←1，并置KN+1←K.Q2.[比较关键词]如果K=Ki，则转到步骤Q4.Q3.[推进i]置i←i+1，并返回步骤Q2.Q4.[i≤N?]如果i≤N，则算法成功结束；
否则以查找失败告终.//此时有i=N+1▐
算法Q（N，R，K．i）Q1[初始化]i←1．KN+1←K．Q2[比较关键词]WHILEK≠KiDOi←i+1.▐从算法S到算法Q利用了一个重要的“加速原理”:当算法的一个内循环要测试两个或多个条件时，应力图将其减少成一个条件。
算法Q大约比算法S节省百分之二十的运行时间。
10●查找成功的平均查找长度：●查找失败的查找长度：N+1●顺序查找的时间复杂度：O(N)
算法Q"(N，R，K.i)Q"1. [初始化]置i←−1 .KN+1←K.Q"2. [前进两步]置i←i+2 .Q"3. [Ki:K]若Ki=K，则转到步骤Q"5 .Q"4. [Ki+1:K]若Ki+1≠K，则返回步骤Q"2；否则置i←i+1 .
算法S、算法Q、算法Q"说明：提高一个算法（或程序）之效率很可能有很大潜力。顺序查找优缺点:优点:算法简单，且适用面广。缺点:平均查找长度较大，N很大时查找效率低。
自组织表表中各元素被查找的概率并不一定相同。把经常出现的元素（它的发生概率较大）自动向表的前端移动，把不经常出现的元素自动向表的后端移动，并称以该方式组织的表为自组织表。MOVE-AHEAD-ONEMOVE-TO-FRONT
一、线性表的查找8.1.1无序表的顺序查找8.1.2有序表的顺序查找8.2.1对半查找8.2.2一致对半查找8.2.3斐波那契查找8.2.4插值查找
158.1.2有序表的顺序查找算法T（R，n，K．i）T1 [初始化]i←1．Kn+1←+∞ .T2 [顺序与表中各元素比较]WHILEK＞KiDOi←i+1.T3 [若未找到，设i←n+1 ]IFK≠KiTHENi←n+1. ▐
算法成功结束时1≤i≤n，否则i=n+1．与算法Q相比较，对于成功的查找，算法T的期望复杂性为(n+1)/2，与算法Q的期望复杂性相同；而对于不成功的查找算法T的期望复杂性为(n+1)/2，而算法Q为n+1，算法T比算法Q大约快一倍。先将文件排序，再查找，是一个快速的查找方法。但如果只需对表查找一次，则进行顺序查找比对这个表进行完整排序要快；
如果要在同一个文件中不断进行查找，那么将表按序排列再查找是个很好的方法。
有序表（K1<K2<…<KN）的查找，比较K和Ki后，有:K<Ki，[不必考虑子表Ri，Ri+1，…，RN]K=Ki，[查找成功结束]K>Ki，[不必考虑子表R1，R2，…，Ri]使用不同的规则确定i，可得到不同的查找方法。算法T的改进方法：对半查找、一致对半查找、斐波那契查找和插值查找等。
188.1线性表的查找8.1.1无序表的顺序查找8.1.2有序表的顺序查找8.2.1对半查找8.2.2一致对半查找8.2.3斐波那契查找8.2.4插值查找
198.2.1对半（折半，二分）查找1、算法思想：K与待查表中间记录的关键词K⌊N/2⌋比较，其结果有三：①K＜K⌊N/2⌋，②K=K⌊N/2⌋，③K＞K⌊N/2⌋由情况②知查找成功结束，由情况①和③能确定下一次应到表的哪一半中去查找，即将查找范围缩小一半；并对确定的那一半重复上述过程，直至找到所查记录或确定该记录不在表中。
[例]假定有序表A中10个元素的关键词序列：12，23，26，37，54，60，68，75，82，96当给定值分别为96和58时进行二分查找。
202、对半查找算法描述算法B(N，R，K.i)B1. [初始化]置s←1 .e←N.B2. [取中点]如果e<s，则该算法以失败告终；
否则，置i←⌊(s+e) /2⌋。B3. [比较]如果K<Ki，则转步骤B4；如果K>Ki，则转步骤B5；如果K=Ki，则算法成功结束。B4. [调整e]置e←i−1，并返回B2 .B5. [调整s]置s←i+1，并返回B2 . ▐
查找k=96时二分查找过程(4次比较成功）1 2 3 4 5 6 7 8 91012 23 26 37 54 60 68 75 82 96s=1e=10e=1012 23 26 375460 68 75 82 96s=1i=5e=1012 23 26 37 54 60 687582 96s=6i=812 23 26 37 54 60 68 758296s=e=10i=10e=1012 23 26 37 54 60 68 758296s=9i=9
查找k=58时二分查找过程(3次比较失败）1 2 3 4 5 6 7 8 9 1012 23 26 37 54 60 68 75 82 96e=1012 23 26 375460 68 75 82 96s=1i=5e=1012 23 26 37 54 60 687582 96s=6i=812 23 26 37 54 60 68 75 82 96s=6e=512 23 26 37 546068 75 82 96s=6e=7i=6
233、对半查找算法分析每个圆圈结点表示关键词比较K:Ki45281369710﹤﹥54758296231226603768﹤﹤﹤﹤﹤﹥﹥﹥﹥﹥﹥﹥﹥﹥﹤﹤﹤﹤==========
二叉判定树二叉判定树，T（s，e）的递归定义如下：(1)当e-s+1≤0时，T（s，e）为空树；(2)当e-s+1>0时，二叉判定树的根结点是有序表中序号为⌊(e+s)/2⌋的记录，根结点的左子树是与有序表Rs，Rs+1，…，R⌊(e+s)/2⌋-1相对应的二叉判定树，根结点的右子树是与有序表R⌊(e+s)/2⌋+1，R⌊(e+s)/2⌋+2，…，Re相对应的二叉判定树。
T（1，10）的二叉判定树：搜索K=964528136971054758296231226603768
264528136971054758296231226603768T（1，10）的二叉判定树：搜索K=58
T(1, 10)查找成功的平均查找长度4528136971054758296231226603768ASLSUCC＝(1*1+2*2+3*4+4*3)/10＝29/10＝2.9
查找失败的平均查找长度：ASLUNSUCC＝En/(n+1)＝(3*5+4*6)/11＝39/114528136971054758296231226603768
引理8.1设算法B对N个记录的成功查找是等概率的，且对不成功的查找也是等概率的，则成功查找的关键词比较的平均次数SN=1+IN/N，不成功查找的关键词比较的平均次数UN=EN/(N+1)，其中IN，EN为T（1,N）的内、外通路长度.引理8.2对半查找二叉判定树T（s,e）的高度是⌈log2(e-s+2)⌉.引理8.3设T(1,N)是N个内结点的二叉判定树，不考虑外结点T(1,N)之高度为k，T(1,N)之外结点均属于k或k+1层.定理8.1算法B在最坏情况下的关键词比较次数为⌈log2(N＋1)⌉，且期望复杂性等于O(log2N).
304、二分查找总结:优点:查找效率为O(log2N)//比顺序查找高缺点:只适用于有序表，且限于顺序存储结构，对线性链表无法进行二分查找。
318.1线性表的查找8.1.1无序表的顺序查找8.1.2有序表的顺序查找8.2.1对半查找8.2.2一致对半查找8.2.3斐波那契查找8.2.4插值查找
当N=10时一株“一致”的二叉判定树5800212243465687881379210910δ=1δ=3δ=18.2.2一致对半查找将对半查找的指针数量由三个(s，i和e)减少为两个。i=⌈N/ 2⌉，m=⌊N/ 2⌋=5i=i+/-⌈m/ 2⌉，m=⌊m/ 2⌋=2i=i+/-⌈m/ 2⌉，m=⌊m/ 2⌋=1i=i+/-⌈m/ 2⌉，m=0
一致对半查找算法算法U(N，R，K.i)U1. [初始化]置i←⌈N/ 2⌉，m←⌊N/ 2⌋.U2. [比较]若K<Ki，转到U3；
若K>Ki，转到U4；若K=Ki，则算法成功结束。U3. [减小i]若m=0，则算法以失败告终；否则置i←i−⌈m/ 2⌉；然后置m←⌊m/ 2⌋并返回U2 .U4. [增大i]若m= 0，则算法以失败告终；否则置i←i+⌈m/ 2⌉；然后置m←⌊m/ 2⌋并返回U2 . ▐
算法U之所以被称为是一致的，是因为，在层l上的一个结点的编号与在层l-1上其父结点的编号之差的绝对值，对于层l上的所有结点均有一致的常数δ.例如，上图中，对第1层均有一致的δ=3，对第2层均有一致的δ=1，对第3层均有一致的δ=1.当查找失败时，U可能在结束前作一次冗余的比较，如图中阴影结点所示。
在算法U中，每次用来找中点i的m的序列如下：中点i序列如下：于是算法U又可以改进：在运行期间，不去计算m及i值，而是使用一张辅助表：
算法C (N，R，K.i)C1. [初始化]置i←DELTA[1] .j←2 .C2. [比较]若K<Ki,则转C3；若K>Ki,则转C4；若K=Ki，则算法成功结束.C3. [减小i]若DELTA [j]=0，则算法以失败告终；
否则置i←i−DELTA [j] .j←j+1，并转C2 .C4. [增大i]若DELTA [j]=0，则此算法以失败告终；否则，置i←i+DELTA [j] .j←j+1，并转C2▐
一致对半查找算法(算法C)的时间复杂度分析：成功的查找：算法C对应的二叉判定树与算法B对应的二叉判定树有相同的内路径长，所以平均比较次数与算法B一样。不成功的查找：算法C总是恰好进行⌊log2N⌋+1次比较，比算法B的⌈log2(N＋1)⌉比较次数多。算法C中的算术运算仅包含加减法，且在算法运行期间未计算诸m之值，而是用一张辅助表来代替，从而明显提高了速度。
算法C的时间花费不足算法B的二分之一。
除了对“待查表”进行均匀划分之外，我们还有没有新的划分思路？就是说一定要对半划分吗？对半划分是最好的划分吗？回答是肯定的，确实存在对半划分的替代方案——斐波那契划分。这一替代方案是更可取的，因为它只包含加、减法，连除以2的除法都没有。
398.1线性表的查找8.1.1无序表的顺序查找8.1.2有序表的顺序查找8.2.1对半查找8.2.2一致对半查找8.2.3斐波那契查找8.2.4插值查找
408.2.3斐波那契查找Fibonacci序列：0，1，1，2，3，5，8，13，21，34，…F0=0，F1=1，Fj=Fj-1+Fj-2，j≥2斐波那契（Fibonacci）查找对半查找的替代，以Fibonacci序列的分划代替了对半查找的均匀分划。
假设有一个长度为Fk+1−1的文件，其记录下标[1，Fk+1−1]。记录Fk将文件分为三个部分：①左子文件[1，Fk−1]；②Fk；③右子文件[Fk+1，Fk+1−1]；其中，左、右子文件的大小分别为Fk−1，Fk−1−1，故左、右子文件还可继续进行上面的划分（黄金分割）过程。
k阶斐波那契树Tk的递归定义如下：⑴当k=0,1时，Tk为空树；⑵当k>1时，二叉判定树之根是有序表中序号为fk的记录，根结点的左子树是与有序表k阶斐波那契树有fk+1−1个内结点和fk+1个外结点.对应的二叉判定树，根为fk−1；根结点的右子树是与有序表对应的二叉判定树，是k−2阶且所有结点之编号都增加fk的斐波那契树Tk−2+fk,其根为fk+fk−2.
f2T1T0+f2101f3T2T1+f321012二阶斐波那契树T2三阶斐波那契树T3Fibonacci序列：0，1，1，2，3，5，8，13，21，34，…
f4T3T2+f4210123434四阶斐波那契树T4Fibonacci序列：0，1，1，2，3，5，8，13，21，34，…
阶斐波那契树，即N=12=f7−1 .9426234567891011120137511110128Fibonacci序列：0，1，1，2，3，5，8，13，21，34，…
算法F(N，R，K.i)F1.[初始化]置i←fk，p←fk−1，q←fk−2（p和q是两个相邻的斐波那契数，用于寻找下一次与K比较的点）.F2.[比较]若K<Ki，则转步骤F3；
若K>Ki，则转步骤F4；若K=Ki，则算法成功结束.F3.[i减值]若q=0（已到树叶），则算法以失败告终;否则置i←i−q，t←p，p←q，q←t−q，并返回F2.F4.[i增值]若p=1（已到树叶），则算法以失败告终;否则置i←i+q，p←p−q，q←q−p，并返回F2.▐
引理8.4设m≥3，Tm是m阶Fibonacci树形，则Tm的左子树形的高度等于右子树形的高度加1，且Tm的高度为m-1.引理8.5设n=Fm+1-1，则m阶Fibonacci树形的高度约等于1.44log2（n＋1）.定理8.2令n=Fm+1-1，则算法Fibonacci在最坏情况下的时间复杂性为O(log2n)，且期望复杂性亦为O(log2n).Fibonacci查找的算法分析
Fibonacci查找算法的效率算法C的平均运行时间大约是算法F的1.2倍，算法B的平均运行时间大约是算法F的2.5倍。最坏情况下，算法F比算法C稍稍慢一点。
小结若实现从有序表的顺序查找到对半查找算法B的“跳跃”,必需实现:①从只考虑K=Ki和K≠Ki等两种情况到考虑K=Ki,K>Ki和K<Ki等三种情况;②从每次比较下一个关键词到每次比较被查找的子文件之中点。若实现从算法B到一致对半查找算法U的“跳跃”,需实现一个思想转弯,即从使用s、e、i等3个指针到仅使用i和m两个指针（m←⌊m/2⌋，下次被查找子文件长度之半）；
若实现从算法U到一致对半查找算法C的“跳跃”,需想到用一张表存放诸m值(算法运行时,省去计算诸m的时间,用空间换时间);当对半查找算法之改进到了“山重水复疑无路”的时候，跳出对半二叉判定树的局限转而去探索新的二叉判定树― ―斐波那契二叉判定树，即斐波那契查找算法F .
508.1线性表的查找8.1.1无序表的顺序查找8.1.2有序表的顺序查找8.2.1对半查找8.2.2一致对半查找8.2.3斐波那契查找8.2.4插值查找
518.2.4插值查找——问题的提出前面讨论的几种查找算法是基于严格比较的，即假定我们对线性表中元素的分布一无所知（或称没有启发式信息）.然而实际中，很多查找问题所涉及的表满足某些统计的特点。例如在一本英汉字典中寻找单词“worst”，我们决不会仿照对半查找(或Fibonacci查找)那样，先查找字典中间的元素，然后查找字典四分之三处的元素等等.事实上，我们是在所期望的地址(在字典的很靠后的地方)附近开始查找的，这样的查找为插值查找.
插值查找基本思想假定表中记录的关键词K1<K2<…<Kn在(K0,Kn+1)区间上呈均匀分布.变元K给定，且K0<K<Kn+1，则由均匀分布的假定，我们可用线性插值来决定K的期望地址n(K-K0)/(Kn+1-K0).若Ks<K<Ke，则将在s+(e-s-1)(K-Ks)/(Ke-Ks)处测试，而接下来的过程类似于对半查找算法。
算法Interpolation(R，n.found)Ip1[初始化]s←0．e←n＋1．found←false.Ip2[插值与比较]WHILEe-s>1ANDNOT(found)DO(m←⌊s+(e-s-1)(K-Ks)/(Ke-Ks)⌋.IFK＜KmTHENe←m.IFK＞KmTHENs←m．IFK=KmTHENfound←true)．▐
一、线性表的查找二、树形结构的查找8.3二叉查找树8.4最优二叉查找树8.5高度平衡树8.7 B树及其变型三、散列
558.3.1二叉查找树的基本概念和性质由上节知道，一株隐含的二叉树结构有助于了解对半查找和斐波那契查找之特性。用一个显式的(explicit)二叉树结构，不但能对表进行有效查找，而且还能迅速插入和删除记录。定义8.1二叉查找树（又称为二叉搜索树、排序树）TB是一棵可为空的二叉树，若TB非空则其所有结点之关键词互异，且中根遍历TB形成按关键词递增序排列的结点序列。
定义:一棵二叉查找树是一棵可能为空的二叉树形，并且关键词各不相同。二叉查找树中的任一结点P，它的左子树中结点的关键词都小于KEY(P)，而右子树中结点的关键词都大于KEY(P)，并且结点P的左右子树也都是二叉查找树。
二叉查找树和对半查找的二叉判定树的联系与区别。OEAUIIEAUOIAEOUIAEOUIEAUO
571、二叉查找树的结点结构：LLINK和RLINK是链接字段，KEY为该结点的关键词。2、基本操作1）创建2）查找3）插入4）删除5）排序RLINKDATAKEYLLINK
581、二叉查找树的查找算法BST(T,K.found)BST1[由根结点开始]P←T．found←false．BST2[比较]WHILEP≠nullANDNOT(found)DOCASEDO（K<KEY（P）：P←LLINK（P）.K>KEY（P）：P←RLINK（P）.K=KEY（P）：found←true）▌
设表中元素的关键词K1<K2<…<Kn，则查找成功应该终止于Ri(内结点)，而查找失败应终止在n＋1个记录间隔(或者称外结点，即Ki<K<Ki+1的情形)。35612OEAUI
602、二叉查找树的创建如何建立一棵二叉查找树。[例]有一数据集合{53,78,65,17,87,09,81,45,23}给定各种查找情况发生的概率αi和βi，如何确定一棵最优(最小加权通路长度)的二叉查找树；(静态树)近似最优树。
613、二叉查找树的插入(动态树)35612OEAUI436712OEAUI5H446712OEAUI3K
设树形T是一棵二叉查找树，T中结点R1,R2,…,Rn相应的关键词满足K1<K2<…<Kn,且Ki<K<Ki+1,0≤i≤n(K0=-∞,Kn+1=+∞).那么插入新结点K的过程就是用代替第i+1个外结点的过程.K
算法T(root,K.p)T1.[初始化]置p←root.//指针p将沿树下移T2.[比较]如果K<key(p)，则转到T3；
如果K>key(p)，则转到T4；如果K=key(p)，则查找成功结束.
T3.[左移]如果llink(p)≠ ，则置p←llink(p)，并转回T2；否则转到T5.T4.[右移]如果rlink(p)≠ ，则置p←rlink(p)，并转回T2.T5.[插入树形中]置q←AVAIL.//q为新结点的地址置key(q)←K，llink(q)←rlink(q)← .若K<key(p)，则置llink(p)←q，否则置rlink(p)←q.置p←q，本算法成功结束▐
显然，算法T的查找执行时间与算法B同阶（对随机输入），即为O(log2N)
664、二叉查找树的删除假定指针q指向二叉查找树中待删除的结点，则删除q后的树仍为二叉查找树。删除q后，由q的中根后继或者中根前驱结点代替q，删除过程分三种情形:1)q无右儿子；2)q有右儿子r，但r无左儿子；3)q的右儿子r有左儿子。
二叉查找树的删除分三种情况加以讨论(删除q)：（1）rlink(q)= .
68372523751248608268961)q无右儿子，此时用q的左儿子代替q所指结点(例如删除23)。二叉查找树的删除（情况一）372575124860826896
二叉查找树的删除分三种情况加以讨论(删除q)：（2）rlink(q)≠ ，且llink(rlink(q) )=
70372523751248608268962)q有右儿子r，但r无左儿子，用以r为根的子树取代q；(例如删除75)二叉查找树的删除（情况二）372523124860826896
二叉查找树的删除分三种情况加以讨论(删除q)：（3）rlink(q)≠ ，且llink(rlink(q))≠ .
72372523751248608268963)q的右儿子r有左儿子，以该左儿子为根的子树的最左下结点s取代q，同时将s的父结点指向原s的右子树。(例如删除25)二叉查找树的删除（情况三）372375124860826896
算法D (q，a. )D1. [rlink(q)= ]t←q.若rlink(t)= ，则t←llink(t)，并转到步骤D4.// t指向取代q位置的结点D2. [llink(rlink(q))= ]r←rlink(t) .若llink(r)= ，则llink(r)←llink(q)，t←r，转D4 .D3. [llink(rlink(q))≠ ]s←llink(r).若llink(s)≠ ，则r←s并重复到llink(s)= 为止.置llink(s)←llink(t)，llink(r)←rlink(s)，rlink(s)←rlink(t)，t←s.D4. [接树与释放结点q]若llink(a)=q，则llink(a)←t；
否则rlink(a)←t.然后置AVAIL←q.
二叉查找树的简单分析由于算法D左右两边很不对称，有理由认为一连串的随机删除和插入操作将使树失去平衡，但事实上，删除操作不会使树退化。定理8.3（T.N.Hibbard，1962）通过算法D从一株随机二叉查找树中删除一个随机元素之后，得到的树仍是随机的。结论:在随机情况下，二叉查找树操作的平均时间为O(log2N)．但在特定情况下，会产生形同线性链表的退化的二叉查找树形，从而使最坏情况查找时间达O(N).
二、树形结构的查找8.3二叉查找树8.4最优二叉查找树8.5高度平衡树8.7 B树及其变型
静态树——给定各种查找情况发生的概率αi和βi，如何确定一棵最优(最小加权通路长度)的二叉查找树；动态树——建立最优二叉查找树；——对树动态调整，保证动态插入删除结点后，仍为最优。缺点：计算复杂度高，有时结点出现的频率无法精确统计。解决方案：构造近似最优或较优的二叉查找树。
二、树形结构的查找8.3二叉查找树8.4最优二叉查找树8.5平衡树8.7 B树及其变型
788.5.1高度平衡树定义8.2：一棵二叉查找树称为高度平衡二叉查找树（高度平衡树、平衡树），当且仅当或者由单一的外结点组成，或者由两个子树形Tl和Tr组成，且满足：(1)|h(Tl)–h(Tr)|≤1，其中h(T)表示树T的高度；(2)Tl和Tr都是高度平衡树.高度平衡树是最佳二叉查找树和任意二叉查找树的一种折中方案。
定义8.3设T为增长二叉树，q是T之内结点，qL和qR是q的左、右子树，hL和hR分别是qL和qR的高度，q的平衡系数（或曰平衡因子）BF(q)定义为hR−hL.高度平衡树的结点结构：B为平衡系数。Fibonacci判定树形是一棵高度平衡树，且每个结点（以该结点为根的二叉树的内结点数≥2）的平衡系数为−1。
BDATAKEYRLINKLLINK
RLINK(HEAD)树形总高度HEADB(ROOT)KEY(ROOT)RLINK(ROOT)LLINK(ROOT)ROOT
平衡树的定义表达了最优二叉树（所有外结点都在两个相邻的层上）和任意二叉树之间的折中。人们自然要问，一棵平衡树比最优树差多少。答案是，平衡树的查找路径长度决不会超过最优树的查找路径长度的45% .定理8.4(Adelson-Velsky和Landis)设T是一棵具有N个内结点的平衡树，T之高度h(T)由下式所限定log2(N+1)≤h(T)≤1.4404×log2(N+2)−0.3277 .
822、高度平衡树的插入操作平衡性将遭到破坏：–平衡系数为+1的结点，如果在它的右子树的外结点上插入新结点，使它的右子树变得更高–平衡系数为−1的结点，如果在它的左子树的叶结点上插入新结点，使它的左子树变得更高
83(a)情况1(b)情况2高度平衡树的调整+++αβBAhhh+1hh++−ABXh−1ha
情况1：“单一转动”结点B从A的右下侧左转到A的右上侧，原B之左子树形变成了A的右子树形，B的新左儿子是结点A.+++αβBAhhh+1插入前以A为根的子树高度为h+2，插入后变换前，其高度h+3．变换后，变成了以B为根的子树，其高度为h+2.
情况2：“双重转动”hh++−ABXh−1ha插入前以A为根的子树高度为h+2，插入后变换前，其高度h+3．变换后，变成了以X为根的子树，其高度为h+2.
hh++−ABXh−1haAh++++Xh−1ahBh以X为轴将B从X的右上侧右转到X的右下侧，记为（X，B），从而A的右儿子是X，X的右儿子是B，原X的右子树变成了新B的左子树；
h++A++Xh−1ahBh−AXhahBhh−1以X为轴心,把A从X的左上方转到X的左下侧,记为(A,X) ,使X的左儿子是A,右儿子是B,原X的左子树变成了A的右子树.
经过插入与调整后，以A为根的子树变成了一棵与插入前有同样高度的新树。原先以结点A为根的子树之外的所有内结点都与插入前有相同的平衡系数，是保持平衡的。插入新结点n后，若树失去平衡，应调整失去平衡的最小子树。为了找到失去平衡的最小子树，我们可以记录从根结点r到结点n的一条路径，在该路径上寻找从下向上的第一个平衡系数非零的结点A；
A确定后，重新平衡以A为根的子树形可。
高度平衡树的插入与调整算法(略)rf..A(+-)n
例：构造包含关键词{20，35，40，15，30，25}高度平衡树。
构造包含关键词{20，35，40，15，30，25}高度平衡树。
923、高度平衡树的删除操作高度平衡树的删除操作，被删除结点的祖先结点的平衡系数均有可能发生变化。算法将从根结点到被删除结点路径上的所有结点依次入栈，设指针son指向被删除结点，current是son的父结点，则按照如下的规则进行删除：1)如果B(current)=0,且son=LLINK(current),则B(current)←+l,否则B(current)←-1.并终止整个过程.
932)如果B(current)=+1且son=RLINK(current),或B(current)=-1且son=LLINK(current),则B(current)=0,且current的高度减1.此时令son←current,current←S,然后继续.3)如果B(current)=+1且son=LLINK(current)，则此时current的平衡系数等于+2，因此根据RLINK(current)的平衡系数来进行重新平衡操作，若调整后树高度不变，则算法终止；
若调整后树高度减1，则令son←current,current←S,然后继续.4)如果B(current)=-1且son=RLINK(current)，则此时所发生的情况正好是(3)所示情况的对称情形.
平衡树的删除操作–如果采用正确的方法，则删除问题可以在O(log2N)步骤内解决；–删除和插入之间的重要差别是：删除可能需要多达平均log2N次调整，而插入所需的调整不多于1次。
954、线性表的平衡树表示用平衡树来表达线性表，既可快速地插入（克服顺序分配的困难），又可对表实施随机存取（克服链接分配的困难）。在每一个结点P增加一个被称之为RANK的字段RANK(P)=P的左子树形的(内)结点数+1RANK域之值确定了结点的相对位置
RANK域之值确定了结点的相对位置若k=6，则所查找的结点为NODE(F)；若k<6，则向左查找；若k>6，则往右去检索如k=8，则NODE(H)便是所求，因RANK(H)=k−6=2.NODE(E)在中根次序下的位置是5，它等于RANK(D)+1；NODE(K)的位置（中序）是11，它等于RANK(F)+RANK(K)=6+5
RLINK(HEAD)树形总高度HEADRLINKLLINKB RANKDATA(KEY)ROOT
算法B(HEAD，k.)B1．[初始化]置M←k，P←RLINK(HEAD) .B2．[比较]若P= ，则算法以失败告终.若M<RANK(P)，则转到步骤B3 ；
若M>RANK(P)，则转到步骤B4 ；若M=RANK(P)，则本算法成功地结束.B3．[左移]置P←LLINK(P)并返回步骤B2 .B4．[右移]置M←M−RANK(P)，P←RLINK(P)并返回步骤B2 .▐
二、树形结构的查找8.3二叉查找树8.4最优二叉查找树8.5高度平衡树8.7 B树及其变型
1008.7 B树及其变形树前面介绍的树形查找方法，主要属于内查找方法，适用于被检索文件能完整地被放到计算机内存中的情形。如果文件很大，以至于计算机内存容纳不下时，则必须放在磁盘等外存储器上。当人们想从一个存放在磁盘上的大文件中查找某些信息时，则需要去研究一种新的查找方法—外查找。
1018.7.1多叉树
1021、基本概念1970年，拜尔(R. Bayer)和麦克瑞特(E. McCreight )提出一种新的外查找树，称为B树。这是一种多叉平衡树形，它在插入或删除操作中有简单的平衡算法。B树及它的一些改进形式已成为索引文件的有效结构，得到了广泛的应用。定义8.7一个m阶的B树满足下述条件：1.每个结点有≤m个儿子；
2.除根和叶之外的每个结点有≥⌈m/2⌉个儿子；3.根结点至少要有两个儿子（除非它本身又是一个叶结点）；4.具有k个儿子的非叶结点包含k−1个关键词；5.所有的叶结点都出现在同一层上，并且它们都不带有信息.8.7.2 B树
103233449031097137191011017023041047059067073083103109127149157167179197211227283353401241257269277307313331347367379389419431439499599677773829883919907937947967461467487509523547563571587607617631643653661691709727739751761797811823853859877一个7阶B树，其所有的叶都在第3层上叶不带有信息，可以认为它们是外部结点，实际上它们不在树中，所以指向叶的指针为空。
104031097137191011017023179197211227103109127149157167083073067059047041
在前面的7阶B树中，每个结点(除了根和叶)，有⌈7/2⌉到7个儿子，故可有3，4，5或6个关键词。根结点允许有1至6个关键词，根结点包含两个关键词。这个B树的所有叶子都在第3层上。应强调指出的是：①每个非叶结点中的关键词是按从左到右的递增顺序排列的；②叶子的总数比关键词总数多1；③①和②两点表明了B树是二叉查找树的一个自然推广。
很自然，我们对1阶和2阶B树毫无兴趣，这里只考虑m≥3的情况。阶为3的B树，也叫做2-3树。
一个包含j个关键词和j+1个指针的B树结点如图所示。结点之关键词满足K1<K2<…<Kj，指针Pi指向一个其所有关键词都在Ki和Ki+1之间的子树形。因此，在B树中进行查找是十分简单的。P0K1P1K2P2…Pj−1KjPjB-树的结点P
1072、查找假定结点P已从磁盘读到内存中，可选择适当的内查找方法。当j比较大时，可选择对半查找算法；当j较小时可采用顺序查找方法。设查找一个给定的变元k，若k在NODE(P)中，则查找成功。否则必是下述三种情形之一：1)Ki<k<Ki+1(1≤i<j)，则继续到结点NODE(Pi)中去查找.2)k>Kj，查找将转NODE(Pj)继续查找。
3)k<K1，查找将转NODE(P0)继续查找。如果指向下一个要查找的结点的指针Pi= ，则查找以失败告终，关键词为k的记录不在树中。
1083、插入（1）若在一个包含j<m−1个关键词的结点中插入一个新关键词，则插入过程将局限于该结点自身（把新关键词直接插入该结点中即可）。如在下图中插入关键词337，只须改变一个结点即可。347337331313307347331313307
插入（2）若把一个新关键词插入一个已包含m−1个(m为B树的阶)关键词的结点(结点已满)，则插入将造成此结点“分裂”。如插入关键词071。此时，把m个关键词分成个数相等的两组，第一组从左向右数，包含⌊m/2⌋个关键词，第二组从右向左数，包含⌊m/2⌋个关键词，剩下的中间那个关键词将被提升到上一层结点中，去开始新的插入。
“分裂”可能会向上传播，在极端情况下，分裂会一直波及到根结点，而这恰恰是B树长高的唯一方式。031097137191083073067059047041031097137191067041047059071073083
1104、删除先找到要删除的关键词Ki的位置，若它不在叶的上一层里，则要把删除Ki后的空位置用最接近Ki而又大于Ki的关键词K*来填充，同时从K*所在的结点中删除K*，这是因为在中间诸层的关键词还起指导向下查找的作用，故不能为空。例如删除353。347367379389307313331283353401379389307313331283367401
当删除关键词后，空位置已在B树之叶子的上一层结点中。要检查该结点目前包含的关键词个数是否小于⌈m/2⌉-1.(1)若不是，则直接删除空位置，即合并两个空指针。(2)若是，则要从相邻的兄弟结点中借关键词，最好使两个结点的大小一样（即包含相同数目的关键词）。如下图删除关键词379的情形。347367379389307313331283353401353367389307313331283347401
若相邻（同父）结点的关键词个数都等于⌈m/2⌉−1，则一个与分裂相反的过程—“合并”便发生了。所谓“合并”，即把两个兄弟结点的关键词连同在父结点中指向这两个结点的指针之间的关键词按递增顺序排列在一个新结点中。例如从上图中删去关键词431。若“合并”操作使上一层结点（父结点）所包含的关键词个数出现了<⌈m/2⌉−1的情况，则又造成了上一层结点或要借关键词或要进行“合并”操作。
“合并”可能会导致上一层发生“合并”，从而可能使“合并”不断向上传播，或许一直波及到根结点，从而有可能使整个B树减少一层。283353401419431439367379389283353439419401389379367
1135、讨论设有一个m阶B树，它包含N个关键词，它的N+1个叶子出现在第l层上。则：这意味着，当N=1999998且m=199时，l最多是3.就是说，在最坏的情况下，一次查找至多需要存取3个结点。因此，B树上的查找操作是很快的。
1148.7.3 B+树由于B树的结点代表一个辅存页或者是一个辅存块，从一个结点到另一个结点需要费时的页切换。所以最好尽可能地少访问结点。如果请求以升序访问B树中的结点，如用中序遍历，但对非末端结点，一次只能显示一个关键词，然后就要访问其他的页。因此，希望增强B树，能以比中序遍历快的方式顺序访问数据。
B+树提供了一个解决方案。
B+树是适应文件系统的需要而产生的一种B树的变形树，一棵m阶B+树须满足下列条件：1)每个分支结点至多有m棵子树；2)除根结点外，其它每个分支结点至少有⌈m/2⌉棵子树；3)根结点至少有两棵子树，至多有m棵子树；4)有n棵子树的结点有n个关键词；5)所有的叶子结点包含全部关键词及指向相应记录的指针，而且叶子结点按关键词自小而大的顺序链接；
6)所有分支结点（可看成是索引的索引）中仅包含它的各个子结点（下级索引的索引块）中最大关键词及指向子结点的指针。
一棵2阶B+树70954070951020204091953540517044518591657093955101120403035444751616570808591929395
一棵m阶B+树和一棵m阶B树的差异在于:⑴B+树中，有n棵子树的结点中含有n个关键词；⑵B+树中，每个结点（根结点和叶结点除外）中的关键词个数n的取值范围是⌈m/2⌉≤n≤m，根结点关键词个数n的取值范围是2≤n≤m；而B树中，它们的取值范围分别是⌈m/2⌉−1≤n≤m−1和1≤n≤m−1；⑶B+树中，所有的叶结点中包含了全部关键词，即其它非叶结点中的关键词都包含在叶结点中；
而在B树中，叶子结点包含的关键词与其它结点包含的关键词是不重复的；⑷B+树中，非叶结点仅起索引作用，即结点中每个索引项只含有对应子树的最大关键词和指向该子树的指针，不含有该关键词对应记录的存储地址。而B树中，每个关键词对应一个记录的存储地址；⑸通常在B+树上有两个头指针，一个指向根结点，另一个指向最小关键词的叶子结点，所有叶子结点链接成一个不定长的线性链表。
B+树进行两种查找运算：一种是从最小关键词开始进行顺序查找，另一种是从根结点开始进行随机查找。在B+树上进行随机查找、插入和删除操作的过程基本上与B树类似。只是在查找时，如果非叶结点上的关键词等于给定值，并不终止，而是继续向下直到叶结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶结点的路径。
一、线性表的查找二、树形结构的查找三、散列(杂凑)8.9.1散列表(杂凑表)的定义8.9.2散列函数的构造8.9.3冲突调解
目前，我们所考虑的查找方法在找到以K为关键词的记录之前，都要检查若干数目的关键词.杂凑技术则完全免去了上述方法所作的搜索，由给定变元K直接计算出函数值f(K)，而f(K)即为包含K的记录所在的地址.杂凑函数满足的条件：1.便于快速计算；2.极少出现冲突(函数是均匀的).
杂凑表(散列表)：根据给定的杂凑函数Hash(Key)和处理冲突的方法，将一组关键词映射到一个有限的连续的地址区间上，并以关键词在地址集上的“映像”作为该记录在表中的存储位置，这种表称为杂凑表或者散列表。这种映射过程称为杂凑，所得到的存储位置称为杂凑地址或者散列地址。
122●杂凑技术避免了关键词的比较●杂凑技术的关键：如何构造均匀的杂凑函数解决冲突的方法
一、线性表的查找二、树形结构的查找三、散列(杂凑)8.9.1散列表(杂凑表)的定义8.9.2散列函数的构造8.9.3冲突调解
1242、杂凑函数杂凑函数h与组成关键词K的符号有关.如果K是从关键词集合中随机选取的一个，则我们希望h(K)以同等概率取区间[0，M-1]中的每一个值.如果一个杂凑函数满足这一性质，则被称为是均匀的.为了方便，我们把关键词表示为二进制代码.例如，可把每个英文字母看成一个5位二进制数，即令A=00001，B=00010，C=00011，…，Z=11010.从而每个单词是一个连续的二进制串，比如THE表示为串h(THE)=101000100000101T H E
构造杂凑函数方法1.抽取法2.压缩法3.除法杂凑函数4.乘法杂凑函数
构造杂凑函数方法1.抽取法从关键词相对的二进制串中抽取几个分散的代码，然后合并这几个代码，形成一个地址.[例]抽取法抽取第三位和最后两位作为杂凑地址，则h(THE)=101000100000101=101T H E
1272.压缩法把关键词的二进制串分割成若干个子串，然后按某种方式把这些子串合并，形成该关键词的地址.例：h(THE)=10100XOR01000XOR00101=11001＝2510异或运算满足交换律，即有同样字母的单词有相同的杂凑地址。h(STEAL)=h(STALE)=h(TALES)=h(LEAST)
1283.除法杂凑函数h(K)=KmodM，其中K为记录的关键词，M为杂凑表容量。例：h(THE)=101000100000101mod31=2074110mod31=2注意合理选择M值，M一般为素数。
1294.乘法杂凑函数给定一个实数θ，0＜θ＜1，则按如下的方式给出一个杂凑函数.H(K)=⌊M(Kθmod1)⌋一般来说，当θ≈0.6180339887或θ=0.3819660113时，杂凑函数能均匀地分布在[0，M-1]上.
一、线性表的查找二、树形结构的查找三、散列(杂凑)8.9.1散列表(杂凑表)的定义8.9.2散列函数的构造8.9.3冲突调解
1313、冲突调节冲突调节方法1.拉链法2.线性探查3.双重杂凑
1321.拉链法假定表T包含M个散列地址T[0]，T[l]，…，T[M-l]，拉链就是令散列地址等于i的记录组成一个链表，且指针T[i]是该单链表的头指针.
为了节约存储空间，改进的方法是将每个T[i]分成两个域，一个域存放记录，另一个域为LINK，存放指针，指向具有相同杂凑地址的下一个记录。当插入关键词K时，如若发现T[h(K)]处已包含别的记录，则沿LINK一直找下去，直到一个表地址的LINK值为空．然后找到一个空的表地址T[free]，把K存储在T[free]处，并置最后一个空LINK域的值为free．寻找空地址可由T[M-l]开始，向T[0]方向搜索．
134-18-110987654321045720-16-11-117-137-12-1231066-1关键词序列为：20, 17, 2, 23,45, 66, 6, 37, 1杂凑函数：h(k)=K%11冲突调节：拉链法-1-1
算法C( TABLE[ ]，K，M. )C1.[散列]置i←h(K) +1（现在1≤i≤M，为检索K，取K的散列位置i=h(K) +1，去检索TABLE [i] ) .C2.[有链表吗?]若TABLE[i]为空，则转到步骤C6.C3.[比较]若K= KEY[i]，则本算法以成功告终.C4.[查下一个]若LINK[i]≠Λ，则置i←LINK[i]并返回步骤C3.
C5.[找空结点](已查完由TABLE[h(K)+1]开始的链表，检索不成功，故应该插入K，所以需要在表中找一个空位置)．令R减1（R初值为M+1），进行此操作一次或多次直到TABLE[R]是空为止．若R=0（表明已经没有剩余的空结点），则本算法以溢出告终；否则，置LINK[i]←R，i←R.C6.[插入K]标记TABLE[i]为已占用，置KEY[i]←K，LINK[i]←Λ，算法以插入成功告终。
▐
1372.线性探查线性探查完全废除链接，以固定的次序检索表中的结点，直到找到一个关键词为K的结点或者找到一个空缺位置.其循环探查路径：h(K)，h(K)+1，…，M-1，0，1，…，h(K)-1
138109876543210206171374522366关键词序列为：20, 17, 2, 23, 45, 66, 6, 37, 1散列函数：h(k)=K%11冲突调节：线性探查
线性探查查找和插入算法L( TABLE[ ]，K，M. )L1.[散列]置i←h(K) .
1403.双重散列从h(K)开始，寻找空地址时，所前进的步长不是固定的，而与K有关，即用△，1≤△＜M（△是K的函数），代替线性探查的前进步长1。为了确保表中的每一个地址都能探查到，必须要求△和M互质，另外，还希望△与K有关，因而可用另一个杂凑函数δ(K)来代替△，1≤δ(K)＜M，因对任意的K，△=δ(K)都要与M互质，因此M应选作质数。
算法D( TABLE[ ]，K，M. ) D1.[第一次散列]置i←h1 (K)．D2.[第一次探查]若TABLE[i]为空，则转到步骤D6．否则若KEY[i] =K，则本算法以成功告终。
D3.[第二次散列]置c←h2 (K)．D4.[查下一个]置i←(i+ c ) modM．D5.[比较]若TABLE[i]为空，则转D6．否则若KEY[i] =K，则本算法以成功告终。否则转D4．D6.[插入K]若N=M-1，则本算法由于溢出而中止，否则置N←N+ 1．标记TABLE[i]为已占用，并置KEY[i]←K．▐
一、线性表的查找8.1.1无序表的顺序查找8.1.2有序表的顺序查找8.2.1对半查找8.2.2一致对半查找8.2.3斐波那契查找8.2.4插值查找二、树形结构的查找8.3二叉查找树8.5高度平衡树8.7 B树及其变型三、散列8.9.1散列表(杂凑表)的定义8.9.2散列函数的构造8.9.3冲突调解
本章作业354页：8-8、8-10、8-13、8-22
1441.有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉查找树，若希望高度最小，则应选择下面哪个序列输入_____。[A] 45, 24, 53, 12, 37, 96, 30[B] 37, 24, 12, 30, 53, 45, 96[C] 12, 24, 30, 37, 45, 53, 96[D] 30, 24, 12, 37, 45, 96, 532.二叉查找树T中关键词互异，则T的最小关键词必无左孩子（指内结点），最大关键词必无右孩子（指内结点）。
此命题是否正确?最小和最大关键词是叶结点吗?一个新结点（其关键词不同于T的任意结点的关键词）总是作为叶结点被插在二叉查找树的合适的外结点处吗?本章练习
1453.设有序顺序表为{10,20,30,40,50,60,70,80}，采用折半查找时，查找成功的平均查找长度是多少（各个关键词等概率）？4.试写一个判别给定二叉树是否为二叉查找树的算法。5.试给出对有序表进行顺序查找的算法，并画出关于有序表顺序查找的判定树，假设每次给定随机的查找值，且成功和不成功查找之概率相等，试求进行每一次查找时，与给定值进行比较的关键词个数的期望值。
1466.下图所示的高度平衡二叉树（AVL树）中，依次插入关键词为6和10的两个结点，请分别画出依次插入后的AVL树。920832
1473.答案：画出相应的二叉判定树，计算查找成功的平均查找次数（查找长度）。3010204070608050查找成功的平均比较次数是(1+2+2+3+3+3+3+4)/8=21/8，查找失败的平均比较次数是。(3+3+3+3+3+3+3+4+4)/9=29/9
1489208326920836289362208103622098936220106.答案：
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}