【數據結構】紅黑樹超詳解 ---一篇通關紅黑樹原理（含源碼解析+動態構建紅黑樹）

一.什么是紅黑樹

紅黑樹是一種自平衡的二叉查找樹，是計算機科學中用到的一種數據結構。
1972年出現，最初被稱為平衡二叉B樹。1978年更名為“紅黑樹”。
是一種特殊的二叉查找樹，紅黑樹的每一個節點上都有存儲表示節點的顏色。
每一個節點可以是紅或者黑；紅黑樹不是高度平衡的，他的平衡是通過“紅黑規則”實現的。

與平衡二叉樹的區別

? ? ? ? 平衡二叉樹：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 紅黑樹：

? ? ? ? 1.高度平衡? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1.是一個二叉查找樹

? ?? ? ?2.當左右子樹高度差超過1時，通過旋轉保持平衡? ? 2.不是高度平衡的

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?3.條件：特有的紅黑規則

所以紅黑樹并不是一個完全意義上的平衡二叉樹，稱它為二叉查找樹最為合適，并且是自平衡的哦，那么下面我們來講一下什么是紅黑規則?

二.紅黑規則

? ? ? ? 紅黑規則是紅黑樹的核心，它決定了紅黑樹的特點，這也是區別于其他數據結構的屬性

1.每一個節點或是紅色的，或是黑色的

2.根節點必須是黑色

3.如果一個節點沒有子節點或父節點，則該節點相應的指針屬性為Nil，這些Nil視為葉節點，每個葉節點(Nil)是

???黑色的

4.如果某一個節點是紅色，那么它的子節點必須是黑色（不能出現兩個紅色節點相連的情況）

5.對于每一個節點，從該節點到其所有后代節點的簡單路徑上，均包含相同數目的黑色節點

? ? ? ? ??

? ? ? ? 下面我們對紅黑規則進行講解

三.紅黑樹原理

上圖是一棵示例紅黑樹

紅黑樹的每一個節點在原有二叉樹的基礎上，又增加了“顏色”的屬性，用來記錄當前節點的顏色，但是他還有什么作用呢？我們一會講到

?通過上圖，我們可以更直觀的了解到紅黑樹的結構，并用它來理解紅黑規則

我們可以看到，圖中每個節點的顏色要么都是紅色，要么都是黑色，并沒有出現其他的顏色，這遵循了紅黑規則第一條；

值為13的根節點的顏色是黑色，遵循了紅黑規則第二條；

同樣我們可以看到，對于沒有父節點或者是子節點的節點來說，他們的對應位置的指針設置為了Nil，比如，值為1的黑色節點，它有右子節點二沒有左子結點，所以它的左子結點的指針就設置為了Nil，右子節點的指針則指向了值為6的節點；對于沒有左子結點也沒有右子結點的節點來說，他們的下面兩個指針都指向了Nil。這遵循了紅黑規則的第三條；

注：Nil同樣是一個葉子結點，只不過沒有任何意義哦，但并非沒用

第四點和第五點我們應該結合起來去理解，首先紅色節點的子節點顏色不能是紅色，然后每一個節點到其后代的葉子結點扥簡單路徑上的黑色節點數量相同。這句話有點拗口，我們來分析一下，首先，后代指的是從一個節點開始，它的所有子節點稱為該節點的后代；葉子結點就是沒有子節點的節點，在圖中就是Nil節點；簡單路徑指的是從一個節點開始，順著它的子節點一直向下的路徑，就是簡單路徑，不能回頭，例如：根節點13到節點6的簡單路徑就是13->8->1->6;

我們用一張圖來加強理解：

?所以也就是說，任何一個節點到它的最下面的葉子結點構成的所有路徑上，黑色節點的數量是相同的且不存在兩個紅色節點相連的情況，很顯然這遵循了紅黑規則第四條和第五條；

我們理解了紅黑樹的紅黑規則的體現，那么我們為什么不來親手構建一棵紅黑樹來學習紅黑規則具體怎么使用呢？

四.紅黑樹構建過程

? ? ? ? 為了加深對紅黑樹的深層理解和紅黑規則的具體應用，我這里將展示一棵紅黑樹的構建過程

? ? ? ? 首先，紅黑樹默認的節點顏色是紅色，這是因為紅色節點的效率高，可是為什么呢？我將給出一個讓你秒懂的對比過程！

