紅黑樹（Red Black Tree）是一種自平衡的二叉搜索樹（Self-balancing Binary Search Tree）。以前也叫做平衡二叉 B 樹（Symmetric Binary B-tree）。

預(yù)備知識

樹的知識框架結(jié)構(gòu)如下圖所示：

平衡二叉搜索樹

平衡二叉搜索樹（Balanced Binary Search Tree），英文簡稱 BBST。經(jīng)典常見的平衡二叉搜索樹是 AVL 樹和紅黑樹。

①二叉搜索樹

二叉搜索樹（Binary Search Tree）是二叉樹的一種，英文簡稱 BST。又稱為二叉查找樹、二叉排序樹。

它的特點(diǎn)是任何一個(gè)結(jié)點(diǎn)的值都大于其左子樹的所有結(jié)點(diǎn)的值，任何一個(gè)結(jié)點(diǎn)的值都小于其右子樹的所有結(jié)點(diǎn)的值。

②平衡

平衡（Balance）：就是當(dāng)結(jié)點(diǎn)數(shù)量固定時(shí)，左右子樹的高度越接近，這棵二叉樹越平衡（高度越低）。而最理想的平衡就是完全二叉樹/滿二叉樹，高度最小的二叉樹。

一棵二叉搜索樹平均時(shí)間復(fù)雜度可以認(rèn)為是樹的高度 O(h)。像左邊這棵，結(jié)點(diǎn)的左右子樹的高度接近，屬于一棵平衡二叉搜索樹，O(h) = O(logn)；而右邊這棵，高度達(dá)到了最大，已經(jīng)退化成了鏈表，O(h)=O(n)。

③改進(jìn)二叉搜索樹

當(dāng)二叉樹退化成鏈表時(shí)，性能是很低的，所以我們需要在結(jié)點(diǎn)的插入、刪除操作之后，想辦法讓二叉搜索樹恢復(fù)平衡（減小樹的高度）。

但是如果為了追求最理想的平衡，而增加了時(shí)間復(fù)雜度也不是很有必要，因此比較合理的方案就是：用盡量少的調(diào)整次數(shù)達(dá)到適度平衡。

由此引申出 AVL 樹的概念。

AVL 樹

AVL 樹是最早發(fā)明的自平衡二叉搜索樹之一，它取名自兩位發(fā)明家的名字：G.M.Adelson-Velsky 和 E.M.Landis。

平衡因子（Balance Factor）：某結(jié)點(diǎn)的左右子樹的高度差。

每個(gè)葉子結(jié)點(diǎn)的平衡因子都是 0?？催@棵二叉搜索樹，紅色數(shù)字標(biāo)注了每個(gè)結(jié)點(diǎn)對應(yīng)的平衡因子。

舉例：8 的左子樹高度為 2，右子樹高度為 1，因此它的平衡因子為 1；5 的左子樹高度為 0，右子樹高度為 3，因此它的平衡因子為 -3；4 的左子樹高度為 2，右子樹高度為 4，因此它的平衡因子為 -2；

再看這棵 AVL 樹和它每個(gè)結(jié)點(diǎn)對應(yīng)的平衡因子：

可以看到 AVL 樹具有以下特點(diǎn)：

每個(gè)結(jié)點(diǎn)的平衡因子只可能是 -1、0、1（如果絕對值超過 1，則認(rèn)為是失衡）

每個(gè)結(jié)點(diǎn)的左右子樹高度差不超過 1

搜索、插入、刪除的時(shí)間復(fù)雜度是 O(logn)

B 樹

B 樹（Balanced Tree）是一種平衡的多路搜索樹，多用于文件系統(tǒng)、數(shù)據(jù)庫的實(shí)現(xiàn)。

這是一個(gè)簡單的 3 階 B 樹：

特點(diǎn)如下：

1 個(gè)結(jié)點(diǎn)可以存儲超過 2 個(gè)元素，可以擁有超過 2 個(gè)子結(jié)點(diǎn)

擁有二叉搜索樹的一些性質(zhì)

平衡，每個(gè)結(jié)點(diǎn)的所有子樹高度一致

