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

《算法设计与分析》上机报告姓名：学号：日期：上机题目：区间树上的重叠区间查找算法实验环境：CPU:2.10GHz;内存:2G;操作系统：Win764位;软件平台：VisualStudio2008;一、算法设计与分析：题目一:区间树的构造基本概念：区间：一个事件占用的时间闭区间：实数的有序对[t1,t2]，使t1≤t2区间的对象表示：[t1,t2]可以用对象i表示，有两个属性：low[i]=t1//起点或低点high[i]=t2//终点或高点区间的重叠：]}[][{]}[][{ihighilowandihighilowii数据结构：本质上是将红黑树扩充，方法如下：tep1：基本结构以红黑树为基础，对Tx，x包含区间int[x]的信息(低点和高点),key=low[int[x]];Step2：附加信息max[x]=max(high[int[x]],max[left[x]],max[right[x]])Step3：维护附加信息(有效性)由定理14.1及max的定义有效Step4：开发新操作查找与给定区间重叠的区间keymax节点x题目二：查找算法IntervalSearch(T,i)基本思想step1：x←root[T]；//从根开始查找step2：若x≠nil[T]且i与int[x]不重叠ifx的左子树非空且左子树中最大高点≥low[i]thenx←left[x]；//到x的左子树中继续查找else//左子树必查不到，到右子树查x←right[x]；step3：返回x//x=nilori和x重叠由于区间树是红黑树的简单扩重，因此区间树相关操作的实现如左旋、右旋、插入，插入调整等与红黑树基本相同，具体而言，仅仅在左旋和右旋的操作中维护max域的取值争取即可，其他与红黑树操作完全相同。二、核心代码：题目一：区间树的构造typedefstructnode{intlow;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;py-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;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_nil){px-max=max(pz-high,px-max);py=px;if(pz-lowpx-low)px=px-pLeft;elsepx=px-pRight;}pz-pParent=py;if(py==pT_nil)pT_root=pz;elseif(pz-lowpy-low)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-highi-low||i-highx-low)){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]输出信息结构为int[x].low-color-max，结果如下：总结：查找与int[i]重叠的区间int[x]的过程从以int[x]为根的树根开始，逐步向下搜索。当找到一个重叠区间或者x指向T.nil时过程结束。由于基本循环的每次迭代耗费O(1)的时间，又因为n个结点的红黑树的高度是O(logn)，所以该算法耗费O(logn)。附录（源代码）算法源代码（C++描述）#includeiostream#includestring#includewindows.husingnamespacestd;#defineSIZE10structNode{intlow;inthigh;intmax;stringcolor;Node*pParent;Node*pLeft;Node*pRight;};classRBT{public:RBT();~RBT();voidLeftRotate(Node*px);//左旋voidRightRotate(Node*px);//右旋voidInsert(Node*pz);//插入voidInsertFixUp(Node*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*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;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;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_nil){px-max=max(pz-high,px-max);py=px;if(pz-lowpx-low)px=px-pLeft;elsepx=px-pRight;}pz-pParent=py;if(py==pT_nil)pT_root=pz;elseif(pz-lowpy-low)py-pLeft=pz;elsepy-pRight=pz;pz-pLeft=pT_nil;pz-pRight=pT_nil;pz-color=Red;InsertFixUp(pz);}voidRBT::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;}else{if(pz==pz-pParent-pRight){pz=pz-pParent;LeftRotate(pz);}pz-pParent-color=Black;pz-pParent-pParent-color=Red;RightRotate(pz-pParent-pParent);}}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;}else{if(pz==pz-pParent-pLeft){pz=pz-pParent;RightRotate(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);coutpx-low-px-color'-'px-max',';InorderTreeWalk(px-pRight);}}Node*RBT::IntervalSearch(Node*i){Node*x=pT_root;while(x!=pT_nil&&(x-highi-