我們先默認添加的節點初始是黑色

以添加三個節點為例：

我們先將20節點添加進去，此時根據構建規則，它應該長這個樣子（此時紅黑規則的五條它都滿足）：

?我們再將18節點添加進去，根據排序規則，18比20小，應該放在左邊：

?這個時候就出現問題了，讓我們回顧一下紅黑規則，很顯然它違背了第五條：任何一個節點的后代的葉子結點的簡單路徑上黑色節點的數量應該相同。但我們看，從根節點開始到左側的葉子結點與右側的葉子結點的簡單路徑上黑色節點的數量是不同的，所以思考一下，為了使它滿足紅黑規則，我們應該怎么改變？

很顯然是將18節點的顏色改為紅色:

接下來我們繼續添加節點，將23節點添加進去，它應該被放在20根節點的右側：

這個時候很顯然他又違背了紅黑規則的第五條，那我們應該怎么改呢？現在有兩種改法：

????????1.將23號節點的顏色改為紅色

????????2.將18號節點的顏色改為黑色

我們應該選擇哪種方法？這里告訴你，應該選擇第一種哦。

然后紅黑樹最終的形態是這個樣子：

?在這個過程中你是否還記得節點的顏色變過幾次呢？根據結果顯示，他一共變了兩次顏色，讓我們記住這個結果。

接下來，我們以節點顏色默認是紅色來展示構建過程：

還是一樣，添加第一個節點20(左圖)。這時候我們發現它此時違背了第二條規則：根節點只能是黑色。于是我們進行修改，變成了右圖所示結果：

?接下來添加第二個節點18，按照規則他被添加到根節點的左邊：

此時我們發現它是不違背規則的

?繼續添加第三個節點23：

很巧！它同樣不違背紅黑規則

所以在這個過程中，節點的顏色總共只被改變了一次

結論：可以發現，我們添加三個節點的情況下，節點顏色默認是黑色的情況下載構建的過程中要比節點顏色默認是紅色的情況多調整一次，所以這也就論證了紅色節點效率高的結論?

????????其次，關于紅黑樹的構建，在上面(節點顏色默認為紅色)的基礎上，還有如下規則：

不要害怕，讓我來細細講解

我們首先要明確一個點，這些所有的構建規則，都是為了維護紅黑規則而出現的，換句話說，這些構建規則實際上就是紅黑規則在實際應用中的具象化體現。

接下來，我將以一個多節點的構建過程來演示這些構建規則，來幫助你理解圖片中的內容，構建過程中會涵蓋圖中所有的情況

?1.添加第一個節點18

? ? 此時我們添加的是根節點，根據圖中的規則，我們需要將節點直接變為黑色(右圖)

?2.添加第二個節點23

按照規則我們將其放在根節點的左側，此時我們填入的節點是非根節點，且父節點是黑色，所以按照圖中的要求，我們不需要進行任何的操作

?3.添加第三個節點23

按照規則我們將其放在根節點的右側，此時我們填入的節點是非根節點，且父節點是黑色，所以按照圖中的要求，我們同樣不需要進行任何的操作

4.添加第四個節點22

因為22比根節點20大且比23小，所以我們應該將其放在節點23的左側，此時我們添加的節點是非根節點，且父節點是紅色，所以按照圖中要求，我們應該判斷一下叔叔節點的顏色，我們發現叔叔節點是紅色，所以按照要求，我們需要將父節點和叔叔節點都變成黑色，然后將爺爺節點變成紅色（左圖），但是由于爺爺節點是根節點，所以再將其變成黑色（右圖）

叔叔節點：父節點的兄弟節點，也就是爺爺節點的另一個子節點，就像你的爺爺生了兩個兒子，一個是你的爸爸，另一個就是你的叔叔（bushi

5.添加第五個節點17

因為17比根節點20小，比18也小，所以應該被放在18的左邊，此時我們添加的是非根節點，且父親是黑色，所以我們不需要進行任何操作

6.添加節點24和19

和上圖原理一樣，因為添加非根節點且父節點是黑色所以不需要進行任何調整

最終結果是這樣

?這個時候你可能會說：

Q：這也不難啊，不是有手就行嗎？

A：這是因為圖中的規則我們還沒有全部碰到哦，那么我再添加兩個節點，我們繼續往下看

