紅黑樹（Red Black Tree）是一種自平衡的二叉搜索樹

紅黑樹（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。又稱為二叉查找樹、二叉排序樹。

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

②平衡

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

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

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

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

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

由此引申出 AVL 樹的概念。

AVL 樹

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

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

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

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

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

可以看到 AVL 樹具有以下特點：

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

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

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

B 樹

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

這是一個簡單的 3 階 B 樹：

特點如下：

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

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

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

比較矮

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

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

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

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

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

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

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

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

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

以此類推。

②B 樹 VS 二叉搜索樹

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

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

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

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

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

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

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

每個結(jié)點是要么是紅色或黑色

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

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

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

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

紅黑樹與 B 樹的等價變換

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

可以得出結(jié)論：

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

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

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

紅黑樹的基本操作

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

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

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

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

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

P-parent：父結(jié)點

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

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

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

左旋

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

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

右旋

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

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

變色

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

變換規(guī)則

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

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

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

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

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

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

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

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

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

對祖父結(jié)點右旋

紅黑樹搜索

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

具體步驟如下：

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

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

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

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

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

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

紅黑樹插入

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

定位插入的位置

具體步驟如下：

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

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

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

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

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

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

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

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

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

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

①場景 1：紅黑樹為空樹

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

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

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

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

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

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

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

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

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

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

處理：

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

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

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

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

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

處理：

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

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

將祖父結(jié)點右旋

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

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

處理：

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

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

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

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

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

處理：

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

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

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

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

處理：

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

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

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

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

紅黑樹刪除

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

定位刪除的位置

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

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

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

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

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

若刪除結(jié)點只有一個子結(jié)點，用子結(jié)點替換刪除結(jié)點。

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

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

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

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

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

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

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

R：替換結(jié)點

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

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

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

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

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

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

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

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

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

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

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

處理：

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

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

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

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

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

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

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

如圖所示：

處理：

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

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

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

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

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

如圖所示：

處理：

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

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

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

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

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

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

處理：

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

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

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

實際上是場景 2.1 的鏡像操作。

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

處理：

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

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

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

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

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

處理：

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

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

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

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

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

處理：

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

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

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

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

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

處理：

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

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