《Java集合詳解系列》是我在完成夯實(shí)Java基礎(chǔ)篇的系列博客后準(zhǔn)備開(kāi)始寫(xiě)的新系列。

這些文章將整理到我在GitHub上的《Java面試指南》倉(cāng)庫(kù)，更多精彩內(nèi)容請(qǐng)到我的倉(cāng)庫(kù)里查看

https://github.com/h2pl/Java-Tutorial

喜歡的話麻煩點(diǎn)下Star钧椰、fork哈

文章首發(fā)于我的個(gè)人博客：

www.how2playlife.com

什么是紅黑樹(shù)

首先，什么是紅黑樹(shù)呢符欠？ 紅黑樹(shù)是一種“平衡的”二叉查找樹(shù)嫡霞，它是一種經(jīng)典高效的算法，能夠保證在最壞的情況下動(dòng)態(tài)集合操作的時(shí)間為O（lgn）希柿。紅黑樹(shù)每個(gè)節(jié)點(diǎn)包含5個(gè)域诊沪，分別為color,key,left,right和p。 color是在每個(gè)節(jié)點(diǎn)上增加的一個(gè)存儲(chǔ)位表示節(jié)點(diǎn)的顏色曾撤，可以是RED或者BLACK端姚。key為結(jié)點(diǎn)中的value值，left,right為該結(jié)點(diǎn)的左右孩子指針挤悉，沒(méi)有的話為NIL寄锐，p是一個(gè)指針，是指向該節(jié)的父節(jié)點(diǎn)尖啡。如下圖（來(lái)自維基百科）表示就是一顆紅黑樹(shù)橄仆，NIL為指向外結(jié)點(diǎn)的指針。（外結(jié)點(diǎn)視為沒(méi)有key的結(jié)點(diǎn)）

   紅黑樹(shù)有什么性質(zhì)呢衅斩？一般稱為紅黑性質(zhì)盆顾，有以下五點(diǎn)：

 1）每個(gè)結(jié)點(diǎn)或者是紅的或者是黑的；

 2）根結(jié)點(diǎn)是黑的畏梆；

 3）每個(gè)葉結(jié)點(diǎn)（NIL）是黑的您宪；

 4）如果一個(gè)結(jié)點(diǎn)是紅的，則它的兩個(gè)孩子都是黑的奠涌；

 5）對(duì)每個(gè)結(jié)點(diǎn)宪巨，從該結(jié)點(diǎn)到其他其子孫結(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑結(jié)點(diǎn)。

   為了后面的分析溜畅，我們還得知道以下知識(shí)點(diǎn)捏卓。

（1）黑高度：從某個(gè)結(jié)點(diǎn)x出發(fā)（不包括該結(jié)點(diǎn)）到達(dá)一個(gè)葉結(jié)點(diǎn)的任意一條路徑上，黑色結(jié)點(diǎn)的個(gè)數(shù)稱為該結(jié)點(diǎn)x的黑高度慈格。

（2）一顆有n個(gè)內(nèi)結(jié)點(diǎn)的紅黑樹(shù)的高度至多為2lg(n+1)怠晴。   （內(nèi)結(jié)點(diǎn)視為紅黑樹(shù)中帶關(guān)鍵字的結(jié)點(diǎn)）

（3）包含n個(gè)內(nèi)部節(jié)點(diǎn)的紅黑樹(shù)的高度是 O(log(n))遥金。

定義

紅黑樹(shù)是特殊的二叉查找樹(shù)，又名R-B樹(shù)(RED-BLACK-TREE)蒜田，由于紅黑樹(shù)是特殊的二叉查找樹(shù)稿械，即紅黑樹(shù)具有了二叉查找樹(shù)的特性，而且紅黑樹(shù)還具有以下特性：

• 1.每個(gè)節(jié)點(diǎn)要么是黑色要么是紅色

• 2.根節(jié)點(diǎn)是黑色

• 3.每個(gè)葉子節(jié)點(diǎn)是黑色冲粤，并且為空節(jié)點(diǎn)(還有另外一種說(shuō)法就是美莫，每個(gè)葉子結(jié)點(diǎn)都帶有兩個(gè)空的黑色結(jié)點(diǎn)（被稱為黑哨兵），如果一個(gè)結(jié)點(diǎn)n的只有一個(gè)左孩子梯捕，那么n的右孩子是一個(gè)黑哨兵茂嗓；如果結(jié)點(diǎn)n只有一個(gè)右孩子，那么n的左孩子是一個(gè)黑哨兵科阎。)

• 4.如果一個(gè)節(jié)點(diǎn)是紅色述吸，則它的子節(jié)點(diǎn)必須是黑色

• 5.從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。

有幾點(diǎn)需要注意的是：

1.特性3中指定紅黑樹(shù)的每個(gè)葉子節(jié)點(diǎn)都是空節(jié)點(diǎn)锣笨，但是在Java實(shí)現(xiàn)中紅黑樹(shù)將使用null代表空節(jié)點(diǎn)蝌矛，因此遍歷紅黑樹(shù)時(shí)看不到黑色的葉子節(jié)點(diǎn)，反而見(jiàn)到的葉子節(jié)點(diǎn)是紅色的

2.特性4保證了從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度不會(huì)超過(guò)任何其他路徑的兩倍错英，例如黑色高度為3的紅黑樹(shù)入撒，其最短路徑(路徑指的是根節(jié)點(diǎn)到葉子節(jié)點(diǎn))是2(黑節(jié)點(diǎn)-黑節(jié)點(diǎn)-黑節(jié)點(diǎn))，其最長(zhǎng)路徑為4(黑節(jié)點(diǎn)-紅節(jié)點(diǎn)-黑節(jié)點(diǎn)-紅節(jié)點(diǎn)-黑節(jié)點(diǎn))椭岩。

實(shí)踐

紅黑樹(shù)操作

插入操作

首先紅黑樹(shù)在插入節(jié)點(diǎn)的時(shí)茅逮，我們?cè)O(shè)定插入節(jié)點(diǎn)的顏色為紅色,如果插入的是黑色節(jié)點(diǎn)，必然會(huì)違背特性5判哥，即改變了紅黑樹(shù)的黑高度献雅，如下插入紅色結(jié)點(diǎn)又存在著幾種情況：

