数据结构教程（Java语言描述）（第2版 微课视频版） 课件 第9章 查找

第9章

查找9.1查找的基本概念9.2线性表的查找CONTENTS提纲9.3树表的查找9.4哈希表查找1/64一般情况下，被查找的对象称为查找表，查找表包含一组元素（或记录），每个元素由若干个数据项组成，并假设有能唯一标识元素的数据项，称为主关键字（默认按主关键字查找）。查找定义为：给定一个值k，在含有n个元素的查找表中找出关键字等于k的元素。若找到这样的元素，表示查找成功，返回该元素的信息或该元素在表中的位置；否则查找不成功或者查找失败，返回相应的指示信息。9.1查找的基本概念2/64查找表按照操作方式分为静态查找表和动态查找表两类。静态查找表是只作查找操作的查找表，主要操作有查询某个“特定的”数据元素是否在查找表中，检索某个“特定的”数据元素及其属性。动态查找表是在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。3/64查找有内查找和外查找之分。若整个查找过程都在内存进行，则称之为内查找。反之，若查找过程中需要访问外存，则称之为外查找。4/64查找算法中的主要操作是关键字之间的比较，所以通常把查找过程中关键字平均比较次数也就是平均查找长度作为衡量一个查找算法效率优劣的依据。平均查找长度ASL（AverageSearchLength）定义为其中，n是查找表中元素的个数，pi是查找第i个元素的概率，一般地，除特别指出外，均认为每个元素的查找概率相等，即pi=1/n（1≤i≤n），ci是查找到第i个元素所需的关键字比较次数。查找性能评价5/64

由于查找的结果有查找成功和不成功两种情况，所以平均查找长度也分为成功情况下的平均查找长度和不成功情况下的平均查找长度。成功情况下的平均查找长度指在查找表中找到指定关键字k的元素平均所需关键字比较的次数。不成功情况下的平均查找长度指在查找表中确定找不到关键字k的元素平均所需关键字比较的次数。6/64

查找表T：含有n个元素。成功情况下（概率相等）的平均查找长度ASL成功是指找到T中任一记录平均需要的关键字比较次数。

关键字514879243找到时的比较次数123456789ASL成功=1+2+3+4+5+6+7+8+99=5例如：7/64

查找表T：含有n个元素。

不成功情况下的平均查找长度ASL不成功是指查找失败（在T中未查找到）平均需要的关键字比较次数。

x

T通过关键字比较后确定不在T中平均关键字比较次数8/649.2线性表的查找线性表采用顺序表存储，由于顺序表不适合数据修改操作（插入和删除元素几乎需要移动一半的元素）