比較矮

①m 階 B 樹的性質(zhì)（m ≥ 2）

m 階 B 樹指的是一個(gè)結(jié)點(diǎn)最多擁有 m 個(gè)子結(jié)點(diǎn)。假設(shè)一個(gè)結(jié)點(diǎn)存儲的元素個(gè)數(shù)為 x，那么如果這個(gè)結(jié)點(diǎn)是：

根結(jié)點(diǎn)：1 ≤ x ≤ m - 1

非根結(jié)點(diǎn)：┌ m / 2 ┐ - 1 ≤ x ≤ m - 1

如果有子結(jié)點(diǎn)，子結(jié)點(diǎn)個(gè)數(shù)為 y = x + 1，那么如果這個(gè)結(jié)點(diǎn)是：

根結(jié)點(diǎn)：2 ≤ y ≤ m

非根結(jié)點(diǎn)：┌ m / 2 ┐ ≤ y ≤ m

向上取整（Ceiling），指的是取比自己大的最小整數(shù)，用數(shù)學(xué)符號 ┌ ┐ 表示；向下取整（Floor），指的是取比自己小的最大整數(shù)，用數(shù)學(xué)符號 └ ┘ 表示。 比如 m=3，子結(jié)點(diǎn)個(gè)數(shù) 2≤y≤3，這個(gè) B 樹可以稱為（2，3）樹、2-3 樹。 比如 m=4，子結(jié)點(diǎn)個(gè)數(shù) 2≤y≤4，這個(gè) B 樹可以稱為（2，4）樹、2-3-4 樹。

比如 m=5，子結(jié)點(diǎn)個(gè)數(shù) 3≤y≤4，這個(gè) B 樹可以稱為（3，5）樹、3-4-5 樹。

以此類推。

②B 樹 VS 二叉搜索樹

這是一棵二叉搜索樹，通過某些父子結(jié)點(diǎn)合并，恰好能與上面的 B 樹對應(yīng)。

我們可以得到結(jié)論：

B 樹和二叉搜索樹，在邏輯上是等價(jià)的

多代結(jié)點(diǎn)合并，可以獲得一個(gè)超級結(jié)點(diǎn)，且 n 代合并的超級結(jié)點(diǎn)，最多擁有 (2^n) 個(gè)子結(jié)點(diǎn) （至少是 (2^n) 階 B 樹）

紅黑樹定義和性質(zhì)

紅黑樹是一種含有紅黑結(jié)點(diǎn)并能自平衡的二叉搜索樹。

為了保證平衡，紅黑樹必須滿足以下性質(zhì)：

每個(gè)結(jié)點(diǎn)是要么是紅色或黑色

根結(jié)點(diǎn)必須是黑色

葉結(jié)點(diǎn)（外部結(jié)點(diǎn)、空結(jié)點(diǎn)）是黑色

紅色結(jié)點(diǎn)不能連續(xù)（也就是，紅色結(jié)點(diǎn)的孩子和父親都是黑色）

對于每個(gè)結(jié)點(diǎn)，從該點(diǎn)至nil（樹尾端，Java 中為null的結(jié)點(diǎn)）的任何路徑都包含所相同個(gè)數(shù)的黑色結(jié)點(diǎn)

紅黑樹與 B 樹的等價(jià)變換

根據(jù)上面的性質(zhì)，可以畫出這樣一棵紅黑樹。接下來對紅黑樹做等價(jià)變換，即將所有的紅色結(jié)點(diǎn)上升一層與它的父結(jié)點(diǎn)放在同一行，這就很像一棵 4 階 B 樹，轉(zhuǎn)換效果如下圖所示。

可以得出結(jié)論：

紅黑樹與 4 階 B 樹（2-3-4樹）具有等價(jià)性

黑色結(jié)點(diǎn)與紅色子結(jié)點(diǎn)融合在一起，形成 1 個(gè) B 樹結(jié)點(diǎn)

紅黑樹的黑色結(jié)點(diǎn)個(gè)數(shù)與 4 階 B 樹的結(jié)點(diǎn)總個(gè)數(shù)相等

