紅黑樹介紹

紅黑樹也是一種自平衡的二叉搜索樹

• 以前也叫做平衡二叉B樹（Symmetric Binary B-tree）
  

紅黑樹必須滿足以下5 條性質

1. 節點是RED 或者BLACK
2. 根節點是BLACK
3. 葉子節點（外部節點，空節點）都是BLACK
4. RED節點的子節點都是BLACK
   ① RED節點的parent 都是BLACK
   ② 從根節點到葉子節點的所有路徑上不能有 2 個連續的RED節點
5. 從任意節點到葉子節點的所有路徑都包含相同數目的BLACK節點

下面的這棵是紅黑樹嗎？

不是

紅黑樹 與 4階B樹（等價性）

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

• BLACK節點與它的RED子節點融合在一起，形成1個B樹節點（在B樹節點中，黑色節點永遠是父節點）

上面那張紅黑樹變成了下面這個樣子：

• 紅黑樹的 BLACK節點個數 與 4階B樹的節點總個數 相等；

下面是一個與上面的紅黑樹等價的 4階B樹；

網上有些教程用 2-3樹 與 紅黑樹 進行類比，這是極其不嚴謹的，2-3樹 并不能完美匹配 紅黑樹 的所有情況，
由于界面有限，后面展示的紅黑樹都會省略 黑色NULL節點，

紅黑樹 與 2-3-4樹 等價轉換

思考：如果上圖最底層的 BLACK 節點是不存在的，在 B樹 中是什么樣的情形？

• 整棵 B樹 只有1個節點，而且是超級節點

紅黑樹基礎代碼

一些輔助函式

/**
 * 對傳入的節點染色，并回傳染色后的該節點
 */
private Node<E> color(Node<E> node, boolean color) {
    if (node == null) return node;
    ((RBTNode<E>) node).color = color;
    return node;
}

/**
 * 染成紅色
 */
private Node<E> red(Node<E> node) {
    return color(node, RED);
}

/**
 * 染成黑色
 */
private Node<E> black(Node<E> node) {
    return color(node, BLACK);
}

/**
 * 判斷當前節點是什么顏色
 * @return 回傳 BLACK 或 RED
 */
private boolean colorOf(Node<E> node) {
    // 如果節點是null，說明是空節點，回傳black，否則回傳節點本身的顏色
    return node == null ? BLACK : ((RBTNode<E>) node).color;
}

/**
 * 判斷當前節點是否是黑顏色
 * @return true 或 false
 */
private boolean isBlack(Node<E> node) {
    return colorOf(node) == BLACK;
}

/**
 * 判斷當前節點是否是紅顏色
 * @return true 或 false
 */
private boolean isRed(Node<E> node) {
    return colorOf(node) == RED;
}

添加（12種情況）

已知

• B樹中，新元素必定是添加到葉子節點中
• 4階B樹所有節點的元素個數 x 都符合 1 ≤ x ≤ 3
• 建議新添加的節點默認為 RED，這樣能夠讓紅黑樹的性質盡快滿足（性質 1、2、3、5 都滿足，性質 4 不一定）
  

添加有12種情況：
新添加的節點（默認紅色）

1、當 parent 是黑色，不做任何處理，添加完成后任是一棵紅黑樹，

2、當 parent 不是黑色（為紅色）：即當前節點和父節點都是紅色的情況（double red）

?Ⅰ：其中4種為上溢的情況：【判定條件：uncle 節點是紅色】
??①：上溢【LL】【RR】【LR】【RL】：
???將 parent、uncle 染成黑色，然后 grand 向上合并，并且將 grand 染成紅色當作新節點處理【遞回】；
???grand 向上合并時，可能會繼續發生上溢，若上溢到根節點，只需將根節點染成黑色，

?Ⅱ：其中4種為旋轉的情況：【判定條件：uncle 節點不是紅色（是黑色）】
??①：旋轉【LL】【RR】
???將 parent 染成黑色，grand 染成紅色，
???然后對 grand 進行旋轉，
????若 grand 是 LL 的情況：右旋轉，
????若 grand 是 RR 的情況：左旋轉，
??②：旋轉【LR】【RL】
???將自己染成黑色，grand 染成紅色，
???然后對 grand 進行旋轉，
????若 grand 是 LR 的情況：parent 左旋轉、grand 右旋轉，
????若 grand 是 RL 的情況：parent 右旋轉、grand 左旋轉，

1、parent 為 BLACK【 4 種】

有 4 種情況滿足紅黑樹的性質 4 ：parent 為 BLACK

• 同樣也滿足 4階B樹 的性質
• 因此不用做任何額外處理
  

2、parent 為 RED

有 8 種情況不滿足紅黑樹的性質 4 ：parent 為 RED（ Double Red ）

