0. 前言

我們采用nil代替null來簡(jiǎn)化操作。如果你之前學(xué)過，有一些印象，那跟隨本文從上到下畫一畫插入與刪除的全過程，也能加深你的印象與熟練程度。

插入和刪除的主邏輯，與前面的文章——紅黑樹01——前傳-二叉搜索樹中基本一致，只是特別處理了一下nil。最大的不同是，當(dāng)插入結(jié)點(diǎn)和它的父結(jié)點(diǎn)都為紅色時(shí)，違反了紅黑樹的屬性，需要重新調(diào)整，共有3種情況（應(yīng)該是6種，因?yàn)槭菍?duì)稱的，所以只討論一半）；刪除結(jié)點(diǎn)時(shí)若涉及到黑結(jié)點(diǎn)的刪除（或替換），會(huì)導(dǎo)致一側(cè)黑結(jié)點(diǎn)數(shù)目減少，違反了紅黑樹的規(guī)則，所以也需要調(diào)整，共有4種情況。

本章內(nèi)容比較長(zhǎng)，如果看得吃力了，可以暫時(shí)停下休息一會(huì)，回頭再看。但長(zhǎng)不可怕，可怕的是看不懂，所以本文中我盡可能地把各個(gè)操作的前因后果講清楚，不像很多書上直接告訴你最終怎么做，但不知道原理所以一直記不住。希望大家能耐心看下去，經(jīng)過測(cè)試，我給部分同學(xué)講過之后，能輕松記住整個(gè)過程，且能寫出來全部代碼。一定要堅(jiān)持看完弄懂，不要覺得麻煩就不看了，請(qǐng)相信我，欠下的債遲早要還的。

1. 插入后的調(diào)整

為了便于說明，設(shè)新插入結(jié)點(diǎn)為x，x的父結(jié)點(diǎn)為p，p的父結(jié)點(diǎn)為pp，p的兄弟結(jié)點(diǎn)為pb，pb的左孩子為pbl, pb的右孩子為pbr。因?yàn)閷?duì)稱性，我們這里只討論p == pp.left的情況。已經(jīng)x和p當(dāng)前均為紅色，pp肯定為黑色。這一系列的字母，直接這樣看下去肯定會(huì)暈的，所以請(qǐng)畫出來，自己邊畫邊往下讀。也可以直接根據(jù)結(jié)論看文章后面的示例，再回頭來看這里討論的原因。

回到主題：因?yàn)橛袃蓚€(gè)紅色結(jié)點(diǎn)，我們需要把其中一個(gè)變成黑色。但置黑的肯定不是x，因?yàn)樾虏迦氲慕Y(jié)點(diǎn)是紅色（為什么新插入的是紅色呢，因?yàn)槿绻徊迦爰t色的話，那就沒有紅色了。但為什么不擔(dān)心沒有黑色了呢？因?yàn)閺?qiáng)制規(guī)定——根為黑色，所以能保證一定有黑色），所以我們將p置黑。

但這樣pp的左子樹就多了一個(gè)黑色，違反規(guī)則，現(xiàn)在要想辦法減少左邊的黑色，前面已分析了，x本身不能變，故只能使pp置紅。但又導(dǎo)致右邊少一個(gè)黑色，所以需要把右邊的黑色加上來，有兩種辦法：

1. 若pb為紅色，將pb置黑即可。因?yàn)閜p置紅了，可能會(huì)違反不能連續(xù)兩個(gè)紅結(jié)點(diǎn)的規(guī)則，所以將x指向pp，進(jìn)入下一輪循環(huán)繼續(xù)；
2. 若pb為黑色，只能右旋pp（還記得我們上一篇文章中旋轉(zhuǎn)的作用嗎？）。但要想pp能夠成功右旋，x、p、pp必須在一條直線上，否則x將作為pp新的左孩子從而造成連續(xù)兩個(gè)紅色。

    private void insertFixup(Node x) {
        while (x.parent != nil && x.parent.color == RED) {
            Node p = x.parent;
            // 因?yàn)楦腹?jié)點(diǎn)為紅色，而根節(jié)點(diǎn)為黑色，所以父節(jié)點(diǎn)肯定不為根，故祖父節(jié)點(diǎn)存在，所以這里不需要判斷為nil。
            Node pp = p.parent;
            pp.color = RED;
            if (pp.left == p) {
                Node pb = pp.right;
                if (pb.color == RED) {
                    insertFixUpStats[0]++;
                    p.color = BLACK;
                    pb.color = BLACK;
                    x = pp;
                } else {
                    if (p.left != x) {
                        insertFixUpStats[1]++;
                        rotateLeft(p);
                        x = p;
                        p = x.parent;
                    }
                    insertFixUpStats[2]++;
                    p.color = BLACK;
                    rotateRight(pp);
                }
            } else {
                Node pb = pp.left;
                if (pb.color == RED) {
                    insertFixUpStats[0]++;
                    p.color = BLACK;
                    pb.color = BLACK;
                    x = pp;
                } else {
                    if (p.right != x) {
                        insertFixUpStats[1]++;
                        rotateRight(p);
                        x = p;
                        p = x.parent;
                    }
                    insertFixUpStats[2]++;
                    p.color = BLACK;
                    rotateLeft(pp);
                }
            }
        }
        root.color = BLACK;
    }

