細講紅黑樹

寫在前面

紅黑樹也是一棵二叉查找樹，既然有了AVL樹為什麼還需要紅黑樹呢？

之前在了平衡二叉樹AVL實作中講到了為什麼使用平衡二叉樹AVL（解決二叉查找樹退化為類似連結清單的問題），最大的作用就是用于查找，其時間複雜度為O(logn)，但AVL樹插入或删除節點後，若使得高度之差大于1，此時，AVL樹的平衡狀态就被破壞，需要旋轉才能達到平衡。是以如果在插入和删除頻繁的場景中就需要頻繁的調整使之達到平衡，性能也随之下降。

是以，紅黑樹的提出是為了解決平衡樹在插入和删除等操作頻繁的情況。

在了解紅黑之前先看看2-3-4樹。

2-3-4樹

在二叉樹中，每個節點有一個資料項（可以了解為節點的值，key），最多有2個子節點。如果允許每個節點可以有更多的資料項和子節點，就是多叉樹，2-3-4樹就屬于多叉樹，并且還是平衡樹（B樹）。

2-3-4樹是一種階（階，可以了解為節點的分支）為4的B樹，是以也可稱它為4叉樹，主要具備以下性質：

1. 有1個key的節點有2個子節點，有2個key的有3個子節點，有3個key的有4個子節點，對應key的節點分别稱為2節點，3節點，4節點，這也是為什麼叫2-3-4樹的原因
2. 所有的葉子節點總在同一層
3. 每個節點的值從左到右保持了從小到大的順序，兩個key之間的子樹中所有的key一定大于它的父節點的左key，小于父節點的右key。如下

   

如下面這棵2-3-4樹：

在上圖中：

有2個連結的為2節點

有3個連結的為3節點

有4個連結的為4節點

插入操作

2-3-4樹的插入總是在葉子節點且一般不允許插入重複的key。

若插入時的葉子節點不是滿節點（即4節點），如插入資料45，如下：

節點分裂

如果插入節點是4節點，這時候節點就需要分裂才能保證樹的平衡（這裡假設分裂的節點不是根節點），一個4節點可以分裂成一個根節點和兩個子節點（這三個節點各含一個key）然後在子節點中插入。若分裂的節點資料分别用ABC來表示：

若分裂節點的父節點也是滿節點，則按照分裂操作繼續分裂即可。

2-3-4樹的删除如果感興趣的可自己去百度，網上很多

點這

紅黑樹

紅黑樹也是一棵二叉查找樹，也是一棵自平衡樹，具備以下性質：

1. 節點是紅色或黑色（非黑即紅）
2. 根節點是黑色
3. 所有的null節點稱為葉子節點，且都是黑色
4. 所有紅色節點的子節點都是黑色（即沒有連續的紅色節點）
5. 任意一個節點到其葉子節點的所有路勁都包含相同數目的黑色節點

如下面這個常見的紅黑樹：

通過以上性質，可以推出：從根節點到葉子節點的最長路徑不會超過最短路徑的2倍

為什麼？

根據上面的性質5我們知道下圖的紅黑樹每條路徑上都是3個黑結點。是以最短路徑長度為2(沒有紅結點的路徑)。再根據性質4(沒有連續的紅色節點)和性質2，3(葉

子和根必須是黑結點)。那麼我們可以得出：

最短路徑：一條具有3個黑結點的路徑上最多隻能有2個紅結點(紅黑間隔存在)，最短路徑為2。

最長路徑：黑深度為2（根結點也是黑色）的紅黑樹最長路徑為4。

從這一點我們可以看出紅黑樹是大緻平衡的。 (比平衡二叉樹要差一些，AVL的平衡因子最多為1)

注：若以下有說到性質1-5，分别表示上述性質，如性質2表示“根節點是黑色”。

2-3-4樹和紅黑樹的等價關系

紅黑樹起源于2-3-4樹，一顆紅黑樹對應一顆确定的2-3-4樹，一顆2-3-4樹對應多個紅黑樹。

上面的2-3-4樹和紅黑樹看上去完全不同，但實際上是等價的，通過一些規則可以讓2-3-4樹變為紅黑樹，如：

