教你透徹了解紅黑樹

《教你透徹了解紅黑樹》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、紅黑樹系列，六篇文章于今日已經(jīng)完成：1、教你透徹了解紅黑樹2、紅黑樹算法的實(shí)現(xiàn)與剖析3、紅黑樹的c源碼實(shí)現(xiàn)與剖析4、一步一圖一代碼，R-BTree5、紅黑樹插入和刪除結(jié)點(diǎn)的全程演示6、紅黑樹的c++完整實(shí)現(xiàn)源碼------------------------------?一、紅黑樹的介紹先來看下算法導(dǎo)論對R-BTree的介紹：紅黑樹，一種二叉查找樹，但在每個(gè)結(jié)點(diǎn)上增加一個(gè)存儲位表示結(jié)點(diǎn)的顏色，可以是Red或Black。通過對任何一條從根到葉子的路徑上各個(gè)結(jié)點(diǎn)著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的。?前面說了，紅黑樹，是一種二

2、叉查找樹，既然是二叉查找樹，那么它必滿足二叉查找樹的一般性質(zhì)。下面，在具體介紹紅黑樹之前，咱們先來了解下二叉查找樹的一般性質(zhì)：1.在一棵二叉查找樹上，執(zhí)行查找、插入、刪除等操作，的時(shí)間復(fù)雜度為O（lgn）。???因?yàn)?，一棵由n個(gè)結(jié)點(diǎn)，隨機(jī)構(gòu)造的二叉查找樹的高度為lgn，所以順理成章，一般操作的執(zhí)行時(shí)間為O（lgn）。???//至于n個(gè)結(jié)點(diǎn)的二叉樹高度為lgn的證明，可參考算法導(dǎo)論第12章二叉查找樹第12.4節(jié)。2.但若是一棵具有n個(gè)結(jié)點(diǎn)的線性鏈，則此些操作最壞情況運(yùn)行時(shí)間為O（n）。?而紅黑樹，能保證在最壞情況下，基本的動態(tài)幾何操作的時(shí)間均為O（lgn）。ok，

3、我們知道，紅黑樹上每個(gè)結(jié)點(diǎn)內(nèi)含五個(gè)域，color，key，left，right，p。如果相應(yīng)的指針域沒有，則設(shè)為NIL。一般的，紅黑樹，滿足以下性質(zhì)，即只有滿足以下全部性質(zhì)的樹，我們才稱之為紅黑樹：1）每個(gè)結(jié)點(diǎn)要么是紅的，要么是黑的。2）根結(jié)點(diǎn)是黑的。3）每個(gè)葉結(jié)點(diǎn)（葉結(jié)點(diǎn)即指樹尾端NIL指針或NULL結(jié)點(diǎn)）是黑的。4）如果一個(gè)結(jié)點(diǎn)是紅的，那么它的倆個(gè)兒子都是黑的。5）對于任一結(jié)點(diǎn)而言，其到葉結(jié)點(diǎn)樹尾端NIL指針的每一條路徑都包含相同數(shù)目的黑結(jié)點(diǎn)。（注：上述第3、5點(diǎn)性質(zhì)中所說的NULL結(jié)點(diǎn)，包括wikipedia.算法導(dǎo)論上所認(rèn)為的葉子結(jié)點(diǎn)即為樹尾端的NIL指

4、針，或者說NULL結(jié)點(diǎn)。然百度百科以及網(wǎng)上一些其它博文直接說的葉結(jié)點(diǎn)，則易引起誤會，因，此葉結(jié)點(diǎn)非子結(jié)點(diǎn)）如下圖所示，即是一顆紅黑樹(下圖引自wikipedia：http://t.cn/hgvH1l)：此圖忽略了葉子和根部的父結(jié)點(diǎn)。同時(shí)，上文中我們所說的"葉結(jié)點(diǎn)"或"NULL結(jié)點(diǎn)"，如上圖所示，它不包含數(shù)據(jù)而只充當(dāng)樹在此結(jié)束的指示，這些節(jié)點(diǎn)在繪圖中經(jīng)常被省略，望看到此文后的讀者朋友注意。?二、樹的旋轉(zhuǎn)知識當(dāng)我們在對紅黑樹進(jìn)行插入和刪除等操作時(shí)，對樹做了修改，那么可能會違背紅黑樹的性質(zhì)。為了保持紅黑樹的性質(zhì)，我們可以通過對樹進(jìn)行旋轉(zhuǎn)，即修改樹種某些結(jié)點(diǎn)的顏色及指針

5、結(jié)構(gòu)，以達(dá)到對紅黑樹進(jìn)行插入、刪除結(jié)點(diǎn)等操作時(shí)，紅黑樹依然能保持它特有的性質(zhì)（如上文所述的，五點(diǎn)性質(zhì)）。樹的旋轉(zhuǎn)，分為左旋和右旋，以下借助圖來做形象的解釋和介紹：1.左旋如上圖所示：當(dāng)在某個(gè)結(jié)點(diǎn)pivot上，做左旋操作時(shí)，我們假設(shè)它的右孩子y不是NIL[T]，pivot可以為樹內(nèi)任意右孩子而不是NIL[T]的結(jié)點(diǎn)。左旋以pivot到y(tǒng)之間的鏈為“支軸”進(jìn)行，它使y成為該孩子樹新的根，而y的左孩子b則成為pivot的右孩子。來看算法導(dǎo)論對此操作的算法實(shí)現(xiàn)（以x代替上述的pivot）：1.?LEFT-ROTATE(T,?x)??1.1??y?←?right[x]??

6、?Set?y.??2.2??right[x]?←?left[y]????????Turn?y's?left?subtree?into?x's?right?subtree.??3.3??p[left[y]]?←?x??4.4??p[y]?←?p[x]???????????????Link?x's?parent?to?y.??5.5??if?p[x]?=?nil[T]??6.6?????then?root[T]?←?y??7.7?????else?if?x?=?left[p[x]]??8.8?????????????then?left[p[x]]?←?y??9.9?

7、????????????else?right[p[x]]?←?y??10.10??left[y]?←?x???????????????Put?x?on?y's?left.??11.11??p[x]?←?y??2.右旋右旋與左旋差不多，再此不做詳細(xì)介紹。?對于樹的旋轉(zhuǎn)，能保持不變的只有原樹的搜索性質(zhì)，而原樹的紅黑性質(zhì)則不能保持，在紅黑樹的數(shù)據(jù)插入和刪除后可利用旋轉(zhuǎn)和顏色重涂來恢復(fù)樹的紅黑性質(zhì)。至于有些書如STL源碼剖析有對雙旋的描述，其實(shí)雙旋只是單旋的兩次應(yīng)用，并無新的內(nèi)容，因此這里就不再介紹了，而且左右旋也是相互對稱的，只要理解其中一種旋轉(zhuǎn)就可以了。?三、紅黑樹

8、插入、刪除操作的具體實(shí)現(xiàn)