2. 刪除

當(dāng)黑色結(jié)點(diǎn)被替代者替換時(shí)，會(huì)導(dǎo)致黑色結(jié)點(diǎn)的缺失而違反性質(zhì)4，我們需要對(duì)替代者做一些處理，使樹恢復(fù)平衡。設(shè)被刪除的結(jié)點(diǎn)為x，x的左孩子為xl(left)，右孩子為xr(right)，x的后繼為s(successor)，后繼的右孩子為sr，替代者為r(replacement)，被替代的顏色為rc(replacedColor)，x的父結(jié)點(diǎn)為p，x的兄弟節(jié)點(diǎn)為b，b的左右孩子分別為bl, br。

因?yàn)閯h除調(diào)整也是對(duì)稱的，下面我們只討論x == p.left的情況。

2.1 確定替代者與被替代的顏色

1. 如果xl或xr不存在時(shí)，直接把xr或xl替換x即可，故r為xr或xl，rc為x.color；否則轉(zhuǎn)2。
2. 如果xr == s，則只發(fā)生一次替換：s -> x，故r為s，rc為x.color。
3. 如果xr != s，則發(fā)生兩次替換：sr -> s, s -> x。我們保留x位置的顏色不變，將x的顏色賦值給s，則在顏色上的替換只有一次：sr -> s，我們只需要調(diào)整一個(gè)結(jié)點(diǎn)的黑色結(jié)點(diǎn)問題，此時(shí)r為s.right，rc為s.color。

2.2 調(diào)整替代者

因?yàn)樯倭艘粋€(gè)黑色的結(jié)點(diǎn)，所以，以根到x.parent整條路徑上的任意結(jié)點(diǎn)為根的子樹，其左子樹都會(huì)少一個(gè)黑色結(jié)點(diǎn)。前人發(fā)明了一招來治標(biāo)：假設(shè)r指針附帶了一層額外的黑色（這個(gè)黑色是跟著r指針走的，與結(jié)點(diǎn)本身無關(guān)，當(dāng)r向上移動(dòng)的時(shí)候，這層黑色也會(huì)跟著指針r走），這樣少的那個(gè)黑色又加回來了。如果r節(jié)點(diǎn)為紅色，那將r置黑（即將虛擬的黑色實(shí)體化），即解決問題；否則，需要更多的調(diào)整。

先確定總的原則：1. x不能再變化，因?yàn)閤的變化會(huì)導(dǎo)致左邊黑色進(jìn)一步減少，無利于解決問題；2. 總需要做出點(diǎn)變化，不然靜止不動(dòng)，肯定無法解決問題。

首先區(qū)分出4種情況：按b的顏色可分為兩種情況，而b為黑時(shí)，又根據(jù)bl, br的顏色，可分為全黑、左紅、右紅3種情況（為什么不考慮全紅：因?yàn)閱为?dú)考慮左紅、右紅已經(jīng)包含全紅了。另外，右紅經(jīng)過左旋可轉(zhuǎn)化為左紅，是的，跟上面插入時(shí)一樣，如果不在一條直線上則旋轉(zhuǎn)到一條直線上）。然后再逐個(gè)攻破：

