网站大量收购独家精品文档,联系QQ:2885784924

算法实验区间树上的重叠区间查找算法.docVIP

算法实验区间树上的重叠区间查找算法.doc

  1. 1、本文档共3页,可阅读全部内容。
  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文档。上传文档
查看更多
算法实验区间树上的重叠区间查找算法

一、算法分析 区间树是在红黑树基础上进行的简单的数据结构扩张。区间便于表示占用一连续时间段的一些事件,且具有三分律的性质,即判断两个区间的重叠与否。区间树按照数据结构扩张的四个步骤对红黑树进行扩张。第一个步骤为选择基础数据结构,即一棵红黑树,,在每个结点x中加入一个区间属性x.int,设置x的关键字为区间的低端点x.int.low。所以以此建立的红黑树中序遍历的结果是按低端点次序排列的各区间。第二个步骤为附加信息,附加的信息为x.maxx.max=max(x.int.high,x.left.max,x.right.max)。第三个步骤为确定维护信息,分析插入与删除操作,都能在lgn时间内完成。第四个步骤为设计新的操作,在区间树的应用中,需要添加的唯一操作类型为查找Interval_Search(T,i),找出树T中与区间i重叠的那个结点,若树中与i重叠的结点不存在,返回指向哨兵T.nil的指针。 区间树是数据结构扩张的典型应用,在区间的查找上提供了nlogn时间复杂度的算法。利用成熟数据结构扩张解决延伸的实际问题是一种效率很高的方法,也降低了解决成本。 二、算法实现 区间树查找重叠区间算法的实现需要三个步骤:第一步建立一棵树()。第二步是树插入操作,为结点的颜色属性赋值,输入的结点赋值为红。第三步根据插入结点的颜色在树中的位置及父结点和孩子结点的颜色进行维持树性质的调整操作(InsertFixup、LeftRotate、RightRotate)。 初始化操作为InitLeafNode构造叶子结点以及BuildIntervalTree建树操作。 三、实验结果 进行次输入实验,每次输入10。 1、第一次实验 2、第次实验 3、第次实验

文档评论(0)

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

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

1亿VIP精品文档

相关文档