資源描述：
《紅黑樹實驗報告》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、紅黑樹實驗報告一、紅黑樹特點簡介紅黑樹(Red?BlackTree)是二叉搜索樹(BinarySearchTree)的一種。二叉搜索樹在最壞的情況下可能會變成一個鏈表(當(dāng)所有節(jié)點按從小到大的順序依次插入后)。這種低效產(chǎn)生的原因是樹沒有維持一定的平衡性，要提高搜索效率，就要想辦法來維持樹左邊的平衡，也就是要盡時降低樹的高度，可行的做法就是用一些策略在每次修改樹的內(nèi)容之后都調(diào)整樹的結(jié)構(gòu)，使之滿足一定的平衡條件。其中一種滿足一定平衡條件而且目前應(yīng)用廣泛的是紅黑樹。它可以在每一次插入或刪除節(jié)點之后都會花0(logN)的時間來對樹的結(jié)構(gòu)作修改，以保持樹的平衡
2、。而紅黑樹的查找方法與二叉搜索樹完全一樣，也能夠在O(logN)時間上完成。而紅黑樹的插入和刪除節(jié)點的的方法只是在原二叉搜索樹搜索和刪除算法Z后經(jīng)過一定的過程來維持紅黑樹的性質(zhì)不變。紅黑樹的每個節(jié)點上的屬性除了有一個key、3個指針：parent、left、right以外，還多了一個屬性：coloro它只能是兩種顏色：紅或黑，當(dāng)然也可以再加一些以key來索引的數(shù)據(jù)。而紅黑樹除了具有二叉搜索樹的所有性質(zhì)之外，還具有以下5點性質(zhì)：1.每個節(jié)點是黑色的或是紅色的。2.根節(jié)點是黑色的。3.空節(jié)點是黑色的(紅黑樹中，根節(jié)點的parent以及所有葉節(jié)點left
3、、right都不指向NULL,而是指向一個定義好的空節(jié)點，這樣可以保持算法的一致性，簡化算法)。4.紅色節(jié)點的父、左子、右子節(jié)點都是黑色。5.在任何一棵子樹中，每一條從根節(jié)點向下走到空節(jié)點的路徑上包含的黑色節(jié)點數(shù)量都相同。二、紅黑樹構(gòu)造過程為了滿足上述5條規(guī)則，在進行節(jié)點插入時需要進行如下操作；先按二叉搜索樹規(guī)則進行插入，之后進行調(diào)整。分為5種調(diào)整情況：easel,case2,case3,case4,case5；Casel：若插入的是根節(jié)點，則不作操作，完成調(diào)整。否則轉(zhuǎn)入case2；Case2：若插入節(jié)點是黑色節(jié)點，則不作操作，完成調(diào)整。否則轉(zhuǎn)入c
4、ase3；Case3：若插入的節(jié)點的叔叔節(jié)點是紅色，則更改叔父兩節(jié)點顏色為黑色，置插入點為祖父節(jié)點，之后進入caselo否則轉(zhuǎn)入case4；Case4：若插入節(jié)點、父節(jié)點和祖父節(jié)點不在同一條直線，以父為軸進行一次旋轉(zhuǎn)，使節(jié)點、父節(jié)點和祖父節(jié)點在同一條直線。否則進入case5；Case5：以祖父為軸進行一次旋轉(zhuǎn)，并且更改祖父節(jié)點為紅色，父節(jié)點為紅色。三、紅黑樹代碼注：僅實現(xiàn)插入操作和存儲讀取操作1.TextMain.java*Author:BYC*Number:71110214*Date:2012-5-20*/importjava.io.File;i
5、mportjava.io.FilelnputStream;importjava.io.FileOutputStream;importjava.io」OException;importjava.io.ObjectlnputStream;importjava.io.ObjectOutputStream;importjava.util.Random;publicclassTestMain{publicstaticvoidmain(String[]args)throwslOException{inti=0;longstartCon二System.curre
6、ntTimeMillisf);RedBlackTreerbt=newRedBlackTree();Randomrandom=newRandom();intrandomNum=0;//Insertonemillionnumberswhile(i<=500000)(randomNum=random.nextlnt(lOOOOOOO);rbt.insertNode(randomNum);i++；}longendCon=System,currentTimelVlillis();System.out.println(HConstructOverlTime:1
7、1);System.out.println((newDouble(endCon-startCon))/1000);//SavetheObjectlongstartSave=System.currentTimeMillis();FilefilePath=newFile(nE:/tree.tmpH)；FileOutputStreamfileOut=newFileOutputStream(filePath);ObjectOutputStreamobjectOut=newObjectOutputStream(fileOut);objectOut.write
8、Object(rbt);objectOut.close();fileOut.close();longendSave=Sys
