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

預備知識

樹的知識框架結構如下圖所示：

平衡二叉搜索樹

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

①二叉搜索樹

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

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

②平衡

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

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

③改進二叉搜索樹

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

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

由此引申出 AVL 樹的概念。

AVL 樹

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

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

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

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

再看這棵 AVL 樹和它每個結點對應的平衡因子：

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

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

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

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

B 樹

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

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

特點如下：

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

擁有二叉搜索樹的一些性質

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

比較矮

①m 階 B 樹的性質（m ≥ 2）

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

根結點：1 ≤ x ≤ m - 1

非根結點：┌ m / 2 ┐ - 1 ≤ x ≤ m - 1

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

根結點：2 ≤ y ≤ m

非根結點：┌ m / 2 ┐ ≤ y ≤ m

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

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

以此類推。

②B 樹 VS 二叉搜索樹

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

我們可以得到結論：

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

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

紅黑樹定義和性質

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

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

每個結點是要么是紅色或黑色

根結點必須是黑色

葉結點（外部結點、空結點）是黑色

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

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

紅黑樹與 B 樹的等價變換

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

可以得出結論：

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

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

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

紅黑樹的基本操作

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

為了達到平衡，需要對樹進行旋轉。而紅黑樹能夠達到自平衡，靠的也就是左旋、右旋和變色。

旋轉操作是局部的。當一側子樹的結點少了，向另一側“借”一些結點；當一側子樹的結點多了，則“租”一些結點給另一側。

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

N-node：當前結點

P-parent：父結點

S-sibling：兄弟結點

U-uncle：叔父結點（P 的兄弟結點）

G-grand：祖父結點（P 的父結點）

左旋

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

不考慮結點顏色，可以看到左旋只影響旋轉結點和其右子樹的結構，把右子樹的結點往左子樹移動。

右旋

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

不考慮結點顏色，可以看到右旋只影響旋轉結點和其左子樹的結構，把左子樹的結點往右子樹移動。

變色

變色指的是結點的顏色由紅變黑或由黑變紅。

變換規(guī)則

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

變色：如果當前結點的父結點和叔父結點是紅色，那么：

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

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

把指針定義到祖父結點

左旋：當前結點是右子樹，且父結點是紅色，叔父結點是黑色，對它的父結點左旋。

右旋：當前結點是左子樹，且父結點是紅色，叔父結點是黑色，那么：

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

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

對祖父結點右旋

紅黑樹搜索

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

具體步驟如下：

從根結點開始檢索，把根結點設置為當前結點。

若當前結點為空，返回 nil。

若當前結點不為空，比較當前結點 key 與搜索 key 的大小。

若當前結點 key 等于搜索 key，那么該 key 就是搜索目標，返回當前結點。

若當前結點 key 大于搜索 key，把當前結點的左子結點設置為當前結點，重復步驟 2。

若當前結點 key 小于搜索 key，把當前結點的右子結點設置為當前結點，重復步驟 2。

紅黑樹插入

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

定位插入的位置

具體步驟如下：

從根結點開始檢索。

若根結點為空，那么插入結點設為根結點，結束。

若根結點不為空，那么把根結點設為當前結點。

若當前結點為 nil，返回當前結點的父結點，結束。

若當前結點 key 等于搜索 key，那么該 key 所在結點就是插入結點，更新結點的值，結束。

若當前結點 key 大于搜索 key，把當前結點的左子結點設置為當前結點，重復步驟 4。

若當前結點 key 小于搜索 key，把當前結點的右子結點設置為當前結點，重復步驟 4。

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

建議新添加的結點默認為紅色，因此這樣能夠讓紅黑樹的性質盡快滿足。不過如果添加的結點是根結點，設為黑色即可。

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

①場景 1：紅黑樹為空樹

紅黑樹的性質 2：根結點必須是黑色。

處理：直接把插入結點設成黑色并作為根結點。

②場景 2：插入結點的 key 已存在

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

將插入結點設為將要替換結點的顏色

更新當前結點的值為插入結點的值

③場景 3：插入結點的父結點為黑色

插入的結點默認是紅色的，當它的父結點是黑色時，并不會破壞平衡。 處理：直接插入。 ④場景 4：插入結點的父結點為紅色

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

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

處理：

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

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

將祖父結點設置為當前插入結點

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

場景 4.2.1：插入結點是左子樹

處理：

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

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

將祖父結點右旋

場景 4.2.2：插入結點是左子樹

這種場景顯然可以轉換為 4.2.1。

處理：

將父結點進行左旋

將父結點設為插入結點，得到場景 4.2.1

進行場景 4.2.1 的處理

場景 4.3：叔父結點不存在或為黑色，插入結點的父結點是祖父結點的右子結點相當于場景 4.2 的方向反轉，直接看圖。

場景 4.3.1：插入結點是左子樹

處理：

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

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

對祖父結點進行左旋

場景 4.3.2：插入結點是右子樹

處理：

將父結點進行右旋

將父結點設置為插入結點，得到場景 4.3.1

進行場景 4.3.1 的處理

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

紅黑樹刪除

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

定位刪除的位置

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

如果不存在目標結點，忽略本次操作；如果找到目標結點，刪除后進行自平衡處理。

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

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

若刪除結點無子結點，直接刪除即可。

若刪除結點只有一個子結點，用子結點替換刪除結點。

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

具體應用，可以借助這張圖理解：

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

在場景三情況下：刪除結點用后繼結點，如果后繼結點有右子結點，那么相當于轉換為場景二，否則轉為場景一。

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

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

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

R：替換結點

P：替換結點的父結點

S：替換結點的兄弟結點

SL：兄弟結點的左子結點

SR：兄弟結點的右子結點

灰色：結點顏色可能是紅色，也可能是黑色

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

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

②場景 2：替換結點為黑色

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

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

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

處理：

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

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

對父結點進行左旋，得到場景 2.1.2.3

進行場景 2.1.2.3 的處理

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

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

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

如圖所示：

處理：

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

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

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

對父結點進行左旋

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

如圖所示：

處理：

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

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

對兄弟結點進行右旋，得到場景 2.1.2.1

進行場景 2.1.2.1 的處理

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

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

處理：

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

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

場景 2.2：替換結點是右子樹

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

場景 2.2.1：替換結點的兄弟結點為紅色

處理：

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

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

對父結點進行右旋，得到場景 2.2.2.3

進行場景 2.2.2.3 的處理

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

處理：

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

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

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

對父結點進行右旋

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

處理：

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

將兄弟結點的右子結點設為黑色

對兄弟結點進行左旋，得到場景 2.2.2.1

進行場景 2.2.2.1 的處理

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

處理：

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

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