紅黑樹的介紹

紅黑樹(Red-Black Tree，簡稱R-B Tree)，它一種特殊的二叉查找樹。

紅黑樹是特殊的二叉查找樹，意味著它滿足二叉查找樹的特征：任意一個節(jié)點所包含的鍵值，大于等于左孩子的鍵值，小于等于右孩子的鍵值。

除了具備該特性之外，紅黑樹還包括許多額外的信息。

紅黑樹的每個節(jié)點上都有存儲位表示節(jié)點的顏色，顏色是紅(Red)或黑(Black)。

紅黑樹的特性:

(1) 每個節(jié)點或者是黑色，或者是紅色。

(2) 根節(jié)點是黑色。

(3) 每個葉子節(jié)點是黑色。 [注意：這里葉子節(jié)點，是指為空的葉子節(jié)點！]

(4) 如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的。

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

關(guān)于它的特性，需要注意的是：

第一，特性(3)中的葉子節(jié)點，是只為空(NIL或null)的節(jié)點。

第二，特性(5)，確保沒有一條路徑會比其他路徑長出倆倍。因而，紅黑樹是相對是接近平衡的二叉樹。

紅黑樹的主要是想對2-3查找樹進行編碼，尤其是對2-3查找樹中的3-nodes節(jié)點添加額外的信息。紅黑樹中將節(jié)點之間的鏈接分為兩種不同類型，紅色鏈接，他用來鏈接兩個2-nodes節(jié)點來表示一個3-nodes節(jié)點。黑色鏈接用來鏈接普通的2-3節(jié)點。特別的，使用紅色鏈接的兩個2-nodes來表示一個3-nodes節(jié)點，并且向左傾斜，即一個2-node是另一個2-node的左子節(jié)點。這種做法的好處是查找的時候不用做任何修改，和普通的二叉查找樹相同。

根據(jù)以上描述，紅黑樹定義如下：

紅黑樹是一種具有紅色和黑色鏈接的平衡查找樹，同時滿足：

1.紅色節(jié)點向左傾斜
2.一個節(jié)點不可能有兩個紅色鏈接
3.整個樹完全黑色平衡，即從根節(jié)點到所以葉子結(jié)點的路徑上，黑色鏈接的個數(shù)都相同。

下圖可以看到紅黑樹其實是2-3樹的另外一種表現(xiàn)形式：如果我們將紅色的連線水平繪制，那么他鏈接的兩個2-node節(jié)點就是2-3樹中的一個3-node節(jié)點了。

紅黑樹的實現(xiàn)

1.節(jié)點

我們可以在二叉查找樹的每一個節(jié)點上增加一個新的表示顏色的標記。該標記指示該節(jié)點指向其父節(jié)點的顏色。

private class Node {
        Node left, right;//左右子樹
        TKey key;//鍵
        TValue value;//相關(guān)聯(lián)的值
        int n;//這顆子樹中的節(jié)點總數(shù)
        boolean color;//由父節(jié)點指向它的連接的顏色


        public Node(TKey key, TValue value, int number, boolean color) {
            this.key = key;
            this.value = value;
            this.n = number;
            this.color = color;
        }
    }

    private boolean isRed(Node node) {
        if (node == null) return false;
        return node.color == RED;
    }

2.查找

紅黑樹是一種特殊的二叉查找樹，他的查找方法也和二叉查找樹一樣，不需要做太多更改。

但是由于紅黑樹比一般的二叉查找樹具有更好的平衡，所以查找起來更快。

//查找獲取指定的值
    public TValue get(TKey key) {
        return getValue(root, key);
    }

    private TValue getValue(Node node, TKey key) {
        if (node == null) return null;
        int cmp = key.compareTo(node.Key);
        if (cmp == 0) {
            return node.value;
        } else if (cmp > 0) {
            return getValue(node.right, key);
        } else {
            return getValue(node.left, key);
        }
    }

3.平衡化

在介紹插入之前，我們先介紹如何讓紅黑樹保持平衡，因為一般的，我們插入完成之后，需要對樹進行平衡化操作以使其滿足平衡化。

旋轉(zhuǎn)

旋轉(zhuǎn)又分為左旋和右旋。通常左旋操作用于將一個向右傾斜的紅色鏈接旋轉(zhuǎn)為向左鏈接。對比操作前后，可以看出，該操作實際上是將紅線鏈接的兩個節(jié)點中的一個較大的節(jié)點移動到根節(jié)點上。

左旋操作如下圖：

  //左旋轉(zhuǎn)
    private Node rotateLeft(Node h) {
        Node x = h.right;
        //將x的左節(jié)點復制給h右節(jié)點
        h.right = x.left;
        //將h復制給x右節(jié)點
        x.left = h;
        x.color = h.color;
        h.color = RED;
        x.n = h.n;
        h.n = 1 + size(h.left) + size(h.right);
        return x;
    }

左旋的動畫效果如下：

右旋是左旋的逆操作，過程如下：

代碼如下：

  //右旋轉(zhuǎn)
    private Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;

        x.color = h.color;
        h.color = RED;
        x.n = h.n;
        h.n = 1 + size(h.left) + size(h.right);
        return x;
    }