1.黑父

如圖所示，這種情況不會(huì)破壞紅黑樹(shù)的特性塌计，即不需要任何處理

2.紅父

當(dāng)其父親為紅色時(shí)又會(huì)存在以下的情況

• 紅叔

紅叔的情況挺身，其實(shí)相對(duì)來(lái)說(shuō)比較簡(jiǎn)單的，如下圖所示锌仅，只需要通過(guò)修改父章钾、叔的顏色為黑色，祖的顏色為紅色热芹，而且回去遞歸的檢查祖節(jié)點(diǎn)即可

• 黑叔

黑叔的情況有如下幾種贱傀，這幾種情況下是不能夠通過(guò)修改顏色達(dá)到平衡的效果，因此會(huì)通過(guò)旋轉(zhuǎn)的操作伊脓，紅黑樹(shù)種有兩種旋轉(zhuǎn)操作府寒，左旋和右旋(現(xiàn)在存在的疑問(wèn)，什么時(shí)候使用到左旋，什么時(shí)候使用到右旋)

• Case 1:[先右旋椰棘，在改變顏色(根節(jié)點(diǎn)必須為黑色纺棺，其兩個(gè)子節(jié)點(diǎn)為紅色榄笙，叔節(jié)點(diǎn)不用改變)],如下圖所示邪狞，注意省略黑哨兵節(jié)點(diǎn)

• Case 2:[先左旋變成Case1中的情況，再右旋茅撞，最后改變顏色(根節(jié)點(diǎn)必須為黑色帆卓，其兩個(gè)子節(jié)點(diǎn)為紅色，叔節(jié)點(diǎn)不用改變)],如下圖所示米丘，注意省略黑哨兵節(jié)點(diǎn)

