区间树上重叠区间查找算法(精).doc

《算法设计与分析》上机报告姓名: 学号: 日期: 上机题目: 区间树上的重叠区间查找算法实验环境: CPU : ;内存:2G ;操作系统: Win7 64位;软件平台: Visual Studio 2008 ; 一、算法设计与分析: 题目一:区间树的构造基本概念: 区间:一个事件占用的时间闭区间:实数的有序对[t1,t2] ,使 t1≤ t2 区间的对象表示: [t1,t2] 可以用对象 i表示,有两个属性: low[i]=t1// 起点或低点 high[i]=t2// 终点或高点区间的重叠: ]}[][{ ]}[][{i high i low and i high i low ii?????????数据结构:本质上是将红黑树扩充,方法如下: tep 1:基本结构以红黑树为基础,对Tx??,x包含区间 int[x] 的信息(低点和高点),key=low[int[x]]; Step 2:附加信息 max[x]=max(high[int[x]], max[left[x]], max[right[x]]) Step 3:维护附加信息(有效性)由定理 及 max 的定义?有效 Step 4:开发新操作查找与给定区间重叠的区间 keymax 节点 x 题目二: 查找算法 IntervalSearch(T, i)基本思想 step 1:x← root[T] ; //从根开始查找 step 2:若 x≠ nil[T] 且i与 int[x] 不重叠 ifx的左子树非空且左子树中最大高点≥ low[i] then x← left[x] ; //到x的左子树中继续查找 else //左子树必查不到,到右子树查 x← right[x] ; step 3:返回 x //x=nil ori和x重叠由于区间树是红黑树的简单扩重,因此区间树相关操作的实现如左旋、右旋、插入,插入调整等与红黑树基本相同,具体而言,仅仅在左旋和右旋的操作中维护 max 域的取值争取即可,其他与红黑树操作完全相同。二、核心代码: 题目一:区间树的构造 typedef struct node { int low; int high; int max; string color; struct node *pParent; struct node *pLeft; struct node *pRight; }Node; void RBT::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; else if(px == px->pParent->pLeft ) px->pParent->pLeft = py; else px->pParent->pRight = py; py->pLeft =px; px->pParent = py; py->max = px->max; px->max = max( px->max,max(px->pLeft->max,px->pR