下面的圖就是 自上而下 方案的流程圖

在介紹2-3樹的時候我們也講解了2-3樹和紅黑樹的等價關(guān)系，由于2-3樹和2-3-4樹非常類似，所以2-3-4樹和紅黑樹的等價關(guān)系也是類似的。不同的是2-3-4的 4-結(jié)點 分解后的結(jié)點顏色變成如下形式：

所以可以得出下面一棵2-3-4樹和紅黑樹的等價關(guān)系圖：

上面在介紹紅黑樹實現(xiàn)2-3樹的時候講解了它的插入操作：

private Node _add(Node node, K key, V value) {
    //向葉子結(jié)點插入新結(jié)點
    if (node == null) {
        size++;
        return new Node<>(key, value);
    }

    //二分搜索的過程
    if (key.compareTo(node.key) < 0)
        node.left = _add(node.left, key, value);
    else if (key.compareTo(node.key) > 0)
        node.right = _add(node.right, key, value);
    else
        node.value = value;

    //1,如果出現(xiàn)右側(cè)紅色鏈接，左旋
    if (isRed(node.right) && !isRed(node.left)) {
        node = rotateLeft(node);
    }

    //2,如果出現(xiàn)兩個連續(xù)的左紅色鏈接，右旋
    if (isRed(node.left) && isRed(node.left.left)) {
        node = rotateRight(node);
    }

    //3,如果結(jié)點的左右子鏈接都是紅色，顏色翻轉(zhuǎn)
    if (isRed(node.left) && isRed(node.right)) {
        flipColor(node);
    }
}

我們可以很輕松的把它改成2-3-4的插入邏輯（只需要把顏色翻轉(zhuǎn)的邏輯提到二分搜索的前面即可）：

private Node _add(Node node, K key, V value) {
    //向葉子結(jié)點插入新結(jié)點
    if (node == null) {
        size++;
        return new Node<>(key, value);
    }
    
    //split 4-nodes on the way down
    if (isRed(node.left) && isRed(node.right)) {
        flipColor(node);
    }

    //二分搜索的過程
    if (key.compareTo(node.key) < 0)
        node.left = _add(node.left, key, value);
    else if (key.compareTo(node.key) > 0)
        node.right = _add(node.right, key, value);
    else
        node.value = value;

    //fix right-leaning reds on the way up
    if (isRed(node.right) && !isRed(node.left)) {
        node = rotateLeft(node);
    }

    //fix two reds in a row on the way up
    if (isRed(node.left) && isRed(node.left.left)) {
        node = rotateRight(node);
    }

}

//使用2-3-4樹插入數(shù)據(jù) [E,C,G,B,D,F,J,A]

RB2_3_4Tree rbTree = new RB2_3_4Tree<>();
rbTree.add("E", "E");
rbTree.add("C", "C");
rbTree.add("G", "G");
rbTree.add("B", "B");
rbTree.add("D", "D");
rbTree.add("F", "F");
rbTree.add("J", "J");
rbTree.add("A", "A");
rbTree.levelorder(rbTree.root);


//使用2-3樹插入數(shù)據(jù) [E,C,G,B,D,F,J,A]

RBTree rbTree = new RBTree<>();
rbTree.add("E", "E");
rbTree.add("C", "C");
rbTree.add("G", "G");
rbTree.add("B", "B");
rbTree.add("D", "D");
rbTree.add("F", "F");
rbTree.add("J", "J");
rbTree.add("A", "A");
rbTree.levelorder(rbTree.root);

下面是 2-3-4樹 和 2-3樹 插入結(jié)果的對比圖：

所以我們一開始用紅黑樹實現(xiàn)完美平衡的2-3樹，左右結(jié)點是不會都是紅色的
現(xiàn)在用紅黑樹實現(xiàn)2-3-4樹，左右結(jié)點的可以同時是紅色的，這樣的紅黑樹效率更高。因為如果遇到左右結(jié)點是紅色，就進行顏色翻轉(zhuǎn)，還需要對紅色的父結(jié)點進行向上回溯，因為父結(jié)點染成紅色了，可能父結(jié)點的父結(jié)點也是紅色，可能需要進行結(jié)點旋轉(zhuǎn)或者顏色翻轉(zhuǎn)操作，所以說2-3-4樹式的紅黑樹效率更高。

所以回到上面我們提到《算法4》和《算法導論》在實現(xiàn)上的差異的問題，就很好回答了，因為《算法4》是用紅黑樹實現(xiàn)2-3樹的，并不是2-3-4樹。但是如果是用紅黑樹實現(xiàn)2-3-4樹就和《算法導論》上介紹的紅黑樹一樣嗎？不一樣。

下面繼續(xù)做一個測試，分別往上面紅黑樹實現(xiàn)的 2-3-4樹 和 JDK TreeMap 中插入[E, D, R, O, S, X]

