數據結構 3 二叉查找樹、紅黑樹、旋轉與變色理解與使用

2020 年 3 月 10 日
筆記

這裡再來複習一下二叉樹的概念：

每個節點下子元素不可超過兩個，必須是0個或者一個或則兩個
二叉樹是一種有序樹。

理解了這些，我們這節要學習的內容就是有關於二叉查找樹以及有關紅黑樹。

二叉查找樹

從這個名字，可以簡單理解一下，他是為了解決什麼被發明出來的。當然是查找了。因為名字自帶查找。哈哈開個玩笑。其實就是為了方便查找

特徵：左邊子元素的值一定 <= 根節點
特徵：右邊子元素的值一定 >= 根節點

這就是一個典型的二叉查找樹，比如我們查找一個2的元素位置

從根節點出發。5比2大，向著左節點4
4比2大，向著左節點
到達2的位置。

二叉查找樹使用二分法的思想，將元素的位置唯一指定出來。查找最大次數=二叉樹高度。

二叉查找樹缺陷

這麼nice的二分法查找樹，也不是沒有缺陷的，世界上沒有任何一個完美的東西。
所以，它的缺陷就是：如果我們的元素全部都是小於根節點的，那就變成這樣的一個東西了。

這樣，若是查找一個關於7 的元素，那麼直接亂套了。直接和線性的數組就沒有區別了。還是需要一個個遍歷。

為了解決這種缺陷，下面這個東西出現了！

紅黑樹

紅黑樹，是一種自我平衡的二叉查找樹，說白了就是比二叉查找樹更加Plus
HashMap 再JDK 8當中。若鏈表長度超過8，則轉換為紅黑樹。這也是一種特別好用的數據結構。所以說。很重要

特點

節點要麼是紅色/黑色（名字中自帶的屬性）
根節點是黑色的。
葉子節點是黑色的空節點
每個紅色節點下面都有兩個黑色節點
從任意節點到每個葉子節點路徑都都包含相同數目的黑色節點

插入一個新值

在插入一個新值的時候，可能會使紅黑樹違反上面的5條規則，這個時候需要進行變色和旋轉，我們逐一來講解。

假設向當前紅黑樹插入一個 21 節點。

21比22小，所以只能放到22左邊的位置。這裡問題也就來了：

為啥這個節點必須是紅色的而不能是黑色？

葉子節點必須是黑色空節點，所以，紅色節點下必須有兩個黑色節點，所以該節點必須是紅色。

當然，又往上面看的話，你就會發現：22 是紅色節點，紅色節點必須包含兩個黑色節點？這又衝突了。怎麼辦？

節點的變色

這裡嘗試將22 節點變為黑色。這樣的話，下面的規則滿足了。但是從17號元素出發。到葉子節點。左邊的線路有三個黑色節點，左邊只有兩個。

從任意節點到每個葉子節點路徑都都包含相同數目的黑色節點

為了規則的完整性，繼續變色。將25號元素變成紅色

這時候還沒有結束，因為

每個紅色節點下面都有兩個黑色節點

這樣才算完全符合規則規範。

節點的旋轉方法

左旋轉

這裡理解起來會很吃力。我先畫個圖。來理解這裡面涉及到的內容。

父節點被自己的右邊孩子取代。
而原來的父節點則需要成為被取代位置的左節點。

最簡單的方式是將子節點的左節點斷開，掛到父節點上，翻轉一下位置即可。

斷開子節點的左邊節點。
將斷開的這個節點掛到父節點上。
旋轉位置

很好理解吧！

右旋轉順時針旋轉

斷開子節點的右孩子。
掛到父節點上
旋轉位置。

往那邊旋轉，就斷開自己的那邊的孩子，然後掛到父級，將節點變換一下位置即可。

小結

其實紅黑樹的內容了解這麼多就可以了。也沒必要必須鑽牛角尖。只需要懂得紅黑樹這種自平衡的主體思想即可。

參考

https://mp.weixin.qq.com/s/jz1ajDUygZ7sXLQFHyfjWA