数据结构第九章

数据结构第九章1第1页，共56页，2023年，2月20日，星期六主要讨论的问题：静态查找;动态查找;哈希查找..几个基本概念.查找表:由同一类型的数据元素构成的集合..静态查找表:若只在查找表中搜索某一特定的数据元素是否存在,这类搜索过程称之为静态查找..动态查找表:若在查找表中搜索时插入了不存在的数据元素或删除了已存在的数据元素,这类搜索过程称之为动态查找表.第2页，共56页，2023年，2月20日，星期六.关键字:是数据元素中某个数据项的值,它可以标识一个数据元素..查找:根据给定的某个值,在查找表中确定一个其关键字等于给定值的记录或数据元素..查找成功:若表中存在这样的记录,称查找是成功的..查找不成功:若表中不存在关键字等于给定值的记录,称查找不成功.3第3页，共56页，2023年，2月20日，星期六§9.1静态查找表.顺序表的查找的定义--又称线性查找,主要用于在线性结构中进行搜索..顺序查找的思想--从表的一端开始,用给定值k与表中各个结点的键值逐个比较.1)查找成功---找出相等k值；2)查找失败---已到达表的另一端(可在此设置一个监视哨，作为下标越界的条件),即表中所有结点的键值都不等于k.4第4页，共56页，2023年，2月20日，星期六.监视哨的作用:作为越界(即已查完)的检测条件,省去在循环中每次均要判定是否越界,从而节省比较的时间..顺序查找算法：intsxcz(JDr[],intn,intk){inti=n;/*从表尾开始向前查找*/r[0].key=k;/*设置监视哨*/while(r[i].key!=k)i--;return(i);}5第5页，共56页，2023年，2月20日，星期六.平均查找长度(在等概率的前提下)（n+1）/2.--平均查找长度ASL..如何衡量顺序查找的性能？.顺序查找的特点：1)算法简单,对线性表的逻辑次序无要求(即不必按关键字值不增或不减的次序排列)；2)存储结构可采用顺序或链式存储结构均可,但其平均查找长度较大((n+1)/2).6第6页，共56页，2023年，2月20日，星期六.思想:先确定待查找记录所在的范围,然后逐步缩小范围,直到找到或确认找不到该记录为止..二分查找.适用条件:必须在具有顺序存储结构的有序表中进行..算法实现7第7页，共56页，2023年，2月20日，星期六.思想:先确定待查找记录所在的范围,然后逐步缩小范围,直到找到或确认找不到该记录为止..二分查找.适用条件:必须在具有顺序存储结构的有序表中进行..算法实现.设表长为n,low,high和mid分别指向待查元素所在区间的上界,下界和中点,k为给定值..初始时,令low=1,high=n,mid=(low+high)/2（只舍不入）.让k与mid指向的记录比较1)若k==r[mid].key,查找成功(k等于中间项的值)2)若k<r[mid].key,则high=mid-1(k小于中间值,在表的前半部分查找)3)若k>r[mid].key,则low=mid+1(k大于中间值,在表的后半部分查找).重复上述操作,直至low>high时,查找失败.8第8页，共56页，2023年，2月20日，星期六例:在查找表(08,14,23,37,46,55,68,79,91)查找23和79的过程..二分查找的示例.二分查找的算法描述折半查找的c语言算法程序：intSearch_Bin(SSTableST[],intn,intkey){intlow,high,mid;low=1;high=n;while(low<=high){mid=(low+high)/2;if(ST[mid].key==key)return(mid);/*查找成功*/elseif(key<ST[mid].key)high=mid-1;/*在前半区间继续查找*/elselow=mid+1;/*在后半区间继续查找*/}return(0);/*查找不成功*/}9第9页，共56页，2023年，2月20日，星期六.设有一有序表(-1,0,1,3,4,6,8,10,12),以二分查找来构造出它的二叉判定树..从有序表构造出二叉查找树(二叉判定树)10第10页，共56页，2023年，2月20日，星期六.若设n=2h-1,则描述二分查找的二叉查找树是高度为h-1的满二叉树.2h=n+1,h=log2(n+1)..第1层结点有1个,搜索第1层结点要比较1次;第2层结点有2个,搜索第2层结点要比较2次;…,第i(0

i

h)层结点有2i个,搜索第i层结点要比较i+1次,….假定每个结点的搜索概率相等,即pi