雖然兩棵樹都是紅黑樹，但是卻不一樣。并且TreeMap允許右節(jié)點是紅色，在2-3-4樹中最多是左右子結(jié)點同時是紅色的情況，不會出現(xiàn)左結(jié)點是黑色，右邊的兄弟結(jié)點是紅色的情況，為什么會有這樣的差異呢？

從上面的2-3-4樹的插入邏輯可以看出，如果右節(jié)點是紅色會執(zhí)行左旋轉(zhuǎn)操作，所以不會出現(xiàn)多帶帶紅右結(jié)點的情況
也就是說只會出現(xiàn)多帶帶的左結(jié)點是紅色的情況，我們把這種形式的紅黑樹稱之為左傾紅黑樹（Left Leaning Red Black Tree），包括上面的紅黑樹實現(xiàn)的完美平衡的2-3樹也是左傾紅黑樹

為什么在《算法4》中，作者規(guī)定所有的紅色鏈接都是左鏈接，這只是人為的規(guī)定，當然也可以是右鏈接，規(guī)定紅鏈接都是左鏈，可以使用更少的代碼來實現(xiàn)黑色平衡，需要考慮的情況會更少，就如上面我們介紹的插入操作，我們只需要考慮3中情況即可。

但是一般意義上的紅黑樹是不需要維持紅色左傾的這個性質(zhì)的，所以為什么TreeMap是允許多帶帶右紅結(jié)點的

如果還需要維護左傾情況，這樣的話就更多的操作，可能還需要結(jié)點旋轉(zhuǎn)和顏色的翻轉(zhuǎn)，性能更差一些，雖然也是符合紅黑樹的性質(zhì)

介紹完了《算法4》上的紅黑樹，下面就來分析下一般意義上的紅黑樹的 插入 和 刪除 操作，也就是《算法導論》上介紹的紅黑樹。

插入操作有兩種情況是非常簡單的，所以在這里多帶帶說一下：

case 1. 如果插入的結(jié)點是根結(jié)點，直接把該結(jié)點設置為黑色，整個插入操作結(jié)束

如下圖所示：

case 2. 如果插入的結(jié)點的父結(jié)點是黑色，也無需調(diào)整，整個插入操作結(jié)束

如下圖所示：

下面開始介紹比較復雜的情況

紅黑樹插入操作，我們只需要處理父結(jié)點是紅色的情況，因為一開始紅黑樹肯定是黑色平衡的，就是因為往葉子節(jié)點插入元素后可能出現(xiàn)兩個連續(xù)的紅色的結(jié)點

需要注意的是，我們把新插入的結(jié)點默認設置為紅色，初始的時候，正在處理的節(jié)點就是插入的結(jié)點，在不斷調(diào)整的過程中，正在處理的節(jié)點會不斷的變化，且叔叔、爺爺、父結(jié)點都是相對于當前正在處理的結(jié)點來說的

case 3. 叔叔結(jié)點為紅色，正在處理的節(jié)點可以是左也可以是右結(jié)點

調(diào)整策略：由于父結(jié)點是紅色，叔叔結(jié)點是紅色，爺爺結(jié)點是黑色，執(zhí)行顏色翻轉(zhuǎn)操作
然后把當前正在處理的結(jié)點設置為爺爺結(jié)點，如果爺爺?shù)母附Y(jié)點是黑色插入操作結(jié)束，如果是紅色繼續(xù)處理

case 4. 叔叔結(jié)點為黑色，正在處理的結(jié)點是右結(jié)點

調(diào)整策略：由于父結(jié)點是紅色，叔叔結(jié)點為黑色，那么爺爺結(jié)點肯定是黑色
把正在處理的節(jié)點設置為父結(jié)點，然后左旋，形成Case5情況

case 5. 叔叔結(jié)點為黑色，正在處理的結(jié)點是左孩子

調(diào)整策略：由于父結(jié)點是紅色，叔叔結(jié)點為黑色，那么爺爺結(jié)點肯定是黑色
把父結(jié)點染黑，爺爺結(jié)點染紅，然后爺爺結(jié)點右旋

Case3、Case4、Case5如果多帶帶來理解的話比較困難，就算多帶帶為每一個Case畫圖，我覺得也很難完整的理解，很多博客上都是這種方式，感覺不太好理解。我將這三種情況通過一張流程圖串聯(lián)起來，將這三個Case形成一個整體，藍色箭頭表示正在處理的結(jié)點，如下所示：

上面介紹完了紅黑樹的插入操作，接下來看下紅黑樹的刪除操作

紅黑樹的刪除操作比插入操作更加復雜一些

為了描述方便，我們把正在處理的結(jié)點稱之為 X，父結(jié)點為 P(Parent)，兄弟節(jié)點稱之為 S(Sibling)，左侄子稱之為 LN(Left Nephew)，右侄子稱之為 RN(Right Nephew)

如果刪除的結(jié)點是黑色，那么就導致本來保持黑平衡的紅黑樹失衡了，從下圖可以看出結(jié)點P到左子樹的葉子結(jié)點經(jīng)過的黑節(jié)點數(shù)量為4(2+2)，到右子樹的葉子節(jié)點經(jīng)過的黑色節(jié)點數(shù)量是5(2+3)，如下圖所示：

