區(qū)間樹上重疊區(qū)間查找算法

1、。解一算法設(shè)計(jì)與分析上機(jī)報(bào)告姓名：學(xué)號(hào)：日期：上機(jī)題目：區(qū)間樹上的重疊區(qū)間查找算法實(shí)驗(yàn)環(huán)境：CPU:2.10GHz;內(nèi)存:2G;操作系統(tǒng)：Win764位；軟件平臺(tái)：VisualStudio2008;題目一:區(qū)間樹的構(gòu)造基本概念：區(qū)間：一個(gè)事件占用的時(shí)間閉區(qū)間：實(shí)數(shù)的有序?qū)1,t2,使t1Wt2區(qū)間的對(duì)象表示：t1,t2可以用對(duì)象i表示，有兩個(gè)屬性：lowi=t1/起點(diǎn)或低點(diǎn)highi=t2/終點(diǎn)或高點(diǎn)區(qū)間的重疊：?ilowi歷衛(wèi)薄andlow漫highi數(shù)據(jù)結(jié)構(gòu)：本質(zhì)上是將紅黑樹擴(kuò)充，方法如下：tep1：基本結(jié)構(gòu)以紅黑樹為基礎(chǔ)，對(duì)xT,x包含區(qū)間intx的信息(低點(diǎn)和高點(diǎn)),key=lowi

2、ntx;Step2：附加信息maxx=max(highintx,maxleftx,maxrightx)Step3：維護(hù)附加信息(有效性)由定理14.1及max的定義有效Step4：開發(fā)新操作查找與給定區(qū)間重疊的區(qū)間keymax節(jié)點(diǎn)x題目二：查找算法IntervalSearch(T,i)基本思想step1：x-rootT；從根開始查找step2：若x/nilT且i與intx不重疊ifx的左子樹非空且左子樹中最大高點(diǎn)三lowithenx-leftx；至x的左子樹中繼續(xù)查找else/左子樹必查不到，到右子樹查x-rightx；step3：返回xx=nilori和x重疊由于區(qū)間樹是紅黑樹的簡(jiǎn)單擴(kuò)重，因

3、此區(qū)間樹相關(guān)操作的實(shí)現(xiàn)如左旋、右旋、插入，插入調(diào)整等與紅黑樹基本相同，具體而言，僅僅在左旋和右旋的操作中維護(hù)卮目木全完V4I操max域的取值爭(zhēng)取即可，題目一：區(qū)間樹的構(gòu)造typedefstructnodeintlow;inthigh;intmax;stringcolor;structnode*pParent;structnode*pLeft;structnode*pRight;Node;voidRBT:LeftRotate(Node*px)Node*py=px-pRight;px-pRight=py-pLeft;if(py-pLeft!=pT_nil)py-pLeft-pParent=px;p

4、y-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(px-pLeft-max,px-pRight-max);voidRBT:RightRotate(Node*py)Node*px=py-pLeft;py-pLeft=px-pRight;px-pRight-pParent=py;

5、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=px;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_

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

7、i-highlow)if(x-pLeft!=pT_nil&x-pLeft-max=i-low)x=x-pLeft;elsex=x-pRight;)returnx;)建立的區(qū)間樹是書上P199圖14-4,搜索的區(qū)間分別為:2,4,7,9,11,13,22,25,26,26輸出信息結(jié)構(gòu)為intx.low-color-max，結(jié)果如下：IU（J:UsersAdministratorUeslrtopte5tDebugtest.exep-Hed-3,5-Black-10,6-Red-10,8-Eed-23,15-Black-23,16-Blacl-30,17-Black-20,19-RBd-20,25R

8、ed-30,26Black_26,Inputlowandhigh：240-Red-3,contuine?：Inputlowandhigh：798-Red-23,contuine?：Inputlowandhigh：1113直疊區(qū)間contuine?：Inputlowandhigh：222515-Black-23,contuine?：Inputlowandhigh：2626M5-Red-30,contuine?：總結(jié):查找與inti重疊的區(qū)間intx的過程從以intx為根的樹根開始，逐步向下搜索。當(dāng)找到一個(gè)重疊區(qū)間或者x指向T.nil時(shí)過程結(jié)束。由于基本循環(huán)的每次迭代耗費(fèi)。的時(shí)間，又因?yàn)閚個(gè)結(jié)點(diǎn)的

9、紅黑樹的高度是O(logn)，所以該算法耗費(fèi)O(logn)。算法源代碼（描述）#include#include#includeusingnamespacestd;附錄(源代碼)#defineSIZE10structNodeintlow;inthigh;intmax;stringcolor;Node*pParent;Node*pLeft;Node*pRight;classRBTpublic:RBT()；RBT()；voidLeftRotate(Node*px);左旋voidRightRotate(Node*px);右旋voidInsert(Node*pz);插入voidInsertFixUp(N

10、ode*pz);調(diào)整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*

11、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;py；elsepx-pParent-py-pLeft=px;px-pParent=py;py-max=px-max;px-max=max(px-max,max(px-pLeft-max,px-pRight-max);voidRBT:Rig

12、htRotate(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=px;px-max=py-max;py-max=max(py-max,max(py-pLeft-max,py-pRight-max);voidRBT:I

13、nsert(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=pz;elseif(pz-lowlow)py-pLeft=pz;else一py-pRight=pz;pz-pLeft=pT_nil;pz-pRight=pT_nil;pz-color=Red;InsertFixUp(pz);v

14、oidRBT:InsertFixUp(Node*pz)Node*py=NULL;while(Red=pz-pParent-color)if(pz-pParent=pz-pParent-pParent-pLeft)py=pz-pParent-pParent-pRight;if(py-color=Red)pz-pParent-color=Black;py-color=Black;pz-pParent-pParent-color=Red;pz=pz-pParent-pParent;elseif(pz=pz-pParent-pRight)pz=pz-pParent;LeftRotate(pz);pz-

15、pParent-color=Black;pz-pParent-pParent-color=Red;elseif(pz-pParent=pz-pParent-pParent-pRight)py=pz-pParent-pParent-pLeft;if(py-color=Red)pz-pParent-color=Black;py-color=Black;pz-pParent-pParent-color=Red;pz=pz-pParent-pParent;RightRotate(pz-pParent-pParent);elseif(pz=pz-pParent-pLeft)pz=pz-pParent;R

16、ightRotate(pz);pz-pParent-color=Black;pz-pParent-pParent-color=Red;LeftRotate(pz-pParent-pParent);pT_root-color=Black;voidRBT:InorderTreeWalk(Node*px)if(px!=pT_nil)InorderTreeWalk(px-pLeft);coutlow-color-maxpRight);Node*RBT:IntervalSearch(Node*i)Node*x=pT_root;while(x!=pT_nil&(x-highlowIIi-highlow)if(x-pLeft!=pT_nil&x-pLeft-max=i-low)x=x-pLeft;elsex=x-pRight;returnx;intmain()RBTrbt;inta102=16,21,8,9,25,30,5,8,15,23,17,19,26,26,0,3,6,1。,19,20;u-工rNode*ptemp=for(inti=0;i10;i+)ptempi.low=ai0;ptempi