前言

紅黑樹是一種特殊的B樹是B樹種2-3-4樹的一種特殊實現，紅黑樹保證了每個節點只會有兩個子節點，通過對每個節點進行染色，然后通過不同顏色的節點組合來分別代表2-3-4的2節點、3節點、4節點樹的情況。在學習紅黑樹之前，我們需要先去了解2-3-4樹。

一、 B樹

那么如果想要對紅黑樹有一個較為深刻的理解，我認為首先去理解其根源，也就是B樹是必不可少的

1.1 概念

樹形結構首先可以分為等叉樹和不等叉樹，等叉樹是每個節點的鍵值個數都相同、子節點個數也都相同，不等叉樹是每個節點的鍵值個數不一定相同、子節點個數也不一定相同。

最簡單的等叉樹是二叉樹，直接二叉樹的作用并不大，我們一般會要求二叉樹所有的節點按照一定的順序排列，這樣我們進行插入、刪除、查找時效率就會非常高，我們把這樣的樹叫做二叉搜索樹或者二叉查找樹。它的具體定義是這樣的，二叉搜索樹，要么是個空樹，要么符合以下幾個條件:

1. 左子樹如果存在的話，左子樹所有節點的鍵值都要小于根節點的鍵值
2. 右子樹如果存在的話，右子樹所有節點的鍵值都要大于根節點的鍵值
3. 它的所有子樹也都要符合前面的兩個條件(前面的小于同時換成大于也成立)。

經過這樣定義之后，二叉樹就變成了二叉搜索樹，它的插入、刪除、查找效率一般情況下都是O(logn)。

相較于等叉樹，我們可以對不等叉樹的節點鍵數值數和插入、刪除邏輯添加一些特殊的要求使其能達到絕對平衡的效果，我們把這種樹叫做 B樹，全稱Balance Tree，是一種自平衡樹，它和等叉樹最大的不同首先表現在存儲結構上，等叉樹上每個幾點的鍵值數和分叉數都是相同的，而B樹不是。如果某個B樹上所有節點的分叉數最大值是m，則把這個B數叫做m階B數。下面我們來看一下B樹的具體定義：

1. 所有節點最多有m個子節點
2. 非根非葉子結點至少有m/2(向上取整)個子節點
3. 根節點至少有兩個子節點(除非總結點數不足3個)
4. 所有葉子節點都在同一層
5. 任意節點如果有k個鍵值，則有k+1個子節點指針，鍵值要按照從小到大排列，子節點數上所有的鍵值都要在對應的兩個鍵值之間

B樹看似5條定義很復雜，但實際上自己分析一下理解后會發現還是蠻簡單的。第一條，對子節點數進行限制，這也是m階B樹m的由來，第二條，是用來限制樹的緊湊性，避免樹又高又長。第三條沒什么好說的。第四條規定了B樹是一個絕對平衡樹不會退化為線性結構，所以B樹的效率永遠是O(logn)。第5條保證了B樹的元素的有序，以便高效率的查找。

1.2 2-3-4樹

2-3-4樹其實就是4階的B樹，目前網上講的紅黑樹大多數就是2-3樹或者是2-3-4樹轉化而成的。這里僅對2-3-4樹進行講解

1.3 2-3-4樹的插入

節點分類

• 2節點：一個節點中有1個鍵值，2條鏈接
• 3節點：一個節點中有2個鍵值，3條鏈接
• 4節點：一個節點中有3個鍵值，4條鏈接

首先是2節點的插入，由于2-3-4樹是4階B樹，最多可以有4條連接，一個節點最多有3個鍵值，所以這里直接添加即可

 

然后是3節點的插入，2節點插入之后，轉化為4節點，仍保持一個節點的狀態

 

4節點插入,由于2-3-4樹是4階B樹，所以當對4節點插入的時候，就需要對4節點進行分裂，首先將中間的節點上升，然后,根據B樹定義，將新增的節點和葉子的其中一個節點結合，形成一個3節點，比如，下圖中要插入4,首先123分裂，之后4根據大小順序，放在3的右邊，和3形成一個3節點。

 