Ⅰ、uncle 節點是紅色【上溢的情況 4 種】

其中這 4 種屬于B樹節點上溢的情況【LL】【RR】【LR】【RL】

Ⅱ、uncle 節點不是紅色【旋轉的情況 4 種】

其中這 4 種為旋轉的情況

添加代碼

@Override
protected void afterAdd(Node<E> node) {

    Node<E> parent = node.parent;

    // 添加的是根節點 或者 上溢到達了根節點
    if (parent == null) {
        black(node);
        return;
    }
    // 如果父節點是黑色，直接回傳
    if (isBlack(parent)) return;

    // 叔父節點
    Node<E> uncle = parent.sibling();
    // 祖父節點
    Node<E> grand = parent.parent;
    if (isRed(uncle)) { // 叔父節點是紅色【B樹節點上溢】
        black(parent);
        black(uncle);
        // 把祖父節點當做是新添加的節點
        afterAdd(red(grand));
    } else { // 叔父節點不是紅色【旋轉】
        if (parent.isLeftChild()) { // L
            if (node.isLeftChild()) { // LL
                red(grand);
                black(parent);
                rotateRight(grand);
            } else { // LR
                red(grand);
                black(node);
                rotateLeft(parent);
                rotateRight(grand);
            }
        } else { // R
            if (node.isLeftChild()) { // RL
                red(grand);
                black(node);
                rotateRight(parent);
                rotateLeft(grand);
            } else { // RR
                red(grand);
                black(parent);
                rotateLeft(grand);
            }
        }
    }

}

洗掉（12種情況）

? B樹中，最后真正被洗掉的元素都在葉子節點中

1、洗掉 RED 節點【 3 種】

? 直接洗掉，不用作任何調整

2、洗掉 BLACK 節點

? BLACK 節點，有 2 個 RED 子節點（擁有 2 個 RED 子節點的 BLACK 節點）
? 不可能被直接洗掉，因為會找它的子節點替代洗掉
? 因此不用考慮這種情況

? BLACK 節點，有 1 個 RED 子節點（擁有 1 個 RED 子節點的 BLACK 節點）

? BLACK 葉子節點

Ⅰ、擁有 2 個 RED 子節點的 BLACK 節點

Ⅱ、擁有 1 個 RED 子節點的 BLACK 節點【 2 種 】

? 判定條件：用以替代該節點的子節點是 RED

? 將替代的子節點染成 BLACK 即可保持紅黑樹性質

Ⅲ、BLACK 葉子節點

兄弟節點 sibling 為 BLACK【 4 種 】

BLACK 葉子節點被洗掉后，會導致B樹節點下溢（比如洗掉88）

? 判斷條件： sibling 至少有 1 個 RED 子節點【3種，左、右、左右節點】（可以找兄弟節點借）

? 步驟：
??? 進行旋轉操作

??? 旋轉之后的中心節點繼承 parent 的顏色（parent可能為黑色 或 紅色）

??? 旋轉之后的左右節點染為 BLACK

? 判定條件：sibling 沒有 RED 子節點【1種】（無法找兄弟節點借）需要看父節點的顏色

• 若是紅色（說明肯定有個黑色節點和它在同一高度），直接將紅色父節點下來合并，原來的位置不會產生下溢
• 若是黑色（說明和它在同一高度，只有它一個節點），那么黑色父節點下來合并后，父節點的位置會產生下溢，此時將父節點當成要洗掉的節點處理即可（遞回）

步驟：
??? 將 sibling 染成 RED、parent 染成 BLACK 即可修復紅黑樹性質


? 如果 parent 是 BLACK

??? 會導致 parent 也下溢

??? 這時只需要把 parent 當做被洗掉的節點處理即可

兄弟節點 sibling 為 RED

? 如果 sibling 是 RED【站在B樹的角度，要處在同一層的兄弟節點才可以借，sibling（55）是在該節點（88）的父節點（80）里，需要將sibing節點的子節點（76）變成該節點的sibing，即要將 76 變成 80 的子節點，對80進行右旋轉】

步驟：
??? sibling 染成 BLACK，parent 染成 RED，進行旋轉

??? 于是又回到 sibling 是 BLACK 的情況

洗掉代碼

