内蒙古大学《算法与数据结构》讲义11搜索树
46页1、下载第11章搜索树本章是关于树结构的最后一章,我们将给出一种适合于描述字典的树形结构。第 7章中的字典描述仅能提供比较好的平均性能,而在最坏情况下的性能很差。当用跳表来描述一个 n 元素的字典时,对其进行搜索、插入或者删除操作所需要的平均时间为 O ( l o gn),而最坏情况下的时间为(n)。当用散列来描述一个n 元素的字典时,对其进行搜索、插入或者删除操作所需要的平均和最坏时间分别为( l )和(n)。使用跳表很容易对字典元素进行高效的顺序访问(如按照升序搜索元素) ,而散列却做不到这一点。当用平衡搜索树来描述一个n 元素的字典时,对其进行搜索、插入或者删除所需要的平均时间和最坏时间均为( l o gn),按元素排名进行的查找和删除操作所需要的时间为 O ( l o gn),并且所有字典元素能够在线性时间内按升序输出。正因为这样(无论是平衡还是非平衡搜索树) ,所以在搜索树中进行顺序访问时,搜索每个元素所需要的平均时间为( l )。实际上,如果所期望的操作为查找、插入和删除(均根据元素的关键值来进行) ,则可以借助于散列函数来实现平衡搜索树。当字典操作仅按关键值来进行时,可将平衡
2、搜索用于那些对时间要求比较严格的应用,以确保任何字典操作所需要的时间都不会超过指定的时间量。平衡搜索树也可用于按排名来进行查找和删除操作的情形。对于那些不按精确的关键值匹配进行字典操作的应用(比如寻找关键值大于k 的最小元素) ,同样可使用平衡搜索树。本章将首先介绍二叉搜索树。这种树提供了可与跳表相媲美的渐进复杂性。其搜索、插入和删除操作的平均时间复杂性为 O ( l o gn),最坏时间复杂性为(n)。接下来将介绍两种大家比较熟悉的平衡树:AV L树和红-黑树。无论哪一种树,其搜索、插入和删除操作都能在对数时间内完成(平均和最坏情况) 。两种结构的实际运行性能也很接近, AV L树一般稍微快一些。所有的平衡树结构都使用“旋转”来保持平衡。 AV L树在执行每个插入操作时最多需要一次旋转,执行每个删除操作时最多需要O ( l o gn)次旋转;而红-黑树对于每个插入和删除操作,都需要执行一次旋转。这种差别对于大多数仅需( l )时间进行一次旋转的应用来说无关紧要,但对于那些不能在常量时间内完成一次旋转的应用来说就非常重要了,比如平衡优先搜索树McCreight 就是这样一种应用。平衡优
3、先搜索树用于描述具有两个关键值的元素,此时,每个关键值是一对数(x,y)。它同时是一个关于y 的优先队列和关于x 的搜索树。在平衡优先搜索树中执行旋转时,每次旋转都需耗时O ( l o gn)。如果用红-黑树来描述平衡优先搜索树,由于每一次插入或删除后仅需执行一次旋转,因此插入或删除操作总的时间复杂性仍保持为 O ( l o gn);当使用AV L树时,删除操作的时间将变为O ( l o gn)。如果所描述的字典比较小(能够完全放入内存) ,AV L树和红-黑树均能提供比较高的性能,但对于很大的字典来说,它们就不适用了。当字典存储在磁盘上时,需要使用带有更高次数(因而有更小高度)的搜索树,本章也将介绍一个这样的搜索树 B-树。本章的应用部分将给出三个搜索树的应用。第一个是直方图的计算,第二个是 1 0 . 5 . 1节所介绍的N P-复杂问题箱子装载,最后一个是关于在电子布线中所出现的交叉分布问题。在直方图的应用中,使用散列函数来取代搜索树,从而使性能得到提高。在最优匹配箱子装载应用中,由于搜索不是按精确匹配完成的,所以不能使用散列函数。在交叉分布问题中,操作是按排名完成的,因此也不能
4、使用散列函数。11.1 二叉搜索树11.1.1 基本概念7 . 1和7 . 4节介绍了抽象数据类型D i c t i o n a ry,从中可以发现当用散列来描述一个字典时,字典操作(包括插入、搜索和删除)所需要的平均时间为( l )。而这些操作在最坏情况下的时间正比于字典中的元素个数 n。如果扩充D i c t i o n a ry 的A D T描述,增加以下操作,那么散列将不能再提供比较好的平均性能:1) 按关键值的升序输出字典元素。2) 按升序找到第k 个元素。3) 删除第k 个元素。为了执行操作1 ),需要从表中取出数据,将它们排序后输出。如果使用除数为 D 的链表,那么能在(D+n) 的时间内取出元素,在O (nl o gn) 时间内完成排序和在(n) 时间内输出,因此共需时间O (D+nl o gn)。如果对散列使用线性开型寻址,则取出元素所需时间为(b),b 是桶的个数,这时所需时间为O (b+nl o gn)。如果使用链表,操作2) 和3) 可以在O (D+n) 的时间内完成,而如果使用线性开型寻址,它们可在(b) 时间内完成。为了获得操作2) 和3) 的这种复杂性,必
5、须采用一个线性时间算法来确定n 元素集合中的第k 个元素(参考1 4 . 5节) 。如果使用平衡搜索树,那么对字典的基本操作(搜索、插入和删除)能够在 O ( l o gn)的时间内完成,操作1) 能在(n)的时间内完成。通过使用带索引的平衡搜索树,也能够在 O ( l o gn)的时间内完成操作2) 和3 )。11 . 3节将考察其他一些散列无法做到而平衡树可以有效解决的应用。在学习平衡树之前,首先来看一种叫作二叉搜索树的简单结构。定义二叉搜索树 二叉搜索树(binary search tree)是一棵可能为空的二叉树,一棵非空的二叉搜索树满足以下特征:1) 每个元素有一个关键值,并且没有任意两个元素有相同的关键值;因此,所有的关键值都是唯一的。2) 根节点左子树的关键值(如果有的话)小于根节点的关键值。3) 根节点右子树的关键值(如果有的话)大于根节点的关键值。4) 根节点的左右子树也都是二叉搜索树。此定义中有一些冗余。特征2 )、3) 和4) 在一起暗示了关键值必须是唯一的。因此,特征 1 )可以用这样的特征代替:根节点必须有关键值。然而,前一种定义比这种简化的定义要清楚明了。图
《内蒙古大学《算法与数据结构》讲义11搜索树》由会员东***分享,可在线阅读,更多相关《内蒙古大学《算法与数据结构》讲义11搜索树》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页