• Case 3:[先左旋剑令，最后改變顏色(根節(jié)點(diǎn)必須為黑色，其兩個(gè)子節(jié)點(diǎn)為紅色拄查，叔節(jié)點(diǎn)不用改變)],如下圖所示吁津，注意省略黑哨兵節(jié)點(diǎn)

• Case 4:[先右旋變成Case 3的情況，再左旋堕扶，最后改變顏色(根節(jié)點(diǎn)必須為黑色碍脏，其兩個(gè)子節(jié)點(diǎn)為紅色，叔節(jié)點(diǎn)不用改變)],如下圖所示稍算，注意省略黑哨兵節(jié)點(diǎn)

以上就是紅黑樹(shù)新增節(jié)點(diǎn)所有可能的操作典尾，下面會(huì)介紹紅黑樹(shù)中的刪除操作

刪除操作

刪除操作相比于插入操作情況更加復(fù)雜，刪除一個(gè)節(jié)點(diǎn)可以大致分為三種情況：

• 1.刪除的節(jié)點(diǎn)沒(méi)有孩子節(jié)點(diǎn)糊探，即當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)钾埂，這種可以直接刪除

• 2.刪除的節(jié)點(diǎn)有一個(gè)孩子節(jié)點(diǎn)，這種需要?jiǎng)h除當(dāng)前節(jié)點(diǎn)科平，并使用其孩子節(jié)點(diǎn)頂替上來(lái)

• 3.刪除的節(jié)點(diǎn)有兩個(gè)孩子節(jié)點(diǎn)褥紫，這種需要先找到其后繼節(jié)點(diǎn)(樹(shù)中大于節(jié)點(diǎn)的最小的元素);然后將其后繼節(jié)點(diǎn)的內(nèi)容復(fù)制到該節(jié)點(diǎn)上，其后繼節(jié)點(diǎn)就相當(dāng)于該節(jié)點(diǎn)的替身瞪慧， 需要注意的是其后繼節(jié)點(diǎn)一定不會(huì)有兩個(gè)孩子節(jié)點(diǎn)(這點(diǎn)應(yīng)該很好理解故源，如果后繼節(jié)點(diǎn)有左孩子節(jié)點(diǎn)，那么當(dāng)前的后繼節(jié)點(diǎn)肯定不是最小的汞贸，說(shuō)明后繼節(jié)點(diǎn)只能存在沒(méi)有孩子節(jié)點(diǎn)或者只有一個(gè)右孩子節(jié)點(diǎn))绳军，即這樣就將問(wèn)題轉(zhuǎn)換成為1,2中的方式。

在講述修復(fù)操作之前矢腻，首先需要明白幾點(diǎn)门驾，

1.對(duì)于紅黑樹(shù)而言，單支節(jié)點(diǎn)的情況只有如下圖所示的一種情況多柑，即為當(dāng)前節(jié)點(diǎn)為黑色奶是，其孩子節(jié)點(diǎn)為紅色,(1.假設(shè)當(dāng)前節(jié)點(diǎn)為紅色，其兩個(gè)孩子節(jié)點(diǎn)必須為黑色，2.若有孫子節(jié)點(diǎn)聂沙，則必為黑色秆麸，導(dǎo)致黑子數(shù)量不等，而紅黑樹(shù)不平衡)

2.由于紅黑樹(shù)是特殊的二叉查找樹(shù)及汉，它的刪除和二叉查找樹(shù)類型沮趣，真正的刪除點(diǎn)即為刪除點(diǎn)A的中序遍歷的后繼(前繼也可以)，通過(guò)紅黑樹(shù)的特性可知這個(gè)后繼必然最多只能有一個(gè)孩子坷随，其這個(gè)孩子節(jié)點(diǎn)必然是右孩子節(jié)點(diǎn)房铭，從而為單支情況(即這個(gè)后繼節(jié)點(diǎn)只能有一個(gè)紅色孩子或沒(méi)有孩子)

下面將詳細(xì)介紹，在執(zhí)行刪除節(jié)點(diǎn)操作之后温眉，將通過(guò)修復(fù)操作使得紅黑樹(shù)達(dá)到平衡的情況缸匪。

