紅黑樹的介紹

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

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

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

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

紅黑樹的特性:

(1) 每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色。

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

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

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

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

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

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

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

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

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

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

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

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

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

1.節(jié)點(diǎn)

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

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


        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.查找

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

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

//查找獲取指定的值
    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.平衡化

在介紹插入之前，我們先介紹如何讓紅黑樹保持平衡，因?yàn)橐话愕?，我們插入完成之后，需要?duì)樹進(jìn)行平衡化操作以使其滿足平衡化。

旋轉(zhuǎn)

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

左旋操作如下圖：

  //左旋轉(zhuǎn)
    private Node rotateLeft(Node h) {
        Node x = h.right;
        //將x的左節(jié)點(diǎn)復(fù)制給h右節(jié)點(diǎn)
        h.right = x.left;
        //將h復(fù)制給x右節(jié)點(diǎn)
        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;
    }

左旋的動(dòng)畫效果如下：

右旋是左旋的逆操作，過(guò)程如下：

代碼如下：

  //右旋轉(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;
    }

右旋的動(dòng)畫效果如下：

顏色反轉(zhuǎn)

當(dāng)出現(xiàn)一個(gè)臨時(shí)的4-node的時(shí)候，即一個(gè)節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)均為紅色，如下圖：

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

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

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

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

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

這種情況很簡(jiǎn)單，只需要：

1.標(biāo)準(zhǔn)的二叉查找樹遍歷即可。新插入的節(jié)點(diǎn)標(biāo)記為紅色

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

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

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

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

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

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

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

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

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

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

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

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

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

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

插入的實(shí)現(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;
    }

紅黑樹的復(fù)雜度–

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

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

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

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

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

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

下圖是紅黑樹各種操作的時(shí)間復(fù)雜度。

總結(jié)

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

最新評(píng)論