左偏堆的特点及其应用ppt课件_第1页
左偏堆的特点及其应用ppt课件_第2页
左偏堆的特点及其应用ppt课件_第3页
左偏堆的特点及其应用ppt课件_第4页
左偏堆的特点及其应用ppt课件_第5页
已阅读5页，还剩17页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

广东省中山市第一中学湟源河左联树的特点及应用。左倾树的定义。左倾树是一个可合并堆，它不仅支持优先级队列的三个基本操作(插入、删除、取最小节点)，还支持一个非常特殊的操作合并操作。左边的部分树是一棵有序的二叉树。左倾树满足左倾属性。2，左倾树的定义左倾属性，它将左倾树中的外部节点定义为其左子树或右子树为空的节点。将节点1的距离(距离(I)定义为从节点1到其后代的最近外部节点所经过的边数。任何节点的左子节点的距离不小于右子节点的距离(左偏置属性)。根据左偏离属性，节点的距离等于根为该节点的子树的最右边路径的长度。3，左倾树的性质，定理：如果左倾树有n个节点，左倾树的距离不超过log (n 1)-1。最右边的路径：a-c-g，最右边的路径节点数=3，距离=2，左倾树的最大距离为8个节点：log (81)-1=2，4，左倾树的操作，左倾树支持以下操作：MakeNull初始化一个空的左倾树合并合并两个左倾树插入插入一个新节点Min获取最小节点DeleteMin删除最小节点Delete左倾树的操作被合并，并且合并操作被递归地执行。将两个左倾树T1和T2合并，先将T1的右子树与T2合并，6，合并左倾树的操作，递归进行合并操作，a，L1，R，先将T1的右子树与T2合并，7，合并左倾树的操作，递归进行合并操作，交换左、右子树，更新根节点距离。合并的右子树的距离可能大于左子树的距离。8.左子树的操作被合并。合并操作的代码如下：FunctionMerge (A，B)IFA=NullThEnTurnbiBeb=NullThEnTurnaIfKey(B)Dist(Left(A)然后Swap (Left (A)，Right (a)如果Right(A)=nutcheindist(A)0 else Dist(A)1 returnendfunction，9，Left-leading tree操作 merge，下面是一个合并示例：10，Left-leading tree操作 merge，下面是左倾树操作 merge，下面是一个合并示例：18，NULL，13，左倾树操作 merge，下面是一个合并示例：37，7，0，1， 14，左倾树操作合并，下面是合并的一个例子：1，1，2，26，17，37，18，8，7，15，左倾树操作合并，下面是合并的一个例子：0，2？左倾树的操作被合并，下面是合并的例子：3，10，2，0，1，17，左倾树的操作被合并，并且合并操作总是沿着两个左倾树的最右边的路径执行。一棵N节点左倾树在最右边的路径上最多有1个LOG节点。因此，合并操作的时间复杂度为：O(logN1 logN2)=O(logN)，18，插入左倾树的操作，插入新节点，待插入的节点被视为单节点左倾树，合并两个左倾树的时间
人人文库> 全部分类> 教育资料 > 作文作品

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论