右旋的動畫效果如下：

顏色反轉(zhuǎn)

當出現(xiàn)一個臨時的4-node的時候，即一個節(jié)點的兩個子節(jié)點均為紅色，如下圖：

這其實是個A，E，S 4-node連接，我們需要將E提升至父節(jié)點，操作方法很簡單，就是把E對子節(jié)點的連線設(shè)置為黑色，自己的顏色設(shè)置為紅色。

有了以上基本操作方法之后，我們現(xiàn)在對應之前對2-3樹的平衡操作來對紅黑樹進行平衡操作，這兩者是可以一一對應的，如下圖：

現(xiàn)在來討論各種情況：

Case 1 往一個2-node節(jié)點底部插入新的節(jié)點

先熱身一下，首先我們看對于只有一個節(jié)點的紅黑樹，插入一個新的節(jié)點的操作：

這種情況很簡單，只需要：

1.標準的二叉查找樹遍歷即可。新插入的節(jié)點標記為紅色

2.如果新插入的節(jié)點在父節(jié)點的右子節(jié)點，則需要進行左旋操作

Case 2往一個3-node節(jié)點底部插入新的節(jié)點

假設(shè)我們往一個只有兩個節(jié)點的樹中插入元素，如下圖，根據(jù)待插入元素與已有元素的大小，又可以分為如下三種情況：

1.如果帶插入的節(jié)點比現(xiàn)有的兩個節(jié)點都大，這種情況最簡單。我們只需要將新插入的節(jié)點連接到右邊子樹上即可，然后將中間的元素提升至根節(jié)點。這樣根節(jié)點的左右子樹都是紅色的節(jié)點了，我們只需要調(diào)研FlipColor方法即可。其他情況經(jīng)過反轉(zhuǎn)操作后都會和這一樣。

2.如果插入的節(jié)點比最小的元素要小，那么將新節(jié)點添加到最左側(cè)，這樣就有兩個連接紅色的節(jié)點了，這是對中間節(jié)點進行右旋操作，使中間結(jié)點成為根節(jié)點。這是就轉(zhuǎn)換到了第一種情況，這時候只需要再進行一次FlipColor操作即可。

3.如果插入的節(jié)點的值位于兩個節(jié)點之間，那么將新節(jié)點插入到左側(cè)節(jié)點的右子節(jié)點。因為該節(jié)點的右子節(jié)點是紅色的，所以需要進行左旋操作。操作完之后就變成第二種情況了，再進行一次右旋，然后再調(diào)用FlipColor操作即可完成平衡操作。

有了以上基礎(chǔ)，我們現(xiàn)在來總結(jié)一下往一個3-node節(jié)點底部插入新的節(jié)點的操作步驟，下面是一個典型的操作過程圖：

可以看出，操作步驟如下：

1.執(zhí)行標準的二叉查找樹插入操作，新插入的節(jié)點元素用紅色標識。

2.如果需要對4-node節(jié)點進行旋轉(zhuǎn)操作

3.如果需要，調(diào)用FlipColor方法將紅色節(jié)點提升

4.如果需要，左旋操作使紅色節(jié)點左傾。

5.在有些情況下，需要遞歸調(diào)用Case1 Case2，來進行遞歸操作。如下：

void flipColors(Node h) {
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }

插入的實現(xiàn)

  private Node put(Node h, TKey key, TValue value) {
        if (h == null) {
            return new Node(key, value, 1, RED);
        }
        int cmp = key.compareTo(h.key);
        if (cmp < 0) {
            h.left = put(h.left, key, value);
        } else if (cmp > 0) {
            h.right = put(h.right, key, value);
        } else {
            h.value = value;
        }
        if (isRed(h.right) && !isRed(h.left)) {
            h = rotateLeft(h);
        }
        if (isRed(h.left) && isRed(h.left.left)) {
            h = rotateRight(h);
        }
        if (isRed(h.left) && isRed(h.right)) {
            flipColors(h);
        }
        h.n = size(h.left) + size(h.right) + 1;
        return h;
    }

紅黑樹的復雜度–

對紅黑樹的分析其實就是對2-3查找樹的分析，紅黑樹能夠保證符號表的所有操作即使在最壞的情況下都能保證對數(shù)的時間復雜度，也就是樹的高度。

1. 在最壞的情況下，紅黑樹的高度不超過2lgN

最壞的情況就是，紅黑樹中除了最左側(cè)路徑全部是由3-node節(jié)點組成，即紅黑相間的路徑長度是全黑路徑長度的2倍。

下圖是一個典型的紅黑樹，從中可以看到最長的路徑(紅黑相間的路徑)是最短路徑的2倍：

2. 紅黑樹的平均高度大約為lgN

下圖是紅黑樹在各種情況下的時間復雜度，可以看出紅黑樹是2-3查找樹的一種實現(xiàn)，他能保證最壞情況下仍然具有對數(shù)的時間復雜度。

下圖是紅黑樹各種操作的時間復雜度。

總結(jié)

本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！

最新評論