之后如果繼續插入，第二層節點如果再形成4節點的情況下插入，那么分裂之后出來的節點，應該和父節點再構成節點

 

如果向上和父節點構成節點，但是父節點已經是4節點了，這個時候父節點就需要繼續分裂，在往上的情況一次類推，進行遞歸分裂

 

1.4 2-3-4樹的刪除

相對于插入，B樹的刪除就相對復雜，需要分情況討論

1.4.1 當刪除節點是葉子節點

當刪除節點是葉子節點的時候，又分為以下情況

1.4.1.1 當刪除節點為非2節點

直接刪除即可，因為從一個非2節點中刪除一個鍵值以后，并不違反B樹的定義

1.4.1.2 當刪除節點為2節點

這種情況又要分多種情況

1.4.1.2.1 兄弟節點是非2節點

當兄弟節點是非2節點，我們可以直接從兄弟節點借一個元素過來，讓當前刪除節點形成非2節點，這樣情況就轉換為了2.3.3.1的情況，直接刪除要刪除的節點既可

 

1.4.1.2.2 兄弟節點是2節點

如果兄弟節點是2節點，那么此時就需要從父節點借元素了，待刪除結點和父節點、兄弟節點構成一個4節點，然后將待刪除節點刪。

如果父節點是非2節點，那么借走就接走了，如果是2節點，借走了當前位置就空了，所以需要再從這個節點的兄弟或父節點借一個元素，如果直到根節點也沒有找到一個非2節點，那么這個B樹的高度就會減一。

 

1.4.2 如果刪除節點是非葉子節點

1. 如果被刪除節點是非葉子節點，那么我們就需要找到他的后繼元素，然后將后繼元素的值覆蓋被刪除元素，再將后繼元素刪除即可
2. 那么如何尋找后繼節點呢？一般來說就是key大小最接近被刪除元素的葉子節點中的元素，這個元素可以大于key也可以小于key，這個是我們可以自己定義，這里我們選小于被刪除元素的那個。也就是左子樹節點中最大的元素。

 

二、 紅黑樹

通過上一節，我們了解了紅黑樹的前身或者說是其本源B樹之后我們再來看紅黑樹，相信你能夠更容易理解紅黑樹，看出其操作的底層邏輯

在講解之前我先講紅黑樹的類結構放出來

public class RedBlackBST<Key extends Comparable<Key>, Value> {

    //很明顯，這個常量用來代指紅或黑
    private static final boolean Red = true;

    private static final boolean Black = false;

    //根節點
    private Node root;


    //節點類結構
    private class Node {
        Key key;
        Value value;
        Node left, right, parent;
        int N;
        boolean color;

        public Node(Key key, Value value, Node parent, int n, boolean color) {
            this.key = key;
            this.value = value;
            N = n;
            this.color = color;
            this.parent = parent;
        }

    }

    public RedBlackBST() {

    }

    //用來判斷一個節點是還是黑色
    private boolean isRed(Node x) {
        if (x == null) return false;
        return x.color == Red;
    }

}

2.1 紅黑樹的定義

紅黑樹，本質上其實就是將一個B樹（我們這里討論2-3-4樹）轉化為一個二叉樹。那么如何去轉化的同時又能繼承B樹絕對平衡性呢？答案就是通過染色和旋轉，到這里打住，讓我們先來看紅黑樹的定義

1. 所有的節點不是黑色就是紅色
2. 根節點是黑色的
3. 所有葉子節點是黑色的
4. 從每個葉子到跟的所有路徑上不能有兩個連續的紅色節點
5. 從任意節點到其每個葉子的所有路徑都包含相同數目的黑色節點

2.2 2-3-4樹節點到紅黑樹的轉換

在解釋這幾個定義之前我們需要先來開2-3-4樹中節點轉化到紅黑樹中的形式是怎樣的

首先我們要明白的是，在紅黑樹中，只有黑色節點才計入高度，紅色節點代表著其和父節點的鏈接是紅色的。

