點擊上方“小白學視覺”，選擇加"星標"或“置頂”

重磅干貨，第一時間送達

正是因為作為二叉查找樹的紅黑樹滿足這些性質(zhì)，才使得樹的節(jié)點是相對平衡的。由歸納法得知，如果一顆子樹的根到nullNode節(jié)點的路徑都包含B個黑色節(jié)點，則這棵子樹含有除nullNode節(jié)點外的2^B-1個節(jié)點，而由性質(zhì)4得從根到nullNode節(jié)點的路徑上至少有一半的節(jié)點是黑色的，從而得到樹包含的節(jié)點數(shù)n>=2^(h/2)-1,h是樹的深度，從而得到h<=2*log(n+1)。即可以保證紅黑樹的深度是對數(shù)的，可以保證對樹的查找、插入刪除等操作滿足對數(shù)級的時間復雜度。

下邊我們將討論紅黑樹最主要的兩個算法，插入和刪除。

對于第一種情況：插入后將根節(jié)點再染成黑色即可。

對于第二種情況：直接插入依然滿足性質(zhì)。首先設(shè)X是新增節(jié)點，P是其父節(jié)點，S是其父節(jié)點的兄弟節(jié)點，G是其的祖父節(jié)點。

對于第三種情況：違反了性質(zhì)4，我們可以通過對P進行右旋和節(jié)點的重新著色對樹進行修復（應對三、四兩種情況我們的著色方式都是：在旋轉(zhuǎn)前先將要旋轉(zhuǎn)的根節(jié)點染紅，然后旋轉(zhuǎn)，最后將新的根節(jié)點染黑）見下面的“圖2”。

對于第四種情況：亦是如此，只不過我們需要兩次旋轉(zhuǎn)，先對P做左旋再對G做右旋，并重新著色，見下面的“圖3”。

紅黑樹的刪除相對復雜些，但只要我們思路明確，問題就迎刃而解。我們先回憶普通二叉樹的刪除操作，可分為三種情況：

1.沒有孩子節(jié)點：直接刪掉該節(jié)點

2.只有一個孩子節(jié)點：將要刪除節(jié)點的父節(jié)點直接與該孩子節(jié)點相鏈

3.有兩個孩子節(jié)點：將中序遍歷的后繼，即待刪除節(jié)點的右子樹中的最小節(jié)點賦給待刪除節(jié)點，然后將該后繼刪掉。實際最終都會歸于1、2兩種情況。

        對于紅黑樹來說，我們不僅要滿足二叉樹的性質(zhì)，而且要滿足著色要求，所以討論的情況會比較多，我們從簡單的情況開始討論。如果待刪除的實際節(jié)點是紅色的，我們可以用普通方法進行刪除，因為刪除過后樹依然滿足紅黑樹的性質(zhì)。如果待刪除的實際節(jié)點是黑色的，就會出現(xiàn)三個問題：

1.如果刪除的節(jié)點是根節(jié)點，而他的紅色孩子成了根節(jié)點，這就違反了“規(guī)則2”。

2.如果刪除的節(jié)點的父節(jié)點是紅色的，而該節(jié)點的孩子也是紅色的，刪除之后就會違反“規(guī)則4”。

3.刪除了一個黑色節(jié)點后，包含該節(jié)點的任何路徑黑色節(jié)點數(shù)都會少1，從而違反了“規(guī)則5”，我們的任務就是把這些問題解決。

百花齊放：

        首先，我們解決問題的總體思路很簡單：將節(jié)點刪除，然后通過旋轉(zhuǎn)和適當?shù)闹珌硇迯蜆涫怪匦聺M足紅黑樹的性質(zhì)。我們的入手點就是我們之后所說的當前節(jié)點。我們知道實際刪除的節(jié)點要么只有一個孩子，要么沒有孩子，如果該刪除節(jié)點有一個孩子，則將這個孩子作為當前節(jié)點，如果沒有孩子，則將nullNode節(jié)點作為當前節(jié)點。當前節(jié)點的父節(jié)點就是原刪除節(jié)點的父節(jié)點。我們第一次調(diào)整樹就是從上邊描述的當前節(jié)點x開始。（要記住第一個當前節(jié)點，要不然后邊的描述會變得含糊不清）。

       對于問題1我們很好解決，最后再把根節(jié)點涂黑即可。而對于問題2，我們可以把當前節(jié)點涂黑就可以讓樹滿足紅黑樹的性質(zhì)?，F(xiàn)在我們需要關(guān)注的問題是問題3，即讓刪除節(jié)點后的樹依然滿足紅黑樹的性質(zhì)5——各個節(jié)點到根節(jié)點到葉節(jié)點nullNode所包含的的黑節(jié)點數(shù)相同。

       現(xiàn)在你有什么思路呢？如果像先前我們執(zhí)行插入的思路那樣，自頂向下，保證刪除的節(jié)點是紅色的，這看起來是可行的，但要怎么處理呢？要處理的情況是不是太多了？我們可不可以加上一些條件限制來減少對情況的處理，比如左節(jié)點不能是紅色的？

