紅黑樹略勝AVL樹

AVL樹是一顆高度平衡搜索二叉樹： 要求左右高度差不超過1（嚴格平衡）

有的大佬認為AVL樹太過嚴格，對平衡的要求越嚴格，會帶來更多的旋轉（旋轉也還是會有一定的消耗?。。?/p>

紅黑樹的出發(fā)點：最長路徑不超過最短路徑的2倍（近似平衡）

相對而言，插入同樣的數(shù)據(jù)，AVL樹旋轉更多，紅黑樹旋轉更少（這是優(yōu)勢）

紅黑樹的劣勢：

?我們在進行查找的時候，我們AVL樹最多查找20次左右

紅黑樹最多查找40次左右

雖然紅黑樹查找的次數(shù)比AVL樹多，但是紅黑樹在插入過程中的旋轉更少，更占優(yōu)勢

紅黑樹的概念

紅黑樹，是一種搜索二叉樹，單在每個節(jié)點上增加一個存儲位表示節(jié)點的顏色，可以是Red或Block，通過對任何一條從根到路徑上各個節(jié)點著色方式的限制，紅黑樹確保沒有一條路徑會比其它路徑長出兩倍，因而是接近平衡的

1.每一個節(jié)點不是紅色就是黑色

2.根節(jié)點是黑色的

3.如果一個節(jié)點是紅的，那么它的兩個孩子節(jié)點是黑色的

解讀? ：?? 樹中沒有連續(xù)的紅色節(jié)點

4.對于每個節(jié)點，從該節(jié)點到其所有后代葉節(jié)點的簡單路徑上，均包含有相同的數(shù)目的黑色節(jié)點

解讀? ： 每條路徑的黑色節(jié)點數(shù)量相等

?5.每個葉子節(jié)點都是黑色的（此處的葉子節(jié)點指的是空節(jié)點NIL節(jié)點）

為什么這里指的是空節(jié)點呢？？

?為什么滿足上面性質，紅黑樹就能保證 ： 其最長路徑中節(jié)點個數(shù)不會超過最短路徑節(jié)點個數(shù)的兩倍？？

因為每條路徑上都有相同數(shù)量的黑節(jié)點? 所以：

這顆樹最短路徑? ：? 一定是全黑

?????????? 最長路徑? ：? 一定是一黑一紅

這樣最短路徑一定不超過最長路徑的二倍

紅黑實現(xiàn)代碼

我們在新插入的節(jié)點是應該選擇紅色還是黑色呢？？

?我們來看看插入紅色，會是什么樣？？

發(fā)現(xiàn)如果插入黑色一定挨打，如果插入紅色有可能不用挨打，拍拍屁股就走人了，就算是挨打，也不用太大費周章的解決

?叔叔也是紅的，那我把叔叔也變黑，祖父變紅

?如果這時候? 25就是這顆樹的根，就結束了，沒必要在往后走了（再像辦法把25變?yōu)楹诘模?/p>

?

?這時候我們發(fā)現(xiàn)還有一個小問題，grandfather變成紅了，但是grandfather這時候是根，根不能是紅的，我們還得把grandfather變成黑，即可

我們上面的過程，紅黑樹的插入問題可能光變色就夠了，插入節(jié)點之后最短并沒有超過最長的2倍，也不需要旋轉，降長度

------------------------------------------------------------------------------------------------------------------

一下這種情況就需要旋轉加變色了

?------------------------------------------------------------------------------------------------------------------------------

情況一 ： cur為紅，p為紅，g為黑，u存在且為紅

?具像圖一：

?具像圖二：

?總共有? 4*4*4*4（在ab的任意位置插入，有4種情況） =256 種組合

這些情況是無窮無盡的?。?！

有可能 a b下面還有一個黑節(jié)點，那么cde的子樹就是有兩個黑節(jié)點的子樹了，情況是無窮無盡的了

---------------------------------------------------------------------------------------------------------------------------

情況二? ：?? 還有的情況是光變色解決不了的！?。?！

cur為紅，p為紅 ， g為黑，u不存在? /?? u存在且為黑

?

?

情況三：就是情況二再變形

雙旋 + 變色

?情況一變過來之后，我們看叔叔的情況?。。?/p>

?文章來源地址http://www.zghlxwxcb.cn/news/detail-684618.html

到了這里，關于紅黑樹（AVL樹的優(yōu)化）上的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！