紅黑樹的基本操作

當(dāng)我們對一棵平衡二叉搜索樹進(jìn)行插入、刪除的時(shí)候，很可能會讓這棵樹變得失衡（最壞可能導(dǎo)致所有祖先結(jié)點(diǎn)失衡，但是父結(jié)點(diǎn)和非祖先結(jié)點(diǎn)都不可能失衡）。

為了達(dá)到平衡，需要對樹進(jìn)行旋轉(zhuǎn)。而紅黑樹能夠達(dá)到自平衡，靠的也就是左旋、右旋和變色。

旋轉(zhuǎn)操作是局部的。當(dāng)一側(cè)子樹的結(jié)點(diǎn)少了，向另一側(cè)“借”一些結(jié)點(diǎn)；當(dāng)一側(cè)子樹的結(jié)點(diǎn)多了，則“租”一些結(jié)點(diǎn)給另一側(cè)。

為了更清楚地講解這部分內(nèi)容，先聲明幾個(gè)概念：

N-node：當(dāng)前結(jié)點(diǎn)

P-parent：父結(jié)點(diǎn)

S-sibling：兄弟結(jié)點(diǎn)

U-uncle：叔父結(jié)點(diǎn)（P 的兄弟結(jié)點(diǎn)）

G-grand：祖父結(jié)點(diǎn)（P 的父結(jié)點(diǎn)）

左旋

左旋指的是以某個(gè)結(jié)點(diǎn)作為支點(diǎn)（旋轉(zhuǎn)結(jié)點(diǎn)），其右子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)，右子結(jié)點(diǎn)的左子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的右子結(jié)點(diǎn)，左子結(jié)點(diǎn)保持不變。

不考慮結(jié)點(diǎn)顏色，可以看到左旋只影響旋轉(zhuǎn)結(jié)點(diǎn)和其右子樹的結(jié)構(gòu)，把右子樹的結(jié)點(diǎn)往左子樹移動。

右旋

右旋指的是以某個(gè)結(jié)點(diǎn)作為支點(diǎn)（旋轉(zhuǎn)結(jié)點(diǎn)），其左子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)，左子結(jié)點(diǎn)的右子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的左子結(jié)點(diǎn)，右子結(jié)點(diǎn)保持不變。

不考慮結(jié)點(diǎn)顏色，可以看到右旋只影響旋轉(zhuǎn)結(jié)點(diǎn)和其左子樹的結(jié)構(gòu)，把左子樹的結(jié)點(diǎn)往右子樹移動。

變色

變色指的是結(jié)點(diǎn)的顏色由紅變黑或由黑變紅。

變換規(guī)則

將左旋、右旋和變色結(jié)合起來，得到一套變換規(guī)則。

變色：如果當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)和叔父結(jié)點(diǎn)是紅色，那么：

把父結(jié)點(diǎn)和叔父結(jié)點(diǎn)變?yōu)楹谏?/p>

把祖父結(jié)點(diǎn)變?yōu)榧t色

把指針定義到祖父結(jié)點(diǎn)

左旋：當(dāng)前結(jié)點(diǎn)是右子樹，且父結(jié)點(diǎn)是紅色，叔父結(jié)點(diǎn)是黑色，對它的父結(jié)點(diǎn)左旋。

右旋：當(dāng)前結(jié)點(diǎn)是左子樹，且父結(jié)點(diǎn)是紅色，叔父結(jié)點(diǎn)是黑色，那么：

把父結(jié)點(diǎn)變?yōu)楹谏?/p>

把祖父結(jié)點(diǎn)變?yōu)榧t色

對祖父結(jié)點(diǎn)右旋

紅黑樹搜索

由于紅黑樹本來就是平衡二叉搜索樹，并且搜索也不會破壞樹的平衡，所以搜索算法也與平衡二叉搜索樹一致：

具體步驟如下：

從根結(jié)點(diǎn)開始檢索，把根結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)。

若當(dāng)前結(jié)點(diǎn)為空，返回 nil。

若當(dāng)前結(jié)點(diǎn)不為空，比較當(dāng)前結(jié)點(diǎn) key 與搜索 key 的大小。