顺序表是一种静态查找表。三种线性表查找方法，即顺序查找、折半查找和分块查找算法。9/64顺序表中元素的类型classRecType{

//顺序表元素类型intkey; //存放关键字，假设关键字为int类型Stringdata; //存放其他数据，假设为String类型publicRecType(intd){ //构造方法key=d;}}10/64顺序表查找类SqListSearchClasspublicclassSqListSearchClass{

//顺序表查找类finalintMAXN=100; //表示最多元素个数RecType[]R; //R[0..n-1]表示查找表intn; //实际元素个数publicvoidCreateR(int[]a){ //由关键字序列a构造顺序表RR=newRecType[MAXN];for(inti=0;i<a.length;i++)R[i]=newRecType(a[i]);n=a.length;}publicvoidDisp(){ //输出顺序表for(inti=0;i<n;i++)System.out.print(R[i].key+"");System.out.println();}

//各种顺序表查找算法，后面讨论}11/649.2.1顺序查找1.顺序查找算法基本思路从顺序表的一端开始依次遍历，将遍历的元素关键字和给定值k相比较。若两者相等，则查找成功，返回该元素的序号。若遍历结束后，仍未找到关键字等于k的元素，则查找失败，返回-1。默认从顺序表的前端开始遍历。12/64publicintSeqSearch1(intk){ //顺序查找算法1inti=0;while(i<n&&R[i].key!=k)i++; //从表头往后找if(i>=n)return-1; //未找到返回-1elsereturni; //找到后返回其序号i}简单比较方法13/64publicintSeqSearch2(intk){ //顺序查找算法2R[n]=newRecType(k); //添加哨兵inti=0;while(R[i].key!=k)i++; //从表头往后找if(i==n)return-1; //未找到返回-1elsereturni; //找到后返回其序号i}设置一个哨兵由于查找算法主要考虑关键字之间的比较，两个算法的效率差不多说明14/642.顺序查找算法分析1）仅考虑查找成功的情况第1个元素即R[0].key=k，1次关键字比较。第2个元素即R[1].key=k，2次关键字比较。以此类推，第n个元素即R[n-1].key=k，n次关键字比较ci=i+1共有n种查找成功的情况，在等概率时，pi=1/n。15/642）仅考虑查找不成功的情况

若k值不在表中，则总是需要n次比较之后才能确定查找失败，所以仅仅考虑查找不成功时对应的平均查找长度为：ASL不成功

=n16/643）既考虑查找成功又考虑查找不成功的情况一个顺序表中顺序查找的全部情况（查找成功和失败）可以用一棵判定树或比较树（这里是单支二叉树）来描述。例如，n=5的关键字序列（18，16，14，12，20）的顺序查找过程对应的判定树如下：R[4].key≠kR[1].key≠kR[2].key≠kR[3].key≠kR[0].key≠kqp0p1p2p3p4182016141217/64

设所有成功查找的概率，q表示不成功查找的概率，当既考虑查找成功又考虑查找不成功的情况时有p+q=1。

不妨假设p=q=0.5，并且所有关键字成功查找的概率相同，即pi=0.5/n，则成功情况下的平均查找长度为：18/64

假设所有不成功查找的情况为m种，它们的查找概率相同，即qi=0.5/m，则不成功情况下的平均查找长度为：合起来：可以推出：顺序查找的时间复杂度为O(n)。19/64顺序查找的优点是算法简单，且对查找表的存储结构无特殊要求，无论是用顺序表还是用链表来存放元素，也无论是元素之间是否按关键字有序，它都同样适用。顺序查找的缺点是查找效率低，因此，当n较大时不宜采用顺序查找。顺序查找总结20/649.2.2折半查找1.折半查找算法基本思路

设R[low..high]是当前的非空查找区间（下界为low，上界为high），首先确定该区间的中点位置mid=

(low+high)/2

（或者mid=(low+high)>>1），然后将待查的k值与R[mid].key比较：

（1）若k=R[mid].key，则查找成功并返回该元素的序号mid。

（2）若k<R[mid].key，则在左子表R[low..mid-1]中查找，即下界不变，上界改为mid-1。

（3）若k>R[mid].key，则在右子表R[mid+1..high]中查找，即下界改为mid+1，上界不变。

下一次查找是针对非空新查找区间进行的，其过程与上述过程类似。若新查找区间为空，表示查找失败，返回-1。查找表R[0..n-1]为递增有序顺序表21/64

【例9.2】在关键字有序序列（2，4，7，9，10，14，18，26，32，40）中采用折半查找方法查找关键字为7的元素。24

791014182632401234567890lowhighmidk=7midmidR[mid].key==k

查找成功22/64publicintBinSearch1(intk){ //拆半查找非递归算法intlow=0,high=n-1,mid;while(low<=high){ //当前区间非空时mid=(low+high)/2; //求查找区间的中间位置if(k==R[mid].key) //查找成功返回其序号midreturnmid;if(k<R[mid].key) //继续在R[low..mid-1]中查找high=mid-1;else //k>R[mid].keylow=mid+1; //继续在R[mid+1..high]中查找}return-1; //当前查找区间空时返回-1}23/64publicintBinSearch2(intk){ //拆半查找递归算法returnBinSearch21(0,n-1,k);}privateintBinSearch21(intlow,inthigh,intk){if(low<=high){ //当前查找区间非空时intmid=(low+high)/2; //求查找区间的中间位置if(k==R[mid].key) //查找成功返回其序号midreturnmid;if(k<R[mid].key) //递归在左区间中查找returnBinSearch21(low,mid-1,k);else //k>R[mid].key,递归在右区间中查找returnBinSearch21(mid+1,high,k);}elsereturn-1; //当前查找区间空时返回-1}24/64

【例9.3】有以下两个折半查找算法，其中参数R是非空递增有序顺序表，指出它们的正确性。publicintBSearch1(intk){intlow=0,high=n-1,mid;while(low<=high){mid=(low+high)/2;if(k==R[mid].key)returnmid;if(k<R[mid].key)high=mid-1;elselow=mid;}return-1;}publicintBSearch2(intk){intlow=0,high=n-1,mid;while(low<high){mid=(low+high)/2;if(k==R[mid].key)returnmid;if(k<R[mid].key)high=mid-1;elselow=mid+1;}if(R[low].key==k)returnlow;elsereturn-1;}25/64publicintBSearch1(intk){intlow=0,high=n-1,mid;while(low<=high){mid=(low+high)/2;if(k==R[mid].key)returnmid;if(k<R[mid].key)high=mid-1;elselow=mid;}return-1;}错误：对于查找区间[low，high]，mid=(low+high)/2，若k>R[mid].key执行low=mid，新查找区间为[mid，high]，若mid与查找区间的low相同（如low=high时），则新查找区间没有变化，从而陷入死循环。以R=（1，3，5），k=2为例可以说明！26/64publicintBSearch2(intk){intlow=0,high=n-1,mid;while(low<high){mid=(low+high)/2;if(k==R[mid].key)returnmid;if(k<R[mid].key)high=mid-1;elselow=mid+1;}if(R[low].key==k)returnlow;elsereturn-1;}正确：这里R是非空表，将while语句改为循环到仅包含一个元素R[low]为止，再判断该元素的关键字是否为k，若不成立返回-1。27/642.折半查找算法分析一个有序顺序表R中所有元素的折半查找过程可用一棵判定树或比较树（这里是二叉树）来描述。查找区间为R[low..high]的判定树T(low，high)定义为，当low>high时，T(low，high)为空树；当low≤high时，根结点为中间序号mid=(low+high)/2的元素，其左子树是R[low..mid-1]对应的判定树T(low，mid-1)，其右子树是R[mid+1，high]对应的判定树T(mid+1，high)。28/64具有11个元素（R[0..10]）的有序表可用下图的判定树来表示5280369-1～012～345～678～9100～11～23～44～56～77～89～1010～∞<>=<>=<>=<>=<>=<>=<>=<>=<>=<>=<>=R[0..10]R[0..4]R[6..10]R[3..4]R[0..1]R[9..10]R[6..7]R[10..10]R[7..7]R[4..4]R[1..1]u-1u0u1u2u3u4u6u5u8u7u9u10内部结点中的数字表示该元素在有序表中的下标。外部结点中的两个值表示查找不成功时关键字对应的元素序号范围29/64

【例9.4】给定11个元素的有序表（2，3，10，15，20，25，28，29，30，35，40），采用折半查找，试问：

（1）若查找给定值为20的元素，将依次与表中哪些元素比较？

（2）若查找给定值为26的元素，将依次与哪些元素比较？

（3）假设查找表中每个元素的概率相同，求查找成功时的平均查找长度和查找不成功时的平均查找长度。30/64（1）有序表为（2，3，10，15，20，25，28，29，30，35，40），查找给定值为20的元素，将依次与表中哪些元素比较？2510302152835320294031/64（2）有序表为（2，3，10，15，20，25，28，29，30，35，40），查找给定值为26的元素，将依次与哪些元素比较？2510302152835320294032/64

（3）假设查找表中每个元素的概率相同，求查找成功时的平均查找长度和查找不成功时的平均查找长度。251030215283532029401个结点，1次比较2个结点，每个2次比较4个结点，每个3次比较4个结点，每个4次比较33/64251030215283532029404个结点，每个3次比较8个结点，每个4次比较34/64

不妨设关键字序列为（k0，k1，…，kn-1），并有k0<k1<…<kn-1，对应n个内部结点，查找关键字ki的概率为pi，则成功情况下的平均查找长度为：

不在判定树中的关键字可分为n+1类Ei（-1≤i≤n-1），对应n+1个外部结点，设qi是查找属于Ei中关键字的概率，那么不成功的平均查找长度为：35/64借助一棵二叉判定树很容易求得折半查找的平均查找长度。为讨论方便起见，不妨设内部结点的总数为n=2h-1，这样的判定树是高度为h=log2(n+1)的满二叉树（高度h不计外部结点）。该满二叉树中第j（1≤j≤h）层上的结点个数为2j-1，查找该层上的每个结点需要进行i次比较。因此，在等概率假设下，折半查找成功情况下的平均查找长度为：h=log2(n+1)………外部结点层36/64

从成功和不成功情况下的平均查找长度看出，折半查找的时间复杂度为O(log2n)，是一种高效的查找算法。h=log2(n+1)………外部结点层层次最大的外部结点就是不成功查找所需关键字比较次数最多的结点，它一定是层次最大的内部结点的孩子结点，其关键字比较次数恰好是h+1-1=h。37/64当n不等于2h-1时，其折半查找判定树不一定为满二叉树，但可以证明n个结点的判定树的高度与n个结点的完全二叉树的高度相等，即h为

log2(n+1)

或者

log2n

+1。同样，查找成功时关键字比较次数最多为判定树的高度h，查找不成功时关键字比较次数最多也为判定树的高度h。38/643.折半查找算法的扩展1）在有序表R中查找插入点对于有序查找表R，关键字k的插入点定义为将k插入R中使其有序的那一点。假设R是递增有序的，插入点就是第一个大于等于k的元素序号。例如，R=（1，1，1），k=2的插入点为3，k=-1的插入点为0。若R=（1，3，5），k=1的插入点为0，k=2的插入点为1，k=5的插入点为2。假设有序表R中可能出现相同关键字的元素。39/64publicintGOEk(intk)//查找第一个大于或者等于k的序号即k的插入点{intlow=0,high=n-1,mid;while(low<=high) //当前区间非空时{mid=(low+high)/2; //求查找区间的中间位置if(k<=R[mid].key) //继续在R[low..mid-1]中查找high=mid-1;else //k>R[mid].keylow=mid+1; //继续在R[mid+1..high]中查找}returnhigh+1; //返回high+1}…

R[low..high]R[high+1]

…R[n-1]k<=R[mid].key

转向左区间R[low..high]为空时结束插入点为空均>=k40/64

【例9.6】有一个按整数关键字key递增有序的顺序表R，其中关键字可能重复出现。设计一个算法返回与k最接近的元素关键字，若有多个最接近的元素关键字时，返回较大的那一个。

例如，R=（1，3，8，8，12），k=6时最接近的元素是8，k=10时最接近的元素是12。41/64若k≤s.R[0].key，则返回s.R[0].key。若k≥s.R[s.n-1].key，则返回s.R[s.n-1].key。否则，先调用前面的算法GOEk(intk)求R中第一个大于或者等于k的元素序号j，再取其前一个元素序号i，最接近元素的区间为[i，j]，通过比较返回R[i].key或者R[j].key。思路R=（1，3，8，8，12），k=6ijGOEk(intk)比较查找最接近k的元素42/64staticintClosest(SqListSearchClasss,intk){if(k<=s.R[0].key)returns.R[0].key;if(k>=s.R[s.n-1].key)returns.R[s.n-1].key;intj=s.GOEk(k); //查找第一个大于或者等于k的序号inti=j-1; //前一个元素的序号if(Math.abs(s.R[i].key-k)<Math.abs(s.R[j].key-k))returns.R[i].key;elsereturns.R[j].key;}43/64Java中的Arrays类提供了静态方法binarySearch(E[]

a,int

fromIndex,int

toIndex],E

key)，使用折半查找在一维有序数组a的[fromIndex，toIndex)范围内查找为k的元素序号。若省略范围，则在整个有序数组中查找。如果数组a中包含多个为k的元素，则无法保证找到的是哪一个。如果查找成功则返回找到的一个元素的序号；否则返回(-插入点-1)。例如，a={1，3，5}，k=4，查找不成功，k的插入点为2，返回值为-2-1=-3。注意，这保证了当且仅当k被找到时，返回的值将≥0。Java44/642）在有序表R中查找关键字k的元素区间

若R中存在多个关键字为k的元素，它们一定是相邻的。查找关键字k的元素区间就是查找其中关键字为k的第一个和最后一个元素序号。1031323354k=31345/64当m为奇数时，中间位置mid=(low+high)/2是唯一的。如R[0..2]=（1，2，3），对应的中位数（中间位置的元素）是R[1]=2。当m为偶数时，中间位置有两个，其中mid1=(low+high)/2是低中间位，mid2=(low+high+1)/2（或者mid=low+(high-low+1)/2）是高中间位。如R[0..3]=（1，2，3，4），对应的低中位数是R[1]=2（mid1=1），高中位数是R[2]=3（mid2=2）。在前面基本的折半查找中总是取低中间位。对于查找区间R[low..high]，其长度为m=(high-low+1)。46/64

Firstequalsk(k)算法用于返回R中第一个等于k的元素序号，若R中没有等于k的元素则返回-1。…

R[low..low]R[low+1]…R[n-1]最多一个为k的元素均≥k查找到的序号R[low].key=k

对于长度大于1的查找区间R[low..high]（满足low<high），置mid=(low+high)/2（其长度为偶数时取低中间位）：

（1）若k≤R[mid].key，新查找区间左移为R[low..mid]。

（2）若k>R[mid].key，新查找区间右移为R[mid+1..high]。上述过程直到找到长度为1的查找区间R[low..low]为止。47/64publicintFirstequalsk(intk){ //查找第一个等于k的元素序号intmid,low=0,high=n-1;while(low<high){mid=(low+high)/2; //n为偶数时取低中间位if(k<=R[mid].key)high=mid;elselow=mid+1;}if(k==R[low].key)returnlow;elsereturn-1;}48/64

Lastequalsk(k)算法用于返回R中最后一个等于k的元素序号，若R中没有等于k的元素则返回-1。R[0..low-1]R[low..low]…

最多一个为k的元素均≤k查找到的序号R[low].key=k

对于长度大于1的查找区间R[low..high]（满足low<high），置mid=(low+high+1)/2（其长度为偶数时取高中间位）：

（1）若k≥R[mid].key，新查找区间右移为R[mid..high]。

（2）若k<R[mid].key，新查找区间左移为R[low..mid-1]。上述过程直到找到长度为1的查找区间R[low..low]为止。49/64publicintLastequalsk(intk) {//查找最后一个等于k的元素序号intmid,low=0,high=n-1;while(low<high){mid=(low+high+1)/2; //n为偶数时取高中间位if(k>=R[mid].key)low=mid;elsehigh=mid-1;}if(k==R[low].key)returnlow;elsereturn-1;}50/64publicint[]Intervalk(intk) {//查找为k的元素区间[v[0]，v[1]]int[]v=newint[2];v[0]=Firstequalsk(k);v[1]=Lastequalsk(k);returnv;}51/649.2.3索引存储结构和分块查找1.索引存储结构索引存储结构是在采用数据表存储数据的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式为（关键字，地址），其中，关键字唯一标识一个元素，地址为该关键字元素在数据表中的存储地址，整个索引表按关键字有序排列。52/64数据表学号姓名分数地址2018001王华9002018010刘丽6212018006陈明5422018009张强9532018007许兵7642018012李萍8852018005李英826索引表学号地址20180010201800562018006220180074201800932018010120180125按关键字k的查找过程：先在索引表按折半查找方法找到关键字为k的索引项，得到其地址，所花时间为O(log2n)。再通过地址在数据表中找到对应的元素，所花时间为O(1)，合起来的查找时间为O(log2n)，53/642.分块查找数据整体无序分块后按块有序54/64

例如，设有一个线性表，其中包含25个元素，其关键字序列为：

8，14，6，9，10，22，34，18，19，31，40，38，54，66，46，71，78，68，80，85，100，94，88，96，87

分块：将n=25个元素分为b=5块，每块中有s=5个元素。数据特性：每组建立一个索引项

索引表55/6481469102234181931403854664671786880851009488968701234567891011121314151617181920212223241434668510005101520索引表keylink数据表分块查找的索引存储结构56/64查找索引表（有序）：可以顺序查找块，也可以二分查找块。查找数据块（无序）：只能顺序查找块中元素。分块查找过程：57/6481469102234181931403854664671786880851009488968701234567891011121314151617181920212223241434668510005101520索引表keylink数据表（1）顺序查找索引表，比较4次（2）在对应块中查找，比较4次，共比较8次。查找关键字为k=80的元素成功找到80的元素58/64索引表的类型定义如下：classIdxType{

//索引表类型intkey; //关键字（这里是对应块中的最大关键字）intlink; //该索引块在数据表中的起始下标}143466851000510152059/64假设数据表长度为n，分为b个块，块长度为s。创建索引表I[0..b-1]publicvoidCreateI(IdxType[]I,intb){//构造索引表ints=(n+b-1)/b; //每块的元素个数intj=0,jmax=R[j].key;for(inti=0;i<b;i++){ //构造b块I[i]=newIdxType();I[i].link=j;while(j<=(i+1)*s-1&&j<=n-1) {//遍历一个块if(R[j].key>jmax) //查找其中最大关键字jmaxjmax=R[j].key;j++;}I[i].key=jmax;if(j<=n-1) //j没有遍历完jmax=R[j].key; //jmax置为下一个块首元素关键字}}60/64分块查找算法publicintIdxSearch(IdxType[]I,intb,intk){//在顺序表R[0..n-1]和索引表I[0..b-1]中查找kintlow=0,high=b-1,mid;while(low<=high){ //在索引表中查找第一个大于等于k的块号mid=(low+high)/2; //与GEOk算法类似if(k<=I[mid].key)high=mid-1;elselow=mid+1;}if(high+1>=b)return-1; //块号超界，查找失败，返回-1inti=I[high+1].link; //所在块的起始位置ints=(n+b-1)/b; //每块的元素个数if(i==b-1) //第i块是最后块，元素个数可能少于ss=n-s*(b-1);while(i<=I[high+1].link+s-1&&R[i].key!=k)i++;if(i<=I[high+1].link+s-1)returni;//查找成功,返回该元素的序号elsereturn-1; //查找失败,返回-1}61/64

【例】

设数据序列中有100个元素，待查找元素的关键字k=47。如果在查找过程中，和k进行比较的元素依次是10，47，16，32，47，则所采用的查找方法可能是（）。A.顺序查找 B.折半查找 C.分块查找 D.都不是只有分块查找需要进行两次查找。第一次与47的比较是在索引表中查找，第2次与47的比较是在对应块中查找。C62/64分块查找性能分析若有n个元素，每块中有s个元素（每块的大小b=

n/s

）用折半查找确定元素所在的块，则分块查找成功时的平均查找长度为：当s越小时，ASLblk的值越小，即当采用折半查找确定块时，每块的长度越小越好。63/64有顺序查找确定元素所在的块，则分块查找成功时的平均查找长度为：当s=sqrt(n)时，ASL'blk取极小值sqrt(n)+1，即当采用顺序查找确定块时，各块中的元素个数选定为

时效果最佳。64/649.3树表的查找几种特殊树形结构—统称为树表。这里的树表采用链式存储结构，由于链式存储结构既适合查找，也适合数据修改，属于动态查找表。对于动态查找表，不仅要讨论查找方法，还讨论修改方法。65/809.3.1二叉排序树1.二叉排序树的定义若它的左子树非空，则左子树上所有结点值（默认为结点关键字）均小于根结点值。若它的右子树非空，则右子树上所有结点值均大于根结点值。左、右子树本身又各是一棵二叉排序树。

二叉排序树（简称BST）又称二叉查找（搜索）树，其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：66/80一棵二叉排序树示例：42135768根结点最左下结点，即为关键字最小的结点根结点最右下结点，即为关键字最大的结点特点：中序序列：1，2，3，4，5，6，7，8中序序列是一个递增有序序列！67/80定义二叉排序树的结点类如下：classBSTNode { //二叉排序树结点类publicintkey; //存放关键字,假设关键字为int类型publicBSTNodelchild; //存放左孩子指针publicBSTNoderchild; //存放右孩子指针BSTNode(){ //构造方法lchild=rchild=null;}}68/80设计二叉排序树类模板BSTClass<T>publicclassBSTClass { //二叉排序树类{publicBSTNoder; //二叉排序树根结点privateBSTNodef; //用于存放待删除结点的双亲结点publicBSTClass(){ //构造方法r=null;}

//二叉排序树的基本运算算法}69/802.二叉排序树的插入和生成在根结点p的二叉排序树中插入关键字为k的结点的过程如下：

（1）若p为空，创建一个key为k的结点，返回将它作为根结点。

（2）若k<p.key，将k插入p结点的左子树中并且修改p的左子树。

（3）若k>p.key，将k插入p结点的右子树中并且修改p的右子树。

（4）其他情况是k=p.key，说明树中已有关键字k，无须插入，直接返回p。70/80publicvoidInsertBST(intk){ //插入一个关键字为k的结点InsertBST1(r,k); }privateBSTNodeInsertBST1(BSTNodep,intk){//在以p为根的BST中插入关键字为k的结点if(p==null){ //空,新插入的元素为根结点p=newBSTNode();p.key=k;}elseif(k<p.key)p.lchild=InsertBST1(p.lchild,k); //插入到p的左子树中elseif(k>p.key)p.rchild=InsertBST1(p.rchild,k); //插入到p的右子树中returnp;}71/80

创建二叉排序树是从一个空树开始，先创建根结点，以后每插入一个关键字k，就调用一次InsertBST(k)算法将k插入到当前的二叉排序树中。publicvoidCreateBST(int[]a){ //由关键字序列a创建一棵二叉排序树r=newBSTNode(); //创建根结点r.key=a[0];for(inti=1;i<a.length;i++) //创建其他结点

InsertBST1(r,a[i]); //插入关键字a[i]}72/80

【例9.8】已知一组关键字为

（25,18,46,2,53,39,32,4,74,67,60,11）按表中的元素顺序依次插入到一棵初始为空的二叉排序树中，画出该二叉排序树，并求在等概率的情况下查找成功的平均查找长度和查找不成功的平均查找长度。73/80解：生成的二叉排序树如下。25182464113953327467602518462533932474676011生成的二叉排序树74/801825241146393253746760在等概率的情况下，查找成功的平均查找长度为：75/801825241146393253746760在等概率的情况下，查找不成功的平均查找长度为：76/803.二叉排序树的查找publicBSTNodeSearchBST(intk){//在二叉排序树中查找关键字为k的结点returnSearchBST1(r,k); //r为二叉排序树的根结点}privateBSTNodeSearchBST1(BSTNodep,intk){//被SearchBST方法调用if(p==null)returnnull; //空树返回nullif(p.key==k)returnp; //找到后返回pif(k<p.key)returnSearchBST1(p.lchild,k); //在左子树中递归查找elsereturnSearchBST1(p.rchild,k); //在右子树中递归查找}77/80与折半查找的判定树类似，在二叉排序树中每个空指针处添加一个外部结点。在二叉排序树中查找时，若查找成功，则是从根结点出发走了一条从根结点到查找到结点的路径。若查找不成功，则是从根结点出发走了一条从根到某个外部结点的路径。因此与折半查找类似，查找中关键字比较的次数不超过树的高度。78/80一个关键字集合可以有多个不同顺序的关键字序列，对于不同的关键字序列，CreateBST()算法创建的二叉排序树可能不同。例如，关键字序列为（5，2，1，6，7，4，3），创建的二叉排序树如图(a)所示。若关键字序列为（1，2，3，4，5，6，7），创建的二叉排序树如图(b)所示。1234567（b）高度为75261437（a）高度为4说明79/801234567（b）高度为75261437（a）高度为480/80那么如何分析二叉排序树的查找性能呢？有如下两种分析方法。给定含n个关键字的集合，假设所有关键字不相同，对应有n!个关键字序列，每个关键字序列构造一棵二叉排序树，所有这些二叉排序树中查找每个关键字的平均时间为O(log2n)。给定含n个关键字的特定关键字序列构造一棵二叉排序树。其中查找性能最好的是高度最小的二叉排序树，最好查找性能为O(log2n)。查找性能最坏的是高度为n的二叉排序树（单支树），最坏查找性能为O(n)。平均情况由具体的关键字序列来确定。所以常说二叉排序树的时间复杂度在O(log2n)和O(n)之间，就是指这种分析方法。81/80

【例9.9】在含有27个结点的二叉排序树上，查找关键字为35的结点，以下4个选项中哪些是可能的关键字比较序列？A.28，36，18，46，35 B.18，36，28，46，35C.46，28，18，36，35 D.46，36，18，28，35查找序列（k1，k2，…，kn）的查找树画法是，每一层只有一个结点，首先k1为根结点，再依次画出其他结点，若ki+1<ki，则ki+1的结点作为ki结点的左孩子，否则作为右孩子。查找树是原来二叉排序树的一部分，也一定构成一棵二叉排序树。82/80A.28,36,18,46,35B.18,36,28,46,35C.46,28,18,36,35D.46,36,18,28,3528361818362846462818364636182635是一棵二叉排序√

ⅩⅩⅩ83/804.二叉排序树的删除删除关键字与删除结点是一回事。删除一个结点时不能简单地把以该结点为根的子树都删去，只能删除该结点本身，并且还要保证删除后的二叉树仍然满足BST性质。也就是说，在二叉排序树中删除一个结点就相当于删除有序序列（即该树的中序序列）中的一个结点。84/80删除结点p分为以下几种情况

（1）若结点p是叶子结点（结点p的度为0），删除该结点等同于删除该结点的子树，所以可以直接删除该结点。526143789（a）结点p为叶子结点：直接删除删除结点9p2614378585/80（b）结点p仅有左孩子：用左孩子q结点替代结点p删除结点4qp52643789526137891

（2）若结点p只有左孩子没有右孩子（结点p的度为1），根据二叉排序树的特点，可以用结点p的左子树替代结点p的子树，也就是直接用其左孩子替代它（结点替代）。86/80（c）结点p仅有右孩子：用右孩子q结点替代结点p删除结点7pq52614378952614389

（3）若结点p只有右孩子没有左孩子（结点p的度为1），根据二叉排序树的特点，可以用结点p的右子树替代结点p的子树，也就是直接用其右孩子替代它（结点替代）。87/80（d）结点p有左右孩子：找到其左孩子的最右下结点q，置p结点值为q结点值（值替代），再删除q结点（q结点没有右孩子，最多只有左孩子，采用(b)删除）删除结点5p52614378942613789q

（4）若结点p既有左孩子又有右孩子（结点p的度为2），根据二叉排序树的特点，可以从其左子树中选择关键字最大的结点（中序前驱）或从其右子树中选择关键字最小的结点（中序后继）q替代结点p，再将结点q从相应子树中删除。操作步骤是先用结点q的值替代结点p的值（值替代），再删除结点q。88/80从二叉排序树中删除结点p是通过修改其双亲的相关指针实现的。为此需要标识结点p的双亲结点f，并且用flag标识结点p是结点f的何种孩子，flag=-1表示结点p是根结点没有双亲，flag=0表示结点p是结点f的左孩子，flag=1表示结点p是结点f的右孩子。所以，删除中的查找不能简单地采用前面的查找算法，而需要在查找中确定结点p对应的双亲结点f和左右孩子标记flag。89/80publicbooleanDeleteBST(intk){ //删除关键字为k的结点f=null;returnDeleteBST1(r,k,-1); //r为二叉排序树的根结点}privatebooleanDeleteBST1(BSTNodep,intk,intflag){if(p==null)returnfalse; //空树返回falseif(p.key==k)returnDeleteNode(p,f,flag); //找到后删除p结点if(k<p.key){f=p;returnDeleteBST1(p.lchild,k,0); //在左子树中递归查找}else{f=p;returnDeleteBST1(p.rchild,k,1); //在右子树中递归查找}}90/80删除仅有左孩子的结点p的过程fp（b）flag=0f.lchild=p.lchildp（a）flag=-1fp（c）flag=1f.rchild=p.lchildr=p.lchild91/80privatebooleanDeleteNode(BSTNodep,BSTNodef,intflag){

//删除结点p（其双亲为f）if(p.rchild==null){ //结点p只有左孩子(含p为叶子的情况)if(flag==-1) //结点p的双亲为空(p为根结点)r=p.lchild; //修改根结点r为p的左孩子elseif(flag==0) //p为双亲f的左孩子f.lchild=p.lchild; //将f的左孩子置为p的左孩子else //p为双亲f的右孩子f.rchild=p.lchild; //将f的右孩子置为p的左孩子}elseif(p.lchild==null){ //结点p只有右孩子if(flag==-1) //结点p的双亲为空(p为根结点)r=p.rchild; //修改根结点r为p的右孩子elseif(flag==0) //p为双亲f的左孩子f.lchild=p.rchild; //将f的左孩子置为p的左孩子else //p为双亲f的右孩子f.rchild=p.rchild; //将f的右孩子置为p的左孩子}92/80

当被删结点p有左、右孩子时，采用前面的删除方法，先让q指向其左孩子结点，分为以下两种情况：p.key=q.keyp.lchild=q.lchildp（a）结点q没有右孩子qp（b）结点q有右孩子qf1p.key=q.keyf1.rchild=q.lchild93/80else{ //结点p有左右孩子BSTNodef1=p; //f1为结点q的双亲结点BSTNodeq=p.lchild;//q转向结点p的左孩子if(q.rchild==null){ //若结点q没有右孩子p.key=q.key; //将被删结点p的值用q的值替代p.lchild=q.lchild; //删除结点q}else{ //若结点q有右孩子while(q.rchild!=null){ //找到最右下结点q,其双亲结点为f1f1=q;q=q.rchild;}p.key=q.key; //将被删结点p的值用q的值替代f1.rchild=q.lchild; //删除结点q}}returntrue;}94/809.3.2平衡二叉树既保持BST性质又保证树的高度较小，通过这样的平衡规则和操作来维护O(log2n)高度的二叉排序树称为平衡二叉树，平衡二叉树有多种。较为著名的有AVL树。95/80AVL树的高度平衡性质：树中每个结点的左、右子树的高度至多相差1。也就是说，如果树T中结点v有孩子结点x和y，则|h(x)-h(y)|≤1，h(x)表示以结点x为根的子树高度。526143710-1010-13142567（b）一棵非AVL树（a）一棵AVL树0-1-2-3-2-1096/80如何使构造的二叉排序树是一棵AVL树呢？关键是每次向树中插入新结点时使所有结点的平衡因子满足高度平衡性质，这就要求插入后一旦哪些结点失衡就要进行调整。97/801.AVL树插入结点的调整方法1）LL型调整ABγhβhαh10插入前BAγhβhαh00调整后LL调整LLABγhβhαh21插入后插入一结点98/80实际上是通过右旋转实现的！99/802）RR型调整ABγhβhαh-10插入前RR插入一结点插入后ABγhβhαh-2-1RR调整BAγhβhαh00调整后100/80实际上是通过左旋转实现的！101/803）LR型调整ABγhβhαh+110插入前Cδh+1LR调整调整后CB00A-1γhβhαh+1δh+1插入一结点插入后ABγhβhαh+12-1Cδh+1LRLR双旋转：A的左子树B先左旋转，再按根结点A右旋转！102/804）RL型调整RL调整调整后CA01B0γhβhαh+1δh+1ABγhβhαh+1-10插入前Cδh+10L插入一结点插入后ABγhβhαh+1-21Cδh+1-1RRL双旋转：A的左子树B先右旋转，再按根结点A左旋转！103/80

【例9.10】输入关键字序列（16，3，7，11，9，26，18，14，15），给出构造一棵AVL树的步骤。1637160161301623-170LR7030160104/801197316-11110-2107316119LL7311916000105/80267311916-11026-2RR73119160000260-1106/80187311916261-2180RL73119182600160107/80731191826161414101-1108/8073119182616-115142150LR731191826150140160构造的结果AVL树109/802.AVL树删除结点的调整方法

首先在AVL树中查找关键字为k的结点x（假定存在这样的结点并且唯一），删除结点x的过程如下：

（1）如果结点x左子树为空，用其右孩子结点替换它，即直接删除结点x。

（2）如果结点x右子树为空，用其左孩子结点替换它，即直接删除结点x。110/80

（3）如果结点x同时有左右子树（这种情况下，结点x是通过值替换间接删除的，称为间接删除结点），分为两种情况：若结点x的左子树较高，在其左子树中找到最大结点q，直接删除结点q，用结点q的值替换结点x的值。若结点x的右子树较高，在其右子树中找到最小结点q，直接删除结点q，用结点q的值替换结点x的值。111/80RL-21xppR(a)pR的左子树高：RLRR-2-1xppR(b)pR的右子树高：RR

（4）当直接删除结点x时，沿着其双亲到根结点方向逐层向上求结点的平衡因子，若一直找到根结点时路径上的所有结点均平衡，说明删除后的树仍然是一棵平衡二叉树，不需要调整，删除结束。若找到路径上的第一个失衡结点p，就要进行调整。①若直接删除的结点在结点p的左子树中。(c)若pR的左右子树高度相同，则做RL或RR调整均可②若直接删除的结点在结点p的右子树中，调整过程类似。112/80【例9.11】对例9.10生成的AVL树，给出删除结点11、9和3的过程。731191826151416113/80删除结点11731191826151416p找到结点11结点1有左右孩子右子树高，找到右孩子的最左小结点qq14值替换1-1-1直接删除14沿着根结点方向求平衡因子731191826151614均平衡114/80删除结点9731191826151614均平衡找到结点9-11直接删除9沿着根结点方向求平衡因子73111826151614115/80删除结点3求平衡因子直接删除3沿着根结点方向求平衡因子7311182615161471118261516140-2116/80RL调整71118261516140-21LR7111826161514删除后的AVL117/803．AVL树的查找

构造一系列的AVL树T1、T2、T3、…，其中，Th（h=1、2、3、…）是高度为h且结点数尽可能少的AVL树（总是让左子树较高）。结点个数n最少的平衡二叉树T1T2T3T4118/80构造Th，先分别构造Th-1和Th-2，使Th以Th-1和Th-2作为其根结点的左、右子树。ThTh-1Th-2设N(h)（高度h是正整数）为Th的结点数：N(1)=1N(2)=2N(h)=N(h-1)+N(h-2)+1T1T2119/80Fibonacci数列的关系：F(1)=1F(2)=1F(h)=F(h-1)+F(h-2)通过检查两个序列的前几项就可发现两者之间的对应关系：N(h)=F(h+2)-1120/80如果树中有n个结点，那么树的最大高度h为：含有n个结点的AVL树对应的查找时间复杂度为O(log2n)。结论h=121/80

另外，设M(h)（高度h是正整数）为Th中最小叶子结点的层次，可以看出有下列关系成立：T1T2T3T4M(1)=1M(2)=2M(h)=min(M(h-1)，M(h-2))+1M(1)=1M(2)=2M(3)=min(2,1)+1=2M(4)=min(2,2)+1=3高度为h的AVL树中叶子结点的层次≥M(h)122/80

【例9.12】在含有15个结点的AVL树中查找关键字为28的结点，以下哪些是可能的关键字比较序列？A.30，36 B.38，48，28C.48，18，38，28 D.60，30，50，40，38，36

画出4个查找序列对应的查找树都是二叉排序树，B序列对应的查找树不是一棵二叉排序树，排除选项B。384828123/80设Nh表示高度为h的AVL树中含有的最少结点数，按照前面N(h)的公式求得：N(3)=4，N(4)=7，N(5)=12，N(6)=20>15也就是说，15个结点的AVL树的最大高度为5。而D序列比较了6次还查找失败，显然是错误的，排除选项D。

A.30，36 B.38，48，28C.48，18，38，28 D.60，30，50，40，38，36k=28124/80n=15的AVL树的最小高度为4，即log2(n+1)=4，此时为一棵满二叉树。即h只能是4和5。h=4时为一棵满二叉树，所有叶子结点的层次为4，此时失败的查找需要4次比较，此时选项A不可能？

A.30，36 B.38，48，28C.48，18，38，28 D.60，30，50，40，38，36k=28125/80h=5时，加上外部结点后树高为6，此时将外部结点看成叶子结点，一定也是一棵AVL树。设M