树型数据结构.pptVIP

  1. 1、本文档共78页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
树型数据结构

数据结构 孙超 Email:schschschsch@163.com 主要内容 以树的概念为基础的数据结构: 堆 线段树 树状数组 二叉查找树 堆 使用堆的目的 堆的定义 堆的操作 取最优值 插入元素 删除元素 建立一个堆 堆的应用 使用堆的目的 空间目的:无需附加空间 时间目的: 取最优值 O(1) 插入元素 O(logn) 删除元素 O(logn) 堆的定义 堆是一颗完全二叉树 堆要么是空树要么满足如下条件: 根节点小于(或大于)子节点 左子树和右子树都是堆 可以看到,堆是递归定义的数据结构。 堆的定义(续) 对于完全二叉树,我们可以直接用数组存储,因此堆还有另一种定义方式 如果对于一个数组A。 满足对于任意的i有: A[i]≥A[i*2] 且 A[i]≥A[i*2+1] 则称A为一个堆(最大堆)。 实际上,堆都是采用数组(根为1)实现的。 堆的实例 一个最大堆的实例 ,对应在数组中的 存储为: (78, 46, 67, 44, 22, 50, 7, 35, 10) 堆的操作 一个基本的堆可以 实现一下几个操作: 取最优值 插入元素 删除元素 建立一个堆 取最优值 根据前面的定义可以简单的发现,堆中的最大(小)元素就是第1个元素,因此我们只需要给出第一个元素即可。 代码如下: function getmax begin getmax:=heap[1]; end 很显然,它的时间复杂度为 O(1) 插入元素 先将元素插入到最后一个位置, 但是,插入后,有可能破坏了堆的结构,因此,我们需要对堆进行调整。使得其能够满足堆的定义。这我们通过一个siftup过程来实现。 siftup过程 siftup过程的作用就是将指定的元素向上调整到合适的位置,代码如下: procedure siftup(i:integer); var x,t,u:integer; begin x:=heap[i]; t:=i; u:=t div 2; while (u0) do begin if x=heap[u] then break; heap[t]:=heap[u]; t:=u; u:=t div 2; end; heap[t]:=x; end; 堆的插入 插入操作的时间复杂度 考虑到一个N个节点的完全二叉数高度为O(logN),因此,插入操作的调整时间复杂度为O(logN) 删除元素 首先考虑删除最后一个元素,我们直接删去[heap(n)]即可。 再考虑删去第一个元素,我们先将它和最后一个交换,再删去。但是,交换后,有可能破坏了堆的结构,因此,我们需要对堆进行调整。使得其能够满足堆的定义。这我们通过一个siftdown过程来实现。 siftdown过程 procedure siftdown(n,i:integer); var x,t,u:integer; begin x:=heap[i]; t:=i; u:=t*2; while (u=n) do begin if heap[u+1]heap[u] then u:=u+1; if x=heap[u] then break; heap[t]:=heap[u]; t:=u; u:=t*2; end; heap[t]:=x; end; 堆的删除 任意位置的元素的删除 对于堆中央的元素的删除,也是采用交换的方法,但是调整的时候,既要考虑siftdown,也要考虑siftup。 删除操作的时间复杂度 易知,删除操作的时间复杂度和插入操作是一样的,也为O(logN)。 建立一个堆 现在给定N个元素,要建立一个堆,怎么办? 将N个元素一个一个插入,每个时间复杂度为O(logN),总时间为 O(NlogN)。 还不如直接排序。 怎么降低复杂度呢? 建立一个堆(续) 假设一个节点的左右子树都已经是堆了,那么只要将这个节点向下调整到适当位置即可。 于是我们可以一步一步的使用siftdown过程来完成建堆。 建堆的代码 procedure buildheap(n:integer); var i:integer; begin for i:=n div 2 downto 1 do siftdown(i,n); end; 建堆的时间复杂度分析 显然buildheap的时间就是shiftdown的时间代价之和。 其中1/2的叶子节点不需移动。 1/4的节点最多移动1层 1/8的节点最多移动2层 ... 所以总的时间复杂度: 可以知道,建堆操作的时间复杂度为O(n) 。 堆的应用 Dijkstra, Prim算法的优化 堆排序(Heapsort) … 经常在模拟题中出现,可以把某些操作的

文档评论(0)

phltaotao + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档