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

自上而下

2-3-4樹(shù)和紅黑樹(shù)的等價(jià)關(guān)系

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

4-結(jié)點(diǎn)分解圖

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

2-3-4樹(shù)和紅黑樹(shù)的等價(jià)

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

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

    //二分搜索的過(guò)程
    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)兩個(gè)連續(xù)的左紅色鏈接哥力，右旋
    if (isRed(node.left) && isRed(node.left.left)) {
        node = rotateRight(node);
    }

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

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

private Node<K, V> _add(Node<K, V> node, K key, V value) {
    //向葉子結(jié)點(diǎn)插入新結(jié)點(diǎn)
    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);
    }

    //二分搜索的過(guò)程
    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ù)插入數(shù)據(jù) [E,C,G,B,D,F,J,A]

RB2_3_4Tree<Character, Character> 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ù)插入數(shù)據(jù) [E,C,G,B,D,F,J,A]

RBTree<Character, Character> 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樹(shù) 和 2-3樹(shù) 插入結(jié)果的對(duì)比圖：

2-3-4樹(shù)和2-3樹(shù)插入對(duì)比

所以我們一開(kāi)始用紅黑樹(shù)實(shí)現(xiàn)完美平衡的 2-3 樹(shù)墩弯，左右結(jié)點(diǎn)是不會(huì)都是紅色的
現(xiàn)在用紅黑樹(shù)實(shí)現(xiàn) 2-3-4 樹(shù)吩跋，左右結(jié)點(diǎn)的可以同時(shí)是紅色的，這樣的紅黑樹(shù)效率更高渔工。因?yàn)槿绻龅阶笥医Y(jié)點(diǎn)是紅色锌钮，就進(jìn)行顏色翻轉(zhuǎn)，還需要對(duì)紅色的父結(jié)點(diǎn)進(jìn)行向上回溯引矩，因?yàn)楦附Y(jié)點(diǎn)染成紅色了梁丘，可能父結(jié)點(diǎn)的父結(jié)點(diǎn)也是紅色，可能需要進(jìn)行結(jié)點(diǎn)旋轉(zhuǎn)或者顏色翻轉(zhuǎn)操作旺韭，所以說(shuō) 2-3-4 樹(shù)式的紅黑樹(shù)效率更高氛谜。

所以回到上面我們提到《算法4》和《算法導(dǎo)論》在實(shí)現(xiàn)上的差異的問(wèn)題，就很好回答了区端，因?yàn)椤端惴?》是用紅黑樹(shù)實(shí)現(xiàn)2-3樹(shù)的值漫，并不是 2-3-4 樹(shù)。但是如果是用紅黑樹(shù)實(shí)現(xiàn) 2-3-4 樹(shù)就和《算法導(dǎo)論》上介紹的紅黑樹(shù)一樣嗎织盼？不一樣杨何。

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

2-3-4樹(shù)和TreeMap插入對(duì)比

雖然兩棵樹(shù)都是紅黑樹(shù)沥邻，但是卻不一樣危虱。并且TreeMap允許右節(jié)點(diǎn)是紅色，在2-3-4樹(shù)中最多是左右子結(jié)點(diǎn)同時(shí)是紅色的情況唐全，不會(huì)出現(xiàn)左結(jié)點(diǎn)是黑色埃跷，右邊的兄弟結(jié)點(diǎn)是紅色的情況，為什么會(huì)有這樣的差異呢邮利？

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

為什么在《算法4》中，作者規(guī)定所有的紅色鏈接都是左鏈接祷愉，這只是人為的規(guī)定窗宦，當(dāng)然也可以是右鏈接，規(guī)定紅鏈接都是左鏈二鳄，可以使用更少的代碼來(lái)實(shí)現(xiàn)黑色平衡赴涵，需要考慮的情況會(huì)更少，就如上面我們介紹的插入操作订讼，我們只需要考慮3中情況即可髓窜。

但是一般意義上的紅黑樹(shù)是不需要維持紅色左傾的這個(gè)性質(zhì)的，所以為什么TreeMap是允許單獨(dú)右紅結(jié)點(diǎn)的

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

介紹完了《算法4》上的紅黑樹(shù)程拭，下面就來(lái)分析下一般意義上的紅黑樹(shù)的 插入 和 刪除 操作定踱，也就是《算法導(dǎo)論》上介紹的紅黑樹(shù)。

紅黑樹(shù)插入操作

插入操作有兩種情況是非常簡(jiǎn)單的恃鞋，所以在這里單獨(dú)說(shuō)一下：

case 1. 如果插入的結(jié)點(diǎn)是根結(jié)點(diǎn)崖媚，直接把該結(jié)點(diǎn)設(shè)置為黑色，整個(gè)插入操作結(jié)束

如下圖所示：

case 1

case 2. 如果插入的結(jié)點(diǎn)的父結(jié)點(diǎn)是黑色恤浪，也無(wú)需調(diào)整畅哑，整個(gè)插入操作結(jié)束

如下圖所示：

父節(jié)點(diǎn)是黑色

下面開(kāi)始介紹比較復(fù)雜的情況

紅黑樹(shù)插入操作，我們只需要處理父結(jié)點(diǎn)是紅色的情況水由，因?yàn)橐婚_(kāi)始紅黑樹(shù)肯定是黑色平衡的荠呐，就是因?yàn)橥~子節(jié)點(diǎn)插入元素后可能出現(xiàn)兩個(gè)連續(xù)的紅色的結(jié)點(diǎn)

