区间树上重叠区间查找算法

1、。解一算法设计与分析上机报告姓名：学号：日期：上机题目：区间树上的重叠区间查找算法实验环境：CPU:2.10GHz;内存:2G;操作系统：Win764位；软件平台：VisualStudio2008;题目一:区间树的构造基本概念：区间：一个事件占用的时间闭区间：实数的有序对t1,t2,使t1Wt2区间的对象表示：t1,t2可以用对象i表示，有两个属性：lowi=t1/起点或低点highi=t2/终点或高点区间的重叠：?ilowi历卫薄andlow漫highi数据结构：本质上是将红黑树扩充，方法如下：tep1：基本结构以红黑树为基础，对xT,x包含区间intx的信息(低点和高点),key=lowi

2、ntx;Step2：附加信息maxx=max(highintx,maxleftx,maxrightx)Step3：维护附加信息(有效性)由定理14.1及max的定义有效Step4：开发新操作查找与给定区间重叠的区间keymax节点x题目二：查找算法IntervalSearch(T,i)基本思想step1：x-rootT；从根开始查找step2：若x/nilT且i与intx不重叠ifx的左子树非空且左子树中最大高点三lowithenx-leftx；至x的左子树中继续查找else/左子树必查不到，到右子树查x-rightx；step3：返回xx=nilori和x重叠由于区间树是红黑树的简单扩重，因

3、此区间树相关操作的实现如左旋、右旋、插入，插入调整等与红黑树基本相同，具体而言，仅仅在左旋和右旋的操作中维护卮目木全完V4I操max域的取值争取即可，题目一：区间树的构造typedefstructnodeintlow;inthigh;intmax;stringcolor;structnode*pParent;structnode*pLeft;structnode*pRight;Node;voidRBT:LeftRotate(Node*px)Node*py=px-pRight;px-pRight=py-pLeft;if(py-pLeft!=pT_nil)py-pLeft-pParent=px;p

4、y-pParent=px-pParent;if(px-pParent=pT_nil)pT_root=py;elseif(px=px-pParent-pLeft)px-pParent-pLeft=py;elsepx-pParent-pRight=py;py-pLeft=px;px-pParent=py;py-max=px-max;px-max=max(px-max,max(px-pLeft-max,px-pRight-max);voidRBT:RightRotate(Node*py)Node*px=py-pLeft;py-pLeft=px-pRight;px-pRight-pParent=py;

5、px-pParent=py-pParent;if(py-pParent=pT_nil)pT_root=px;elseif(py=py-pParent-pLeft)py-pParent-pLeft=px;elsepy-pParent-pRight=px;px-pRight=py;py-pParent=px;px-max=py-max;py-max=max(py-max,max(py-pLeft-max,py-pRight-max);)voidRBT:Insert(Node*pz)pz-max=pz-high;Node*py=pT_nil;Node*px=pT_root;while(px!=pT_

6、nil)px-max=max(pz-high,px-max);py=px;if(pz-lowlow)px=px-pLeft;elsepx=px-pRight;)pz-pParent=py;if(py=pT_nil)pT_root=pz;elseif(pz-lowlow)py-pLeft=pz;elsepy-pRight=pz;pz-pLeft=pT_nil;pz-pRight=pT_nil;pz-color=Red;InsertFixUp(pz);)Node*RBT:IntervalSearch(Node*i)Node*x=pT_root;while(x!=pT_nil&(x-highlow|

7、i-highlow)if(x-pLeft!=pT_nil&x-pLeft-max=i-low)x=x-pLeft;elsex=x-pRight;)returnx;)建立的区间树是书上P199图14-4,搜索的区间分别为:2,4,7,9,11,13,22,25,26,26输出信息结构为intx.low-color-max，结果如下：IU（J:UsersAdministratorUeslrtopte5tDebugtest.exep-Hed-3,5-Black-10,6-Red-10,8-Eed-23,15-Black-23,16-Blacl-30,17-Black-20,19-RBd-20,25R

8、ed-30,26Black_26,Inputlowandhigh：240-Red-3,contuine?：Inputlowandhigh：798-Red-23,contuine?：Inputlowandhigh：1113直叠区间contuine?：Inputlowandhigh：222515-Black-23,contuine?：Inputlowandhigh：2626M5-Red-30,contuine?：总结:查找与inti重叠的区间intx的过程从以intx为根的树根开始，逐步向下搜索。当找到一个重叠区间或者x指向T.nil时过程结束。由于基本循环的每次迭代耗费。的时间，又因为n个结点的