• 情況1：如果b為紅色，則p、bl和br都為黑色。因不能連續(xù)兩紅，故p、bl、br都不能變色，唯一能做的只能是b，故將其置為黑色，這樣右邊又多了一個(gè)黑色，現(xiàn)在多了2個(gè)黑色，如果現(xiàn)在左旋最多只能減少一個(gè)，那就先把p置紅（這里為什么敢置紅呢？先試試嘛，萬(wàn)一不行不變就是了，恰好接下來的左旋操作，使得p的父親變成黑色的b，所以不會(huì)出現(xiàn)兩個(gè)紅色），右邊黑色數(shù)目恢復(fù)，但左邊又少了一個(gè)黑色。那就p左旋（旋轉(zhuǎn)就是用來將一邊的顏色分享給另一邊而原來那一邊顏色不減少），這時(shí)b的黑色作用到兩邊使左右兩邊的黑色數(shù)目都恢復(fù)。另外p左旋導(dǎo)致原來的bl成了p.right，成為x的新兄弟，且bl是黑色的，故轉(zhuǎn)換為情況2/3/4的一種。
• 情況2：b, bl, br都為黑色，唯一可能的變化是右邊的某個(gè)結(jié)點(diǎn)由黑轉(zhuǎn)紅，如果該結(jié)點(diǎn)是bl或br的話，那會(huì)造成b子樹的不平衡，不但沒解決問題反而引入了新的問題，肯定不行，所以只能是b由黑轉(zhuǎn)紅。這時(shí)右邊就少了一個(gè)黑色。將r上移指向p，相當(dāng)于將r的虛擬黑色分享給右邊，增加了一個(gè)黑色。但此時(shí)只解決了原r子樹的黑色不平衡問題，新的r及更上層的不平衡問題還未解決，故進(jìn)入下一輪循環(huán)繼續(xù)。
• 情況3：b為黑色，bl為紅色，因p, b, bl不在一條直線上，參考插入過程，我們需要將p, b, bl調(diào)整到一條直線上來以便進(jìn)行旋轉(zhuǎn)操作。故b置紅，bl置黑，右旋b，再重置b，轉(zhuǎn)為情況4。
• 情況4：b為黑色，br為紅色，則p, b, br在一條直線上，這個(gè)時(shí)候怎么搞事情呢？因?yàn)閎r是紅色，所以b不能再置紅，而bl和p顏色不確定，所以也不能直接修改顏色。故可能的變化只能是br置黑，則右邊多了一個(gè)黑色。因?yàn)椴荒軐置紅來減少右邊的黑色，唯一能做的就是想辦法把b的黑色弄到左邊去。首先想到的就是左旋p，但如果p是黑色的，左旋p會(huì)導(dǎo)致右邊黑色減1左邊加1，最終左邊黑色數(shù)目比右邊多2（算上那個(gè)虛擬黑色），所以不能直接左旋p。我們?cè)囍粨Qp和b的顏色，再左旋p，則p原來的顏色還在原來的位置，b的黑色成功置換到了左邊。但現(xiàn)在左邊又多了一個(gè)黑色，我們把r移走，指向root，則總體平衡了（右邊黑色一加一減不變，左邊增加了一個(gè)），結(jié)束處理。

所以將來大家記不住4種情況分別是什么時(shí)，不妨自己在紙上畫畫，強(qiáng)迫自己搞點(diǎn)事情出來，再逐步恢復(fù)之前的局勢(shì)，想必能幫助你想起來。

    private void deleteFixUp(Node r) {
        while (r.color == BLACK && r != root) {
            Node p = r.parent;
            if (r == p.left) {
                Node b = p.right;
                // 情況1，處理之后轉(zhuǎn)化為情況2/3/4的一種。
                if (b.color == RED) {
                    deleteFixUpStats[0]++;
                    b.color = BLACK;
                    p.color = RED;
                    rotateLeft(p);
                    b = p.right;
                }

                // 因?yàn)橛猩诒鴑il，所以這里不需要判斷brother.left是否存在。
                if (b.left.color == BLACK && b.right.color == BLACK) {
                    deleteFixUpStats[1]++;
                    b.color = RED;
                    r = p;
                } else {
                    // 情況3轉(zhuǎn)化為情況4
                    if (b.left.color == RED) {
                        deleteFixUpStats[2]++;
                        b.left.color = BLACK;
                        b.color = RED;
                        rotateRight(b);
                        b = p.right;
                    }
                    deleteFixUpStats[3]++;
                    b.right.color = BLACK;
                    b.color = p.color;
                    p.color = BLACK;
                    rotateLeft(p);
                    r = root;
                }
            } else {
                Node b = p.left;
                if (b.color == RED) {
                    deleteFixUpStats[0]++;
                    b.color = BLACK;
                    p.color = RED;
                    rotateRight(p);
                    b = p.left;
                }

                if (b.left.color == BLACK && b.right.color == BLACK) {
                    deleteFixUpStats[1]++;
                    b.color = RED;
                    r = p;
                } else {
                    if (b.right.color == RED) {
                        deleteFixUpStats[2]++;
                        b.right.color = BLACK;
                        b.color = RED;
                        rotateLeft(b);
                        b = p.left;
                    }
                    deleteFixUpStats[3]++;
                    b.left.color = BLACK;
                    b.color = p.color;
                    p.color = BLACK;
                    rotateRight(p);
                    r = root;
                }
            }
        }
        r.color = BLACK;
    }

3. 示例