• Case 1:被刪除的節(jié)點(diǎn)為紅色，則這節(jié)點(diǎn)必定為葉子節(jié)點(diǎn)(首先這里的被刪除的節(jié)點(diǎn)指的是真正刪除的節(jié)點(diǎn)类溢，通過(guò)上文得知的真正刪除的節(jié)點(diǎn)要么是節(jié)點(diǎn)本身凌蔬，要么是其后繼節(jié)點(diǎn)，若是節(jié)點(diǎn)本身則必須為葉子節(jié)點(diǎn)闯冷，不為葉子節(jié)點(diǎn)的話其會(huì)有左右孩子砂心，則真正刪除的是其右孩子樹(shù)上的最小值，若是后繼節(jié)點(diǎn)窃躲，也必須為葉子節(jié)點(diǎn)不傅，若不是則其也會(huì)有左右孩子恃锉，從而和2中相違背)，這種情況下刪除紅色葉節(jié)點(diǎn)就可以了，不用進(jìn)行其他的操作了歧匈。

• Case 2:被刪除的節(jié)點(diǎn)是黑色轴或，其子節(jié)點(diǎn)是紅色拼余，將其子節(jié)點(diǎn)頂替上來(lái)并改變其顏色為黑色帕棉，如下圖所示

• Case 3:被刪除的節(jié)點(diǎn)是黑色，其子節(jié)點(diǎn)也是黑色衰抑，將其子節(jié)點(diǎn)頂替上來(lái)象迎，變成了雙黑的問(wèn)題，此時(shí)有以下情況

  • Case 1:新節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為紅色呛踊，此時(shí)若新節(jié)點(diǎn)在左邊則做左旋操作砾淌，否則做右旋操作，之后再將其父節(jié)點(diǎn)顏色改變?yōu)榧t色谭网，兄弟節(jié)點(diǎn)

從圖中可以看出汪厨，操作之后紅黑樹(shù)并未達(dá)到平衡狀態(tài)，而是變成的黑兄的情況

• Case 2:新節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為黑色,此時(shí)可能有如下情況

  • 紅父二黑侄：將父節(jié)點(diǎn)變成黑色愉择，兄弟節(jié)點(diǎn)變成紅色劫乱，新節(jié)點(diǎn)變成黑色即可,如下圖所示

• 黑父二黑侄：將父節(jié)點(diǎn)變成新節(jié)點(diǎn)的顏色织中，新節(jié)點(diǎn)變成黑色，兄弟節(jié)點(diǎn)染成紅色衷戈，還需要繼續(xù)以父節(jié)點(diǎn)為判定點(diǎn)繼續(xù)判斷,如下圖所示

• 紅侄：

情況一:新節(jié)點(diǎn)在右子樹(shù)狭吼，紅侄在兄弟節(jié)點(diǎn)左子樹(shù)，此時(shí)的操作為右旋殖妇，并將兄弟節(jié)點(diǎn)變?yōu)楦赣H的顏色刁笙，父親節(jié)點(diǎn)變?yōu)楹谏豆?jié)點(diǎn)變?yōu)楹谏唬缦聢D所示

情況二:新節(jié)點(diǎn)在右子樹(shù)采盒，紅侄在兄弟節(jié)點(diǎn)右子樹(shù)旧乞，此時(shí)的操作為先左旋蔚润，后右旋并將侄節(jié)點(diǎn)變?yōu)楦赣H的顏色，父節(jié)點(diǎn)變?yōu)楹谏咂埽缦聢D所示

情況三：新節(jié)點(diǎn)在左子樹(shù)嫡纠，紅侄在兄弟節(jié)點(diǎn)左子樹(shù),此時(shí)的操作為先右旋在左旋并將侄節(jié)點(diǎn)變?yōu)楦赣H的顏色，父親節(jié)點(diǎn)變?yōu)楹谏佣模缦聢D所示

