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

《区间树上重叠区间查找算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、,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//左子树必查不

3、到，到右子树查x ←right[x]；step3：返回x//x=nilori和x重叠由于区间树是红黑树的简单扩重，因此区间树相关操作的实现如左旋、右旋、插入，插入调整等与红黑树基本相同，具体而言，仅仅在左旋和右旋的操作中维护max域的取值争取即可，其他与红黑树操作完全相同。二、核心代码：题目一：区间树的构造typedefstructnode{intlow;inthigh;intmax;stringcolor;structnode*pParent;structnode*pLeft;structnode*pRight;}Node;voidRBT::LeftRotate(Node*

4、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

5、(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=p

6、x;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->lowlow)px=px->pLeft;elsepx=px->pRight;}pz->pParent=py;if(py==pT_nil)pT_root=

7、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

8、

9、i->highlow)){if(x->pLeft!=pT_nil&&x