下面我將演示按{6, 3, 5, 4, 2, 1, 0}的順序逐個(gè)插入，再按{6, 4, 5, 0, 1, 3, 2}的順序逐個(gè)刪除結(jié)點(diǎn)，演示插入的3種情況和刪除的4種情況。話說你這兩串?dāng)?shù)字怎么得來了，你怎么能知道能出現(xiàn)所有的情況？嘿嘿，多運(yùn)行幾次代碼，你就能挑到一個(gè)滿足條件的。

開始插入5

前面兩個(gè)結(jié)點(diǎn)太簡(jiǎn)單，就不演示了。我們從插入5開始，現(xiàn)在3和5連續(xù)兩個(gè)紅結(jié)點(diǎn)，且6、3、5不在一條直接線，為插入情況2，我們左旋3，轉(zhuǎn)化為情況3；然后5置黑，6置紅，右旋6.

完成插入5

接下來插入4之后，3和6都為紅，為情況1，所以將3和6置黑，5置紅。然后繼續(xù)判斷的時(shí)候，x已經(jīng)指向根，所以將根置黑即結(jié)束。

插入4

接下來插入2，不需要調(diào)整，所以不演示了，繼續(xù)插入1.此時(shí)2和4均為紅，為情況1，將2和4置黑，3置紅，因?yàn)?的父結(jié)點(diǎn)5不再是紅色，所以處理結(jié)束。

插入2和1

插入0，0、1、2在一條直線上，為情況3，所以1置黑，2置紅，右旋2.

插入0

現(xiàn)在插入完畢，哈哈，看起來左邊高很多，但也只是2倍啦，還是一棵合法的紅黑樹。接下來我們開始刪除操作{6, 4, 5, 0, 1, 3, 2}。繼續(xù)使用上文中的符號(hào)來表示。

刪除6。因6的左孩子為nil，所以r為其右孩子（也是nil，但沒關(guān)系，我們把nil當(dāng)成普通結(jié)點(diǎn)看待），rc為6的顏色黑色，所以需要做調(diào)整。b為3，顏色為紅，符合情況1。所以將3置黑色，5置紅色，右旋5，再重置b。

此時(shí)b(4)為黑色，左右孩子均為nil，也為黑色，符合情況2，故4置紅，r指向5。

此時(shí)r本身為紅色了，所以結(jié)束循環(huán)，將其置黑，結(jié)束處理?？偨Y(jié)一下，刪除結(jié)點(diǎn)6，我們共進(jìn)行了2次調(diào)整，分別為情況1和情況2。

刪除6

繼續(xù)刪除結(jié)點(diǎn)4。因?yàn)?左孩子不存在，所以r為其右孩子，rc為4的顏色紅色，故不需要調(diào)整，這里不再單獨(dú)作圖。

再刪除5。因5的左孩子不存在，故r為其右孩子nil，rc為5的顏色黑色，所以需要調(diào)整。因?yàn)閎(1)為黑色，且其右孩子為紅色，符合情況3，故1置紅，2置黑，b左旋，2成為新的b，轉(zhuǎn)情況4；情況4中，將bl(1)置黑，p(3)顏色給b，p置黑，右旋3，r指向root。

總結(jié)一下，刪除結(jié)點(diǎn)5，我們共進(jìn)行了2次調(diào)整，情況3和情況4.

刪除5

接下來刪除0，因它沒有左右結(jié)點(diǎn)，且顏色為紅色，不需要調(diào)整，直接刪除即可，不再畫圖。接下來刪除1。1沒有左結(jié)點(diǎn)，故r為1，rc為1的顏色黑色，b為3，顏色為黑色，且3的左右孩子均為黑色（nil的顏色），符合情況2，故將b置紅，r指向p。因?yàn)榇藭r(shí)p已經(jīng)是根了，將其置黑結(jié)束處理。

刪除1

接下來刪除3，3為紅色，不需要調(diào)整，刪除2樹為空，也不需要調(diào)整，不再畫圖。

5. 結(jié)語(yǔ)

通過本文的練習(xí)，如果能正確得到結(jié)果，證明你已經(jīng)基本掌握了紅黑樹的插入與刪除操作。記得，插入調(diào)整的3種情況和刪除調(diào)整的4種情況，都可以通過自己演練出來，記不住了，就在紙上畫畫，試著隨便去做一些調(diào)整（如果調(diào)整造成了其他的沖突，則想辦法往回調(diào)整），最終會(huì)得到正確的解決辦法。

源碼

https://github.com/readyou/algorithm-introduction-code/blob/master/src/main/java/me/wxl/demo/data/struct/RedBlackTree.java

轉(zhuǎn)載聲明

如果您需要轉(zhuǎn)載，請(qǐng)注明轉(zhuǎn)載來源。