[programming]RedBlackTree

紅黑樹兩個條件

1. 兩個紅子不能互為親子
2. 由根(root)至每個葉(leaf)的路徑(path)上，黑子數相同

如果將[1,2,...15]共15個key插入紅黑樹，最後紅黑樹的外形，不會像是完美的(optimal)二元樹(Binary Search Tree)一樣是個對稱的金字塔。紅黑樹會變得左邊高度2，右邊高度5。



看起來好像不太好，你很怕[16.17.18]等key加上去，樹右方會無限制地變長。但實際上插入[16,17]後，樹右方仍只有5。




再加入[18]後，紅黑樹就開始左旋，讓左方分攤一節高度。右邊高度還是只有5。



因為有一、二的條件限制，樹左邊是3黑子，那樹右邊至多是[黑紅黑紅黑紅]，如果再繼續加上去的話，樹就會左旋，讓樹左邊分攤重量。

因此，紅黑樹的最長一邊(此例中為右邊)最多不會超過2⌈logN⌉，紅黑樹的search複雜度是在O(logN)。

紅黑樹跟一般的二元樹有何不同？

• 由於條件二，紅黑樹會算每一側的黑子數，所以不會過於偏斜

紅黑樹跟力求完美平衡的二元樹又有何不同？

• 紅黑樹允許紅子參雜在其中一側，而且只算黑子數，所以不會為了力平衡，使得旋轉次數太多。又由於條件一，避免兩個紅子互為親子，所以不會發生[黑紅紅紅紅...紅]的情況。

紅黑樹是平衡樹與一般二元樹的折衷之作，