紅黑樹的刪除操作，如果刪除的是黑色會導致紅黑樹就不能保持黑色平衡了，需要進行調(diào)整了；
如果刪除的是紅色，那么就無需調(diào)整，直接刪除即可，因為沒有沒有破壞黑色平衡

刪除結(jié)點后，無需調(diào)整的情況

case 1 刪除的結(jié)點是紅色結(jié)點，直接刪除即可

case 2 刪除的節(jié)點是黑色，如果當前處理的節(jié)點X是根結(jié)點

無論根結(jié)點是什么顏色，都將根結(jié)點設置為黑色

case 3 刪除的結(jié)點是黑色，如果當前處理的結(jié)點是紅色結(jié)點，將該結(jié)點設置為黑色

因為刪除黑色結(jié)點后，就打破了黑色平衡，黑高少了1
所以把一個紅色節(jié)點設置為黑色，這樣黑高又平衡了

刪除節(jié)點后，需要調(diào)整的情況

正在處理的結(jié)點為X，要刪除的結(jié)點是左結(jié)點，分為4中情況：

case 4 兄弟結(jié)點為紅色

調(diào)整方案：兄弟設置為黑色，父結(jié)點設置為紅色，父結(jié)點進行左旋轉(zhuǎn)
轉(zhuǎn)化為 case5、case6、case7

case 5 兄弟結(jié)點為黑色，左侄子LN為黑色，右侄子RN為黑色

在這種條件下，還有兩種情況：父結(jié)點是紅色或黑色，不管是那種情況，調(diào)整方案都是一致的

調(diào)整方案：將兄弟結(jié)點設置為紅色，把當前處理的結(jié)點設置為父結(jié)P

case 6 兄弟結(jié)點為黑色，左侄子為紅色，右侄子RN為黑色

調(diào)整方案：將左侄子結(jié)點設置為黑色，兄弟結(jié)點設置為紅色，兄弟結(jié)點右旋轉(zhuǎn)，這樣就轉(zhuǎn)化成了case7

case 7 兄弟結(jié)點為黑色，左侄子不管紅黑，右侄子為紅色

處理方式：兄弟結(jié)點變成父結(jié)點的顏色，然后父結(jié)點設置黑色，右侄子設置黑色，父結(jié)點進行左旋轉(zhuǎn)

和插入操作一樣，下面通過一張流程圖把刪除需要調(diào)整的情況串聯(lián)起來：

上面處理的所有情況都是基于正在處理的結(jié)點是左結(jié)點
如果要調(diào)整正在處理的結(jié)點是右節(jié)點的情況，就是上面的處理的鏡像。插入操作也是同理，所以就省略了

TreeMap底層就是用紅黑樹實現(xiàn)的，它在插入后調(diào)整操作主要在fixAfterInsertion方法里，我為每種情況都添加注釋，如下所示：

/** From CLR */
private void fixAfterInsertion(Entry x) {
    x.color = RED;

    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry y = rightOf(parentOf(parentOf(x)));
            //-----Case3情況-----
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                //-----Case4情況-----
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                //-----Case5情況-----
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            //省略鏡像情況
        }
    }
    root.color = BLACK;
}

它的刪除后調(diào)整操作主要在fixAfterDeletion方法：

/** From CLR */
private void fixAfterDeletion(Entry x) {
    while (x != root && colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            Entry sib = rightOf(parentOf(x));
            //-----Case4的情況-----
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }
            //-----Case5的情況-----
            if (colorOf(leftOf(sib))  == BLACK &&
                colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                //-----Case6的情況-----
                if (colorOf(rightOf(sib)) == BLACK) {
                    setColor(leftOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateRight(sib);
                    sib = rightOf(parentOf(x));
                }
                //-----Case7的情況-----
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(rightOf(sib), BLACK);
                rotateLeft(parentOf(x));
                x = root;
            }
        } else { // symmetric
            //省略鏡像的情況
        }
    }
    setColor(x, BLACK);
}

TreeSet 底層就是用 TreeMap 來實現(xiàn)的，往TreeSet添加進的元素當作TreeMap的key，TreeMap的value是一個常量Object。掌握了紅黑樹，對于這兩個集合的原理就不難理解了。

本文從一開始講的2-3樹和紅黑樹的對應關(guān)系，再到2-3-4樹和紅黑樹的對應關(guān)系，再到《算法4》和《算法導論》JDK TreeMap在紅黑樹上的差異
然后詳細介紹了紅黑樹的插入、刪除操作，最后分析了下Java中的TreeMap和TreeSet集合類。

人生當如紅黑樹，當過于自喜或過于自卑的時候，應當自我調(diào)整，尋求平衡。

我很丑，紅黑樹卻很美。希望本文對你有 些許幫助。

參考資料：

https://www.cs.princeton.edu/...

http://professor.ufabc.edu.br...

《算法4》、《算法導論》