上圖中3節點存在2種情況：

• 右傾：紅色在右邊
• 左傾：紅色在左邊

是以，這就決定了一顆紅黑樹對應一顆确定的2-3-4樹，一顆2-3-4樹對應多個紅黑樹。

然後我們把最開始的那棵2-3-4樹按照上面的規則轉化為紅黑樹，如下：

節點之間的轉化對應如下：

由規則生成的紅黑樹：

那麼到底2-3-4樹和紅黑樹是怎麼對應的？就是上面簡單的替換嗎？那我插入或删除的時候怎麼調整，通過什麼規則去調整，我們繼續往下分析。

左傾紅黑樹

在上面等價替換中，3節點可以轉化為2中不同類型的紅黑樹，即左傾紅黑樹和右傾紅黑樹，下面的内容主要通過左傾紅黑樹來講解。

那什麼是左傾紅黑樹呢？

一個節點要麼有一個子節點，要麼有兩個子節點，如果有一個紅色子節點，那麼這個子節點隻能在左邊，如果有2個紅色子節點，那就是兩邊都是紅色。右傾紅黑樹同理：

了解了左傾紅黑樹，我們再看看紅黑樹的調整和它以及2-3-4樹有什麼關系，繼續往下看。

紅黑樹的調整

根據上面的性質，如果我們在插入一個元素的時候違反了，此時我們需要調整才能使其遵守上述性質。而調整方式隻有以下2種可能：

• 改變節點的顔色
• 對節點進行旋轉

旋轉和變色

左旋：以某個結點作為支點(旋轉結點)，其右子結點變為旋轉結點的父結點，右子結點的左子結點變為旋轉結點的右子結點，左子結點保持不變

右旋：以某個結點作為支點(旋轉結點)，其左子結點變為旋轉結點的父結點，左子結點的右子結點變為旋轉結點的左子結點，右子結點保持不變

這裡的插入操作主要通過從插入節點的過程和左傾紅黑樹以及右傾紅黑樹的規則來分析插入過程中存在的情況。

基本定義：

• 叔父節點：指新節點的父節點的兄弟節點（若不存在叔父節點，則用null表示）
• 祖父節點：指新節點的父節點的父節點
• 插入原則：插入的新節點預設為紅色節點

下面的1-5序号表示從根節點（包括根節點）開始插入的第幾個節點。

1. 建立一棵紅黑樹（

   13

   為根節點，這裡不展示null節點），根據紅黑樹的性質：根節點是黑色

1. 插入第二個節點，此時會存在兩種情況
   • 若插入的節點小于13，則該節點為13的左子節點，若插入節點

     8

     ，此時它就是一棵紅黑樹，也符合左傾紅黑樹的規則。

     

   • 若插入的節點大于13，則該節點為13的右子節點，若插入節點

     17

     。

     此時，節點17為右子節點，不符合左傾紅黑樹的規則，那麼怎麼調整使其平衡？我們上圖還原為一棵2-3-4樹：

     

     這個2-3-4樹其實就是一個3節點，按照左傾的規則（父節點黑色，子節點紅色）把它變為一棵左傾紅黑樹：

     我們把對比一下2-3-4樹和紅黑樹的插入：

     

     通過上圖可以看出，對2-3-4樹來說就是一個3節點，對紅黑樹來說就是插入一個右子節點，做一次左旋轉變色。如果說不左傾的話，那就是第一種情況，既不用旋轉也不用變色
   通過1，2兩步操作我們可以得出第一種情形：

   情形一：插入的新節點位于樹的根上或插入的新節點的父節點是黑色，無需做任何操作即可使其平衡

