資源描述：
《紅黑樹源程序》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、GeneratedbyFoxitPDFCreator?FoxitSoftwarehttp://www.foxitsoftware.comForevaluationonly.文件:G:研一資料(下)算法導(dǎo)論RBTreeRBTree.cpp2011/4/8,16:32:30RBTreeRBTree.cpp2011/4/8,16:32:30/*作者：黃樂君學(xué)校：中國科學(xué)技術(shù)大學(xué)日期：2011-3-20*//*題目要求紅黑樹、二叉搜索樹的實現(xiàn)和性能比較問題描述：實現(xiàn)紅黑樹、二叉搜索樹相關(guān)算法：插入（紅黑樹涉及樹的調(diào)整：左旋、右旋等），刪
2、除，搜索（指定Key值節(jié)點）。另外，紅黑樹實現(xiàn)計算樹黑高的算法。實驗要求：1).插入測試，輸入13,8，11，17，15，6，1，22，25，27，建立紅黑樹，按照紅黑樹信息輸出方式輸出整棵紅黑樹以及黑高。2).刪除測試，刪除1）中紅黑樹中Key=15的節(jié)點，按照紅黑樹信息輸出方式輸出調(diào)整后的整棵紅黑樹以及黑高。3).隨機(jī)產(chǎn)生300,000個不同自然數(shù)Key值（1－300,000，每個數(shù)出現(xiàn)一次，出現(xiàn)順序隨機(jī)），建立紅黑樹，查找Key=15000的節(jié)點，輸出查找花費時間。用上面的數(shù)據(jù)，建立二叉搜索樹，查找Key=15000的節(jié)點，輸出查找
3、花費時間。4).重復(fù)3－5次3）中操作，求各自平均時間。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é)點的高度,在PrintRBTree函數(shù)里使用*//*構(gòu)造葉子結(jié)點*/voidInitLeafNode();/*創(chuàng)建一個新的樹結(jié)點*/第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é)點*/voidPrintRBTree(RBTreeT);/*查找樹中與key值相同的結(jié)點，返回該結(jié)點的指針*/RBTreeTreeNodeSearch(RBTreeT,intkey,int&outcome);/*紅黑樹的黑高度*/intBlackHeight(RBTreeT);/*計算查詢key=15000所用的時間*/voidPrintSearchTime(RBTreeT,inttimes,intoutcome,intrb);voidInitLeafNode()//構(gòu)造葉子結(jié)點{nil=(RBTr
8、ee)malloc(sizeof(RBTree));root=(RBTree)malloc(sizeof(RBTree));nil->color=BLACK;nil->left=NULL;ni
