引言：

上次我們學習了比二叉搜索樹更高效的平衡二叉搜索樹（AVL樹），這次我們要學習的是另外一種對二叉搜索樹的優化后的紅黑樹。

一：紅黑樹概念：

紅黑樹是一棵二叉搜索樹，他的每個結點增加一個存儲位來表示結點的顏色，可以是紅色或者黑色。通過對任何一條從根到葉子的路徑上各個結點的顏色進行約束，紅黑樹確保沒有一條路徑會比其他路徑長出2倍，因而是接近平衡的。

（1）紅黑樹規則：

1. 每個結點不是紅色就是黑色。
2. 根結點是黑色的。
3. 如果一個結點是紅色的，則它的兩個孩子結點必須是黑色的，也就是說任意一條路徑不會有連續的紅色結點。
4. 對于任意一個結點，從該結點到其所有NULL結點的簡單路徑上，均包含相同數量的黑色結點。

（2）思考：紅黑樹是如何確保最長路徑不超過最短路徑的2倍的？

1. 由規則4可知，從根到NULL結點的每條路徑都有相同數量的黑色結點，所以極端場景下，最短路徑就就是全是黑色結點的路徑，假設最短路徑長度為bh(black height)。
2. 由規則2和規則3可知，任意一條路徑不會有連續的紅色結點，所以極端場景下，最長的路徑就是一黑一紅間隔組成，那么最長路徑的長度為2*bh。
3. 綜合紅黑樹的4點規則而言，理論上的全黑最短路徑和一黑一紅的最長路徑并不是在每棵紅黑樹都存在的。假設任意?條從根到NULL結點路徑的長度為x，那么bh <= h <= 2*bh。

（3）紅黑樹效率：

假設N是紅黑樹中節點的數量，h為最短路徑的長度，那么2^h - 1 <= N < 2 ^ (2 * h) - 1 ，由此推出h ≈ logN ，也就是意味著紅黑樹的增刪查改最壞情況下也就是走最長路徑時的效率也是logN 。
但紅黑樹的表達相對于AVL樹要抽象一些，AVL樹是通過高度差來直觀地控制，紅黑樹通過4條規則的顏色約束，間接實現了近似平衡，他們效率都是同一檔次，但是相對而言，插入相同數量的結點，紅黑樹的旋轉次數是更少的，因為他對平衡的控制沒那么嚴格。

二：紅黑樹的實現

1. 紅黑樹的結構：

跟前面實現的AVL樹相比，紅黑樹的結構只是將平衡因子變為了顏色記錄。

2. 紅黑樹的插入：

（1）約定：

下面我們分析時的各節點命名：
下圖中假設我們把新增結點標識為c(cur)，c的父親標識為p(parent)，p的父親標識為g(grandfather)，p的兄弟標識為u（uncle）。

（2）紅黑樹插入的大致流程：

1. 插入一個值按二叉搜索樹規則進行插入，插入后我們只需要觀察是否符合紅黑樹的4條規則。
2. 如果是空樹插入，新增結點是黑色結點。如果是非空樹插入，新增結點必須為紅色結點，因為非空樹插入，新增黑色結點就破壞了規則4，規則4是很難維護的。
3. 非空樹插入后，新增結點必須紅色結點，如果父親結點是黑色的，則沒有違反任何規則，插入結束。
4. 非空樹插入后，新增結點必須紅色結點，如果父親結點是紅色的，則違反規則3。進一步分析，c是紅色，p為紅，g必為黑，這三個顏色都固定了，關鍵的變化看u的情況，需要根據u分為以下幾種情況分別處理。

（3）情況1：u存在且為紅（只變色）

c為紅，p為紅，g為黑，u存在且為紅，則將p和u變黑，g變紅。在把g當做新的c，繼續往上更新。
分析：因為p和u都是紅色，g是黑色，把p和u變黑，左邊子樹路徑各增加一個黑色結點，g再變紅，相當于保持g所在子樹的黑色結點的數量不變，同時解決了c和p連續紅色結點的問題，需要繼續往上更新是因為，g是紅色，如果g的父親還是紅色，那么就還需要繼續處理；如果g的父親是黑色，則處理結束了；如果g就是整棵樹的根，再把g變回黑色。（因為根節點應該為黑色）
情況1只變色，不旋轉。所以無論c是p的左還是右，p是g的左還是右，都是上面的變色處理方式。

a. 具體示例：

b. 抽象示例：

情況1代碼實現：

（4）情況2：u 不存在或者存在且為黑（單旋＋變色）

1. c為紅，p為紅，g為黑，u不存在或者u存在且為黑
2. 若u不存在，則c?定是新增結點，
3. u存在且為黑，則c一定不是新增，c之前是黑色的，是在c的子樹中插入，符合情況1，變色將c從黑色變成紅色，更新上來的。
   分析：p必須變黑，才能解決連續紅黑結點的問題，u不存在或者是黑色的，這里單純的變色無法解決問題，需要旋轉+變色。

單旋＋變色代碼實現：

情況2：u 不存在或者 u 存在且為黑（雙旋＋變色）

1. c為紅，p為紅，g為黑，u不存在或者u存在且為黑。
2. u不存在，則c一定是新增結點，
3. u存在且為黑，則c一定不是新增，c之前是黑色的，是在c的子樹中插入，符合情況1，變色將c從黑色變成紅色，更新上來的。
   分析：p必須變黑，才能解決，連續紅色結點的問題，u不存在或者是黑色的，這里單純的變色無法解決問題，需要旋轉+變色。

雙旋＋變色 代碼實現：

當 p u 位置反過來時的代碼：

3. 紅黑樹的查找：

按二叉搜索樹的邏輯實現即可，搜索效率為O(logN)。

4. 紅黑樹的驗證

這里獲取最長路徑和最短路徑，檢查最長路徑不超過最短路徑的2倍是不可行的，因為就算滿足這個條件，紅黑樹也可能顏色不滿足規則，當前暫時沒出問題，后續繼續插入還是會出問題的。所以我們還是去檢查4點規則，滿足這4點規則，一定能保證最長路徑不超過最短路徑的2倍。

1. 規則1枚舉顏色類型，天然實現保證了顏色不是黑色就是紅色。
2. 規則2直接檢查根即可。
3. 規則3前序遍歷檢查，遇到紅色結點查孩子不太方便，因為孩子有兩個，且不一定存在，反過來檢查父親的顏色就方便多了。
4. 規則4前序遍歷，遍歷過程中用形參記錄跟到當前結點的blackNum(黑色結點數量)，前序遍歷遇到黑色結點就++blackNum，走到空就計算出了一條路徑的黑色結點數量。再任意一條路徑黑色結點數量作為參考值，依次比較即可。

5. 測試：

（1）插入及其合法性驗證：

（2）性能測試：

完結！！！