這個呢,是我很久之前就寫了一部分的,本來想把插入刪除的都給寫了,后面由于我的懶惰,一直沒有更新刪除,但這次,我還是不會更,啊哈哈哈哈
迷之分割線,第一次使用Markdown,不太6啊
下面就是正題了.
首先呢,要知道什么是紅黑樹.
在算法導(dǎo)論對R-B Tree的介紹：紅黑樹，一種二叉查找樹，但在每個結(jié)點(diǎn)上增加一個存儲位表示結(jié)點(diǎn)的顏色，可以是Red或Black。通過對任何一條從根到葉子的路徑上各個結(jié)點(diǎn)著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的。
紅黑樹有以下幾個特點(diǎn):
- 每個結(jié)點(diǎn)要么是紅的要么是黑的。
- 根結(jié)點(diǎn)是黑的。
- 每個葉結(jié)點(diǎn)（葉結(jié)點(diǎn)即指樹尾端NIL指針或NULL結(jié)點(diǎn)）都是黑的。
- 如果一個結(jié)點(diǎn)是紅的，那么它的兩個兒子都是黑的。
- 對于任意結(jié)點(diǎn)而言，其到葉結(jié)點(diǎn)樹尾端NIL指針的每條路徑都包含相同數(shù)目的黑結(jié)點(diǎn)。
其次是為什么要用紅黑樹而不用AVL,我個人理解就是AVL是平衡的,每插入刪除一個節(jié)點(diǎn)都會調(diào)整,而且調(diào)整的效率并不高,很可能要調(diào)很多次.而紅黑樹是近似平衡的,最多3次即可調(diào)整完畢,是比較快速的.
接下來就是紅黑樹的插入刪除了.
PS:刪除等我哪天閑下來再更吧...雖然不難,但是我懶啊
紅黑樹的每次插入刪除的調(diào)整的目的都是為了使得這棵樹滿足上面的5個特點(diǎn).所以調(diào)整思路很容易就確定出來的(這里就當(dāng)我扯淡吧,在沒看例子的時候還是挺難想到想全的,膜一下魯?shù)婪颉へ悹柎蟠?.
插入部分
插入的過程相對來說還是比較容易的.因?yàn)樘攸c(diǎn)中說從根到葉節(jié)點(diǎn)的黑節(jié)點(diǎn)數(shù)要相同.所以每次插入的要是是紅色的節(jié)點(diǎn)那就肯定不會影響紅黑樹的這幾個特點(diǎn)了,所以我們就每次插入紅色的節(jié)點(diǎn).但又有個問題,紅節(jié)點(diǎn)的孩子不能是紅色的,所以要進(jìn)行變色調(diào)整.接下來就詳細(xì)描述一下這個過程好了.
1.最簡單的情況插入的位置的父節(jié)點(diǎn)是黑色的,那就直接插就好了,不用做調(diào)整.因?yàn)樗牟迦氩粫绊懠t黑樹的性質(zhì).
2.插入的是根節(jié)點(diǎn),那直接把這個節(jié)點(diǎn)變成黑色就好了,因?yàn)楦?jié)點(diǎn)必須是黑色的.
3.插入的節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色的,這個系列是最麻煩的. 詳細(xì)說一下.
-
3.1父節(jié)點(diǎn)是紅色的且叔叔節(jié)點(diǎn)(叔叔節(jié)點(diǎn)就是父親的兄弟節(jié)點(diǎn))是紅色的.
因?yàn)楦赣H是紅色的,所以必須有爺爺節(jié)點(diǎn)(父親的父節(jié)點(diǎn)).且爺爺是黑色的,那么解決策略就是：將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)涂黑，祖父結(jié)點(diǎn)涂紅，把當(dāng)前結(jié)點(diǎn)指向祖父節(jié)點(diǎn)，從新的當(dāng)前節(jié)點(diǎn)重新開始算法.
插個圖說明下好了
插入前:
Paste_Image.png
插入后:
廢話下,說詳細(xì)點(diǎn)好了,為什么這么做呢.原因:它的插入使得紅黑樹的性質(zhì)被破壞了,所以,我們就先維護(hù)爺爺節(jié)點(diǎn)這一塊往下的子樹,使得其滿足紅黑樹的性質(zhì),然后再往上接著維護(hù).那這么維護(hù)真的可以么,嗯,因?yàn)槿绻麑⒏赣H和叔叔都變黑了,祖父變成紅色,那么這一整顆子樹的從祖父到葉子的黑節(jié)點(diǎn)數(shù)還是和插入這貨之前的一樣,所以這方法是可以的.
- 3.2父節(jié)點(diǎn)是紅色,叔叔節(jié)點(diǎn)是黑色.這個可以用一個圖表來總結(jié).(本人寫字丑,忍忍吧).
上面呢就是總結(jié)出來的.
下面引用個JULY(原文鏈接)的圖來說明下,圖上的圓圈呢是情況的號碼.如果5出現(xiàn),必定接著使用6的方法來進(jìn)行調(diào)整.先湊合著看看,下面詳細(xì)說下
5和6是配套的,因?yàn)椴豢赡苤怀霈F(xiàn)5,出現(xiàn)5都會轉(zhuǎn)到6.簡單的說,5就是將樹調(diào)整成6的適用條件.然后6的調(diào)整原理就是:(舉個例子,用圖中左左的的情況)因?yàn)椴迦胧羌t的,父是紅的,且插入的和父親都是左子,叔叔是黑的,那祖父肯定是黑的,所以變色后右旋一次,路徑中的黑子數(shù)還是一樣的,也沒有紅節(jié)點(diǎn)孩子是紅色,保證了紅黑樹的性質(zhì),所以這個解決方案就是可行的了.
到此插入就講完了,很簡單吧. 有空再更刪除.不用期待,很少有空的,啊哈哈哈.