=1/n,则搜索成功的平均搜索长度为:.二分查找的性能分析11第11页，共56页，2023年，2月20日，星期六.可以用归纳法证明.于是,可得.特点:比顺序查找方法效率高.最坏的情况下,需要比较log2n+1次,即时间复杂度为O(log2n).12第12页，共56页，2023年，2月20日，星期六.分块查找(索引顺序查找).是顺序查找的一种改进方法,就是把被查找的表分成若干块,每块中记录的存放顺序是无序的,但块与块之间必须按关键字有序.即第一块中任一记录的关键字都小于第二块中任一记录的关键字,而第二块中任一记录的关键字都小于第三块中任一记录的关键字,依此类推..思想:该法要为被查找的表建立一个索引表,索引表中的一项对应于表中的一块,索引表中含有这一块中的最大关键字和指向块内第一个记录位置的指针,索引表中各项关键字有序.13第13页，共56页，2023年，2月20日，星期六索引表20538916111812852051362229538960726676块中的最大关键字块内第一个记录位置的指针分块查找分两步进行:先查索引表(索引表表长较短用顺序查找,较长可用折半查找)确定纪录在哪一块.然后在相应的块中查找.例,查找12,由索引表的第一项知,纪录要么在第一块中,要么不存在,由此取到第一块中第一个纪录位置.接着在第一块中进行顺序查找.分块查找效率高于顺序查找,但低于折半查找.14第14页，共56页，2023年，2月20日，星期六§9.2动态查找表.回忆:动态查找表的特点..二叉排序树(二叉搜索树)

二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:

每个结点都有一个作为搜索依据的关键码(key)，所有结点的关键码互不相同.

左子树(如果存在)上所有结点的关键码都小于根结点的关键码.

右子树(如果存在)上所有结点的关键码都大于根结点的关键码.

左子树和右子树也是二叉排序树.的定义15第15页，共56页，2023年，2月20日，星期六.几个二叉排序树的例子.由此,可得到二叉排序树的作用:查找.二叉排序树上的查找---在二叉搜索树上进行搜索,是一个从根结点开始,沿某一个分支逐层向下进行比较判等的过程..二叉排序树上的查找可以是一个递归过程,也可以是一个迭代过程.16第16页，共56页，2023年，2月20日，星期六.二叉排序树是的搜索示例.88插入到哪个地方?.每次结点的插入,都要从根结点出发搜索插入位置,然后把新结点作为叶结点插入.17第17页，共56页，2023年，2月20日，星期六.二叉排序树上的插入---为了向二叉搜索树中插入一个新元素,必须先检查这个元素是否在树中已经存在..在插入之前,先使用搜索算法在树中检查要插入元素有还是没有.搜索成功:树中已有这个元素,不再插入.

搜索不成功:树中原来没有关键码等于给定值的结点,把新元素加到搜索操作停止的地方.例:输入数据序列{53,78,65,17,87,09,81,45,23},写出建立二叉排序树的过程.18第18页，共56页，2023年，2月20日，星期六.为了引入二叉排序树上的删除,先简单讨论下面这个问题..同样3个数据{1,2,3},输入顺序不同,建立起来的二叉搜索树的形态也不同.这直接影响到二叉搜索树的搜索性能.如果输入序列选得不好,会建立起一棵单支树,使得二叉搜索树的高度达到最大,这样必然会降低搜索性能.123111132223323直观上的结论,二叉排序树的高度不能太高.19第19页，共56页，2023年，2月20日，星期六.二叉排序树上的删除---在二叉搜索树中删除一个结点时,必须将因删除结点而断开的二叉链表重新链接起来,同时确保二叉搜索树的性质不会失去..为保证在执行删除后,树的搜索性能不至于降低,还需要防止重新链接后树的高度增加.1)删除叶结点,只需将其双亲结点指向它的指针清零,再释放它即可.2)被删结点缺右子树,可以拿它的左子女结点顶替它的位置,再释放它.3)被删结点缺左子树,可以拿它的右子女结点顶替它的位置，再释放它.20第20页，共56页，2023年，2月20日，星期六4)被删结点左,右子树都存在,可以在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删结点中,再来处理这个结点的删除问题.21第21页，共56页，2023年，2月20日，星期六.二叉排序树上的查找性能分析.二叉排序树上的查找与折半查找类似..但,折半查找长度为n的表的判定树惟一..显然,n个结点的二叉排序树的平均查找长度与树的二叉树的形态有关.想想,最好情况与最坏情况各是什么样?.结论:在随机情况下,二叉排序树的平均查找长度是对数级.但这种情况出现的概率小于50%..结论:在构建二叉排序树的过程中要进行”平衡化”处理.22第22页，共56页，2023年，2月20日，星期六.平衡二叉树(AVL树).AVL树的定义.一棵AVL树或者是空树,或者是具有下列性质的二叉搜索树:它的左子树和右子树都是AVL树,且左子树和右子树的高度之差的绝对值不超过1.(a)(b)23第23页，共56页，2023年，2月20日，星期六.结点的平衡因子.每个结点附加一个数字,给出该结点右(左)子树的高度减去左(右)子树的高度所得的高度差.这个数字即为结点的平衡因子balance..如果一个结点的平衡因子的绝对值大于1,则这棵二叉搜索树就失去了平衡,不再是AVL树.任何一个结点的平衡因子有几个取值?.一棵AVL树的高度保持在什么级别?.高度可保持在O(log2n).24第24页，共56页，2023年，2月20日，星期六.平衡化处理.平衡化旋转有两类：