需要注意的是，我們把新插入的結(jié)點(diǎn)默認(rèn)設(shè)置為紅色绷杜，初始的時(shí)候直秆，正在處理的節(jié)點(diǎn)就是插入的結(jié)點(diǎn)，在不斷調(diào)整的過(guò)程中鞭盟，正在處理的節(jié)點(diǎn)會(huì)不斷的變化圾结，且叔叔、爺爺齿诉、父結(jié)點(diǎn)都是相對(duì)于當(dāng)前正在處理的結(jié)點(diǎn)來(lái)說(shuō)的

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

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

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

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

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

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

Case3晒衩、Case4、Case5如果單獨(dú)來(lái)理解的話比較困難墙歪，就算單獨(dú)為每一個(gè)Case畫(huà)圖听系，我覺(jué)得也很難完整的理解，很多博客上都是這種方式箱亿，感覺(jué)不太好理解跛锌。我將這三種情況通過(guò)一張流程圖串聯(lián)起來(lái)弃秆，將這三個(gè)Case形成一個(gè)整體届惋，藍(lán)色箭頭表示正在處理的結(jié)點(diǎn)，如下所示：

紅黑樹(shù)的插入操作流程圖

紅黑樹(shù)刪除操作

上面介紹完了紅黑樹(shù)的插入操作菠赚，接下來(lái)看下紅黑樹(shù)的刪除操作

紅黑樹(shù)的刪除操作比插入操作更加復(fù)雜一些

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

如果刪除的結(jié)點(diǎn)是黑色拌牲，那么就導(dǎo)致本來(lái)保持黑平衡的紅黑樹(shù)失衡了俱饿，從下圖可以看出結(jié)點(diǎn)P到左子樹(shù)的葉子結(jié)點(diǎn)經(jīng)過(guò)的黑節(jié)點(diǎn)數(shù)量為 4(2+2)，到右子樹(shù)的葉子節(jié)點(diǎn)經(jīng)過(guò)的黑色節(jié)點(diǎn)數(shù)量是 5(2+3)塌忽，如下圖所示：

在這里插入圖片描述

紅黑樹(shù)的刪除操作拍埠，如果刪除的是黑色會(huì)導(dǎo)致紅黑樹(shù)就不能保持黑色平衡了，需要進(jìn)行調(diào)整了土居；
如果刪除的是紅色枣购，那么就無(wú)需調(diào)整，直接刪除即可擦耀，因?yàn)闆](méi)有沒(méi)有破壞黑色平衡

刪除結(jié)點(diǎn)后棉圈，無(wú)需調(diào)整的情況

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

case 2 刪除的節(jié)點(diǎn)是黑色眷蜓，如果當(dāng)前處理的節(jié)點(diǎn)X是根結(jié)點(diǎn)

無(wú)論根結(jié)點(diǎn)是什么顏色分瘾，都將根結(jié)點(diǎn)設(shè)置為黑色

case 3 刪除的結(jié)點(diǎn)是黑色，如果當(dāng)前處理的結(jié)點(diǎn)是紅色結(jié)點(diǎn)吁系，將該結(jié)點(diǎn)設(shè)置為黑色

因?yàn)閯h除黑色結(jié)點(diǎn)后德召，就打破了黑色平衡，黑高少了1
所以把一個(gè)紅色節(jié)點(diǎn)設(shè)置為黑色垮抗，這樣黑高又平衡了

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

正在處理的結(jié)點(diǎn)為X，要?jiǎng)h除的結(jié)點(diǎn)是左結(jié)點(diǎn)冒版，分為4中情況：

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

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

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

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

調(diào)整方案：將兄弟結(jié)點(diǎn)設(shè)置為紅色明郭，把當(dāng)前處理的結(jié)點(diǎn)設(shè)置為父結(jié)P

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

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

case 7 兄弟結(jié)點(diǎn)為黑色话侄，左侄子不管紅黑亏推，右侄子為紅色

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

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

紅黑樹(shù)刪除操作流程圖

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

Java TreeMap锄贷、TreeSet源碼分析

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

/** From CLR */
private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;

    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> 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<K,V> x) {
    while (x != root && colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            Entry<K,V> 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 來(lái)實(shí)現(xiàn)的柔昼，往TreeSet添加進(jìn)的元素當(dāng)作TreeMap的key，TreeMap的value是一個(gè)常量Object炎辨。掌握了紅黑樹(shù)捕透，對(duì)于這兩個(gè)集合的原理就不難理解了。

最后

本文從一開(kāi)始講的2-3樹(shù)和紅黑樹(shù)的對(duì)應(yīng)關(guān)系碴萧，再到2-3-4樹(shù)和紅黑樹(shù)的對(duì)應(yīng)關(guān)系乙嘀，再到《算法4》和《算法導(dǎo)論》JDK TreeMap在紅黑樹(shù)上的差異
然后詳細(xì)介紹了紅黑樹(shù)的插入、刪除操作破喻，最后分析了下Java中的TreeMap和TreeSet集合類虎谢。

人生當(dāng)如紅黑樹(shù)，當(dāng)過(guò)于自喜或過(guò)于自卑的時(shí)候曹质，應(yīng)當(dāng)自我調(diào)整婴噩，尋求平衡擎场。

我很丑，紅黑樹(shù)卻很美几莽。 希望本文對(duì)你有 些許幫助迅办。

參考資料：

1. https://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf
2. http://professor.ufabc.edu.br/~jesus.mena/courses/mc3305-2q-2015/AED2-13-redblack-paper.pdf
3. 《算法4》、《算法導(dǎo)論》

原文鏈接

https://blog.csdn.net/johnny901114/article/details/81046088