- 1、本文档共3页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 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、第次实验
您可能关注的文档
- 竖曲线缓和曲线计算公式.doc
- 端口与漏洞扫描及网络监听.doc
- 笔试练习(宏)答案.doc
- 等高线2.doc
- 等值线图的判读与训练.doc
- 等高线地图的判读公开课.doc
- 等高线地图的应用修订稿.doc
- 等高线地形图专训.doc
- 等高线地形图刘长清.doc
- 等高线地形图副本.doc
- [中央]2023年中国电子学会招聘应届生笔试历年参考题库附带答案详解.docx
- [吉安]2023年江西吉安市青原区总工会招聘协理员笔试历年参考题库附带答案详解.docx
- [中央]中华预防医学会科普信息部工作人员招聘笔试历年参考题库附带答案详解.docx
- [保定]河北保定市第二医院招聘工作人员49人笔试历年参考题库附带答案详解.docx
- [南通]江苏南通市崇川区人民法院招聘专职人民调解员10人笔试历年参考题库附带答案详解.docx
- [厦门]2023年福建厦门市机关事务管理局非在编工作人员招聘笔试历年参考题库附带答案详解.docx
- [三明]2023年福建三明市尤溪县招聘小学幼儿园新任教师79人笔试历年参考题库附带答案详解.docx
- [哈尔滨]2023年黑龙江哈尔滨市木兰县调配事业单位工作人员笔试历年参考题库附带答案详解.docx
- [上海]2023年上海市气象局所属事业单位招聘笔试历年参考题库附带答案详解.docx
- [台州]2023年浙江台州椒江区招聘中小学教师40人笔试历年参考题库附带答案详解.docx
文档评论(0)