算法实验三-区间树上的重叠区间查找算法

教育专区 > 高等教育 > 其它 > 文档预览

5 页 1327 浏览 5 收藏 4.7分

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

温馨提示：当前文档最多只能预览 5 页，若文档总页数超出了 5 页，请下载原文档以浏览全部内容。

下载文档到电脑，方便使用

下载文档

当前文档最多只能预览 5 页
还有 2 页可预览，继续阅读

本文档由匿名用户于 2023-01-04 23:33:17上传分享

下载原文档(351.50 KB)

你可能在找

数据结构实验5查找排序算法

实验五、查找排序算法的实现一、实验目的1．掌握顺序、二分法查找方法及适用场合，并能在解决实际问题时灵活应用。 2．掌握各种排序（直接插入，希尔，冒泡，快速排序，简单选择，堆排序等）方法及适用场合，并能在解决实际问题时灵活应用。二、实验内容随机输入（或随机产生）30个数（1）采用冒泡排序完成对这30个数的排序（2）采用顺序、折半查找在（1）中排好序的数据中完成查找任务（3）分别采用插入、快速和希尔完成对这30个数的排序任务，并输出每一趟排序后的结果三

5.0 分 8 页 | 157.79 KB | 2020-12-19 11:47
贪心法的应用

课程实验报告课程名算法分析与设计班级实验日期学号实验成绩称姓名实验名实验5：贪心算法的应用称实1．理解贪心算法的概念；2．掌握贪心算法的基本思想。每个活动i都有一个要求使用该实验资源的起始时间si和一个结束时间fi，且si

3.0 分 9 页 | 85.19 KB | 2020-01-29 17:03
实验项目三：搜索算法

《算法设计与分析》实验报告实验项目（三）搜索算法专业、班级学号姓名实验时间实验地点指导教师教学目标使学生掌握“算法设计与分析”中的基本原理、基本技术和方法，提升计算机问题求解的水平。熟练掌握编程中常见问题的求解策略，培养学生对算法复杂性进行正确分析的能力。（1）掌握编程求解问题的常用算法策略。（2）熟练强化深入计算机求解问题的过程。（3）增强理论结合实际能力，增强获得理论联系实际问题的能力。（4）培养系统分析能力和团队协作能力。一、实验目的及要求（1）练习搜索算法和分支限界算法中剪枝的使用；（2）初步掌握回溯法和分支限界的编码。

5.0 分 3 页 | 202.00 KB | 2020-11-06 14:14
额温枪查表算法

额温枪查表算法目前额温枪这个东西特别火，所以大家都在搞这个事情，那我也来蹭个热度吧。大概的工作原理：热电堆传感器->ADC->MCU->LCD显示。其实原理很简单，那比较麻烦的事情就是温度补偿和校准的事情了。这个需要太多专业仪器，繁琐，这里不多说。那其实简而言之，就是传感器，ADC采集出来之后运算，就得到了温度。那从传感器采集到的数据是什么呢？这里可以推算出来的温度一共有两种，一种是环境温度，一种是物体表面温度。环境温度主要通过热敏电阻NTC的值来算，表面温度主要根据环境温度和热电堆电压来算。那怎么算呢？

4.9 分 3 页 | 100.50 KB | 2020-11-07 12:51
人教版三年级数学上教学计划及进度安排

人教版三年级数学上教学计划及课时安排一、教材分析本学期教材内容包括下面一些内容：时、分、秒，毫米、分米、千米和吨的认识，万以内的加法和减法笔算，倍的认识，多位数乘一位数，分数的初步认识，长方形和正方形，数学广角—集合（重叠问题）和数学实践活动（数字编码）等。最后在激发学生学习兴趣方面多寻找方法，使他们乐学，愿学。二、本学期教学的指导思想1、改进笔算教学的编排，体现计算教学改革的理念，重视培养学生的数感。

3.0 分 4 页 | 20.96 KB | 2019-09-01 05:37
继续教育统计学作业及答案2020

1(4分)、0在统计汇总时，如果只要求计算各组分配的单位数，可采用A、B、C、D、过录法划记法折叠法卡片法参考答案：B展开解析2(4分)、0按调查对象包括的范围不同，统计调查可以分为A 、经常性调查和一次性调查B、全面调查和非全面调查C、统计报表和专门调查D、普查和抽样调查参考答案：B展开解析3(4分)、0统计调查收集的资料主要是指A、B、C、D、原始资料总体资料数字资料初次整理过的资料 参考答案：A展开解析4(4分)、0简单表与分组表的区别在于A、主词是否分组B、宾词是否分组C、分组标志的多少D、分组标志是否重叠参考答案：A展开解析5(4分)、0普查规定的标准时间是

4.7 分 221 页 | 386.18 KB | 2020-11-17 16:00
DDA算法-中点画线算法-Bresenham算法

实验1直接绘制实验(提示：#表示Project的编号，##表示Project题目)学号题号姓名程序逻辑(40)上交时间算法新颖性(20)代码规范(20)实验报告总分(20)得分1.问题描述如何利用OpenGL 实现直线光栅化的DDA算法、中点画线算法和Bresenham算法2.算法描述DDA算法：据直线公式y=kx+b来推导出来的，其关键之处在于如何设定单位步进，即一个方向的步进为单位步进，另一个方向的步进必然是小于若M=(xp+1,yp+0.5)为P1与P2之中点，Q为P理想直线与x=xp+1垂线的交点。当M在Q的下方，则P2应为下一个像素点；M在Q的上方，应取P1为下一个像素点。

4.7 分 4 页 | 17.51 KB | 2022-11-26 23:09
大槐树民间说法

大槐树民间说法“问我祖先在何处？山西洪洞大槐树。祖先故居叫什么？大槐树下老鹳窝。”数百年来，这首民谣在我国广大地区祖辈相传，妇孺皆知。寻根古大槐树，又称洪洞大槐树，位于山西省洪洞县城西北二公里的贾村。七八个10岁左右的孩子在遗址前的广场上疯狂地抢着追逐足球。虽然是玩耍，但胜利者模仿着电视里球星式的欢呼———挥臂狂奔，颇有几分专业味道！

4.8 分 4 页 | 93.00 KB | 2022-07-11 23:36
三位数加减法计算题300道

三位数加减法计算题1、995-775=2、985-807=3、136+471=4、345+427=5、622+190=6、437+270=7、238+204=8、736-675=9、978-276=10

4.8 分 12 页 | 53.50 KB | 2020-11-08 11:51
三年级上册数学除法用竖式计算题

1.用竖式计算：704÷8=816÷6=108÷3=765÷9=908÷6=624÷6=756÷6=6300÷7=624÷3=903÷3=930÷5=408÷4=909÷9=640÷8=714÷7=165 ÷8=421÷7=465÷3=72÷6=634÷8=315÷3=705÷5=312÷2=318÷3=196÷6=721÷7=900÷5=7060÷5=605÷5=708÷3=651÷7=2.用脱式计算：

3.0 分 4 页 | 29.50 KB | 2020-01-16 14:37