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

算法设计与分析》上机报告
姓名：学号：日期：
上机题目：区间树上的重叠区间查找算法
实验环境：
CPU:;内存:2G;操作系统：Win764位；软件平台：VisualStudio2008;―、算法设计与分析：
题目一;pz->color="Red";InsertFixUp(pz);
}
题目二：查找算法
Node*RBT::IntervalSearch(Node*i)
{
Node*x=pT_root;
while(x!=pT_nil&&(x->high<i->lowIIi->high<x->low))
{
if(x->pLeft!=pT_nil&&x->pLeft->max>=i->low)x=x->pLeft;
else
x=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]为根的树根开始，逐步向下搜索。。由于基本循环的每次迭代耗费0⑴的时间，又因为n个结点的红黑树的高度是O(logn),所以该算法耗费O(logn)。
算法源代码（C++描述）
附录(源代码){
#include<iostream>#includevstring>#>usingnamespacestd;#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;
p