情況四：新節(jié)點(diǎn)在右子樹(shù)除盏，紅侄在兄弟節(jié)點(diǎn)右子樹(shù),此時(shí)的操作為左旋，并將兄弟節(jié)點(diǎn)變?yōu)楦腹?jié)點(diǎn)的顏色挫以，父親節(jié)點(diǎn)變?yōu)楹谏呷洌豆?jié)點(diǎn)變?yōu)楹谏缦聢D所示

紅黑樹(shù)實(shí)現(xiàn)

如下是使用JAVA代碼實(shí)現(xiàn)紅黑樹(shù)的過(guò)程掐松，主要包括了插入踱侣、刪除、左旋大磺、右旋抡句、遍歷等操作

插入

/* 插入一個(gè)節(jié)點(diǎn)
 * @param node
 */
private void insert(RBTreeNode<T> node){
    int cmp;
    RBTreeNode<T> root = this.rootNode;
    RBTreeNode<T> parent = null;

    //定位節(jié)點(diǎn)添加到哪個(gè)父節(jié)點(diǎn)下
    while(null != root){
        parent = root;
        cmp = node.key.compareTo(root.key);
        if (cmp < 0){
            root = root.left;
        } else {
            root = root.right;
        }
    }

    node.parent = parent;
    //表示當(dāng)前沒(méi)一個(gè)節(jié)點(diǎn)，那么就當(dāng)新增的節(jié)點(diǎn)為根節(jié)點(diǎn)
    if (null == parent){
        this.rootNode = node;
    } else {
        //找出在當(dāng)前父節(jié)點(diǎn)下新增節(jié)點(diǎn)的位置
        cmp = node.key.compareTo(parent.key);
        if (cmp < 0){
            parent.left = node;
        } else {
            parent.right = node;
        }
    }

    //設(shè)置插入節(jié)點(diǎn)的顏色為紅色
    node.color = COLOR_RED;

    //修正為紅黑樹(shù)
    insertFixUp(node);
}

/**
 * 紅黑樹(shù)插入修正
 * @param node
 */
private void insertFixUp(RBTreeNode<T> node){
    RBTreeNode<T> parent,gparent;
    //節(jié)點(diǎn)的父節(jié)點(diǎn)存在并且為紅色
    while( ((parent = getParent(node)) != null) && isRed(parent)){
        gparent = getParent(parent);

        //如果其祖父節(jié)點(diǎn)是空怎么處理
        // 若父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左孩子
        if(parent == gparent.left){
            RBTreeNode<T> uncle = gparent.right;
            if ((null != uncle) && isRed(uncle)){
                setColorBlack(uncle);
                setColorBlack(parent);
                setColorRed(gparent);
                node = gparent;
                continue;
            }

            if (parent.right == node){
                RBTreeNode<T> tmp;
                leftRotate(parent);
                tmp = parent;
                parent = node;
                node = tmp;
            }

            setColorBlack(parent);
            setColorRed(gparent);
            rightRotate(gparent);
        } else {
            RBTreeNode<T> uncle = gparent.left;
            if ((null != uncle) && isRed(uncle)){
                setColorBlack(uncle);
                setColorBlack(parent);
                setColorRed(gparent);
                node = gparent;
                continue;
            }

            if (parent.left == node){
                RBTreeNode<T> tmp;
                rightRotate(parent);
                tmp = parent;
                parent = node;
                node = tmp;
            }

            setColorBlack(parent);
            setColorRed(gparent);
            leftRotate(gparent);
        }
    }
    setColorBlack(this.rootNode);
}

插入節(jié)點(diǎn)的操作主要分為以下幾步：

• 1.定位：即遍歷整理紅黑樹(shù)杠愧，確定添加的位置待榔，如上代碼中insert方法中就是在找到添加的位置

• 2.修復(fù)：這也就是前面介紹的，添加元素后可能會(huì)使得紅黑樹(shù)不在滿足其特性流济，這時(shí)候需要通過(guò)變色锐锣、旋轉(zhuǎn)來(lái)調(diào)整紅黑樹(shù)，也就是如上代碼中insertFixUp方法

刪除節(jié)點(diǎn)

如下為刪除節(jié)點(diǎn)的代碼