单旋转(左旋和右旋)双旋转(左平衡和右平衡).每插入一个新结点时,AVL树中相关结点的平衡状态会发生改变.因此,在插入一个新结点后,需要从插入位置沿通向根的路径回溯,检查各结点的平衡因子(左,右子树的高度差).如果在某一结点发现高度不平衡,停止回溯.25第25页，共56页，2023年，2月20日，星期六.从发生不平衡的结点起,沿刚才回溯的路径取直接下两层的结点.如果这三个结点处于一条直线上，则采用单旋转进行平衡化.单旋转可按其方向分为左单旋转和右单旋转,其中一个是另一个的镜像,其方向与不平衡的形状相关.如果这三个结点处于一条折线上，则采用双旋转进行平衡化.双旋转分为先左后右和先右后左两类.右单旋转左单旋转左右双旋转右左双旋转26第26页，共56页，2023年，2月20日，星期六.AVL树的插入例:输入关键码序列为{16,3,7,11,9,26,18,14,15},写出插入和调整过程.0-1-201161631630701左右双旋731600731101-2右单旋371690001371126916110112227第27页，共56页，2023年，2月20日，星期六181803163-101602右左双旋739000182611-1732616119-1左单旋97161400171126269111128第28页，共56页，2023年，2月20日，星期六1518231816-2左右双旋73000117149-1161501112626141-29例:以{30,35,39,15,10,28,16,29,17}为例建AVL树.29第29页，共56页，2023年，2月20日，星期六.动态的m路搜索树.二叉搜索树适合于组织在内存中的较小的索引(或目录),对于存放在外存中的较大的文件系统,用二叉搜索树来组织索引不太合适..在文件检索系统中大量使用的是用B-(B)树或B+树做文件索引..当数据对象数目特别大,索引表本身也很大,在内存中放不下,需要分批多次读取外存才能把索引表搜索一遍.30第30页，共56页，2023年，2月20日，星期六.在此情况下,可以建立索引的索引,称为二级索引.二级索引可以常驻内存,二级索引中一个索引项对应一个索引块,登记该索引块的最大关键码及该索引块的存储地址..如果二级索引在内存中也放不下,需要分为许多块多次从外存读入.可以建立二级索引的索引，叫做三级索引.这时,访问外存次数等于读入索引次数再加上1次读取对象..必要的话,还可以有4级索引,5极索引,….多级索引结构形成一种m叉树.31第31页，共56页，2023年，2月20日，星期六.树中每一个分支结点表示一个索引块,它最多存放m个索引项,每个索引项分别给出各子树结点(低一级索引块)的最大关键码和结点地址..树的叶结点中各索引项给出在数据表中存放的对象的关键码和存放地址.这种m叉树用来作为多级索引,就是m路搜索树..m路搜索树可能是静态索引结构,即结构在初始创建,数据装入时就已经定型,在整个运行期间,树的结构不发生变化..m路搜索树还可能是动态索引结构,即在整个系统运行期间,树的结构随数据的增删及时调整,以保持最佳的搜索效率.32第32页，共56页，2023年，2月20日，星期六多级索引结构形成m路搜索树33第33页，共56页，2023年，2月20日，星期六.动态的m路搜索树.一般定义为:.一棵m路搜索树,它或者是一棵空树,或者是满足如下性质的树：根最多有m棵子树,并具有如下的结构：

n,P0,(K1,P1),(K2,P2),……,(Kn,Pn)其中，Pi是指向子树的指针,0i

n<m;Ki是关键码,1

i

