介紹
今天我們來介紹另一種平衡二叉樹：紅黑樹（Red Black Tree），紅黑樹由Rudolf Bayer於1972年發明，當時被稱為平衡二叉B樹（symmetric binary B-trees），1978年被Leonidas J. Guibas 和 Robert Sedgewick改成一個比較摩登的名字：紅黑樹。
紅黑樹和之前所講的AVL樹類似，都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。自從紅黑樹出來後，AVL樹就被放到了博物館裡，據說是紅黑樹有更好的效率，更高的統計性能。不過在我了解了紅黑樹的實現原理後，並不相信這是真的，關於這一點我們會在後面進行討論。
紅黑樹和AVL樹的區別在於它使用顏色來標識結點的高度，它所追求的是局部平衡而不是AVL樹中的非常嚴格的平衡。之前我們在講解AVL樹時，已經領教過AVL樹的復雜，但AVL樹的復雜比起紅黑樹來說簡直是小巫見大巫。紅黑樹是真正的變態級數據結構。
首先來一個Silverlight做的紅黑樹的動畫，它有助於幫你理解什麼是紅黑樹。這裡需要注意，必須安裝Silverlight 2.0 RTW 才能正常運行游戲，下載地址：
http://www.microsoft.com/silverlight/resources/install .ASPx?v=2.0
使用注意事項：
l 結點只接收整數，如果在添加和刪除操作中輸入非法字串，則會隨機添加或刪除一個0~99之間的整數。
l 可以不在編輯框中輸入數字，直接單擊添加和刪除按鈕進行添加和刪除操作。
l 可以拖動拖動條控制動畫速度。
紅黑樹的平衡
紅黑樹首先是一棵二叉查找樹，它每個結點都被標上了顏色（紅色或黑色），紅黑樹滿足以下5個性質：
1、每個結點的顏色只能是紅色或黑色。
2、根結點是黑色的。
3、每個葉子結點都帶有兩個空的黑色結點（被稱為黑哨兵），如果一個結點n的只有一個左孩子，那麼n的右孩子是一個黑哨兵；如果結點n只有一個右孩子，那麼n的左孩子是一個黑哨兵。
4、如果一個結點是紅的，則它的兩個兒子都是黑的。也就是說在一條路徑上不能出現相鄰的兩個紅色結點。
5、對於每個結點來說，從該結點到其子孫葉結點的所有路徑上包含相同數目的黑結點。
紅黑樹的這5個性質中，第3點是比較難理解的，但它卻非常有必要。我們看圖1中的左邊這張圖，如果不使用黑哨兵，它完全滿足紅黑樹性質，結點50到兩個葉結點8和葉結點82路徑上的黑色結點數都為2個。但如果加入黑哨兵後（如圖1右圖中的小黑圓點），葉結點的個數變為8個黑哨兵，根結點50到這8個葉結點路徑上的黑高度就不一樣了，所以它並不是一棵紅黑樹。
要看真正的紅黑樹請在以上動畫中添加幾個結點，看看是否滿足以上性質。
