中科大软院算法导论区间树实验报告（定稿）_中科大算法导论答案
中科大软院算法导论区间树实验报告（定稿）由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“中科大算法导论答案”。
区间树实验报告
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 程序设计
区间树的操作基本和红黑树的相同，在其基础上增加了一个新方法： INTERVAL_SEARCH(T,i）；它用来找出树中覆盖区间i 的那个结点。如果树中不存在，则返 回nil[T]指针。代码如下：
ITNode* IntervalTree::Interval_Search(Interval i){ ITNode* x=root;while(x!=Nil &&!x->Overlap(i)){ // x!= nil and i doesn't overlap int[x] if(x->left!=Nil && x->left->max>=i.low)x=x->left;else x=x->right;} return x;} 区间树的插入、删除除了有可能改变红黑树性质，还有可能改变结点的max 值。前者 向红黑树那样处理就可以了，又
max[x] = max(high[int[x]], max[left[x]], max[right[x]])为解决后者，增加一方法Nodemax（），让它来维护结点的max 值。Nodemax()如下： void ITNode::NodeMax(ITNode* xl, ITNode* xr){ Type tp=this->interval->high;if(tp max)tp=xl->max;if(tp max)tp=xr->max;this->max=tp;} 在左旋、右旋时调用此方法。
2.3 数据结构设计
基础数据结构选择红黑树，每个结点x 包含一个区间域int[x]，x 的关键字为区间的低 端点low[int[x]]，对树；进行中序遍历就可按低端点的次序列出个区间，结点还包含一个 max[x]，即以x 为根的子树中所有区间的端点的最大.2.4 运行结果
为了增加算法运行时间减少误差，search、insert、delete 的都是树的最小关键字结点，让查找深度尽可能的深。运行时间如下所示，单位:us： T(us)方法
search insert delete 2^4 2.933 14.176 2.933 2^6 3.399 17.098 3.422 2^8 3.422 20.042 3.911 2^10 4.399 17.598 4.547 2^12 3.441 18.087 4.888 运行
平
台
：
2.5 结果分析
根据以上数据作如下t-lg(n)图像：
有图知当n=2^8 时，Insert 操作数据不是很好，出去它可得如下图：
在树规模较小的时候, 会对n 造成比较明显的影响, 3 条测量的曲线中, insert 与lgn 的 曲线增长率最符合，但都大致以lgn 增长。，在n 较小的时候, 算法执行时间受系统本身配置
影响较大, 数据也不会很准确, 这个也可以从表格中看出, 有一些与通常时间偏差较大的记 录, 这个应该和系统的任务调度, 和其他程序的影响有关.2.6 心得体会
由于区间树的很多操作与红黑书相似，此程序最大难点在维护结点的max 值。应仔细
分析左旋、右旋、插入、删除时改变那些结点的max 值、如何改变结点的max 值，这样编 程时会事半功倍。
区间树与红黑树差别不是很大，很多操作都相似，可考虑从红黑树继承，实现代码重用。例如：
cla ITNode: public RBTNode{ private: Type NodeMax(ITNode* x);public: Type max;//以x 为根的子树中所有区间的端点最大值 Type low;Type high;ITNode(Type ilow=0, Type ihigh=0):RBTNode(ilow), low(ilow), high(ihigh){max=NodeMax(this)} };cla IntervalTree : public RBTree{ public: IntervalTree(Type ilow=0, Type ihigh=0):RBTree(ilow){} void Interval_Insert(ITNode* x){RB_Insert(x);} void Interval_Insert(Type ilow, Type ihigh){Interval_Insert(new ITNode(ilow,ihigh));} void Interval_Delete(ITNode* x){RB_Delete(x);} ITNode* Interval_Search(Interval i);};