若當(dāng)前結(jié)點(diǎn) key 等于搜索 key，那么該 key 就是搜索目標(biāo)，返回當(dāng)前結(jié)點(diǎn)。

若當(dāng)前結(jié)點(diǎn) key 大于搜索 key，把當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)，重復(fù)步驟 2。

若當(dāng)前結(jié)點(diǎn) key 小于搜索 key，把當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)，重復(fù)步驟 2。

紅黑樹插入

紅黑樹插入操作分為下面兩步：

定位插入的位置

具體步驟如下：

從根結(jié)點(diǎn)開始檢索。

若根結(jié)點(diǎn)為空，那么插入結(jié)點(diǎn)設(shè)為根結(jié)點(diǎn)，結(jié)束。

若根結(jié)點(diǎn)不為空，那么把根結(jié)點(diǎn)設(shè)為當(dāng)前結(jié)點(diǎn)。

若當(dāng)前結(jié)點(diǎn)為 nil，返回當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)，結(jié)束。

若當(dāng)前結(jié)點(diǎn) key 等于搜索 key，那么該 key 所在結(jié)點(diǎn)就是插入結(jié)點(diǎn)，更新結(jié)點(diǎn)的值，結(jié)束。

若當(dāng)前結(jié)點(diǎn) key 大于搜索 key，把當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)，重復(fù)步驟 4。

若當(dāng)前結(jié)點(diǎn) key 小于搜索 key，把當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)設(shè)置為當(dāng)前結(jié)點(diǎn)，重復(fù)步驟 4。

插入后實(shí)現(xiàn)自平衡

建議新添加的結(jié)點(diǎn)默認(rèn)為紅色，因此這樣能夠讓紅黑樹的性質(zhì)盡快滿足。不過如果添加的結(jié)點(diǎn)是根結(jié)點(diǎn)，設(shè)為黑色即可。

總結(jié)一下紅黑樹插入可能出現(xiàn)的所有場景：

①場景 1：紅黑樹為空樹

紅黑樹的性質(zhì) 2：根結(jié)點(diǎn)必須是黑色。

處理：直接把插入結(jié)點(diǎn)設(shè)成黑色并作為根結(jié)點(diǎn)。

②場景 2：插入結(jié)點(diǎn)的 key 已存在

二叉搜索樹中不能插入相同元素，既然結(jié)點(diǎn)的 key 已經(jīng)存在，紅黑樹也已平衡，無需重復(fù)插入。 處理：

將插入結(jié)點(diǎn)設(shè)為將要替換結(jié)點(diǎn)的顏色

更新當(dāng)前結(jié)點(diǎn)的值為插入結(jié)點(diǎn)的值

③場景 3：插入結(jié)點(diǎn)的父結(jié)點(diǎn)為黑色

插入的結(jié)點(diǎn)默認(rèn)是紅色的，當(dāng)它的父結(jié)點(diǎn)是黑色時(shí)，并不會破壞平衡。 處理：直接插入。 ④場景 4：插入結(jié)點(diǎn)的父結(jié)點(diǎn)為紅色

如果插入結(jié)點(diǎn)的父結(jié)點(diǎn)為紅色，那么父結(jié)點(diǎn)不可能為根結(jié)點(diǎn)，所以插入結(jié)點(diǎn)總是存在祖父結(jié)點(diǎn)。這點(diǎn)很重要，后續(xù)的旋轉(zhuǎn)操作需要祖父結(jié)點(diǎn)的參與。 場景 4.1：存在叔父結(jié)點(diǎn)，且為紅色

由紅黑樹性質(zhì) 4 可知：紅色結(jié)點(diǎn)不能連續(xù)。那么此時(shí)該插入子樹的紅黑層數(shù)的情況是：黑-紅-紅。顯然最簡單的處理方式就是將其改為：紅-黑-紅。

處理：

將父結(jié)點(diǎn)和叔父結(jié)點(diǎn)變?yōu)楹谏?/p>

將祖父結(jié)點(diǎn)變?yōu)榧t色