這時候我們再添加兩個節點15和14

7.添加節點15

按照排序規則，我們將15節點放在17節點的左邊，此時我們添加的是非根節點，父節點是紅色，叔叔也是紅色，所以將父節點和叔叔節點都變為黑色，并將爺爺節點變成紅色，因為爺爺節點不是根節點，根據圖中要求，將爺爺節點作為當前節點再進行判斷（也就是假設爺爺節點是當前加入的節點），我們發現爺爺節點是非根節點，且爺爺節點的父節點是黑色的，所以我們不進行變動

8.添加節點14

根據排序規則，我們將14節點放在15節點的左邊，此時我們添加的是非根節點，父節點是紅色，但叔叔節點是黑色，且我們添加的是父節點的左孩子，所以我們將父節點設置為黑色，將爺爺節點設置為紅色，并以爺爺節點為軸進行右旋，這里我分兩張圖來演示

右旋：將該節點作為其左子節點的右子節點，左子節點原本的右子節點作為該節點的左子節點

右旋之前：

右旋之后：

相對的，如果我們此次添加的節點出現在了15的右子節點上，那么我們就需要以15為基準進行左旋，并進行判斷（15當作此次添加的節點）

此時整棵樹的結構符合紅黑規則的規范。

總結：我們在理解構建紅黑樹的過程時，我們首先要理解紅黑樹的本質，最佳思路：首先思考其是否符合紅黑規則的要求，其次根據紅黑樹構建要求進行構建，因為其本質就是遵循紅黑規則而構建的。

注：紅黑樹的增刪改查效率都很高

看了這些，相信你已經學會了紅黑樹的構建方法了，但是你是否覺得這些又太片面化太生硬了呢？好的，那我們----上源碼。

五.紅黑樹源碼分析

? ? ? ? 接下來我將以源碼作為背景深入分析紅黑樹的構建過程，相信到最后你會理解為什么要有紅黑樹，它的效率又為什么高。

考慮到紅黑樹實現源碼設計大量的Map操作，實現相當復雜，完整實現代碼1000+行，這里摘取其核心邏輯插入、刪除以及紅黑樹邏輯維護(旋轉)的部分進行講解

1.紅黑樹節點的定義

我們可以看到，由于紅黑樹是Map效率優化的產物，所以其在定義上存在著key、value的值

結合我上面給出的紅黑樹節點定義圖，不難看出，源碼中同樣定義著左子節點、右子節點、父節點和節點顏色，節點同樣是RBNode本類類型

// 紅黑樹節點定義 (簡化自 java.util.TreeMap.Entry)static final class RBNode<K, V> {//在紅黑樹節點中，其值是以key、value形式存儲的K key;V value;RBNode<K, V> left;    // 左子節點RBNode<K, V> right;   // 右子節點RBNode<K, V> parent;  // 父節點boolean color;       // 顏色：RED 或 BLACK//在定義節點時，需要傳給其key、value和其父節點RBNode(K key, V value, RBNode<K, V> parent) {this.key = key;this.value = value;this.parent = parent;this.color = RED; // 新節點默認紅色}}

紅黑樹節點類同樣給出了一個構造方法，我們需要傳入節點的值以及其父節點，其中節點顏色默認為紅色我們前面也是提到過的，后續我們需要通過這個構造方法對紅黑樹的節點進行插入。

2.紅黑樹操作類

了解了紅黑樹節點的定義，我們再來看看紅黑樹中具體的操作，比如增刪旋轉是如何實現的

由于整體代碼偏長，我分出幾個方法分別講解

紅黑樹操作類定義

可以看到，紅黑樹操作類上定義了兩個泛型，分別是key和value，其中key實現了Comparable接口便于進行標準的排序比較操作。

在類內部首先定義了紅黑樹的根節點，并定義了兩個靜態常量，分別是RED和BLACK用來表示節點顏色，其用Boolean類型標識就是因為它只有兩個值且互相對立。

// 紅黑樹核心操作類 (簡化版，基于 TreeMap 邏輯)public class RedBlackTree<K extends Comparable<K>, V> {private RBNode<K, V> root; // 根節點private static final boolean RED = false;private static final boolean BLACK = true;

插入操作與平衡修復

1.插入

