




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、左侧部分树的特性和应用,广东省中山市第一中学黄元河、2、左侧部分树的定义,左侧部分树除支持优先级队列的三个基本操作(插入、删除、最小节点)外,还支持非常特殊的作业合并操作的一种并集(Mergeable Heap)左侧的部分树是“堆顺序”(Heap Ordered)二进制树。左侧部分树满足左侧部分的“Leftist Property(属性)”。3,左侧部分树定义左侧部分特性,左侧部分树的外部节点(外部节点)定义左侧或右侧子树为空的节点。节点I的距离(dist(i)是从节点I到其后代最近的外部节点通过的边数。任何节点的左侧子节点距离都不小于右侧子节点的距离(左侧部分属性)。如左侧部分属性所示,一个
2、节点的距离等于该节点为根的子树最右侧路径的长度。4,左侧部分树的特性,清理:如果左侧部分树中有N个节点,则左侧部分树的距离不会超过log(N 1) -1。最大右侧路径3360 ACG最大右侧路径节点数=3距离=2,8节点左侧部分树的最大距离:log(8 1) -1=2,5,左侧部分树操作,左侧部分树支持以下操作:MakeNull初始化左空部分树Merge。插入两个左侧部分树Insert新节点Min插入最小节点DeleteMin删除最小节点Delete删除所有已知节点Decrease减少一个节点的关键值,6,合并左侧部分树操作,合并操作递归。合并T1和T2的左侧子树,首先合并T1的右侧子树与T2
3、,合并左侧子树的操作,合并操作递归,合并操作递归,a,L1,R,T1的右侧子树与T2合并,8,合并左侧子树的操作,合并操作递归,左侧合并后,右侧子树大于左侧子树距离9,左侧子树的操作可能被合并。合并操作的代码如下:functionmerge (a,b)if a=NULL then return b if b=NULL then return a if key(b)dist(left(a)then sware、15、合并左侧部分树中的任务,以下是合并的示例:1、1、2、26、17、37、18、8、7、16、合并左侧部分树中的任务,17,合并左侧部分树中的操作。以下是合并的示例:3,10,2,0,1,18,合并左侧部分树中的任务。合并操作始终沿两个左侧部分树的最右侧路径执行。N个节点的左侧部分树,最右侧路径中最多包含log(N 1)节点。因此,合并操作的时间复杂性为O(log N1 log N2)=O(log N),19,插入左侧树的操作,并将插入新节点的节点合并到单节点左侧部分树中的两个左侧部分树时间复杂性(O(log N),20,)删除最小节点合并根节点左右子树时间复杂性:o (log n),21,摘要,左侧
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 停业通知的司法实践-洞察及研究
- 楷书硬笔、毛笔书法技法系统化教程
- 发酵技术的基础原理与应用分析
- 文化产业发展融资模式探究
- 自然辩证法考试重点与难点总结
- 多维度特征提取在电力系统扰动识别中的应用
- 内部资金调剂管理办法
- 生物炭与有机肥配施对土壤健康及设施栽培黄瓜生长的影响机制研究
- 安全运输操作规程与案例分析
- PCR实验室管理与标准化操作流程
- 2025数学新课程标准培训
- 2025-2030中国新能源行业市场现状供需分析及重点企业投资评估规划分析研究报告
- GB/T 45698-2025物业服务客户满意度测评
- 2025年新高考1卷(新课标Ⅰ卷)语文试卷(含答案)
- 本土品牌“品牌年轻化”策略研究
- 湖南省永州市宁远县2025届七年级数学第二学期期末达标检测试题含解析
- 创新人才小升初试题及答案
- 2025年行政管理期末试题及答案
- 胰岛素笔的使用操作流程
- 九年级化学上册(沪教版2024)新教材解读课件大纲
- 江山南方水泥有限公司浙江省江山市大陈乡乌龙村铁锤山水泥用灰岩矿建设项目环境影响报告表
评论
0/150
提交评论