[TOC] ## 概述 紅黑樹，Red-Black Tree，是一種自平衡（大致平衡）二叉查找樹。紅黑樹在進行插入和刪除時通過特定操作保持二叉樹的平衡，從而獲得較高的查找性能。 &nbsp; 紅黑樹具有以下五個特性： **1. 節點是紅色或黑色。 2. 根是黑色。 3. 所有葉子都是黑色（葉子是NIL節點）。 4. 每個紅色節點必須有兩個黑色的子節點。（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。） 5. 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。** &nbsp; 下面是一個具體的紅黑樹實例：  &nbsp; 通過以上約束強制了紅黑樹的關鍵性質：**從根到葉子的最長的可能路徑不多余最短的可能路徑的兩倍長**。結果是這個樹大致上是平衡的，插入、刪除、查找操作的最壞情況都與樹的高度成比例，不會出現二叉查找樹中左右子樹極度不平衡的情況。 &nbsp; 再來解釋一下為什么"從根到葉子的最長的可能路徑不多余最短的可能路徑的兩倍長"？ 根據性質4和性質5，紅黑樹中最短的可能路徑都是黑色節點，最長的可能路徑有交替的紅色和黑色節點，并且最短路徑和最長路徑有相同數量的黑色節點，這就表明了最長的可能路徑不多余最短的可能路徑的兩倍長。 <br/> ## 紅黑樹的操作 ### 紅黑樹的插入 紅黑樹的插入操作可以分成兩步來理解： 1. 先把新節點掛到紅黑樹相應位置上。 2. 調整紅黑樹，使其滿足紅黑樹的5個性質。 第一步比較簡單，從根節點開始，按二叉查找樹左子小右子大的規則找到插入位置就可以了。我們重點考慮另外一個問題，新插入節點是否會破壞紅黑樹的平衡（不滿足紅黑樹的5個性質），還有如何恢復平衡？ &nbsp; 新增節點或刪除節點之后，紅黑樹為了恢復平衡，有兩大操作： * **recolor 重新標記顏色** * **rotation 旋轉** 先嘗試 recolor，如果 recolor 不能達到紅黑樹的5點要求，接著嘗試 rotation。弄清楚 recolor 和 rotation 的規則也是掌握紅黑樹的關鍵，接下來看看紅黑樹中插入新節點X的邏輯： 1. **將新插入的節點X標記為紅色。（因為標記為紅色不會破壞性質5）** 2. **如果X是根節點root，標記為黑色。** 3. **如果X的父節點是黑色。這種情況不會破壞紅黑樹的特性，不需要處理。** 4. **如果X的父節點是紅色：** 4.1 **如果X的叔父節點也是紅色：** 4.1.1. **將父節點和叔父節點都標記為黑色。** 4.1.2. **將祖父節點標記為紅色** 4.1.3. **然后對X的祖父節點重復步驟2、3。**  上面幾種情況都是 recolor 操作，也就是父節點和叔父節點同為紅色的情況下應該執行的操作。下面來看一下旋轉操作： &nbsp; 4.2. **如果X的叔父節點是黑色，要分4種情況處理：** 4.2.1. **左左：P是G的左節點，且X是P的左節點** 對G節點執行右旋操作，之后交換 P、G 顏色。  &nbsp; 4.2.2. **左右（P是G的左節點，且X是P的右節點）** 先對P節點執行左旋，用X節點替換P節點，然后再應用左左情況。  &nbsp; 4.2.3. **右右（P是G的右節點，且X是P的右節點）** 對G節點執行左旋操作，之后交換 P、G 顏色。  &nbsp; 4.2.4. **右左（P是G的右節點，且X是P的左節點）** 先對P節點執行右旋操作，用X節點替換P節點，然后再應用右右情況  <br/> ### 紅黑樹的刪除 為了容易理解，先列一下紅黑樹刪除的大體思路： 1. 刪除節點： 1.1 如果要刪除的節點沒有子節點，直接刪除節點。 1.2 如果要刪除的節點有一個子節點，刪除節點之后，用子節點頂替上來。 1.3 如果要刪除的節點有兩個子節點，那么問題可以被轉化成刪除另一個只有一個子節點的節點。就是回到了上面1.2這種情況，具體怎么轉化后面會講。 2. 刪除節點之后，調整紅黑樹，使其滿足紅黑樹的5個性質。 先看這個問題"如果要刪除的節點有兩個子節點，那么問題可以被轉化成刪除另一個只有一個子節點的節點"。 &nbsp; 在刪除帶有兩個子節點的節點的時候，我們要么找到它左子樹中的最大元素、要么找到它右子樹中的最小元素，并把它的值復制到要刪除的節點中（不復制顏色），接著去刪除我們從中復制出值的那個節點，它必定只有一個子節點或沒有子節點（因為它是最大或最小元素，不可能有兩個子節點）。不好理解就直接看圖：  圖中實例使用的是左子樹的最大元素6來代替8，實際上，找右子樹的最小值也是可以的，兩者選其一即可。 &nbsp; 接著，**怎么刪除有一個子節點的節點呢？**假設要刪除節點X，子節點是N。 1. **X是紅色節點，刪除X之后用N頂替，僅僅是少了一個紅色節點，不會破壞紅黑樹的性質。**  &nbsp; 2. **X是黑色節點：** 2.1 **子節點N是紅色。** 刪除X之后用N頂替。由于經過N的路徑上少了個黑色節點，所以要把N改成黑色。  &nbsp; 2.2 **子節點N也是黑色：** &nbsp;&nbsp;&nbsp;&nbsp;2.2.1 **節點X是樹根。** &nbsp;&nbsp;&nbsp;&nbsp;N成為新根，在所有路徑上少了個黑色節點，然后又出現一個黑色的新根，所以保持了紅黑樹的性質。 &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;2.2.2 **節點S是紅色。** &nbsp;&nbsp;&nbsp;&nbsp;在節點P上做左旋，接著互換P節點和S節點的顏色，之后按后面的2.2.4、2.2.5、2.2.6來處理。  &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;2.2.3 **節點P、節點S、S的子節點都是黑色。** &nbsp;&nbsp;&nbsp;&nbsp;直接把節點S改成紅色，之后按2.2.2來處理。  &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;2.2.4 **節點P是紅色，節點S和S的子節點都是黑色。** &nbsp;&nbsp;&nbsp;&nbsp;交換節點P和節點S的顏色，經過S的路徑上黑色節點保持不變，經過N的路徑上新增了一個黑色節點，正好填補已刪除的黑色節點。  &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;2.2.5 **節點S是黑色，S的左子節點是紅色，S的右子節點是黑色，并且N是它父節點的左子節點。** &nbsp;&nbsp;&nbsp;&nbsp;在節點S上右旋，交換節點L和節點S的顏色，之后按2.2.6處理。  &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;2.2.6 **節點S是黑色，S的右子節點是紅色，并且N是它父節點的左子節點。** &nbsp;&nbsp;&nbsp;&nbsp;在P節點上做左旋，接著交換節點P和節點S的顏色，并把節點R改成黑色，這樣，經過節點N的路徑、經過L的路徑、經過R的路徑上的黑色數目與原來保持一致了。  &nbsp; 以上就是紅黑樹的刪除操作，多處都涉及到了遞歸邏輯，所以稍微難懂一點。結合圖例多看幾遍還是能看懂的。