2. 插入第三個節點，以節點13和17為例，此時存在3種情況
   • 若插入的節點小于13，則該節點為13的左子節點，若插入節點8

     

     根據紅黑樹的性質不能有連續的紅色節點，是以需要對它做調整使其平衡，那麼怎麼調整使其平衡？我們還是還原為一棵2-3-4樹：

     

     再對比一下2-3-4樹和紅黑樹的插入：

     

     通過上圖可以看出，對2-3-4樹來說就是一個4節點，2-3-4樹要變成一棵左傾紅黑樹就就是父黑子紅。對紅黑樹來說就是插入一個左子節點，做一次右旋轉然後變色。這裡的變色怎麼了解？就了解為2-3-4樹變紅黑樹，父黑子紅。

     由于左傾的原因，新節點為其父節點的左子節點，父節點也是其父節點的左子節點，可以得出第二種情形：

     情形二：插入的新節點的父節點是紅色，叔父節點為黑色（若沒有則是null節點，null節點為黑色節點），且新節點為其父節點的左子節點，父節點也是其父節點的左子節點。這種情形隻需要一次右旋變色即可。

     這裡其實可以聯想一下，上面的節點13和17通過左傾使得13為17的左子節點，如果不左傾，按照插入的順序來，應該是這樣的：

     

     是以，若此時我插入節點大于17，那麼剛好和情形二相反，若插入節點25：

     這裡就可以非常簡單的推出第三種情形：

     情形三：插入的新節點的父節點是紅色，叔父節點為黑色（若沒有則是null節點，null節點為黑色節點），且新節點為其父節點的右子節點，父節點也是其父節點的右子節點。這種情形需要一次左旋變色即可。

   • 若插入的節點比13大，比17小，則該節點為13的右子節點，若插入節點15

     

     肯定也是不符合紅黑樹的性質的，這裡直接檢視對比圖：

     這種情況可以看到，插入節點還是形成了一棵2-3-4樹，在按照左傾的規則，先左旋，這時就和上面的情況相同，然後再右旋，在變色，也就形成了最終的紅黑樹。

     情形四：插入的新節點的父節點是紅色，叔父節點為黑色（若沒有則是null節點，null節點為黑色節點），且新節點為其父節點的右子節點，父節點是其父節點的左子節點。這種情形需要先進行一次左旋，然後右旋，最後變色即可。

     同樣，若不左傾，當插入節點15：

     

     情形五：插入的新節點的父節點是紅色，叔父節點為黑色（若沒有則是null節點，null節點為黑色節點），且新節點為其父節點的左子節點，父節點是其父節點的右子節點。這種情形需要先進行一次右旋，然後左旋，最後變色即可。

   • 若插入的節點比17大，則該節點為17的右子節點，若插入節點25

     

     此時，它就是一棵滿足條件的紅黑樹，這種情形就是情形一，無需做任何操作。

     

     是以，連續插入3個節點，對于2-3-4樹形成一個4節點，對于紅黑樹，形成都是這樣：

   

3. 插入第四個節點，以節點13，17，25為例，此時可能存在4種情況，即第四個節點可能為13的左子節點，右子節點，25的左子節點，右子節點。
   • 若為13的左子節點 ，插入節點11，即插入節點在根節點的左邊

     

     上圖中的變色實際就對應2-3-4樹的3節點，3節點左傾變為父黑子紅的左傾紅黑樹，2節點對應黑色節點。
   • 若為13的右子節點，插入節點15，即插入節點在根節點的左邊

     

     上圖中是按照左傾的方式來處理的，如果不左傾則簡單很多，因為不需要左旋，直接變色即可，如下：
   • 若為25的左子節點 ，插入節點22，即插入節點在根節點的右邊

     

   • 若為25的右子節點 ，插入節點27，即插入節點在根節點的右邊

     

     如果不左傾直接變色即可：

     

     上面通過插入第四個節點的分析，可以看到新節點插入時，其父節點和叔父節點都是紅色，若不考慮左傾，它們都是隻做了變色操作，是以得出情形六：

     情形六：若插入節點的父節點和叔父節點都是紅色，則做變色操作即可使其平衡。

至此，紅黑樹插入節點的情形都分析完成，如果了解了2-3-4樹到紅黑樹的轉變，就不用去死記插入節點時會碰到那些情況。

小結

通過上面插入操作的分析，插入的情形可以總結出以下幾點：