9、红黑树的高度是O(logn)，所以该算法耗费O(logn)。算法源代码（描述）#include#include#includeusingnamespacestd;附录(源代码)#defineSIZE10structNodeintlow;inthigh;intmax;stringcolor;Node*pParent;Node*pLeft;Node*pRight;classRBTpublic:RBT()；RBT()；voidLeftRotate(Node*px);左旋voidRightRotate(Node*px);右旋voidInsert(Node*pz);插入voidInsertFixUp(N

10、ode*pz);调整voidInorderTreeWalk(Node*px)中序遍历Node*GetRoot()returnthis-pT_root;Node*GetNil()returnthis-pT_nil;Node*IntervalSearch(Node*i);private:Node*pT_nil;Node*pT_root;RBT:RBT()pT_nil=newNode;pT_nil-color=Black;pT_nil-max=0;pT_root=pT_nil;RBT:RBT()if(pT_nil!=NULL)deletepT_nil;voidRBT:LeftRotate(Node*

11、px)Node*py=px-pRight;px-pRight=py-pLeft;if(py-pLeft!=pT_nil)py-pLeft-pParent=px;py-pParent=px-pParent;if(px-pParent=pT_nil)pT_root=py;elseif(px=px-pParent-pLeft)px-pParent-pLeft=py;py；elsepx-pParent-py-pLeft=px;px-pParent=py;py-max=px-max;px-max=max(px-max,max(px-pLeft-max,px-pRight-max);voidRBT:Rig

12、htRotate(Node*py)Node*px=py-pLeft;py-pLeft=px-pRight;px-pRight-pParent=py;px-pParent=py-pParent;if(py-pParent=pT_nil)pT_root=px;elseif(py=py-pParent-pLeft)py-pParent-pLeft=px;elsepy-pParent-pRight=px;px-pRight=py;py-pParent=px;px-max=py-max;py-max=max(py-max,max(py-pLeft-max,py-pRight-max);voidRBT:I

13、nsert(Node*pz)pz-max=pz-high;Node*py=pT_nil;Node*px=pT_root;while(px!=pT_nil)px-max=max(pz-high,px-max);py=px;if(pz-lowlow)px=px-pLeft;elsepx=px-pRight;pz-pParent=py;if(py=pT_nil)pT_root=pz;elseif(pz-lowlow)py-pLeft=pz;else一py-pRight=pz;pz-pLeft=pT_nil;pz-pRight=pT_nil;pz-color=Red;InsertFixUp(pz);v

14、oidRBT:InsertFixUp(Node*pz)Node*py=NULL;while(Red=pz-pParent-color)if(pz-pParent=pz-pParent-pParent-pLeft)py=pz-pParent-pParent-pRight;if(py-color=Red)pz-pParent-color=Black;py-color=Black;pz-pParent-pParent-color=Red;pz=pz-pParent-pParent;elseif(pz=pz-pParent-pRight)pz=pz-pParent;LeftRotate(pz);pz-

15、pParent-color=Black;pz-pParent-pParent-color=Red;elseif(pz-pParent=pz-pParent-pParent-pRight)py=pz-pParent-pParent-pLeft;if(py-color=Red)pz-pParent-color=Black;py-color=Black;pz-pParent-pParent-color=Red;pz=pz-pParent-pParent;RightRotate(pz-pParent-pParent);elseif(pz=pz-pParent-pLeft)pz=pz-pParent;R

16、ightRotate(pz);pz-pParent-color=Black;pz-pParent-pParent-color=Red;LeftRotate(pz-pParent-pParent);pT_root-color=Black;voidRBT:InorderTreeWalk(Node*px)if(px!=pT_nil)InorderTreeWalk(px-pLeft);coutlow-color-maxpRight);Node*RBT:IntervalSearch(Node*i)Node*x=pT_root;while(x!=pT_nil&(x-highlowIIi-highlow)if(x-pLeft!=pT_nil&x-pLeft-max=i-low)x=x-pLeft;elsex=x-pRight;returnx;intmain()RBTrbt;inta102=16,21,8,9,25,30,5,8,15,23,17,19,26,26,0,3,6,1。,19,20;u-工rNode*ptemp=for(inti=0;i10;i+)ptempi.low=ai0;ptempi