n<m.Ki<Ki+1,1

i<n..在子树Pi中所有的关键码都小于

Ki+1，且大于

Ki,0<i<n..在子树Pn中所有的关键码都大于Kn..在子树P0中的所有关键码都小于

K1..子树Pi也是m路搜索树,0

i

n.34第34页，共56页，2023年，2月20日，星期六.一棵3路搜索树的示例.AVL树是m=?路搜索树?35第35页，共56页，2023年，2月20日，星期六.B-树.一棵m阶B_树是一棵m路搜索树,它或者是空树,或者是满足下列性质的树:.根结点至少有2个子女..除根结点以外的所有结点(不包括失败结点)至少有m/2个子女..所有的失败结点都位于同一层..事实上,在B-树的每个结点中还包含有一组指针D[m],指向实际对象的存放地址.K[i]与D[i](1in<m)形成一个索引项(K[i],D[i]).通过K[i]可找到某个对象的存储地址D[i].36第36页，共56页，2023年，2月20日，星期六.非B-树与B-树的示例图非B-树B-树.B-树上的搜索37第37页，共56页，2023年，2月20日，星期六.B-树的搜索过程是一个在结点内搜索和循某一条路径向下一层搜索交替进行的过程.因此,B-树的搜索时间与B-树的阶数m和B-树的高度h直接有关,必须加以权衡..在B-树上进行搜索,搜索成功所需的时间取决于关键码所在的层次,搜索不成功所需的时间取决于树的高度..在B-树上搜索的示例38第38页，共56页，2023年，2月20日，星期六.B-树上的插入.B-树是从空树起,逐个插入关键码而生成的..在B-树,每个非失败结点的关键码个数都在

[m/2-1,m-1]之间..插入在某个叶结点开始.如果在关键码插入后结点中的关键码个数超出了上界m-1,则结点需要“分裂”,否则可以直接插入..实现“分裂”的原则39第39页，共56页，2023年，2月20日，星期六.设结点p中已经有m-1个关键码,当再插入一个关键码后结点中的状态为:.(m,P0,K1,P1,K2,P2,……,Km,Pm)

其中Ki

<Ki+1,1

i<m这时必须把结点p分裂成两个结点p和q,它们包含的信息分别为：

结点p：

(m/2-1,P0,K1,P1,……,Km/2-1,Pm/2-1)

结点q：

(m-m/2,Pm/2,Km/2+1,Pm/2+1,……,Km,Pm)位于中间的关键码Km/2与指向新结点q的指针形成一个二元组(Km/2,q),插入到这两个结点的双亲结点中去.40第40页，共56页，2023年，2月20日，星期六结点“分裂”的示例41第41页，共56页，2023年，2月20日，星期六.B-树上的插入示例:从空树开始逐个加入关键码53,75,139,49,145,36,101建立3阶B-树.42第42页，共56页，2023年，2月20日，星期六.若设B-树的高度为h.那么在自顶向下搜索到叶结点的过程中需要进行h次读盘..在插入新关键码时,需要自底向上分裂结点,最坏情况下从被插关键码所在叶结点到根的路径上的所有结点都要分裂.43第43页，共56页，2023年，2月20日，星期六.B-树上的删除.在B-树上删除一个关键码时,首先需要找到这个关键码所在的结点,从中删去这个关键码..若该结点不是叶结点,且被删关键码为Ki,1

i

n,则在删去该关键码之后,应以该结点Pi所指示子树中的最小关键码x来代替被删关键码Ki

所在的位置,然后在x所在的叶结点中删除x..在叶结点上删除有4种情况:1)被删关键码所在叶结点同时又是根结点且删除前该结点中关键码个数n

2,则直接删去该关键码并将修改后的结点写回磁盘.44第44页，共56页，2023年，2月20日，星期六2)被删关键码所在叶结点不是根结点且删除前该结点中关键码个数n

m/2,则直接删去该关键码并将修改后的结点写回磁盘,删除结束.45第45页，共56页，2023年，2月20日，星期六3)被删关键码所在叶结点删除前关键码个数n=m/2-1,若这时与该结点相邻的右兄弟(或左兄弟)结点的关键码个数n

m/2，则可按以下步骤调整该结点,右兄弟(或左兄弟)结点以及其双亲结点,以达到新的平衡。.将双亲结点中刚刚大于(或小于)该被删关键码的关键码Ki

(1i

n)下移；.将右兄弟(或左兄弟)结点中的最小(或最大)关键码上移到双亲