資源描述:
《紅黑樹源程序》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、GeneratedbyFoxitPDFCreator?FoxitSoftwarehttp://www.foxitsoftware.comForevaluationonly.文件:G:研一資料(下)算法導(dǎo)論RBTreeRBTree.cpp2011/4/8,16:32:30RBTreeRBTree.cpp2011/4/8,16:32:30/*作者:黃樂君學(xué)校:中國(guó)科學(xué)技術(shù)大學(xué)日期:2011-3-20*//*題目要求紅黑樹、二叉搜索樹的實(shí)現(xiàn)和性能比較問題描述:實(shí)現(xiàn)紅黑樹、二叉搜索樹相關(guān)算法:插入(紅黑樹涉及樹的調(diào)整:左旋、右旋等),刪
2、除,搜索(指定Key值節(jié)點(diǎn))。另外,紅黑樹實(shí)現(xiàn)計(jì)算樹黑高的算法。實(shí)驗(yàn)要求:1).插入測(cè)試,輸入13,8,11,17,15,6,1,22,25,27,建立紅黑樹,按照紅黑樹信息輸出方式輸出整棵紅黑樹以及黑高。2).刪除測(cè)試,刪除1)中紅黑樹中Key=15的節(jié)點(diǎn),按照紅黑樹信息輸出方式輸出調(diào)整后的整棵紅黑樹以及黑高。3).隨機(jī)產(chǎn)生300,000個(gè)不同自然數(shù)Key值(1-300,000,每個(gè)數(shù)出現(xiàn)一次,出現(xiàn)順序隨機(jī)),建立紅黑樹,查找Key=15000的節(jié)點(diǎn),輸出查找花費(fèi)時(shí)間。用上面的數(shù)據(jù),建立二叉搜索樹,查找Key=15000的節(jié)點(diǎn),輸出查找
3、花費(fèi)時(shí)間。4).重復(fù)3-5次3)中操作,求各自平均時(shí)間。5).在1)-4)的紅黑樹算法基礎(chǔ)上修改完成P30714.1-4算法OS_Key_Rank(T,k).輸入1,2,3,4,5,6,7,8建樹,k=6,輸出OS_Key_Rank的返回值。*/#include#include#include#include#defineRED0#defineBLACK1#defineNUM20#defineMAX_NUM300000typedefstructRBTNode{int
4、key;structRBTNode*parent,*left,*right;intcolor;intsize;//擴(kuò)張紅黑樹}RBTNode,*RBTree;RBTreenil,root;intprintnode=0;/*記錄結(jié)點(diǎn)的高度,在PrintRBTree函數(shù)里使用*//*構(gòu)造葉子結(jié)點(diǎn)*/voidInitLeafNode();/*創(chuàng)建一個(gè)新的樹結(jié)點(diǎn)*/第1頁GeneratedbyFoxitPDFCreator?FoxitSoftwarehttp://www.foxitsoftware.comForevaluationonly.文件:
5、G:研一資料(下)算法導(dǎo)論RBTreeRBTree.cpp2011/4/8,16:32:30RBTreeRBTree.cpp2011/4/8,16:32:30RBTreeCreateNode(intkey,intcolor);/*找出樹種最小的key并返回key的指針*/RBTreeTreeMinimum(RBTreex);/*找出中序遍歷順序下它的后繼并返回它的指針*/RBTreeTreeSuccessor(RBTreex);/*二叉查找樹的插入操作*/voidTreeInsert(RBTree&T,RBTreez);/*左旋
6、*/voidLeftRotate(RBTree&T,RBTreex);/*右旋*/voidRightRotate(RBTree&T,RBTreex);/*紅黑樹的插入操作*/voidRBTreeInsert(RBTree&T,RBTreez);/*紅黑樹插入后調(diào)整顏色達(dá)到紅黑樹*/voidRBTreeInsertFixup(RBTree&T,RBTreez);/*紅黑樹樹的刪除操作*/voidRBTreeDelete(RBTree&T,RBTreez);/*紅黑樹刪除后調(diào)整顏色達(dá)到紅黑樹*/voidRBDeleteFixup(RBTree
7、&T,RBTreez);/*中序打印樹結(jié)點(diǎn)*/voidPrintRBTree(RBTreeT);/*查找樹中與key值相同的結(jié)點(diǎn),返回該結(jié)點(diǎn)的指針*/RBTreeTreeNodeSearch(RBTreeT,intkey,int&outcome);/*紅黑樹的黑高度*/intBlackHeight(RBTreeT);/*計(jì)算查詢key=15000所用的時(shí)間*/voidPrintSearchTime(RBTreeT,inttimes,intoutcome,intrb);voidInitLeafNode()//構(gòu)造葉子結(jié)點(diǎn){nil=(RBTr
8、ee)malloc(sizeof(RBTree));root=(RBTree)malloc(sizeof(RBTree));nil->color=BLACK;nil->left=NULL;ni