private void remove(RBTreeNode<T> node){
    RBTreeNode<T> child,parent;
    boolean color;
    //被刪除節(jié)點(diǎn)左右孩子都不為空的情況
    if ((null != node.left) && (null != node.right)){

        //獲取到被刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)
        RBTreeNode<T> replace = node;

        replace = replace.right;
        while(null != replace.left){
            replace = replace.left;
        }

        //node節(jié)點(diǎn)不是根節(jié)點(diǎn)
        if (null != getParent(node)){
            //node是左節(jié)點(diǎn)
            if (getParent(node).left == node){
                getParent(node).left = replace;
            } else {
                getParent(node).right = replace;
            }
        } else {
            this.rootNode = replace;
        }

        child = replace.right;
        parent = getParent(replace);
        color = getColor(replace);

        if (parent == node){
            parent = replace;
        } else {
            if (null != child){
                setParent(child,parent);
            }
            parent.left = child;

            replace.right = node.right;
            setParent(node.right, replace);
        }

        replace.parent = node.parent;
        replace.color = node.color;
        replace.left = node.left;
        node.left.parent = replace;
        if (color == COLOR_BLACK){
            removeFixUp(child,parent);
        }

        node = null;
        return;
    }

    if (null != node.left){
        child = node.left;
    } else {
        child = node.right;
    }

    parent = node.parent;
    color = node.color;
    if (null != child){
        child.parent = parent;
    }

    if (null != parent){
        if (parent.left == node){
            parent.left = child;
        } else {
            parent.right = child;
        }
    } else {
        this.rootNode = child;
    }

    if (color == COLOR_BLACK){
        removeFixUp(child, parent);
    }
    node = null;
}

/**
 * 刪除修復(fù)
 * @param node
 * @param parent
 */
private void removeFixUp(RBTreeNode<T> node, RBTreeNode<T> parent){
    RBTreeNode<T> other;
    //node不為空且為黑色绳瘟，并且不為根節(jié)點(diǎn)
    while ((null == node || isBlack(node)) && (node != this.rootNode) ){
        //node是父節(jié)點(diǎn)的左孩子
        if (node == parent.left){
            //獲取到其右孩子
            other = parent.right;
            //node節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是紅色
            if (isRed(other)){
                setColorBlack(other);
                setColorRed(parent);
                leftRotate(parent);
                other = parent.right;
            }

            //node節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是黑色雕憔，且兄弟節(jié)點(diǎn)的兩個(gè)孩子節(jié)點(diǎn)也是黑色
            if ((other.left == null || isBlack(other.left)) &&
                    (other.right == null || isBlack(other.right))){
                setColorRed(other);
                node = parent;
                parent = getParent(node);
            } else {
                //node節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是黑色，且兄弟節(jié)點(diǎn)的右孩子是紅色
                if (null == other.right || isBlack(other.right)){
                    setColorBlack(other.left);
                    setColorRed(other);
                    rightRotate(other);
                    other = parent.right;
                }
                //node節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是黑色稽荧，且兄弟節(jié)點(diǎn)的右孩子是紅色橘茉，左孩子是任意顏色
                setColor(other, getColor(parent));
                setColorBlack(parent);
                setColorBlack(other.right);
                leftRotate(parent);
                node = this.rootNode;
                break;
            }
        } else {
            other = parent.left;
            if (isRed(other)){
                setColorBlack(other);
                setColorRed(parent);
                rightRotate(parent);
                other = parent.left;
            }

            if ((null == other.left || isBlack(other.left)) &&
                    (null == other.right || isBlack(other.right))){
                setColorRed(other);
                node = parent;
                parent = getParent(node);
            } else {
                if (null == other.left || isBlack(other.left)){
                    setColorBlack(other.right);
                    setColorRed(other);
                    leftRotate(other);
                    other = parent.left;
                }

                setColor(other,getColor(parent));
                setColorBlack(parent);
                setColorBlack(other.left);
                rightRotate(parent);
                node = this.rootNode;
                break;
            }
        }
    }
    if (node!=null)
        setColorBlack(node);
}