• 若插入新節點為根節點或者父節點為黑色，則無需做任何操作（黑父）
• 若插入新節點的父節點和叔父節點都是紅色，則做變色操作即可（紅父紅叔）
• 若插入新節點的父節點為紅色，叔父節點為黑色（紅父黑叔）
  • 若新節點及左子節點，父節點為左子節點，先右旋再變色（子左父左）
  • 若新節點為右子節點，父節點為左子節點，先左旋再右旋再變色（子右父左）
  • 若新節點為左子節點，父節點為右子節點，先右旋再右旋再變色（子左父右）
  • 若新節點為右子節點，父節點為右子節點，先左旋再變色（子右父右）

删除操作

紅黑樹的删除如果還原為2-3-4樹分析個人感覺複雜很多，是以這裡還是按照二叉排序樹的删除方式來分析。紅黑樹的删除和二叉排序樹類似，也分為3種情況，即删除節點無子節點，有1個子節點和有2個子節點三中情況，也就是說紅黑樹的删除要先考慮是否有子節點再考慮删除節點的顔色。是以在紅黑樹的删除中，存在6種情形（3*2）。

無子節點

情形一：删除節點無子節點 ，且删除節點為紅色

由紅黑樹的性質4和5可知，若删除節點為紅色，則其父節點必為黑色，是以這種情況不會破壞紅黑樹的性質，直接删除即可。如下圖删除節點

27

情形二：删除節點無子節點，且删除節點為黑色

這種情況是比較複雜的，建議先看完其他幾種在回頭來看。

情形二的删除情形又分為以下幾種：

① 删除節點的兄弟節點為黑色，且兄兒子與兄同邊（左或右）紅色

上圖中，删除節點D，則經過D路徑的黑色節點減少1個，以P為支點旋轉，将B節點旋轉（左旋）到P的位置，

并把與B同邊的BS節點變為黑色，P節點變為黑色，并将替代節點null删除，達到局部平衡。

同理，若節點D在右邊，節點B，BS在左邊，那就是右旋+變色即可達到平衡。

② 删除節點的兄弟節點為黑色，且兄兒子與兄不同邊（左或右）紅色

将BS和B旋轉（右旋），變色，變成①。

同理，節點D在右邊，節點B，BS在左邊，左旋+變色，變成①。

③ 删除節點的兄弟節點為黑色，且兄弟節點的子節點為黑色

• 若删除節點的父節點P為紅色

  

  如果删除D，經過D節點的路徑上黑色就少了一個，這個時候可以把P變成黑色，這樣删除D後經過D節點路徑上

  的黑色節點就和原來一樣了。但是這樣會導緻經過B節點的路徑上的黑色節點數增加一個，是以這個時候可以

  再将B節點變成紅色，這樣路徑上的黑色節點數就和原來保持一緻。

• 若删除節點的父節點P也為黑色

  

  D節點删除之後，不管怎麼變色都無法使左右平衡，因為左邊少了一個黑色節點，若将D的兄弟節點B變為紅色，P節點的左右子樹的黑色節點相同，但是經過PB路徑的黑色節點會減少1，是以此時需要對P節點（把P當做要删除的節點分析，但不是真的删除）進行平衡操作。

④ 删除節點的兄弟節點為紅色

若删除節點的兄弟節點為紅色，則其父節點必為黑色，且B的子節點也為黑色節點

這裡我們把節點B進行左旋和變色操作：

從上圖可以看出旋轉之後删除節點D的兄弟節點變為了黑色節點BSL，這就是前面分析的情形①或②。

這裡就可以解釋為什麼紅黑樹的删除最多需要三次旋轉：

1. 若BSL的右子節點為紅色，則符合情形①，經過一次旋轉變色，共2次旋轉。
2. 若BSL的左子節點為紅色，則符合情形②，經過一次旋轉變色符合情形①，共3次旋轉。

是以整個過程隻需要旋轉三次即可達到平衡，這也是為什麼删除要優于AVL的原因。

有一個子節點

情形三：删除節點有一個子節點，且删除節點為紅色

這種情況如下：