將祖父結(jié)點(diǎn)設(shè)置為當(dāng)前插入結(jié)點(diǎn)

場景 4.2：叔父結(jié)點(diǎn)不存在或?yàn)楹谏?，插入結(jié)點(diǎn)的父結(jié)點(diǎn)是祖父結(jié)點(diǎn)的左子結(jié)點(diǎn)這種場景下，叔父結(jié)點(diǎn)所在的子樹的黑色結(jié)點(diǎn)就比父結(jié)點(diǎn)所在子樹的多，不滿足紅黑樹的性質(zhì) 5。

場景 4.2.1：插入結(jié)點(diǎn)是左子樹

處理：

將父結(jié)點(diǎn)變?yōu)楹谏?/p>

將祖父結(jié)點(diǎn)變?yōu)榧t色

將祖父結(jié)點(diǎn)右旋

場景 4.2.2：插入結(jié)點(diǎn)是左子樹

這種場景顯然可以轉(zhuǎn)換為 4.2.1。

處理：

將父結(jié)點(diǎn)進(jìn)行左旋

將父結(jié)點(diǎn)設(shè)為插入結(jié)點(diǎn)，得到場景 4.2.1

進(jìn)行場景 4.2.1 的處理

場景 4.3：叔父結(jié)點(diǎn)不存在或?yàn)楹谏?，插入結(jié)點(diǎn)的父結(jié)點(diǎn)是祖父結(jié)點(diǎn)的右子結(jié)點(diǎn)相當(dāng)于場景 4.2 的方向反轉(zhuǎn)，直接看圖。

場景 4.3.1：插入結(jié)點(diǎn)是左子樹

處理：

將父結(jié)點(diǎn)變?yōu)楹谏?/p>

將祖父結(jié)點(diǎn)變?yōu)榧t色

對祖父結(jié)點(diǎn)進(jìn)行左旋

場景 4.3.2：插入結(jié)點(diǎn)是右子樹

處理：

將父結(jié)點(diǎn)進(jìn)行右旋

將父結(jié)點(diǎn)設(shè)置為插入結(jié)點(diǎn)，得到場景 4.3.1

進(jìn)行場景 4.3.1 的處理

下面舉個(gè)例子，往一棵紅黑樹中插入元素，整棵樹的變換如下圖所示：

紅黑樹刪除

紅黑樹刪除操作也分為兩步：

定位刪除的位置

定位刪除位置可以復(fù)用紅黑樹搜索的操作。

如果不存在目標(biāo)結(jié)點(diǎn)，忽略本次操作；如果找到目標(biāo)結(jié)點(diǎn)，刪除后進(jìn)行自平衡處理。

刪除后實(shí)現(xiàn)自平衡

二叉搜索樹刪除的時(shí)候可能出現(xiàn)三種場景：

若刪除結(jié)點(diǎn)無子結(jié)點(diǎn)，直接刪除即可。

若刪除結(jié)點(diǎn)只有一個(gè)子結(jié)點(diǎn)，用子結(jié)點(diǎn)替換刪除結(jié)點(diǎn)。

若刪除結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，用**后繼結(jié)點(diǎn)（大于刪除結(jié)點(diǎn)的最小結(jié)點(diǎn)）**替換刪除結(jié)點(diǎn)。

具體應(yīng)用，可以借助這張圖理解：

我們可以發(fā)現(xiàn)，另外兩種二叉樹的刪除場景都可以通過相互轉(zhuǎn)換變?yōu)閳鼍耙弧?在場景二情況下：刪除結(jié)點(diǎn)用其唯一的子結(jié)點(diǎn)替換，子結(jié)點(diǎn)替換為刪除結(jié)點(diǎn)后，可以認(rèn)為刪除的是子結(jié)點(diǎn)，若子結(jié)點(diǎn)又有兩個(gè)子結(jié)點(diǎn)，那么相當(dāng)于轉(zhuǎn)換為場景三，一直自頂向下轉(zhuǎn)換，總是能轉(zhuǎn)換為場景一。

