中科大软院算法导论区间树实验报告.docx

《中科大软院算法导论区间树实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、区间树实验报告1.区间树的实验源码见另外一个文件2.区间树实验分析2.1需求分析基础数据结构选择红黑树，每个结点x包含一个区间域int[x]，x的关键字为区间的低端点low[int[x]]，对树；进行中序遍历就可按低端点的次序列出个区间，结点还包含一个max[x]，即以x为根的子树中所有区间的端点的最大值。如：实验要求：将红黑树扩展为区间树(1)区间的端点为正整数，随机生成；(2)内部节点数为n：2^4，2^6,2^8,2^10,2^12；(3)测试插入，删除，查找的时间并绘出曲线，运行次数为10次；2.2程序设计区间树的操作基本和红黑树的相同，在

2、其基础上增加了一个新方法：INTERVAL_SEARCH(T,i）；它用来找出树中覆盖区间i的那个结点。如果树中不存在，则返回nil[T]指针。代码如下：ITNode*IntervalTree::Interval_Search(Intervali){ITNode*x=root;while(x!=Nil&&!x->Overlap(i)){//x!=nilandidoesn'toverlapint[x]if(x->left!=Nil&&x->left->max>=i.low)x=x->left;elsex=x->right;}returnx;}区间树的

3、插入、删除除了有可能改变红黑树性质，还有可能改变结点的max值。前者向红黑树那样处理就可以了，又max[x]=max(high[int[x]],max[left[x]],max[right[x]])为解决后者，增加一方法Nodemax（），让它来维护结点的max值。Nodemax()如下：voidITNode::NodeMax(ITNode*xl,ITNode*xr){Typetp=this->interval->high;if(tpmax)tp=xl->max;if(tpmax)tp=xr->max;this->max=tp;

4、}在左旋、右旋时调用此方法。2.3数据结构设计基础数据结构选择红黑树，每个结点x包含一个区间域int[x]，x的关键字为区间的低端点low[int[x]]，对树；进行中序遍历就可按低端点的次序列出个区间，结点还包含一个max[x]，即以x为根的子树中所有区间的端点的最大.2.4运行结果为了增加算法运行时间减少误差，search、insert、delete的都是树的最小关键字结点，让查找深度尽可能的深。运行时间如下所示，单位:us：T(us)方法searchinsertdelete2^42.93314.1762.9332^63.39917.0983.

5、4222^83.42220.0423.9112^104.39917.5984.5472^123.44118.0874.888运行平台：2.5结果分析根据以上数据作如下t-lg(n)图像：有图知当n=2^8时，Insert操作数据不是很好，出去它可得如下图：在树规模较小的时候,会对n造成比较明显的影响,3条测量的曲线中,insert与lgn的曲线增长率最符合，但都大致以lgn增长。，在n较小的时候,算法执行时间受系统本身配置影响较大,数据也不会很准确,这个也可以从表格中看出,有一些与通常时间偏差较大的记录,这个应该和系统的任务调度,和其他程序的影响有

6、关.2.6心得体会由于区间树的很多操作与红黑书相似，此程序最大难点在维护结点的max值。应仔细分析左旋、右旋、插入、删除时改变那些结点的max值、如何改变结点的max值，这样编程时会事半功倍。区间树与红黑树差别不是很大，很多操作都相似，可考虑从红黑树继承，实现代码重用。例如：classITNode:publicRBTNode{private:TypeNodeMax(ITNode*x);public:Typemax;//以x为根的子树中所有区间的端点最大值Typelow;Typehigh;ITNode(Typeilow=0,Typeihigh=0):

7、RBTNode(ilow),low(ilow),high(ihigh){max=NodeMax(this)}};classIntervalTree:publicRBTree{public:IntervalTree(Typeilow=0,Typeihigh=0):RBTree(ilow){}voidInterval_Insert(ITNode*x){RB_Insert(x);}voidInterval_Insert(Typeilow,Typeihigh){Interval_Insert(newITNode(ilow,ihigh));}voidInte

8、rval_Delete(ITNode*x){RB_Delete(x);}ITNode*Interval_Search(In