@Override
protected void afterRemove(Node<E> node) {
    // 如果洗掉的節點是紅色
    // 或者 用以取代洗掉節點的子節點是紅色
    if (isRed(node)) {
        black(node);
        return;
    }

    Node<E> parent = node.parent;
    // 洗掉的是根節點
    if (parent == null) return;

    // 洗掉的是黑色葉子節點【下溢】
    // 判斷被洗掉的node是左還是右
    boolean left = (parent.left == null || node.isLeftChild());
    // 如果left為true，兄弟節點就是right，否則就是left
    Node<E> sibling = left ? parent.right : parent.left;

    if (left) { // 被洗掉的節點在左邊，兄弟節點在右邊
        if (isRed(sibling)) { // 兄弟節點是紅色
            black(sibling);
            red(parent);
            rotateLeft(parent);
            // 更換兄弟
            sibling = parent.right;
        }

        // 兄弟節點必然是黑色
        if (isBlack(sibling.left) && isBlack(sibling.right)) {
            // 兄弟節點沒有1個紅色子節點，父節點要向下跟兄弟節點合并
            boolean parentBlack = isBlack(parent);
            black(parent);
            red(sibling);
            if (parentBlack) {
                afterRemove(parent);
            }
        } else { // 兄弟節點至少有1個紅色子節點，向兄弟節點借元素
            // 兄弟節點的左邊是黑色，兄弟要先旋轉
            if (isBlack(sibling.right)) {
                rotateRight(sibling);
                sibling = parent.right;
            }

            color(sibling, colorOf(parent));
            black(sibling.right);
            black(parent);
            rotateLeft(parent);
        }
    } else { // 被洗掉的節點在右邊，兄弟節點在左邊
        if (isRed(sibling)) { // 兄弟節點是紅色
            black(sibling);
            red(parent);
            rotateRight(parent);
            // 更換兄弟
            sibling = parent.left;
        }

        // 兄弟節點必然是黑色
        if (isBlack(sibling.left) && isBlack(sibling.right)) {
            // 兄弟節點沒有1個紅色子節點，父節點要向下跟兄弟節點合并
            boolean parentBlack = isBlack(parent);
            black(parent);
            red(sibling);
            if (parentBlack) {
                afterRemove(parent);
            }
        } else { // 兄弟節點至少有1個紅色子節點，向兄弟節點借元素
            // 兄弟節點的左邊是黑色，兄弟要先旋轉
            if (isBlack(sibling.left)) {
                rotateLeft(sibling);
                sibling = parent.left;
            }

            color(sibling, colorOf(parent));
            black(sibling.left);
            black(parent);
            rotateRight(parent);
        }
    }

}

紅黑樹的完整代碼

由于紅黑樹完整代碼太多，單獨寫了一篇文章 紅黑樹的完整代碼

紅黑樹的平衡

? 最初遺留的困惑：為何那 5 條性質，就能保證紅黑樹是平衡的？

? 那 5 條性質，可以保證 紅黑樹 等價于 4階B樹

? 相比 AVL 樹，紅黑樹的平衡標準比較寬松：沒有一條路徑會 大于 其他路徑的2倍

? 是一種弱平衡、黑高度平衡

? 紅黑樹的最大高度是 2 ? l o g 2 ( n + 1 ) 2 ? log2(n + 1) 2?log2(n+1) ，依然是 O ( l o g n ) O(logn) O(logn) 級別

平均時間復雜度

? 搜索：O(logn)

? 添加：O(logn)，O(1) 次的旋轉操作

? 洗掉：O(logn)，O(1) 次的旋轉操作

AVL樹 vs 紅黑樹

? AVL樹

• 平衡標準比較嚴格：每個左右子樹的高度差不超過 1
• 最大高度是 1.44 ? l o g 2 n + 2 ? 1.328 1.44 ? log2 n + 2 ? 1.328 1.44?log2n+2?1.328 （100W 個節點，AVL樹最大樹 高28）
• 搜索、添加、洗掉都是 O ( l o g n ) O(logn) O(logn) 復雜度，其中添加僅需 O ( 1 ) O(1) O(1) 次旋轉調整、洗掉最多需要 O ( l o g n ) O(logn) O(logn) 次旋轉調整

? 紅黑樹

• 平衡標準比較寬松：沒有一條路徑會大于其他路徑的 2倍
• 最大高度是 2 ? l o g 2 ( n + 1 ) 2 ? log2(n + 1) 2?log2(n+1) （ 100W 個節點，紅黑樹最大樹 高40）
• 搜索、添加、洗掉都是 O ( l o g n ) O(logn) O(logn) 復雜度，其中添加、洗掉都僅需 O(1) 次旋轉調整

? 搜索的次數遠遠大于插入和洗掉，選擇AVL樹；
?搜索、插入、洗掉次數幾乎差不多，選擇紅黑樹

? 相對于AVL樹來說，紅黑樹犧牲了部分平衡性以換取插入/洗掉操作時少量的旋轉操作，整體來說性能要優于AVL樹

? 紅黑樹的平均統計性能優于AVL樹，實際應用中更多選擇使用紅黑樹

BST vs AVL Tree vs Red Black Tree

插入數值：10, 35, 47, 11, 5, 57, 39, 14, 27, 26, 84, 75, 63, 41, 37, 24, 96