要點核心：

      這里的處理的思路是：既然刪除節(jié)點后經(jīng)過該節(jié)點的路徑上黑色節(jié)點都少一個，我們可不可以將這黑色下推到他的子節(jié)點，這樣子節(jié)點就有了兩重顏色。這樣就可以滿足性質(zhì)5了。而又違反了性質(zhì)1，即節(jié)點要么是紅色的要么是黑色的。我們要做的在保持性質(zhì)的情況下去掉。（實際上這一層黑色是我們處理問題所轉(zhuǎn)換的標記，并非節(jié)點的顏色屬性，當前節(jié)點指向誰，誰就有了這一層黑色，最終我們在保證基本性質(zhì)的情況下去掉這一層黑色的影響，問題解決）要想去掉這一層黑色，我們處理的方式有：

1.將這層黑色推向一個包含刪除節(jié)點路徑上的一個紅色節(jié)點，在滿足其他性質(zhì)的情況下將其染成黑色。

2.一直推至根節(jié)點，減掉這層黑色。（因為我們每次的調(diào)整最后都是滿足性質(zhì)的）

3.在某些情況下，通過調(diào)整和重新著色，我們就可以保住性質(zhì)，當然這一點有點難以憑空想象，那就看看下邊的情況分析吧。

具體操作：

      首先我們可以將情況分為兩類，即當前節(jié)點是其父節(jié)點的右節(jié)點或左節(jié)點，他們是對稱的，只需要對一種情況進行詳細討論，另一種情況也就是以此類推了。一般的資料都是對當前節(jié)點x是做節(jié)點的情況進行分析，在這里我們就先對x是右節(jié)點的情況一一畫圖進行分析。這里先對圖中的標記進行解釋：x表示當前節(jié)點，w表示當前節(jié)點的，p表示x的父節(jié)點，c表示某個確定的顏色（可能是紅，也可能是黑，就看實際情況了）對應于邏輯中的存在，c'表示任意顏色（才不管你是什么顏色咧，對討論無影響）對應于邏輯中的任意。

情況1：

當前節(jié)點x的兄弟w是紅色的。這種情況我們可以確定x的父節(jié)點為黑色，w的兩個孩子為黑。如圖所示，我們先對p染紅，再將w染黑，然后對p進行一次右旋，紅黑性質(zhì)得以保持。而這時新的兄弟節(jié)點是黑色的，進而可以將情況一轉(zhuǎn)換成情況2、3、4中的一種。

情況2：

當前節(jié)點x的兄弟節(jié)點w是黑色的，且w的兩個孩子都是黑色的。這種情況我們無法確定父節(jié)點p的顏色，所以其顏色標記為c，情況3、4同。在這個情況下，我們可以將x、w同時去掉一層黑色，將這一層黑色指向根節(jié)點p，p變成新的當前節(jié)點x。此時如果該標記顏色c為紅色，則可以將節(jié)點染成黑色，此時指針x的那一層黑色被去掉，同時紅黑性質(zhì)得到滿足，調(diào)整完畢；如果c為黑色，則需要對新的當前節(jié)點x的情況進行處理，直到調(diào)整完畢。

情況3：

當前節(jié)點x的兄弟節(jié)點為黑色，且w的左孩子是黑色，右孩子是紅色的。在這種情況下，我們將w和其右孩子的顏色交換，并對w進行左轉(zhuǎn)，紅黑性質(zhì)得以保持。此時已將情況3轉(zhuǎn)換成情況4。

情況4：

當前節(jié)點x的兄弟節(jié)點w為黑色，且w的左孩子是紅的，有孩子可以為任意顏色。將p的顏色賦給w，然后將p，和w的左節(jié)點染黑，并對p做右旋轉(zhuǎn)。這是可以去掉x的額外的黑色，而且可以保持紅黑性質(zhì)。最后將樹的根賦給x后，調(diào)整結(jié)束。

我們發(fā)現(xiàn)，情況1、3、4最多經(jīng)過三次旋轉(zhuǎn)調(diào)整就可以結(jié)束。情況二在最壞的情況下一直向上推最多也是樹的層數(shù)log(n),這就是紅黑樹刪除操作的性能優(yōu)勢。