由紅黑樹的性質4和5可知，在建構一棵紅黑樹的時候，任意節點的路徑都具有相同的黑色節點，且紅色節點和紅色

節點不連續，是以若删除節點為紅色其子節點必為黑色，這樣就破壞了性質5，是以這種情況在建構紅黑樹的時候

就不會存在，是以删除的情況也不會存在。

情形四：删除節點有一個子節點，且删除節點為黑色

若删除節點為黑色，則其子節點必為紅色（為黑色則不滿足性質5），是以删除節點後隻需要用子節點替換然後變

色即可（因為黑色節點被删除，由于性質5，是以需要把子節點在變為黑色）。如删除節點

8

：

有兩個子節點

節點的删除可以通過前驅節點（删除節點左子樹中的最大值）或後繼節點（删除節點右子樹中的最小值）替換掉要删除的節點，若通過後繼節點删除，存在2種情況：

是以，用後繼節點代替要删除節點，轉化為删除後繼節點，通過判斷後繼節點的删除來調整。

若後繼節點是①的情況：

情形五：删除節點有2個子節點

• 若後繼節點successor為紅色
  • 沒有右子節點，對應情形一
  • 若存在右子節點，隻能為黑色，不滿足性質5，對應情形三
• 若後繼節點successor為黑色
  • 沒有右子節點，對應情形二
  • 若存在右子節點，不能為黑色，隻能為紅色，對應情形四

若後繼節點是②的情況：

情形六：删除節點有2個子節點

• • 沒有子節點，對應情形一
  • 若存在子節點，隻能為黑色，不滿足性質5，對應情形三
• • 沒有子節點，對應情形二
  • 若存在子節點，隻能為紅色，對應情形四

有2個節點的删除通過後繼節點的方式，如果是前驅節點的方式，可能又是不一樣的，但分析過程卻是差不多的。

這裡的紅黑樹的删除是根據删除節點是否存在子節點來分析的，但總結一下上面的六種情形，情形五和情形六同時被轉化為上面的一，二，四，是以我們隻需要掌握這三種即可。

判斷屬于那種情形的時候，通過下面的順序：

1. 先看删除節點的顔色
2. 再看兄弟節點的顔色
3. 再看兄弟子節點的顔色（兄弟子節點先看兄弟右子節點右再看兄弟左子節點）
4. 最後看父節點的顔色

紅黑樹和AVL的差別

平衡二叉樹類型	平衡度	新增旋轉次數(最多)	删除旋轉次數(最多)	适用場景
AVL樹	高(|BF|=1)	2	取決于删除節點路徑上的其他節點O(logn)	查詢多，增/删少
	低		3	增/删頻繁

是以，在實際應用中，若搜尋的次數遠遠大于插入和删除，那麼選擇AVL，如果搜尋，插入删除次數幾乎差不多，應該選擇RB。

總結

在學習紅黑樹的時候查閱了很多資料，同時也讓我很頭疼，比如它和AVL的增删效率到底怎麼去計算，明明在新增的時候旋轉的次數都是兩次，有的博文卻說AVL要高于2次，10篇文章就有10種說法，但是我還是堅持自己在實際操作中所記錄下的。

本來準備把代碼貼上來，但是我覺得沒必要，因為在面試中也不會有面試官叫你手寫紅黑樹，如果有，請把鍵盤給他，他行他上。而且對于我們實際開發也沒有太大用處，也可能一輩子都不會去手寫一個紅黑樹，比如你不會去自己實作HashMap，是以沒有必要動不動就什麼死磕紅黑樹的，我們隻需要知道他的基本邏輯就行了，如新增的時候怎麼旋轉保持平衡，删除的時候怎麼旋轉保持平衡的邏輯就夠了。而在你有一定代碼能力之後，很可能你就自己能寫一個簡單的demo了，寫代碼的前提就是要清晰的知道邏輯。

這裡還是把代碼提供出來，需要的可自行去下載下傳：

data-structure

之前有人問上面的動圖是怎麼做的，資料結構可視化：

Data Structure Visualizations

參考

• 紅黑樹删除節點——這一篇就夠了
• AVL樹和紅黑樹有什麼差別