紅黑樹紅黑樹和AVL 樹一樣都是平衡二叉搜索樹。但是 AVL 樹 比紅黑樹更加嚴格AVL 樹要求左右子樹的高度差 1 而紅黑樹只能保證最長路徑不超過最短路徑的 2 倍。AVL 樹通過旋轉控制平衡為了達到它嚴格的規(guī)定需要旋轉的次數較多。紅黑樹通過旋轉 變色控制平衡同時也因為規(guī)定比較寬松所以旋轉的次數少。在插入方面顯然是紅黑樹更具有效率優(yōu)勢。在查找方面由于 AVL樹 比 紅黑樹 更平衡一些所以效率更快但它們的效率都是 O (log n)級別的所以紅黑樹瑕不掩瑜多數情況下使用的都比比AVL樹更多。紅黑樹的規(guī)則上面提到紅黑樹能保證最長路徑不超過最短路徑的 2 倍。它是如何做到的呢這和紅黑樹的構造規(guī)則相關如下1.每個節(jié)點不是紅色就是黑色。2.根節(jié)點是黑色的。3.如果一個節(jié)點是紅色的它的兩個孩子必須是黑色即不能連續(xù)出現兩次紅色節(jié)點。4.對于任意一個節(jié)點從該節(jié)點到其所有NULL節(jié)點的簡單路徑上均包含相同數量的黑色節(jié)點。這四條規(guī)則共同約束了樹的結構最終保證了紅黑樹的核心性質從任意節(jié)點出發(fā)到其所有葉子節(jié)點的最長路徑不會超過最短路徑的 2 倍。舉一些例子仔細觀察你會發(fā)現這些樹都滿足了紅黑樹的規(guī)則同時它們也做到了最長路徑不超過最短路徑的2倍。紅黑樹的調整AVL樹于1962年誕生紅黑樹比它晚了 10 年所謂前人栽樹后人乘涼紅黑樹 的旋轉調整邏輯和 AVL樹 完全一致AVL樹在上一篇博客講過那么我們接下來所需要討論就是紅黑樹的專屬調整邏輯變色。在講調整邏輯之前我們得先搞清楚什么情況下需要調整。從第一個規(guī)則可知新插入的節(jié)點非黑即紅我們來分類討論黑當插入節(jié)點為黑色時我們會違法第四個規(guī)則因為插入一個黑色節(jié)點無論如何都不能保持每條路徑上的黑色節(jié)點相同了注意走到空節(jié)點才算一條路徑所以絕對不能插入黑色節(jié)點。沒錯即使插入節(jié)點是 root 我們也應該插入紅色節(jié)點然后再讓它變色。紅既然不能插入黑色那么插入的必然就是紅色節(jié)點了。但是插入紅色節(jié)點的情況有兩種通過父節(jié)點來區(qū)分。父節(jié)點為黑沒有違法任何規(guī)則即滿足紅黑樹故無需調整。父節(jié)點為紅違反第三個規(guī)則此時我們就需要進行調整了。那么如何調整呢先看圖上圖是一顆新插入了節(jié)點的紅黑樹為了方便說明我們對調整所需的相關節(jié)點進行標記新節(jié)點為 c意為current表示當前節(jié)點新節(jié)點的父節(jié)點為 p 意為parent表示父節(jié)點父節(jié)點的兄弟為 u意為uncle表示 “叔叔” 節(jié)點父節(jié)點的父節(jié)點為 g意為grandparent意為 “爺爺” 節(jié)點。對紅黑樹的調整最關鍵的就是 “叔叔” 節(jié)點。在上面這顆樹中 p 和u 存在且為紅色g 為黑色此時我們將 p 和 u 變?yōu)楹谏玤 變?yōu)榧t色完美解決啦但當 u 不存在或者u 為黑色的時候單純的變色是無法解決問題的比如u 不存在時此時樹的結構違反第四個規(guī)則。從根節(jié)點到 g 再到 g 的右孩子這條路徑比其他路徑少一個黑節(jié)點。那么怎么辦答案是旋轉只需要對 g 為根節(jié)點的樹進行一次右單旋即可解決問題。當 c 節(jié)點插入在 p 的不同位置時使用的旋轉方法不同u 為黑色時u 是黑色節(jié)點的情況是什么樣的按照之前的邏輯既然我們需要調整了那么 c 與 p 必然是紅色節(jié)點g 必然是黑色節(jié)點如果 u 是黑色原來的樹不是違反規(guī)則了嗎我們難道能給一顆違反規(guī)則的樹插入節(jié)點嗎我們當然不能給一顆違反規(guī)則的樹插入節(jié)點但是想象一下當我們某次調整時對 g 進行變色本來是黑色的 g 變成了 紅色。此時如果 g 的父節(jié)點也是紅色那么我們的調整并沒有將樹調整好需要繼續(xù)向上進行我們將 g 設置為 c 當前節(jié)點就有可能出現新的 c 節(jié)點的 u 節(jié)點為黑色的情況。對于這樣一顆樹我們要做的是 變色加旋轉 。經過 變色加旋轉 處理的不需要繼續(xù)向上調整。這里給出插入的核心代碼因為代碼量比較大這里只貼了核心代碼的一部分另一部分邏輯類似。