在場景三情況下：刪除結(jié)點(diǎn)用后繼結(jié)點(diǎn)，如果后繼結(jié)點(diǎn)有右子結(jié)點(diǎn)，那么相當(dāng)于轉(zhuǎn)換為場景二，否則轉(zhuǎn)為場景一。

綜上所述，刪除的結(jié)點(diǎn)可以看作刪除替換結(jié)點(diǎn)，且替換結(jié)點(diǎn)最后總是在樹末。

下面總結(jié)一下紅黑樹刪除可能出現(xiàn)的所有場景：

為了方面理解，我們先約定一下結(jié)點(diǎn)的叫法：

R：替換結(jié)點(diǎn)

P：替換結(jié)點(diǎn)的父結(jié)點(diǎn)

S：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)

SL：兄弟結(jié)點(diǎn)的左子結(jié)點(diǎn)

SR：兄弟結(jié)點(diǎn)的右子結(jié)點(diǎn)

灰色：結(jié)點(diǎn)顏色可能是紅色，也可能是黑色

注意：R 是即將被替換到刪除結(jié)點(diǎn)的位置的替換結(jié)點(diǎn)，在刪除前，它還在原來所在位置參與樹的子平衡，平衡后再替換到刪除結(jié)點(diǎn)的位置，才算刪除完成。 ①場景 1：替換結(jié)點(diǎn)為紅色 我們把替換結(jié)點(diǎn)換到了刪除結(jié)點(diǎn)的位置時(shí)，由于替換結(jié)點(diǎn)為紅色，刪除也了不會影響紅黑樹的平衡，只要把替換結(jié)點(diǎn)的顏色變?yōu)閯h除的結(jié)點(diǎn)的顏色即可重新平衡。

處理：替換結(jié)點(diǎn)顏色變?yōu)閯h除結(jié)點(diǎn)的顏色。

②場景 2：替換結(jié)點(diǎn)為黑色

當(dāng)替換結(jié)點(diǎn)是黑色時(shí)，就必須進(jìn)行自平衡處理了，我們可以通過區(qū)分替換結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)還是右子結(jié)點(diǎn)，來做不同的旋轉(zhuǎn)，使樹重新平衡。

場景 2.1：替換結(jié)點(diǎn)是左子樹場景 2.1.1：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)為紅色

若兄弟結(jié)點(diǎn)是紅結(jié)點(diǎn)，那么根據(jù)紅黑樹性質(zhì) 4，兄弟結(jié)點(diǎn)的父結(jié)點(diǎn)和子結(jié)點(diǎn)肯定為黑色，按照下圖方式處理，得到刪除場景 2.1.2.3。

處理：

將兄弟結(jié)點(diǎn)變?yōu)楹谏?/p>

將父結(jié)點(diǎn)變?yōu)榧t色

對父結(jié)點(diǎn)進(jìn)行左旋，得到場景 2.1.2.3

進(jìn)行場景 2.1.2.3 的處理

場景 2.1.2：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)為黑色 當(dāng)兄弟結(jié)點(diǎn)為黑時(shí)，其父結(jié)點(diǎn)和子結(jié)點(diǎn)的具體顏色也無法確定，此時(shí)又得考慮多種子場景。

場景 2.1.2.1：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)的右子結(jié)點(diǎn)為紅色，左子結(jié)點(diǎn)任意顏色

即將刪除的左子樹的一個(gè)黑色結(jié)點(diǎn)，顯然左子樹的黑色結(jié)點(diǎn)少 1 了，然而右子結(jié)點(diǎn)又是紅色，那么我們直接向右子樹“借”個(gè)紅結(jié)點(diǎn)來補(bǔ)充黑結(jié)點(diǎn)，并進(jìn)行旋轉(zhuǎn)處理。

如圖所示：

處理：

將兄弟結(jié)點(diǎn)的顏色變?yōu)楦附Y(jié)點(diǎn)的顏色

將父結(jié)點(diǎn)變?yōu)楹谏?/p>

將兄弟結(jié)點(diǎn)的右子結(jié)點(diǎn)變?yōu)楹谏?/p>

對父結(jié)點(diǎn)進(jìn)行左旋

