資料結構系列 - 紅黑樹
一、紅黑樹介紹
紅黑樹由Rudolf Bayer於1972年發明,當時被稱為平衡二叉B樹(symmetric binary B-trees),1978年被Leonidas J. Guibas 和 Robert Sedgewick改成一個比較摩登的名字:紅黑樹。
二、紅黑樹與AVL樹比較
紅黑樹AVL樹類似,都是在進行插入和刪除操作時通過特定操作保持二叉查詢樹的平衡,從而獲得較高的查詢效能。自從紅黑樹出來後,AVL樹就被放到了博物館裡,據說是紅黑樹有更好的效率,更高的統計效能。
紅黑樹和AVL樹的區別:紅黑樹使用顏色來標識結點的高度,它所追求的是區域性平衡而不是AVL樹中的非常嚴格的平衡。
三、紅黑樹的工作原理
使用紅黑樹的主要目的是在一定的控制範圍內保持二叉樹的平衡,保持了二叉樹的平衡便能達到更好的查詢效率。
那麼紅黑樹是如何使二叉樹達到平衡的呢? 紅黑樹沒有使用二叉平衡樹那種嚴格的平衡準則,紅黑樹使二叉樹平衡是靠自身的紅黑樹規則來實現的,下面是紅黑樹的規則(共四條):
(1) 每個結點的顏色只能是紅色或黑色,且根結點一定是黑色的。
(2) 如果一個結點是紅的,則它的兩個兒子都是黑的。也就是說在一條路徑上不能出現相鄰的兩個紅色結點,只要有一個紅節點,它的父節點和子節點必然都是黑色的。
(3 )對於每個結點來說,從該結點到其子孫葉結點的所有路徑上包含相同數目的黑結點。
(4 )每個葉子結點都帶有兩個空的黑色結點(被稱為黑哨兵),如果一個結點的只有一個左孩子,那麼這個節點右孩子是一個黑哨兵;如果這個節點只有一個右孩子,那麼這個節點的左孩子是一個黑哨兵。沒有孩子節點的地方,都被黑哨兵填充,目的是為了是紅黑樹為滿足第3條規則進行限制。
紅黑樹的這4個性質中,第4點是比較難理解的,但它卻非常有必要。我們看下面左邊這張圖,如果不使用黑哨兵,它完全滿足紅黑樹性質,結點50到兩個葉結點8和葉結點82路徑上的黑色結點數都為2個。但如果加入黑哨兵後(如右圖中的小黑圓點),葉結點的個數變為8個黑哨兵,根結點50到這8個葉結點路徑上的黑高度就不一樣了,所以它並不是一棵紅黑樹。
圖 紅黑樹示例
思考這樣一個問題: 通過上面的性質為什麼能使二叉樹保持一定的平衡呢?
通過性質3可以知道:從根節點到葉節點路徑上的黑色節點的數目均為n,於是,紅黑樹的最短路徑為全黑,即“黑 –> 黑 –>......... 黑 –> 黑”,即最短路徑長度為n-1(相鄰節點間的距離為1),而最長路徑只能取為紅黑交替“黑 –> 紅 –>......... 紅 –> 黑”,這樣可使黑色節點數量最多,即最長路徑為2(n-1)。通過上面的分析可以得出:在紅黑樹的所有從根節點到葉節點的路徑中,最長路徑不會超過最短路徑的2倍。
可見,紅黑樹使用紅黑二色進行“著色”,目的是利用顏色值做二叉樹的平衡對稱性的檢查,只要插入的節點“著色”滿足紅黑二色的規定,最短路徑與最長路徑不會相差太遠,紅色樹的節點分佈就能大體上達到平衡。當然這種平衡時一種有所放寬的平衡。
四、紅黑樹插入刪除簡介
紅黑樹的插入和刪除過程比較複雜,具體過程留在後面進行總結。總體上來說,紅黑樹在插入一個節點的時候,會將插入的節點著色為紅色,然後再檢查紅黑樹定義的規則是否被破壞,如果破壞需要對子樹進行左右旋轉,這裡的旋轉也涉及到LL、LR、RR、RL四種旋轉方式。紅黑樹的刪除比插入更為複雜,這裡不進行介紹。
五、紅黑樹的效能
一個有n個節點的紅黑樹的高度最大為2log(n + 1) (演算法導論上證明)。在紅黑樹中查詢、插入、刪除的時間為O(log n),其中n是樹種元素的數目.