/**
 * 1.沒有孩子節(jié)點：直接刪掉該節(jié)點 
 * 2.只有一個孩子節(jié)點：將要刪除節(jié)點的
      父節(jié)點直接與該孩子節(jié)點相鏈 
 * 3.有兩個孩子節(jié)點：將中序遍歷的后繼，即待刪除節(jié)點的右
     子樹中的最小節(jié)點賦給待刪除節(jié)點，然后將該后繼刪掉。
 * @param e 要刪除的元素 
 * @param t 刪除元素的樹的根節(jié)點 
 * @return  被刪除的節(jié)點
 */
private RedBlackNode<E> remove(E e,RedBlackNode<E> t){
    if(t==nullNode)
        return null;
    //找到要刪除的節(jié)點  
    while(compare(e,t)!=0){
        if(compare(e,t)<0&&t.left!=nullNode)
            t = t.left;
        else if(compare(e,t)>0&&t.right!=nullNode)
            t = t.right;
        else
            return null;
    }
    RedBlackNode<E> x;//當前節(jié)點  
    RedBlackNode<E> y;//要刪除的節(jié)點  
    //如果待刪除節(jié)點只有一個孩子或沒有孩子，則實際刪除的節(jié)點
      //就是所指節(jié)點，如果有兩個孩子則實際刪除節(jié)點是右子樹的最小項  
    //先確定刪除節(jié)點  
    if(t.left==nullNode||t.right==nullNode)
        y = t;
    else
        y = findMin(t.right);
     //再確定當前節(jié)點，如果實際刪除節(jié)點的左節(jié)點不為nullNode，
      //則當前節(jié)點為左節(jié)點，如果刪除節(jié)點只有右節(jié)點或沒有孩子  
    //我們都將右孩子賦給他，因為沒有孩子時右節(jié)點為nullNode  
    if(y.left!=nullNode)
        x = y.left;
    else
        x = y.right;
    //當前節(jié)點的父親指向刪除節(jié)點的父親  
    x.parent = y.parent;
    //我們根據(jù)刪除節(jié)點在其父節(jié)點的子樹方向，將父節(jié)點直接鏈接到當前節(jié)點  
   //需要注意的是我們引用的偽根節(jié)點就是為了減少對特殊情況的討論，
    //不然有這行代碼if(y.parent==header)header.right = x;  
    if(y==y.parent.left)
        y.parent.left = x;
    else
        y.parent.right = x;
    //如果實際刪除的節(jié)點不是我們找到的具有該鍵的節(jié)點，它屬于有兩個
     //孩子的情況，我們將實際刪除的節(jié)點的值賦給它  
    if(y!=t)
        t.element = y.element;
    if(y.color==BLACK)
        removeFixUp(x);
    return y;
}

/**
 * 刪除修復方法 
 * @param x 當前節(jié)點 
 */
private void removeFixUp(RedBlackNode<E> x){
    RedBlackNode<E> w;
    while(x!=header.right&&x.color==BLACK){
            //當前節(jié)點是父節(jié)點的左節(jié)點  
    if(x==x.parent.left){
          w = x.parent.right;
          //case1，如上詳細分析，如果x的兄弟節(jié)點為紅色，
          //調(diào)整后是兄弟節(jié)點為黑后再往下走  
       if(w.color==RED){
          x.parent.color = RED;
          w.color = BLACK;
          rightRotate(x.parent,x.parent.parent);
          w = x.parent.right;
       }
          //case2，新的x如果為紅色，循環(huán)終止，否則繼續(xù)循環(huán)  
    if(w.left.color==BLACK&&w.right.color==BLACK){
           w.color = RED;
           x = x.parent;
       }else {
          //case3,兄弟節(jié)點的右孩子是黑色的，
          //左孩子時紅色的，調(diào)整后進入case4  
       if(w.right.color==BLACK){
           w.left.color = BLACK;
           w.color = RED;
           rightRotate(w, w.parent);
           w = x.parent.right;
       }
          //case4，調(diào)整完成，滿足紅黑性質(zhì)  
           w.color = x.parent.color;
           x.parent.color = BLACK;
           w.right.color = BLACK;
      leftRotate(x.parent, x.parent.parent);
           x = header.right;
        }
        }else{
        //對稱  
        }
        x.color = BLACK;
    }
}

交流群

歡迎加入公眾號讀者群一起和同行交流，目前有SLAM、三維視覺、傳感器、自動駕駛、計算攝影、檢測、分割、識別、醫(yī)學影像、GAN、算法競賽等微信群（以后會逐漸細分），請掃描下面微信號加群，備注：”昵稱+學校/公司+研究方向“，例如：”張三 + 上海交大 + 視覺SLAM“。請按照格式備注，否則不予通過。添加成功后會根據(jù)研究方向邀請進入相關(guān)微信群。請勿在群內(nèi)發(fā)送廣告，否則會請出群，謝謝理解~