刪除節(jié)點(diǎn)主要分為幾種情況去做對(duì)應(yīng)的處理：

• 1.刪除節(jié)點(diǎn),按照如下三種情況去刪除節(jié)點(diǎn)
  • 1.真正刪除的節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)
  • 2.真正刪除的節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)
  • 3.正在刪除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
• 2.修復(fù)紅黑樹(shù)的特性工腋，如代碼中調(diào)用removeFixUp方法修復(fù)紅黑樹(shù)的特性。

3.總結(jié)

以上主要介紹了紅黑樹(shù)的一些特性畅卓，包括一些操作詳細(xì)的解析了里面的過(guò)程擅腰，寫(xiě)的時(shí)間比較長(zhǎng)，感覺(jué)確實(shí)比較難理清楚翁潘。后面會(huì)持續(xù)的理解更深入趁冈，若有存在問(wèn)題的地方，請(qǐng)指正拜马。

參考文章

紅黑樹(shù)(五)之 Java的實(shí)現(xiàn)

通過(guò)分析 JDK 源代碼研究 TreeMap 紅黑樹(shù)算法實(shí)現(xiàn)

紅黑樹(shù)

（圖解）紅黑樹(shù)的插入和刪除

紅黑樹(shù)深入剖析及Java實(shí)現(xiàn)

微信公眾號(hào)

Java技術(shù)江湖

如果大家想要實(shí)時(shí)關(guān)注我更新的文章以及分享的干貨的話渗勘，可以關(guān)注我的公眾號(hào)【Java技術(shù)江湖】一位阿里 Java 工程師的技術(shù)小站，作者黃小斜俩莽，專注 Java 相關(guān)技術(shù)：SSM旺坠、SpringBoot、MySQL扮超、分布式取刃、中間件、集群出刷、Linux璧疗、網(wǎng)絡(luò)、多線程馁龟，偶爾講點(diǎn)Docker崩侠、ELK，同時(shí)也分享技術(shù)干貨和學(xué)習(xí)經(jīng)驗(yàn)坷檩，致力于Java全棧開(kāi)發(fā)却音！

Java工程師必備學(xué)習(xí)資源: 一些Java工程師常用學(xué)習(xí)資源，關(guān)注公眾號(hào)后淌喻，后臺(tái)回復(fù)關(guān)鍵字 “Java” 即可免費(fèi)無(wú)套路獲取僧家。

我的公眾號(hào)

個(gè)人公眾號(hào)：黃小斜

黃小斜是跨考軟件工程的 985 碩士，自學(xué) Java 兩年裸删，拿到了 BAT 等近十家大廠 offer八拱，從技術(shù)小白成長(zhǎng)為阿里工程師。

作者專注于 JAVA 后端技術(shù)棧涯塔，熱衷于分享程序員干貨肌稻、學(xué)習(xí)經(jīng)驗(yàn)、求職心得和程序人生匕荸，目前黃小斜的CSDN博客有百萬(wàn)+訪問(wèn)量爹谭，知乎粉絲2W+，全網(wǎng)已有10W+讀者榛搔。

黃小斜是一個(gè)斜杠青年诺凡，堅(jiān)持學(xué)習(xí)和寫(xiě)作东揣，相信終身學(xué)習(xí)的力量，希望和更多的程序員交朋友腹泌，一起進(jìn)步和成長(zhǎng)嘶卧！關(guān)注公眾號(hào)【黃小斜】后回復(fù)【原創(chuàng)電子書(shū)】即可領(lǐng)取我原創(chuàng)的電子書(shū)《菜鳥(niǎo)程序員修煉手冊(cè)：從技術(shù)小白到阿里巴巴Java工程師》

程序員3T技術(shù)學(xué)習(xí)資源： 一些程序員學(xué)習(xí)技術(shù)的資源大禮包，關(guān)注公眾號(hào)后凉袱，后臺(tái)回復(fù)關(guān)鍵字 “資料” 即可免費(fèi)無(wú)套路獲取芥吟。

?

本文由博客一文多發(fā)平臺(tái) OpenWrite 發(fā)布！