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

預(yù)備知識(shí)

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

平衡二叉搜索樹(shù)

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

①二叉搜索樹(shù)

二叉搜索樹(shù)（Binary Search Tree）是二叉樹(shù)的一種，英文簡(jiǎn)稱(chēng) BST。又稱(chēng)為二叉查找樹(shù)、二叉排序樹(shù)。

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

②平衡

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

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

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

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

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

由此引申出 AVL 樹(shù)的概念。

AVL 樹(shù)

AVL 樹(shù)是最早發(fā)明的自平衡二叉搜索樹(shù)之一，它取名自?xún)晌话l(fā)明家的名字：G.M.Adelson-Velsky 和 E.M.Landis。

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

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

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

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

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

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

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

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

B 樹(shù)

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

這是一個(gè)簡(jiǎn)單的 3 階 B 樹(shù)：

特點(diǎn)如下：

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

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

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

比較矮

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

m 階 B 樹(shù)指的是一個(gè)結(jié)點(diǎn)最多擁有 m 個(gè)子結(jié)點(diǎn)。假設(shè)一個(gè)結(jié)點(diǎn)存儲(chǔ)的元素個(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é)符號(hào) ┌ ┐ 表示；向下取整（Floor），指的是取比自己小的最大整數(shù)，用數(shù)學(xué)符號(hào) └ ┘ 表示。 比如 m=3，子結(jié)點(diǎn)個(gè)數(shù) 2≤y≤3，這個(gè) B 樹(shù)可以稱(chēng)為（2，3）樹(shù)、2-3 樹(shù)。 比如 m=4，子結(jié)點(diǎn)個(gè)數(shù) 2≤y≤4，這個(gè) B 樹(shù)可以稱(chēng)為（2，4）樹(shù)、2-3-4 樹(shù)。

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

以此類(lèi)推。

②B 樹(shù) VS 二叉搜索樹(shù)

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

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

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

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

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

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

為了保證平衡，紅黑樹(shù)必須滿(mǎ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)的孩子和父親都是黑色）

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

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

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

可以得出結(jié)論：

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

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

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

紅黑樹(shù)的基本操作

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

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

旋轉(zhuǎn)操作是局部的。當(dāng)一側(cè)子樹(shù)的結(jié)點(diǎn)少了，向另一側(cè)“借”一些結(jié)點(diǎn)；當(dāng)一側(cè)子樹(shù)的結(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)和其右子樹(shù)的結(jié)構(gòu)，把右子樹(shù)的結(jié)點(diǎn)往左子樹(shù)移動(dòng)。

右旋

右旋指的是以某個(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)和其左子樹(shù)的結(jié)構(gòu)，把左子樹(shù)的結(jié)點(diǎn)往右子樹(shù)移動(dòng)。

變色

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

變換規(guī)則

將左旋、右旋和變色結(jié)合起來(lái)，得到一套變換規(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)是右子樹(shù)，且父結(jié)點(diǎn)是紅色，叔父結(jié)點(diǎn)是黑色，對(duì)它的父結(jié)點(diǎn)左旋。

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

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

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

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

紅黑樹(shù)搜索

由于紅黑樹(shù)本來(lái)就是平衡二叉搜索樹(shù)，并且搜索也不會(huì)破壞樹(shù)的平衡，所以搜索算法也與平衡二叉搜索樹(shù)一致：

具體步驟如下：

從根結(jié)點(diǎn)開(kāi)始檢索，把根結(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。

紅黑樹(shù)插入

紅黑樹(shù)插入操作分為下面兩步：

定位插入的位置

具體步驟如下：

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

若根結(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)為紅色，因此這樣能夠讓紅黑樹(shù)的性質(zhì)盡快滿(mǎn)足。不過(guò)如果添加的結(jié)點(diǎn)是根結(jié)點(diǎn)，設(shè)為黑色即可。

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

①場(chǎng)景 1：紅黑樹(shù)為空樹(shù)

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

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

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

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

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

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

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

插入的結(jié)點(diǎn)默認(rèn)是紅色的，當(dāng)它的父結(jié)點(diǎn)是黑色時(shí)，并不會(huì)破壞平衡。 處理：直接插入。 ④場(chǎng)景 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)的參與。 場(chǎng)景 4.1：存在叔父結(jié)點(diǎn)，且為紅色

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

處理：

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

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

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

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

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

處理：

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

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

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

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

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

處理：

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

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

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

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

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

處理：

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

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

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

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

處理：

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

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

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

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

紅黑樹(shù)刪除

紅黑樹(shù)刪除操作也分為兩步：

定位刪除的位置

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

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

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

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

若刪除結(jié)點(diǎn)無(wú)子結(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)，另外兩種二叉樹(shù)的刪除場(chǎng)景都可以通過(guò)相互轉(zhuǎn)換變?yōu)閳?chǎng)景一。 在場(chǎng)景二情況下：刪除結(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)換為場(chǎng)景三，一直自頂向下轉(zhuǎn)換，總是能轉(zhuǎn)換為場(chǎng)景一。

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

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

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

為了方面理解，我們先約定一下結(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)，在刪除前，它還在原來(lái)所在位置參與樹(shù)的子平衡，平衡后再替換到刪除結(jié)點(diǎn)的位置，才算刪除完成。 ①場(chǎng)景 1：替換結(jié)點(diǎn)為紅色 我們把替換結(jié)點(diǎn)換到了刪除結(jié)點(diǎn)的位置時(shí)，由于替換結(jié)點(diǎn)為紅色，刪除也了不會(huì)影響紅黑樹(shù)的平衡，只要把替換結(jié)點(diǎn)的顏色變?yōu)閯h除的結(jié)點(diǎn)的顏色即可重新平衡。

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

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

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

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

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

處理：

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

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

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

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

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

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

即將刪除的左子樹(shù)的一個(gè)黑色結(jié)點(diǎn)，顯然左子樹(shù)的黑色結(jié)點(diǎn)少 1 了，然而右子結(jié)點(diǎn)又是紅色，那么我們直接向右子樹(shù)“借”個(gè)紅結(jié)點(diǎn)來(lái)補(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>

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

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

如圖所示：

處理：

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

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

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

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

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

兄弟子樹(shù)沒(méi)有紅結(jié)點(diǎn)可以“借”了，再向父結(jié)點(diǎn)“借”。如果父結(jié)點(diǎn)是黑色，為了讓父結(jié)點(diǎn)在所在的子樹(shù)中保證平衡（替換結(jié)點(diǎn)即將刪除，少了一個(gè)黑色結(jié)點(diǎn)，子樹(shù)也需要少一個(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)的場(chǎng)景處理。

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

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

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

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

處理：

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

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

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

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

場(chǎng)景 2.2.2：替換結(jié)點(diǎn)的兄弟結(jié)點(diǎn)為黑色場(chǎng)景 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>

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

場(chǎng)景 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è)為黑色

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

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

場(chǎng)景 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)的場(chǎng)景處理。

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