紅黑樹是如何自二叉搜索樹演變而來的？

01-10

我們知道，二叉搜索樹最壞的情況是變成一棵包含一側全空子節點的雙向鏈表。為了避免這種情況，有諸多的平衡二叉搜索樹出現了，其中就有紅黑樹。紅黑樹的插入和刪除操作，都需要進行紅黑樹性質維護，性質維護的操作包含了旋轉，著色等。那麼問題來了：先輩們是通過怎樣的思路，一步步地推導和實現紅黑樹的呢？

這個問題很不錯。

紅黑樹就是一種以二叉樹形式實現了2-3-4樹的想法。

因此紅黑樹的各種操作其實是對應到2-3-4樹的相應操作的。

而2-3-4樹是平衡樹，所以紅黑樹的樣子也就差不多算平衡樹了。

ps：具體來說，紅黑樹其實就3類節點，分別是一黑，一黑一紅，一黑二紅。就是用來對應二，三，四節點的。其他細節的話還是看wiki吧。

pps：如果要問2-3-4樹怎麼來的。。！@#￥%……*

到這裡找

Robert Sedgewick

http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf

由2-3-4樹演化而來，2-3-4樹可以很方便直觀地實現完美平衡。

所謂2-3-4樹可以看做二叉樹的推廣，就是樹中有三種節點：2節點，3節點，4節點。

而n節點就是節點中用n-1個數劃分成n個區間，

比如普通的二叉樹就只有2節點，節點中用一個數劃分成2個區間（大於和小於）。

至於紅黑樹則是用二叉樹的形狀來描述2-3-4樹，這樣就可以復用大部分已經寫好的二叉樹代碼。

然而2-3-4樹節點內部可以有多個數，

所以就用紅色線把節點內部的數字連接起來，至於節點之間就用黑色線連接，這就是紅黑樹的來歷。

開頭我說過，2-3-4樹可以實現完美平衡，這種說法只是在以節點為單位的情況下正確，

而紅黑樹是用二叉樹表達2-3-4樹，2-3-4樹中的節點在紅黑樹中以黑線連接，所以紅黑樹只能是黑平衡。

更詳細的講解可以看Sedgewick的Algorithms，推薦結合Coursera上的動畫演示，更直觀明白

去看algorithms, 4th edition, 肯定比我們這些人講的都清楚。不過我想了想紅黑樹為什麼能實現平衡的原因：

普通的二叉搜索樹的高度受node插入順序的影響，在最壞的情況下，即所有的node按key值由大到小或由小到大依次插入，n個node組成的二叉搜索樹的高度會是n。

紅黑樹想了一種辦法，通過a.允許3節點的存在; b.旋轉操作，使得key值處在中間的節點會被調整到中間來，比如，key值分別為a, f, k，為f的那個節點會通過紅黑樹被調整為a和f的父節點或更靠近root，在a和f的中間，不論插入順序如何，這樣樹就更平衡。

歷史上紅黑樹貌似是派生自2-3-4樹，而非二叉搜索樹，硬要扯的話可以參照這個說法。

通篇建議sedgewick《演算法》第四版

附議

這本書真是淺顯易懂的典範。

可以看一下《演算法》第四版的2-3樹和紅黑樹

授人以魚，不如授之以漁，何況自己都忘了，建議去看sedgewick的《演算法》第四版平衡搜索樹和紅黑樹部分，講得非常清晰。