紅黑樹（Red Black Tree）是一種自平衡的二叉搜尋樹（Self-balancing Binary Search Tree）。以前也叫做平衡二叉 B 樹（Symmetric Binary B-tree）。
預備知識
樹的知識架構結構如下圖所示：
平衡二叉搜尋樹
平衡二叉搜尋樹（Balanced Binary Search Tree），英文簡稱 BBST。經典常見的平衡二叉搜尋樹是 AVL 樹和紅黑樹。
①二叉搜尋樹
二叉搜尋樹（Binary Search Tree）是二叉樹的一種，英文簡稱 BST。又稱為二叉查找樹、二叉排序樹。
它的特點是任何一個結點的值都大于其左子樹的所有結點的值，任何一個結點的值都小于其右子樹的所有結點的值。
②平衡
平衡（Balance）：就是當結點數量固定時，左右子樹的高度越接近，這棵二叉樹越平衡（高度越低）。而最理想的平衡就是完全二叉樹/滿二叉樹，高度最小的二叉樹。
一棵二叉搜尋樹平均時間複雜度可以認為是樹的高度 O(h)。像左邊這棵，結點的左右子樹的高度接近，屬于一棵平衡二叉搜尋樹，O(h) = O(logn)；而右邊這棵，高度達到了最大，已經退化成了連結清單，O(h)=O(n)。
③改進二叉搜尋樹
當二叉樹退化成連結清單時，性能是很低的，是以我們需要在結點的插入、删除操作之後，想辦法讓二叉搜尋樹恢複平衡（減小樹的高度）。
但是如果為了追求最理想的平衡，而增加了時間複雜度也不是很有必要，是以比較合理的方案就是：用盡量少的調整次數達到适度平衡。
由此引申出 AVL 樹的概念。
AVL 樹
AVL 樹是最早發明的自平衡二叉搜尋樹之一，它取名自兩位發明家的名字：G.M.Adelson-Velsky 和 E.M.Landis。
平衡因子（Balance Factor）：某結點的左右子樹的高度差。
每個葉子結點的平衡因子都是 0。看這棵二叉搜尋樹，紅色數字标注了每個結點對應的平衡因子。
舉例：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）是一種平衡的多路搜尋樹，多用于檔案系統、資料庫的實作。
這是一個簡單的 3 階 B 樹：
特點如下：
- 1 個結點可以存儲超過 2 個元素，可以擁有超過 2 個子結點
- 擁有二叉搜尋樹的一些性質
- 平衡，每個結點的所有子樹高度一緻
- 比較矮
①m 階 B 樹的性質（m ≥ 2）
m 階 B 樹指的是一個結點最多擁有 m 個子結點。假設一個結點存儲的元素個數為 x，那麼如果這個結點是：
- 根結點：1 ≤ x ≤ m - 1
- 非根結點：┌ m / 2 ┐ - 1 ≤ x ≤ m - 1
如果有子結點，子結點個數為 y = x + 1，那麼如果這個結點是：
- 根結點：2 ≤ y ≤ m
- 非根結點：┌ m / 2 ┐ ≤ y ≤ m
向上取整（Ceiling），指的是取比自己大的最小整數，用數學符号 ┌ ┐ 表示；向下取整（Floor），指的是取比自己小的最大整數，用數學符号 └ ┘ 表示。
比如 m=3，子結點個數 2≤y≤3，這個 B 樹可以稱為（2，3）樹、2-3 樹。
比如 m=4，子結點個數 2≤y≤4，這個 B 樹可以稱為（2，4）樹、2-3-4 樹。比如 m=5，子結點個數 3≤y≤4，這個 B 樹可以稱為（3，5）樹、3-4-5 樹。以此類推。
②B 樹 VS 二叉搜尋樹
這是一棵二叉搜尋樹，通過某些父子結點合并，恰好能與上面的 B 樹對應。我們可以得到結論：
- B 樹和二叉搜尋樹，在邏輯上是等價的
- 多代結點合并，可以獲得一個超級結點，且 n 代合并的超級結點，最多擁有 (2^n) 個子結點 （至少是 (2^n) 階 B 樹）
紅黑樹定義和性質
紅黑樹是一種含有紅黑結點并能自平衡的二叉搜尋樹。為了保證平衡，紅黑樹必須滿足以下性質：
- 每個結點是要麼是紅色或黑色
- 根結點必須是黑色
- 葉結點（外部結點、空結點）是黑色
- 紅色結點不能連續（也就是，紅色結點的孩子和父親都是黑色）
- 對于每個結點，從該點至 nil（樹尾端，Java 中為 null 的結點）的任何路徑都包含所相同個數的黑色結點
紅黑樹與 B 樹的等價變換
根據上面的性質，可以畫出這樣一棵紅黑樹。接下來對紅黑樹做等價變換，即将所有的紅色結點上升一層與它的父結點放在同一行，這就很像一棵 4 階 B 樹，轉換效果如下圖所示。
可以得出結論：
- 紅黑樹與 4 階 B 樹（2-3-4樹）具有等價性
- 黑色結點與紅色子結點融合在一起，形成 1 個 B 樹結點
- 紅黑樹的黑色結點個數與 4 階 B 樹的結點總個數相等
紅黑樹的基本操作
當我們對一棵平衡二叉搜尋樹進行插入、删除的時候，很可能會讓這棵樹變得失衡（最壞可能導緻所有祖先結點失衡，但是父結點和非祖先結點都不可能失衡）。為了達到平衡，需要對樹進行旋轉。而紅黑樹能夠達到自平衡，靠的也就是左旋、右旋和變色。
旋轉操作是局部的。當一側子樹的結點少了，向另一側“借”一些結點；當一側子樹的結點多了，則“租”一些結點給另一側。
為了更清楚地講解這部分内容，先聲明幾個概念：
- N-node：目前結點
- P-parent：父結點
- S-sibling：兄弟結點
- U-uncle：叔父結點（P 的兄弟結點）
- G-grand：祖父結點（P 的父結點）
左旋
左旋指的是以某個結點作為支點（旋轉結點），其右子結點變為旋轉結點的父結點，右子結點的左子結點變為旋轉結點的右子結點，左子結點保持不變。
不考慮結點顔色，可以看到左旋隻影響旋轉結點和其右子樹的結構，把右子樹的結點往左子樹移動。
右旋
右旋指的是以某個結點作為支點（旋轉結點），其左子結點變為旋轉結點的父結點，左子結點的右子結點變為旋轉結點的左子結點，右子結點保持不變。
不考慮結點顔色，可以看到右旋隻影響旋轉結點和其左子樹的結構，把左子樹的結點往右子樹移動。
變色
變色指的是結點的顔色由紅變黑或由黑變紅。
變換規則
将左旋、右旋和變色結合起來，得到一套變換規則。變色：如果目前結點的父結點和叔父結點是紅色，那麼：
- 把父結點和叔父結點變為黑色
- 把祖父結點變為紅色
- 把指針定義到祖父結點
左旋：目前結點是右子樹，且父結點是紅色，叔父結點是黑色，對它的父結點左旋。右旋：目前結點是左子樹，且父結點是紅色，叔父結點是黑色，那麼：
- 把父結點變為黑色
- 對祖父結點右旋
紅黑樹搜尋
由于紅黑樹本來就是平衡二叉搜尋樹，并且搜尋也不會破壞樹的平衡，是以搜尋算法也與平衡二叉搜尋樹一緻：
具體步驟如下：
- 從根結點開始檢索，把根結點設定為目前結點。
- 若目前結點為空，傳回 nil。
- 若目前結點不為空，比較目前結點 key 與搜尋 key 的大小。
- 若目前結點 key 等于搜尋 key，那麼該 key 就是搜尋目标，傳回目前結點。
- 若目前結點 key 大于搜尋 key，把目前結點的左子結點設定為目前結點，重複步驟 2。
- 若目前結點 key 小于搜尋 key，把目前結點的右子結點設定為目前結點，重複步驟 2。
紅黑樹插入
紅黑樹插入操作分為下面兩步：
定位插入的位置
- 從根結點開始檢索。
- 若根結點為空，那麼插入結點設為根結點，結束。
- 若根結點不為空，那麼把根結點設為目前結點。
- 若目前結點為 nil，傳回目前結點的父結點，結束。
- 若目前結點 key 等于搜尋 key，那麼該 key 所在結點就是插入結點，更新結點的值，結束。
- 若目前結點 key 大于搜尋 key，把目前結點的左子結點設定為目前結點，重複步驟 4。
- 若目前結點 key 小于搜尋 key，把目前結點的右子結點設定為目前結點，重複步驟 4。
插入後實作自平衡
建議新添加的結點預設為紅色，是以這樣能夠讓紅黑樹的性質盡快滿足。不過如果添加的結點是根結點，設為黑色即可。
總結一下紅黑樹插入可能出現的所有場景：
①場景 1：紅黑樹為空樹
紅黑樹的性質 2：根結點必須是黑色。處理：直接把插入結點設成黑色并作為根結點。②場景 2：插入結點的 key 已存在二叉搜尋樹中不能插入相同元素，既然結點的 key 已經存在，紅黑樹也已平衡，無需重複插入。
處理：
- 将插入結點設為将要替換結點的顔色
- 更新目前結點的值為插入結點的值
③場景 3：插入結點的父結點為黑色插入的結點預設是紅色的，當它的父結點是黑色時，并不會破壞平衡。
處理：直接插入。
④場景 4：插入結點的父結點為紅色如果插入結點的父結點為紅色，那麼父結點不可能為根結點，是以插入結點總是存在祖父結點。這點很重要，後續的旋轉操作需要祖父結點的參與。
場景 4.1：存在叔父結點，且為紅色
由紅黑樹性質 4 可知：紅色結點不能連續。那麼此時該插入子樹的紅黑層數的情況是：黑-紅-紅。顯然最簡單的處理方式就是将其改為：紅-黑-紅。
- 将父結點和叔父結點變為黑色
- 将祖父結點變為紅色
- 将祖父結點設定為目前插入結點
場景 4.2：叔父結點不存在或為黑色，插入結點的父結點是祖父結點的左子結點這種場景下，叔父結點所在的子樹的黑色結點就比父結點所在子樹的多，不滿足紅黑樹的性質 5。
場景 4.2.1：插入結點是左子樹
- 将父結點變為黑色
- 将祖父結點右旋
場景 4.2.2：插入結點是左子樹
這種場景顯然可以轉換為 4.2.1。
- 将父結點進行左旋
- 将父結點設為插入結點，得到場景 4.2.1
- 進行場景 4.2.1 的處理
場景 4.3：叔父結點不存在或為黑色，插入結點的父結點是祖父結點的右子結點相當于場景 4.2 的方向反轉，直接看圖。
場景 4.3.1：插入結點是左子樹
- 對祖父結點進行左旋
場景 4.3.2：插入結點是右子樹
- 将父結點進行右旋
- 将父結點設定為插入結點，得到場景 4.3.1
- 進行場景 4.3.1 的處理
下面舉個例子，往一棵紅黑樹中插入元素，整棵樹的變換如下圖所示：
紅黑樹删除
紅黑樹删除操作也分為兩步：
定位删除的位置
定位删除位置可以複用紅黑樹搜尋的操作。如果不存在目标結點，忽略本次操作；如果找到目标結點，删除買二手地圖後進行自平衡處理。
删除後實作自平衡
二叉搜尋樹删除的時候可能出現三種場景：
- 若删除結點無子結點，直接删除即可。
- 若删除結點隻有一個子結點，用子結點替換删除結點。
- 若删除結點有兩個子結點，用**後繼結點（大于删除結點的最小結點）**替換删除結點。
具體應用，可以借助這張圖了解：
我們可以發現，另外兩種二叉樹的删除場景都可以通過互相轉換變為場景一。
在場景二情況下：删除結點用其唯一的子結點替換，子結點替換為删除結點後，可以認為删除的是子結點，若子結點又有兩個子結點，那麼相當于轉換為場景三，一直自頂向下轉換，總是能轉換為場景一。
在場景三情況下：删除結點用後繼結點，如果後繼結點有右子結點，那麼相當于轉換為場景二，否則轉為場景一。
綜上所述，删除的結點可以看作删除替換結點，且替換結點最後總是在樹末。下面總結一下紅黑樹删除可能出現的所有場景：
為了方面了解，我們先約定一下結點的叫法：
- R：替換結點
- P：替換結點的父結點
- S：替換結點的兄弟結點
- SL：兄弟結點的左子結點
- SR：兄弟結點的右子結點
- 灰色：結點顔色可能是紅色，也可能是黑色
注意：R 是即将被替換到删除結點的位置的替換結點，在删除前，它還在原來所在位置參與樹的子平衡，平衡後再替換到删除結點的位置，才算删除完成。
①場景 1：替換結點為紅色
我們把替換結點換到了删除結點的位置時，由于替換結點為紅色，删除也了不會影響紅黑樹的平衡，隻要把替換結點的顔色變為删除的結點的顔色即可重新平衡。處理：替換結點顔色變為删除結點的顔色。②場景 2：替換結點為黑色當替換結點是黑色時，就必須進行自平衡處理了，我們可以通過區分替換結點是其父結點的左子結點還是右子結點，來做不同的旋轉，使樹重新平衡。場景 2.1：替換結點是左子樹
場景 2.1.1：替換結點的兄弟結點為紅色
若兄弟結點是紅結點，那麼根據紅黑樹性質 4，兄弟結點的父結點和子結點肯定為黑色，按照下圖方式處理，得到删除場景 2.1.2.3。
- 将兄弟結點變為黑色
- 将父結點變為紅色
- 對父結點進行左旋，得到場景 2.1.2.3
- 進行場景 2.1.2.3 的處理
場景 2.1.2：替換結點的兄弟結點為黑色
當兄弟結點為黑時，其父結點和子結點的具體顔色也無法确定，此時又得考慮多種子場景。場景 2.1.2.1：替換結點的兄弟結點的右子結點為紅色，左子結點任意顔色即将删除的左子樹的一個黑色結點，顯然左子樹的黑色結點少 1 了，然而右子結點又是紅色，那麼我們直接向右子樹“借”個紅結點來補充黑結點，并進行旋轉處理。
如圖所示：
- 将兄弟結點的顔色變為父結點的顔色
- 将兄弟結點的右子結點變為黑色
- 對父結點進行左旋
場景 2.1.2.2：替換結點的兄弟結點的右子結點為黑色，左子結點為紅色
兄弟結點所在的子樹有紅結點，又可以向兄弟子樹“借”個紅結點過來，這就轉換回了場景 2.1.2.1。
- 将兄弟結點變為紅色
- 将兄弟結點的左子結點變為黑色
- 對兄弟結點進行右旋，得到場景 2.1.2.1
- 進行場景 2.1.2.1 的處理
場景 2.1.2.3：替換結點的兄弟結點的子結點都為黑色
兄弟子樹沒有紅結點可以“借”了，再向父結點“借”。如果父結點是黑色，為了讓父結點在所在的子樹中保證平衡（替換結點即将删除，少了一個黑色結點，子樹也需要少一個）先把兄弟結點變為紅色，再讓父結點成為新的替換結點。
- 如果父結點為黑色：将兄弟結點變為紅色；将父結點作為新的替換結點；重新進行删除結點的場景處理。
- 如果父結點為紅色：替換結點的父結點和替換結點的兄弟結點顔色交換；删除結點和替換結點的值交換後，删除替換結點。
場景 2.2：替換結點是右子樹實際上是場景 2.1 的鏡像操作。
場景 2.2.1：替換結點的兄弟結點為紅色
- 對父結點進行右旋，得到場景 2.2.2.3
- 進行場景 2.2.2.3 的處理
場景 2.2.2：替換結點的兄弟結點為黑色
場景 2.2.2.1：替換結點的兄弟結點的左子結點為紅色，右子結點任意顔色
- 對父結點進行右旋
場景 2.2.2.2：替換結點的兄弟結點的左子結點為黑色，右子結點為紅色
- 将兄弟結點的右子結點設為黑色
- 對兄弟結點進行左旋，得到場景 2.2.2.1
- 進行場景 2.2.2.1 的處理
場景 2.2.2.3：替換結點的兄弟結點的子結點都為黑色