public void put(K key, V value) {//首先定義一個節點，將根節點的值復制給該節點RBNode<K, V> t = root;//判斷t是否為空，如果t為空則表示樹為空，根節點還未定義if (t == null) {//初始化根節點，值設置為key和valueroot = new RBNode<>(key, value, null);//顏色設置為黑色root.color = BLACK; // 根節點必須黑色return;}// 查找插入位置int cmp;   //定義比較參數//定義一個父節點RBNode<K, V> parent;do {//首先將父節點定義臨時為根節點parent = t;//cmp為比較參數cmp = key.compareTo(t.key);//如果cmp小于0，表示key小于當前父節點的鍵，則將父節點的左子節點作為新的父節點（向左子樹查找）if (cmp < 0) t = t.left;//如果cmp小于0，表示key大于當前父節點的鍵，則將父節點的右子節點作為新的父節點（向右子樹查找）else if (cmp > 0) t = t.right;//因為紅黑樹不允許存在相同的值，所以遇到相同的值則更新else { t.value = value; return; } // 已存在則更新} while (t != null); //結束條件是遍歷到葉子節點// 創建新節點并插入RBNode<K, V> newNode = new RBNode<>(key, value, parent);  //最終parent就是當前新增節點的父節點，調用構造函數插入//根據最后有一次的比較參數的值來決定該節點作為左子樹還是右子樹if (cmp < 0) parent.left = newNode;  else parent.right = newNode;  // 插入后修復紅黑樹性質fixAfterInsertion(newNode);}

插入節點方法代碼的邏輯就是先判斷根節點是否為空，如果根節點為空就初始化根節點；根節點不為空就不斷遍歷樹去尋找到合適的插入位置（key比根節點key小則向左子樹查找，反之亦然），最終找到位置后再判斷是左子節點還是右子節點。

最終在插入節點后進行修復紅黑樹的操作

總結：

從根節點開始，逐步向下查找插入位置：
- 若當前鍵?<?當前節點的鍵，向左子樹查找。
- 若當前鍵?>?當前節點的鍵，向右子樹查找。
- 若鍵相等，直接更新值并返回（紅黑樹不允許重復鍵）。
終止條件：當?t?移動到?null?時，parent?即為新節點的父節點。

2.修復紅黑樹（插入后）

 private void fixAfterInsertion(RBNode<K, V> x) {x.color = RED; // 新插入節點設為紅色//當該節點非空、節點不是根節點、節點的父節點的顏色為紅色時while (x != null && x != root && x.parent.color == RED) {// 父節點是祖父的左子節點if (parentOf(x) == leftOf(grandparentOf(x))) {RBNode<K, V> uncle = rightOf(grandparentOf(x)); // 獲取叔叔節點// Case 1: 叔叔節點是紅色（顏色翻轉）if (colorOf(uncle) == RED) {//將父節點顏色設置為黑色setColor(parentOf(x), BLACK);//將叔叔節點顏色設置為黑色setColor(uncle, BLACK);//將爺爺節點設置為紅色setColor(grandparentOf(x), RED);x = grandparentOf(x); // 向上回溯} else {// Case 2: 當前節點是父的右子節點（轉為 Case 3）if (x == rightOf(parentOf(x))) {x = parentOf(x);rotateLeft(x); // 左旋父節點}// Case 3: 當前節點是父的左子節點//將當前節點父節點的顏色設置為黑色setColor(parentOf(x), BLACK);//將爺爺節點的顏色設置為紅色setColor(grandparentOf(x), RED);rotateRight(grandparentOf(x)); // 右旋祖父}} else { // 對稱情況：父節點是祖父的右子節點//定義叔叔節點，此時叔叔節點一定是爺爺節點的左子節點RBNode<K, V> uncle = leftOf(grandparentOf(x));//如果叔叔節點的顏色為紅色if (colorOf(uncle) == RED) { // Case 1//將父節點的顏色改為黑色setColor(parentOf(x), BLACK);//將叔叔節點的顏色改為黑色setColor(uncle, BLACK);//將爺爺節點的顏色設置為紅色setColor(grandparentOf(x), RED);//以祖父為當前節點進行判斷x = grandparentOf(x);} else {//如果叔叔節點是黑色且當前節點是父節點的左子節點if (x == leftOf(parentOf(x))) { // Case 2//以父節點作為當前節點并進行右旋x = parentOf(x);rotateRight(x);}// Case 3//將父節點顏色設置為黑色setColor(parentOf(x), BLACK);//將爺爺節點顏色設置為紅色setColor(grandparentOf(x), RED);//以爺爺節點為基準進行左旋rotateLeft(grandparentOf(x));}}}root.color = BLACK; // 確保根節點為黑色          }

由于我們上面已經對紅黑樹構建邏輯進行分析和講解，所以對于這個方法我們也不難理解，只不過這里的判斷順序與我們講過的修些許不同，這里是先將父節點相對于爺爺節點的位置進行了分類，再對叔叔節點的顏色加以判斷，并分別分出三種情況進行處理。

以下是這幾種情況的操作演示

場景 1：叔叔節點為紅色

黑 (祖父)/   \紅 (父) 紅 (叔)/紅 (新節點 x)

操作：父、叔變黑，祖父變紅。

結果：

    紅 (祖父)/   \黑      黑/紅 (x)

后續：將?x?回溯到祖父節點，繼續檢查更高層的連續紅色問題。

場景 2：叔叔節點為黑色（Case 2 → Case 3）

 黑 (祖父)/   \紅 (父) 黑 (叔)\紅 (x，右子)

操作：

Case 2：左旋父節點，結構變為：

 黑 (祖父)/   \紅 (x) 黑 (叔)/
紅 (原父節點)   再以原父節點為準進行判斷

Case 3：右旋祖父，父變黑，祖父變紅：

 黑 (父)/   \
紅 (x) 紅 (祖父)\黑 (叔)

刪除操作與平衡修復?

1.刪除

//刪除節點操作方法public void remove(K key) {// 1. 查找要刪除的節點RBNode<K, V> p = getNode(key);if (p == null) return; // 節點不存在// 2. 實際刪除節點并修復紅黑樹deleteNode(p);}//查找節點方法private RBNode<K, V> getNode(K key) {//設置一個節點的值為rootRBNode<K, V> t = root;//循環條件為節點不為空while (t != null) {//要查找的節點的key不斷與當前t節點的的key進行比較//如果比t的key小，就繼續向其左子樹查找，反之則向右子樹查找int cmp = key.compareTo(t.key);if (cmp < 0) t = t.left;else if (cmp > 0) t = t.right;//如果值相等直接返回t的位置else return t;}return null;}//刪除節點具體操作private void deleteNode(RBNode<K, V> p) {// --- 情況1: 節點有兩個子節點 ---if (p.left != null && p.right != null) {// 找到后繼節點（右子樹的最小節點）RBNode<K, V> s = successor(p);// 用后繼節點的鍵值替換當前節點p.key = s.key;p.value = s.value;p = s; // 實際刪除后繼節點（問題簡化為刪除單子或無子節點）}// --- 情況2: 刪除節點是葉節點或只有一個子節點 ---RBNode<K, V> replacement = (p.left != null ? p.left : p.right);if (replacement != null) {// 刪除節點有一個子節點（用子節點替換）replacement.parent = p.parent;if (p.parent == null) {root = replacement; // 刪除根節點} else if (p == p.parent.left) {p.parent.left = replacement;} else {p.parent.right = replacement;}// 清空被刪節點的指針p.left = p.right = p.parent = null;// 刪除黑色節點后需要修復（紅色節點不影響黑高）if (p.color == BLACK) {fixAfterDeletion(replacement);}} else if (p.parent == null) {root = null; // 樹中僅剩根節點} else {// 刪除葉節點（無子節點）if (p.color == BLACK) {fixAfterDeletion(p); // 先修復再刪除}// 從父節點斷開鏈接if (p.parent != null) {if (p == p.parent.left) {p.parent.left = null;} else {p.parent.right = null;}p.parent = null;}}}//找到節點的后繼結點，右子樹最小節點private RBNode<K, V> successor(RBNode<K, V> t) {if (t == null) return null;//不斷向下查找t的右子節點的左子樹的最小值else if (t.right != null) {RBNode<K, V> p = t.right;while (p.left != null) p = p.left;return p;} else {// ...（此處省略向上查找邏輯，實際刪除中不需要）return null;}}

? ? ? ? 刪除節點的流程：

? ? ? ? 1.先查找要刪除節點的位置，這個過程是通過不斷進行key的比較完成的（小則左，大則右）

? ? ? ? 2.刪除節點，這個過程分為兩種大情況：1.要刪除的節點有兩個子節點，2.除第一種情況的所有情況。

? ? ? ? 對于第一種情況，我們需要找到比要刪除節點的大的最小節點s，將其節點的信息賦值給要刪除的節點，由于s是葉節點或單子節點，所以此時刪除操作可以轉化為第二種情況。

? ? ? ? 第二種情況，先取出該節點的葉子結點，因為其并沒有兩個子節點，所以通過

BNode<K, V> replacement = (p.left != null ? p.left : p.right);

取出其不為空的一個節點，但是考慮到該節點還有可能是葉子結點，所以下面又分出了兩種情況

? ? ? ? 1.當replacement不為空時表示其不是葉子結點，將替代節點的父指針指向?p?的父節點。更新父節點的子指針（左或右）指向替代節點。斷開?p?的所有指針。

????????若?p?是黑色：調用?fixAfterDeletion(replacement)?修復黑高。

? ? ? ? 2.replacement為空時表示其為葉子結點，這里還要分出兩種情況，我們首先要判斷要刪除的節點是不是根節點，是根節點就直接將根節點設置為Null，否則就將該節點的父指針置空+父節點指向該節點的指針置空，但是需要先修復紅黑樹再進行刪除。

關鍵問題解答

Q1. 為什么刪除有兩個子節點的節點時要找后繼節點？

保持二叉搜索樹性質：后繼節點是右子樹的最小節點，替換后能保證左子樹所有節點仍小于它，右子樹所有節點仍大于它。
簡化操作：后繼節點至多有一個右子節點，將問題簡化為刪除單子節點或葉節點。

Q2. 為什么刪除黑色節點后需要修復？

黑高失衡：刪除黑色節點會減少其路徑上的黑色節點數量，違反紅黑樹性質 5（所有路徑黑高相同）。
連續紅色風險：若父節點和兄弟節點均為紅色，可能導致連續紅色節點。

Q3. 為什么葉節點刪除要先修復再斷開鏈接？

修復依賴父指針：fixAfterDeletion(p)?需要訪問?p?的父節點和兄弟節點。若先斷開父指針，修復邏輯將無法正確執行。

Q4. 如何處理根節點刪除？

直接更新根指針：若刪除的是根節點且無子節點，直接將?root?設為?null。若有子節點，替代節點成為新根。

2.修復紅黑樹（刪除后）

 private void fixAfterDeletion(RBNode<K, V> x) {//開始條件:刪除節點不是根節點且節點顏色是黑色while (x != root && colorOf(x) == BLACK) {//當節點是父節點的左節子點時if (x == leftOf(parentOf(x))) {//設置一個節點賦值為父節點的右子節點，也就是叔叔節點RBNode<K, V> sib = rightOf(parentOf(x));//如果叔叔節點是紅色if (colorOf(sib) == RED) {//將叔叔節點設置為黑色setColor(sib, BLACK);//將父節點設置為紅色setColor(parentOf(x), RED);//以父節點為基準進行左旋rotateLeft(parentOf(x));//叔叔節點的值重新設置為當前（旋轉后）的叔叔節點sib = rightOf(parentOf(x));}//如果叔叔節點的左右子節點顏色都為黑if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {//將叔叔節點顏色設置為紅色setColor(sib, RED);//將當前節點的父節點作為當前節點再做判斷x = parentOf(x);} else { //叔叔節點的左右子節點不全為黑色時//如果叔叔節點左子結點為紅，右子節點為黑if (colorOf(rightOf(sib)) == BLACK) {//將叔叔節點左子結點設置為黑色setColor(leftOf(sib), BLACK);//將叔叔節點設置為紅色setColor(sib, RED);//右旋叔叔節點rotateRight(sib);//叔叔節點重新設置為旋轉后的叔叔節點sib = rightOf(parentOf(x));}//將叔叔節點的顏色設置為其兄弟節點的顏色（當前節點的父節點）setColor(sib, colorOf(parentOf(x)));//將當前節點的父節點的顏色設置為黑色setColor(parentOf(x), BLACK);//將叔叔節點的右子節點設置為黑色setColor(rightOf(sib), BLACK);//左旋父節點rotateLeft(parentOf(x));//以根節點作為當前節點進行判斷x = root;}} else {  //當前節點是父節點的右子節點// 對稱邏輯//所有操作與上面的情況完全對立，比如左旋->右旋、rightOf->leftOfRBNode<K, V> sib = leftOf(parentOf(x));if (colorOf(sib) == RED) {setColor(sib, BLACK);setColor(parentOf(x), RED);rotateRight(parentOf(x));sib = leftOf(parentOf(x));}if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) {setColor(sib, RED);x = parentOf(x);} else {if (colorOf(leftOf(sib)) == BLACK) {setColor(rightOf(sib), BLACK);setColor(sib, RED);rotateLeft(sib);sib = leftOf(parentOf(x));}setColor(sib, colorOf(parentOf(x)));setColor(parentOf(x), BLACK);setColor(leftOf(sib), BLACK);rotateRight(parentOf(x));x = root;}}}//最終將當前節點的顏色設置為黑色setColor(x, BLACK);}

當刪除一個黑色節點后，可能導致路徑黑高減少或連續紅色節點問題。fixAfterDeletion?的目標是通過顏色調整和旋轉操作，恢復紅黑樹的五個性質，也就是紅黑規則。其核心處理邏輯圍繞?兄弟節點?的狀態展開。

1. 循環條件

while (x != root && colorOf(x) == BLACK)

含義：當?x?不是根節點且為黑色時，需要修復。
原因：刪除黑色節點會減少路徑黑高，需通過調整兄弟節點子樹來補償。

2. 分支處理：x 是父節點的左子

if (x == leftOf(parentOf(x))) {RBNode<K, V> sib = rightOf(parentOf(x)); // 獲取兄弟節點// 后續處理...
}

Case 1：兄弟節點為紅色

if (colorOf(sib) == RED) {setColor(sib, BLACK);setColor(parentOf(x), RED);rotateLeft(parentOf(x));sib = rightOf(parentOf(x)); // 更新兄弟節點
}

操作：
- 將兄弟節點設為黑色，父節點設為紅色。
- 對父節點左旋，使原兄弟節點的左子成為新兄弟。
目的：將情況轉換為兄弟節點為黑色，進入后續處理。

Case 2：兄弟節點的子節點均為黑色

if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {setColor(sib, RED);x = parentOf(x); // 向上回溯
}

操作：將兄弟節點設為紅色，x?上移至父節點。
影響：父節點路徑的黑高減少 1，需繼續循環處理父節點。

Case 3 & 4：兄弟節點的子節點至少有一個紅色

else {if (colorOf(rightOf(sib)) == BLACK) { // Case 3：兄弟右子為黑（左子為紅）setColor(leftOf(sib), BLACK);setColor(sib, RED);rotateRight(sib); // 右旋兄弟節點sib = rightOf(parentOf(x)); // 更新兄弟節點}// Case 4：兄弟右子為紅setColor(sib, colorOf(parentOf(x)));setColor(parentOf(x), BLACK);setColor(rightOf(sib), BLACK);rotateLeft(parentOf(x)); // 左旋父節點x = root; // 終止循環
}

Case 3（兄弟右子為黑）：
- 將兄弟左子設為黑色，兄弟設為紅色。
- 右旋兄弟節點，使兄弟的右子成為新兄弟。
Case 4（兄弟右子為紅）：
- 兄弟繼承父節點顏色，父節點設為黑色，兄弟右子設為黑色。
- 左旋父節點，平衡黑高。
- 設置?x = root?強制退出循環。

3. 對稱分支：x 是父節點的右子

else { // 對稱邏輯：x 是父的右子RBNode<K, V> sib = leftOf(parentOf(x));// 處理邏輯與左子分支對稱（left ? right，rotateLeft ? rotateRight）
}

操作與左子分支完全對稱，方向相反。

4. 最終修正

setColor(x, BLACK); // 確保當前節點為黑色

作用：無論循環如何退出，最終確保?x?為黑色（可能直接修復根節點顏色）。

關鍵場景示例

場景 1：兄弟節點為紅色

   B (父，黑)            B (父，紅)/ \                   / \x   D (兄弟，紅)  →→   x   D (黑)/ \                   / \C   E                 C   E

操作：兄弟變黑，父變紅，左旋父節點，更新兄弟為?C。

場景 2：兄弟子節點均為黑

 B (父，黑)            B (父，黑)/ \                   / \x   D (兄弟，黑)  →→   x   D (紅)/ \                   / \C   E (均黑)          C   E

操作：兄弟變紅，x?上移至父節點，繼續處理父節點。

場景 3 & 4：兄弟右子為紅

 B (父，黑)            D (兄弟，父顏色)/ \                   / \x   D (兄弟，黑)  →→   B   E (黑)/ \               / \C   E (紅)        x   C

操作：兄弟繼承父顏色，父變黑，兄弟右子變黑，左旋父節點，結束循環。

所以刪除+修復操作相比插入+修復操作的邏輯更加復雜，因為我們需要逆向去思考這個過程。

紅黑樹操作工具方法

//---------------- 旋轉操作 (核心工具方法) ----------------/** 左旋（維護紅黑樹平衡） */private void rotateLeft(RBNode<K, V> p) {if (p == null) return;// 1. 獲取 p 的右子節點 r（左旋必須保證 r 存在）RBNode<K, V> r = p.right;if (r == null) return; // 無法左旋// 2. 將 r 的左子節點 rl 掛載到 p 的右子p.right = r.left;if (r.left != null) {r.left.parent = p; // 更新 rl 的父指針}// 3. 將 r 的父指針指向 p 的父節點r.parent = p.parent;// 4. 處理父節點的子指針if (p.parent == null) {root = r; // p 是根節點 → r 成為新根} else if (p == p.parent.left) {p.parent.left = r; // p 是父的左子 → r 替代 p 的位置} else {p.parent.right = r; // p 是父的右子 → r 替代 p 的位置}// 5. 將 p 作為 r 的左子r.left = p;p.parent = r;}/** 右旋（與左旋對稱） */private void rotateRight(RBNode<K, V> p) {if (p == null) return;// 1. 獲取 p 的左子節點 l（右旋必須保證 l 存在）RBNode<K, V> l = p.left;if (l == null) return; // 無法右旋// 2. 將 l 的右子節點 lr 掛載到 p 的左子p.left = l.right;if (l.right != null) {l.right.parent = p; // 更新 lr 的父指針}// 3. 將 l 的父指針指向 p 的父節點l.parent = p.parent;// 4. 處理父節點的子指針if (p.parent == null) {root = l; // p 是根節點 → l 成為新根} else if (p == p.parent.right) {p.parent.right = l; // p 是父的右子 → l 替代 p 的位置} else {p.parent.left = l; // p 是父的左子 → l 替代 p 的位置}// 5. 將 p 作為 l 的右子l.right = p;p.parent = l;}//---------------- 工具方法 ----------------private RBNode<K, V> parentOf(RBNode<K, V> p) {return (p == null ? null : p.parent);}private RBNode<K, V> leftOf(RBNode<K, V> p) {return (p == null) ? null : p.left;}private boolean colorOf(RBNode<K, V> p) {return (p == null ? BLACK : p.color);}private void setColor(RBNode<K, V> p, boolean c) {if (p != null) p.color = c;}private RBNode<K, V> rightOf(RBNode<K, V> node) {// 返回節點的右子節點return (node == null) ? null : node.right;}private RBNode<K, V> grandparentOf(RBNode<K, V> node) {if (node != null && node.parent != null) {return node.parent.parent;}return null; // 如果節點沒有父節點或祖父節點，則返回null}

這些工具方法都是在維護紅黑樹結構時發揮作用。左旋、右旋的具體方法和原理我將會在后續的平衡二叉樹部分中展開講解。

看到這里相信你對紅黑樹的實現和有了更進一步的理解，由于原始源碼部分內容過于繁重，這里無法全部進行分析，原始源碼可見：Open_JDK的TreeMap部分的實現

六.總結

? ? ? ? 紅黑樹在數據結構中有著舉足輕重的地位，像我們熟知的HashMap，它在jdk1.8以后也增加了紅黑樹的實現，這是因為紅黑樹在各方面的性能都非常好，通過解讀源碼部分我們已經發現，紅黑樹在維護結構的過程中最多的操作就是顏色的變化，但這個操作是消耗資源最少的操作，所以相比其他的二叉查找樹，紅黑樹的優勢就體現在了這里。

? ? ? ? 為了讓大家更好的去理解紅黑樹，我已經整理好并上傳了一份紅黑樹操作腳本（自行下載資源），包括增刪和紅黑樹修復的功能，可以打印出每次的圖形結果，便于大家的調試。