場景 2.1.2.2：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)的右子結(jié)點(diǎn)為黑色，左子結(jié)點(diǎn)為紅色 兄弟結(jié)點(diǎn)所在的子樹有紅結(jié)點(diǎn)，又可以向兄弟子樹“借”個(gè)紅結(jié)點(diǎn)過來，這就轉(zhuǎn)換回了場景 2.1.2.1。

如圖所示：

處理：

將兄弟結(jié)點(diǎn)變?yōu)榧t色

將兄弟結(jié)點(diǎn)的左子結(jié)點(diǎn)變?yōu)楹谏?/p>

對兄弟結(jié)點(diǎn)進(jìn)行右旋，得到場景 2.1.2.1

進(jìn)行場景 2.1.2.1 的處理

場景 2.1.2.3：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)的子結(jié)點(diǎn)都為黑色

兄弟子樹沒有紅結(jié)點(diǎn)可以“借”了，再向父結(jié)點(diǎn)“借”。如果父結(jié)點(diǎn)是黑色，為了讓父結(jié)點(diǎn)在所在的子樹中保證平衡（替換結(jié)點(diǎn)即將刪除，少了一個(gè)黑色結(jié)點(diǎn)，子樹也需要少一個(gè)）先把兄弟結(jié)點(diǎn)變?yōu)榧t色，再讓父結(jié)點(diǎn)成為新的替換結(jié)點(diǎn)。

處理：

如果父結(jié)點(diǎn)為黑色：將兄弟結(jié)點(diǎn)變?yōu)榧t色；將父結(jié)點(diǎn)作為新的替換結(jié)點(diǎn)；重新進(jìn)行刪除結(jié)點(diǎn)的場景處理。

如果父結(jié)點(diǎn)為紅色：替換結(jié)點(diǎn)的父結(jié)點(diǎn)和替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)顏色交換；刪除結(jié)點(diǎn)和替換結(jié)點(diǎn)的值交換后，刪除替換結(jié)點(diǎn)。

場景 2.2：替換結(jié)點(diǎn)是右子樹

實(shí)際上是場景 2.1 的鏡像操作。

場景 2.2.1：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)為紅色

處理：

將兄弟結(jié)點(diǎn)變?yōu)楹谏?/p>

將父結(jié)點(diǎn)變?yōu)榧t色

對父結(jié)點(diǎn)進(jìn)行右旋，得到場景 2.2.2.3

進(jìn)行場景 2.2.2.3 的處理

場景 2.2.2：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)為黑色場景 2.2.2.1：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)的左子結(jié)點(diǎn)為紅色，右子結(jié)點(diǎn)任意顏色

處理：

將兄弟結(jié)點(diǎn)的顏色變?yōu)楦附Y(jié)點(diǎn)的顏色

將父結(jié)點(diǎn)變?yōu)楹谏?/p>

將兄弟結(jié)點(diǎn)的左子結(jié)點(diǎn)變?yōu)楹谏?/p>

對父結(jié)點(diǎn)進(jìn)行右旋

場景 2.2.2.2：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)的左子結(jié)點(diǎn)為黑色，右子結(jié)點(diǎn)為紅色

處理：

將兄弟結(jié)點(diǎn)變?yōu)榧t色

將兄弟結(jié)點(diǎn)的右子結(jié)點(diǎn)設(shè)為黑色

對兄弟結(jié)點(diǎn)進(jìn)行左旋，得到場景 2.2.2.1

進(jìn)行場景 2.2.2.1 的處理

場景 2.2.2.3：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)的子結(jié)點(diǎn)都為黑色

處理：

如果父結(jié)點(diǎn)為黑色：將兄弟結(jié)點(diǎn)變?yōu)榧t色；將父結(jié)點(diǎn)作為新的替換結(jié)點(diǎn)；重新進(jìn)行刪除結(jié)點(diǎn)的場景處理。

如果父結(jié)點(diǎn)為紅色：替換結(jié)點(diǎn)的父結(jié)點(diǎn)和替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)顏色交換；刪除結(jié)點(diǎn)和替換結(jié)點(diǎn)的值交換后，刪除替換結(jié)點(diǎn)。