非2節點由黑色節點+紅色節點組合的形式表示，紅黑樹對應到2-3-4樹的節點組合中只會存在一個黑色節點。

2.2.1 2節點轉換

 

2.2.2 3節點轉換

3節點轉換成紅黑樹就是一個黑色節點帶著紅色子節點的樹，這個樹可以是左傾的也可以是右傾的，根據節點的key來決定，在以2-3樹為基礎實現的紅黑樹中，我們一般只允許左傾或則右傾樹存在，如果出現不允許的傾斜樹情況，一般會通過旋轉變色來調整。

 

2.2.3 4節點轉換

 

2.2.4 例子

 

2.3 紅黑樹定義解釋

先在我們再來來挨個看這5條定義

1. 第一條這個沒什么好說的，紅黑樹紅黑樹，那肯定節點不是紅色就是黑色
2. 由于根節點必然是沒有父節點的，而在上面我們所列舉的轉換形式中并沒有紅色節點為父節點的結構，所以根節點必然是黑色的
3. 在紅黑樹中葉子節點會默認擁有兩個為null的子節點，顏色自然是黑色
4. 不允許又連續兩個紅色節點是為了限制紅黑樹的階數為4，不允許出現2、3、4節點之外的節點類型
5. 對應2-3-4樹的第五條，保證了樹的絕對平衡，對應到紅黑樹中只有黑色節點代表高度，所以只需要保證黑色節點的數目一致即可。

2.3.1 紅黑樹的旋轉與變色

我們在對紅黑樹進行添加的時候，一開始按照二叉樹的方式添加，每個新節點的初始元素為紅色（root節點為黑色），當我們繼續進行添加，發現當前的紅黑樹結構不符合定義時，我們就需要通過旋轉和對節點變色來重新平衡紅黑樹。

2.3.2 紅黑樹的旋轉

先說旋轉，紅黑樹的旋轉分為左旋和右旋，我們先通過左旋來進行詳細講解。左旋就是一個節點繞著他的右子節點逆時針旋轉，變成右子節點的左子節點，我們以下圖為例

 

A進行左旋，變成B的左子節點，于此同時，B原先的左子樹變成A的右子樹，A的父節點變為B的父節點。

A的左子樹依舊是A的左子樹，B的右子樹也依舊是B的右子樹，不做變化。

這樣，我們就完成了一次左旋，右旋則是繞則操作節點自身的子節點順時針旋轉，變成左子節點的右子樹，左子節點的右子樹遷移到操作節點的左子樹，操作節點的父節點變成左子節點的父節點。原理一模一樣。

2.3.3 紅黑樹的變色

當然，我們在旋轉以后，如果不變色，結果肯定是不正確的，只有進行變色之后的紅黑樹才是正確的，由于變色有很多種情況，所以我們這里只舉一個簡單的例子，后面在講解添加和刪除的時候再進行細致列舉。

 

首先我們這里有一個兩個節點的二叉樹，現在他是正確的，這個時候我們再插入一個新的節點3，那么根據二叉樹的性質，插入后這個樹會變成這個樣子

 

當然，這個結果明顯是錯誤的，其結構明顯不符合我們我們在2.2.2中展示的任何一種形式,所以我們要通過旋轉和變色變換為2.2.2中的哪幾種形式。

 

首先這個組合在2-3-4樹種是一個4節點，但是他的形態并不符合紅黑樹的節點，所以我們需要將它轉換為已個合法的形態，先進行旋轉，1節點左旋，這個時候結構對了，但是顏色不對，需要將2變色為黑色，而1變色為紅色，這樣我們的這個紅黑樹就完全符合定義了。

 

這就是一個最簡單的旋轉變色的紅黑樹自動平衡過程。

下面是左旋和右旋的JAVA代碼實現，并沒有添加變色，因為變色的邏輯并不是固定的故而我們將其解耦到其他方法中

//左旋
    Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        if(h.right!=null){
            h.right.parent = h;
        }
        x.parent = h.parent;
        h.parent = x;
        x.left = h;
        if(x.left!=null){
            x.left.parent = x;
        }
        if(x.parent!=null){
            int cmp = x.parent.key.compareTo(x.key);
            if(cmp>0) x.parent.left = x;
            else x.parent.right = x;
        }
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        show();
        return x;
    }

    //右旋
    Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        if(h.left!=null){
            h.left.parent = h;
        }
        x.parent = h.parent;
        h.parent = x;
        x.right = h;
        if(x.right!=null){
            x.right.parent = x;
        }
        if(x.parent!=null){
            int cmp = x.parent.key.compareTo(x.key);
            if(cmp>0) x.parent.left = x;
            else x.parent.right = x;
        }
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        show();
        return x;
    }

2.4 紅黑樹的添加

紅黑樹的添加分為以下幾種情況

2.4.1 在黑色節點下面插入

這種情況無論是插入在左還是右，都可以直接插入，紅黑樹的正確性不會受到影響

2.4.2 在紅色節點下插入且被插入節點無兄弟節點

2.4.2.1 當被插入的節點是右子節點

 

在右側插入

 

操作步驟：

1.節點1左旋


2. 變色，1變色為紅色， 2變色為黑色

在左側插入

 

這種情況會比上面那種多一個步驟

1.節點3右旋，無需變色，這個操作主要是為了將情況轉換為上面在右側插入的情況，然后下面按照在右側的情況處理即可

2.節點1左旋

3.變色，1變色為紅色，2變色為黑色

2.4.2.2 當被插入節點是左子節點

其實這種情況和上面的處理邏輯是一樣的，只不過左右是反過來的，就不再贅述了，大家自己舉一反三即可。

2.4.3 在紅色節點下插入且被插入節點有兄弟節點

這種時候，我們需要先進行變色，再插入，如下圖（這里，我們默認，1節點是有父節點的，1節點非根節點）

 

2和3節點變黑色，1節點變紅色，這個變化其實對應著2-3-4樹的4節點插入，其實就是將一個4節點拆分開來，中間的節點向上和父節點組合，左右兩邊的節點分裂為兩個單獨的節點，然后再正常插入一個新的節點。紅黑樹也是這么個道理。

2、3節點變黑，形成單獨的節點，而1節點則變紅和父節點結合，那么這里我們要注意的是，1節點和父節點結合的時候，也相當于一次新的插入，相當于在1的父節點新插入一個紅色，所以這個過程是遞歸的，一直向上傳遞，直到紅黑樹的結構符合定義為止。

 

到這里，紅黑樹的插入操作就結束了，以上的操作，只是單純的一步操作，這些操作只是在插入之后對被插入節點紅黑樹的一個平衡，我們在進行旋轉變色之后，很有可能上層的節點就又不符合定義了，這個時候我們就需要進行遞歸的旋轉變色， 直到最后整個紅黑樹平衡。

下面扔代碼

        if (cmp < 0) h.left = put(h.left, h, key, val);
        else if (cmp > 0) h.right = put(h.right, h, key, val);
        else h.value = val;

        //判斷紅黑，進行旋轉，調整樹的平衡
        if (isRed(h.right) && isRed(h.right.right)) {
            h.right.color = h.color;
            h.color = Red;
            h = rotateLeft(h);
        }
        if (isRed(h.right) && isRed(h.right.left)) {
            //RL問題，先右旋,將問題轉換為RR
            h.right = rotateRight(h.right);
            //變色
            h.right.color = h.color;
            h.color = Red;
            //再左旋
            h = rotateLeft(h);
        }
        if (isRed(h.left) && isRed(h.left.left)) {
            h.left.color = h.color;
            h.color = Red;
            h = rotateRight(h);
        }
        if (isRed(h.left) && isRed(h.left.right)) {
            //LR問題，先左旋，將問題轉換為LL問題
            h.left = rotateLeft(h.left);
            //變色
            h.left.color = h.color;
            h.color = Red;
            //再右旋
            h = rotateRight(h);
        }

        h.N = size(h.left) + size(h.right) + 1;

        return h;
    }

歡迎點贊關注+轉發！