數(shù)據(jù)結(jié)構(gòu)之紅黑樹(shù)

2-3樹(shù)

在了解紅黑樹(shù)之前，我們先來(lái)認(rèn)識(shí)2-3樹(shù)，在算法（第4版）里也是先從2-3樹(shù)切入到紅黑樹(shù)的。并且了解2-3樹(shù)對(duì)于理解B類(lèi)樹(shù)也會(huì)有幫助，因?yàn)?-3樹(shù)可以說(shuō)就是基礎(chǔ)的B類(lèi)樹(shù)。

2-3樹(shù)的特性：

  • 滿(mǎn)足二分搜索樹(shù)的基本性質(zhì)
  • 節(jié)點(diǎn)可以存放一個(gè)元素或者兩個(gè)元素，或者說(shuō)數(shù)據(jù)項(xiàng)
  • 每個(gè)節(jié)點(diǎn)有2個(gè)或者3個(gè)子節(jié)點(diǎn)，這也是2-3樹(shù)的名稱(chēng)由來(lái)
  • 2-3樹(shù)是一棵絕對(duì)平衡的樹(shù)，對(duì)于任意節(jié)點(diǎn)的左右子樹(shù)的高度一定是相等的

2-3樹(shù)為了維持絕對(duì)平衡，需要滿(mǎn)足以下條件：

  1. 2節(jié)點(diǎn)有且只能有兩個(gè)子節(jié)點(diǎn)，并只能包含一個(gè)數(shù)據(jù)項(xiàng)
  2. 3節(jié)點(diǎn)有且只能有三個(gè)子節(jié)點(diǎn)，并只能包含兩個(gè)數(shù)據(jù)項(xiàng)，大小關(guān)系從左至右依次遞增
  3. 添加數(shù)據(jù)項(xiàng)時(shí)不能將該數(shù)據(jù)項(xiàng)添加到一個(gè)空節(jié)點(diǎn)上，因?yàn)樾碌墓?jié)點(diǎn)只能通過(guò)分裂或者融合產(chǎn)生
  4. 當(dāng)2-3樹(shù)只有2節(jié)點(diǎn)的時(shí)候，其只能是一棵滿(mǎn)二叉樹(shù)

2-3樹(shù)的兩類(lèi)節(jié)點(diǎn)：


image.png
  • 可以看到，2節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，5和15，且自身只包含一個(gè)數(shù)據(jù)項(xiàng)，即10。3節(jié)點(diǎn)則有三個(gè)子節(jié)點(diǎn)，自身只能包含兩個(gè)數(shù)據(jù)項(xiàng)，從左至右依次遞增：5 < 6 < 7 < 8 < 9

下圖是一顆完整的2-3樹(shù)：


image.png

從上圖中可以看到2-3樹(shù)是滿(mǎn)足二分搜索樹(shù)的基本性質(zhì)的，只有兩個(gè)節(jié)點(diǎn)的情況，如 42 這個(gè)節(jié)點(diǎn)，右子節(jié)點(diǎn)小于父節(jié)點(diǎn)，左子節(jié)點(diǎn)大于父節(jié)點(diǎn)。而有三個(gè)節(jié)點(diǎn)時(shí)，右子節(jié)點(diǎn)仍然小于父節(jié)點(diǎn)，中間的子節(jié)點(diǎn)大于父節(jié)點(diǎn)的左數(shù)據(jù)項(xiàng)，小于父節(jié)點(diǎn)的右數(shù)據(jù)項(xiàng)（如圖中18大于17，小于33），左子節(jié)點(diǎn)則大于父節(jié)點(diǎn)。

2-3樹(shù)的絕對(duì)平衡性

之前我們提到了2-3樹(shù)插入節(jié)點(diǎn)時(shí)不能將該節(jié)點(diǎn)插入到一個(gè)空節(jié)點(diǎn)上，新的節(jié)點(diǎn)只能通過(guò)分裂或者融合產(chǎn)生。我們知道對(duì)二分搜索樹(shù)依次添加有序的數(shù)據(jù)時(shí)，如依次添加 1、2、3、4、5，會(huì)產(chǎn)生連續(xù)的節(jié)點(diǎn)，使得二分搜索樹(shù)退化成鏈表。

為了避免退化成鏈表，具有平衡特性的樹(shù)狀結(jié)構(gòu)，會(huì)采取一些手段來(lái)維持樹(shù)的平衡，例如AVL是通過(guò)旋轉(zhuǎn)節(jié)點(diǎn)，而2-3樹(shù)則是通過(guò)分裂和融合。當(dāng)我們依次添加 1、2、3、4、5 到2-3樹(shù)時(shí)，其流程如下：


image.png

  1. 添加元素1，創(chuàng)建一個(gè)2節(jié)點(diǎn)類(lèi)型的根節(jié)點(diǎn)

  2. 添加元素2，此時(shí)元素1和2存在同一個(gè)節(jié)點(diǎn)中，成為一個(gè)3節(jié)點(diǎn)。為什么添加元素2時(shí)，不能生成一個(gè)新的節(jié)點(diǎn)作為元素1所在節(jié)點(diǎn)的右子節(jié)點(diǎn)呢？因?yàn)椤疤砑訑?shù)據(jù)項(xiàng)時(shí)不能將該數(shù)據(jù)項(xiàng)添加到一個(gè)空節(jié)點(diǎn)上，新的節(jié)點(diǎn)只能通過(guò)分裂或者融合產(chǎn)生”

  3. 添加元素3，元素1、2、3，暫時(shí)存在同一個(gè)節(jié)點(diǎn)中，形成一個(gè)4節(jié)點(diǎn)

  4. 分裂，2-3樹(shù)中最多只有3節(jié)點(diǎn)，不能存在4節(jié)點(diǎn)，所以暫時(shí)形成的4節(jié)點(diǎn)要進(jìn)行分裂，將中間的元素作為根節(jié)點(diǎn)，左右兩個(gè)元素各為其左右子節(jié)點(diǎn)。這時(shí)可見(jiàn)形成了一棵滿(mǎn)二叉樹(shù)

  5. 添加元素4，根據(jù)元素的大小關(guān)系，將會(huì)存放到元素3所在的節(jié)點(diǎn)。因?yàn)樾绿砑拥脑夭荒芴砑拥揭粋€(gè)空節(jié)點(diǎn)上，所以元素4將根據(jù)搜索樹(shù)的性質(zhì)找到最后一個(gè)節(jié)點(diǎn)與其融合。即元素3和4將融合為一個(gè)三節(jié)點(diǎn)。并且根據(jù)大小關(guān)系元素4要位于元素3的右側(cè)

  6. 添加元素5，同插入元素4，元素5一路查找到元素3、4所在的三節(jié)點(diǎn)，與其融合，暫時(shí)形成一個(gè)4節(jié)點(diǎn)

  7. 分裂，元素3、4、5所在的4節(jié)點(diǎn)同上面元素1、2、3形成的4節(jié)點(diǎn)一樣，進(jìn)行分裂操作。根據(jù)大小關(guān)系，4元素將會(huì)作為根節(jié)點(diǎn)，元素3、5則各為其左右子節(jié)點(diǎn)

  8. 融合，前面的分裂操作已經(jīng)導(dǎo)致該2-3樹(shù)不滿(mǎn)足其第四條性質(zhì)“當(dāng)2-3樹(shù)只有2節(jié)點(diǎn)的時(shí)候，其只能是一棵滿(mǎn)二叉樹(shù)”，所以該2-3樹(shù)將要向上融合以滿(mǎn)足2-3樹(shù)的性質(zhì)。我們只需要將元素4所在節(jié)點(diǎn)與其父節(jié)點(diǎn)即元素2所在的節(jié)點(diǎn)進(jìn)行融合即可。這時(shí)，元素2、4就形成了一個(gè)3節(jié)點(diǎn)

如果我們繼續(xù)往2-3樹(shù)中添加元素6和7，那么最終形成的2-3樹(shù)如下圖所示：


image.png

如果在這個(gè)案例中我們使用的是二分搜索樹(shù)，那么該二分搜索樹(shù)將會(huì)退化為一個(gè)鏈表，而2-3樹(shù)則通過(guò)分裂、融合的方式成為了一顆滿(mǎn)二叉樹(shù)。

紅黑樹(shù)與2-3樹(shù)的等價(jià)性

了解了2-3樹(shù)后，我們來(lái)看下紅黑樹(shù)與2-3樹(shù)的等價(jià)性，嚴(yán)格來(lái)說(shuō)是左傾紅黑樹(shù)才是與2-3樹(shù)是等價(jià)的。與2-3樹(shù)一樣，紅黑樹(shù)具有二分搜索樹(shù)的性質(zhì)，并且也是自平衡的，但不是絕對(duì)平衡，甚至平衡性比AVL樹(shù)還要差一些。

之前提到了2-3樹(shù)是絕對(duì)平衡的，對(duì)于任意節(jié)點(diǎn)的左右子樹(shù)的高度一定是相等的。而AVL樹(shù)則是任意節(jié)點(diǎn)的左右子樹(shù)高度相差不超過(guò) 1 即可，屬于高度平衡的二分搜索樹(shù)。

紅黑樹(shù)則是從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長(zhǎng)路徑不超過(guò)最短路徑的2倍，其高度僅僅只會(huì)比AVL樹(shù)高度大一倍，所以在性能上，下降得并不多。由于紅黑樹(shù)也是自平衡的樹(shù)，也會(huì)采取一些機(jī)制來(lái)維持樹(shù)的平衡。

紅黑樹(shù)的定義：

  1. 每個(gè)節(jié)點(diǎn)或者是紅色的，或者是黑色的
  2. 根節(jié)點(diǎn)是黑色的
  3. 每一個(gè)葉子節(jié)點(diǎn)（最后的空節(jié)點(diǎn)）是黑色的
  4. 如果一個(gè)節(jié)點(diǎn)是紅色的，那么它的左右子節(jié)點(diǎn)都是黑色的
  5. 從任意一個(gè)節(jié)點(diǎn)到葉子節(jié)點(diǎn)，經(jīng)過(guò)的黑色節(jié)點(diǎn)是一樣的

這里的第三點(diǎn)要求“每一個(gè)葉子節(jié)點(diǎn)（最后的空節(jié)點(diǎn)）是黑色的”，稍微有些奇怪，它主要是為了簡(jiǎn)化紅黑樹(shù)的代碼實(shí)現(xiàn)而設(shè)置的。我們也可以理解為，只要是空的節(jié)點(diǎn)，它就是黑色的。

下圖是一顆典型的紅黑樹(shù)：


image.png

在了解了2-3樹(shù)之后，我們知道2-3樹(shù)是通過(guò)分裂和融合來(lái)產(chǎn)生新的節(jié)點(diǎn)并維持平衡的。2-3樹(shù)有兩類(lèi)節(jié)點(diǎn)，2節(jié)點(diǎn)和3節(jié)點(diǎn)。除此之外，還會(huì)有一種臨時(shí)的4節(jié)點(diǎn)。接下來(lái)我們看看2-3樹(shù)向紅黑樹(shù)轉(zhuǎn)換的過(guò)程，下圖展示了2-3樹(shù)的這三種節(jié)點(diǎn)對(duì)應(yīng)于紅黑樹(shù)的節(jié)點(diǎn)：


image.png
  • 2節(jié)點(diǎn)：對(duì)應(yīng)于紅黑樹(shù)的黑色節(jié)點(diǎn)
  • 3節(jié)點(diǎn)：對(duì)應(yīng)于紅黑樹(shù)中黑色的父節(jié)點(diǎn)和紅色的左子節(jié)點(diǎn)
  • 臨時(shí)的4節(jié)點(diǎn)：對(duì)應(yīng)于紅色的父節(jié)點(diǎn)和黑色的左右子節(jié)點(diǎn)。這里需要說(shuō)一下，為什么是紅色的父節(jié)點(diǎn)而不是黑色的呢？主要是因?yàn)?-3樹(shù)的3節(jié)點(diǎn)需要將分裂后的父節(jié)點(diǎn)進(jìn)行向上融合，紅色的符合我們向紅黑樹(shù)中插入任何一個(gè)節(jié)點(diǎn)默認(rèn)都是紅色的實(shí)現(xiàn)方式。如果該父節(jié)點(diǎn)是紅黑樹(shù)的根節(jié)點(diǎn)的話(huà)，那它肯定需要變色，這一點(diǎn)就不屬于2-3樹(shù)向紅黑樹(shù)的變換規(guī)則了，而屬于紅黑樹(shù)的性質(zhì)。

根據(jù)這個(gè)對(duì)應(yīng)關(guān)系，我們將這樣一顆2-3樹(shù)：


image.png

轉(zhuǎn)換成紅黑樹(shù)，就是這樣子的，可以看到其中的紅色節(jié)點(diǎn)都對(duì)應(yīng)著2-3樹(shù)的3節(jié)點(diǎn)：


image.png

如果這樣看著不太好對(duì)應(yīng)的話(huà)，我們也可以將其繪制成這個(gè)樣子，就更容易理解紅黑樹(shù)與2-3樹(shù)是等價(jià)的了：


image.png

從2-3樹(shù)過(guò)渡到紅黑樹(shù)后，接下來(lái)，我們就著手實(shí)現(xiàn)一個(gè)紅黑樹(shù)。首先，編寫(xiě)紅黑樹(shù)的基礎(chǔ)結(jié)構(gòu)代碼，如節(jié)點(diǎn)定義等。具體代碼如下所示：

package tree;

/**
 * 紅黑樹(shù)
 *
 * @author 01
 * @date 2021-01-22
 **/
public class RBTree<K extends Comparable<K>, V> {

    /**
     * 因?yàn)橹挥屑t色和黑色，這里用兩個(gè)常量來(lái)表示
     */
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    /**
     * 定義紅黑樹(shù)的節(jié)點(diǎn)結(jié)構(gòu)
     */
    private class Node {
        public K key;
        public V value;
        public Node left, right;
        // 表示節(jié)點(diǎn)是紅色還是黑色
        public boolean color;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            left = null;
            right = null;
            // 默認(rèn)新節(jié)點(diǎn)都是紅色
            color = RED;
        }
    }

    /**
     * 根節(jié)點(diǎn)
     */
    private Node root;

    /**
     * 紅黑樹(shù)中的元素個(gè)數(shù)
     */
    private int size;

    public RBTree() {
        root = null;
        size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 判斷節(jié)點(diǎn)node的顏色
     */
    private boolean isRed(Node node) {
        if (node == null) {
            // 空節(jié)點(diǎn)我們都認(rèn)為是黑色的葉子節(jié)點(diǎn)
            return BLACK;
        }

        return node.color;
    }
 }

保持根節(jié)點(diǎn)為黑色和左旋轉(zhuǎn)

前面介紹了紅黑樹(shù)的五個(gè)定義，這些定義使得紅黑樹(shù)能夠維持自平衡。我們都清楚，當(dāng)對(duì)一顆樹(shù)添加或刪除節(jié)點(diǎn)時(shí)，就有可能會(huì)破壞這棵樹(shù)的平衡。紅黑樹(shù)也不例外，所以這個(gè)時(shí)候就需要作出一些調(diào)整，來(lái)讓紅黑樹(shù)繼續(xù)滿(mǎn)足這五個(gè)定義。調(diào)整的方法有兩種，變色和旋轉(zhuǎn)，其中旋轉(zhuǎn)又分為左旋轉(zhuǎn)和右旋轉(zhuǎn)。

變色：

  • 為了重新符合紅黑樹(shù)的規(guī)則，嘗試把紅色節(jié)點(diǎn)變?yōu)楹谏蛘甙押谏?jié)點(diǎn)變?yōu)榧t色

從上面我們編寫(xiě)的紅黑樹(shù)的基礎(chǔ)結(jié)構(gòu)代碼可以看到，在添加一個(gè)節(jié)點(diǎn)時(shí)，默認(rèn)是紅色。如果新添加的這個(gè)紅色節(jié)點(diǎn)不能滿(mǎn)足紅黑樹(shù)的定義，那么我們就需要對(duì)其進(jìn)行變色。例如，當(dāng)添加的節(jié)點(diǎn)是一個(gè)根節(jié)點(diǎn)時(shí)，為了保持根節(jié)點(diǎn)為黑色，就需要將其顏色變?yōu)楹谏?/p>

image.png

左旋轉(zhuǎn)：

  • 逆時(shí)針旋轉(zhuǎn)紅黑樹(shù)的兩個(gè)節(jié)點(diǎn)，使得父節(jié)點(diǎn)被自己的右子節(jié)點(diǎn)取代，而自己成為自己的左子節(jié)點(diǎn)
image.png

在上圖中，身為右子節(jié)點(diǎn)的Y取代了X的位置，而X變成了自己的左子節(jié)點(diǎn)，因此為左旋轉(zhuǎn)。例如，我們往根節(jié)點(diǎn) 1 添加一個(gè)元素 2，其左旋轉(zhuǎn)過(guò)程如下：


image.png
  • Tips：本文中設(shè)定紅黑樹(shù)是左傾的

左旋轉(zhuǎn)的具體實(shí)現(xiàn)代碼如下：

//   node                     x
//  /   \     左旋轉(zhuǎn)         /  \
// T1   x   --------->   node   T3
//     / \              /   \
//    T2 T3            T1   T2
private Node leftRotate(Node node) {
    Node x = node.right;
    // 左旋轉(zhuǎn)
    node.right = x.left;
    x.left = node;

    x.color = node.color;
    node.color = RED;

    return x;
}

假設(shè)我們要對(duì) 37 這個(gè) node 進(jìn)行左旋轉(zhuǎn)，其右子節(jié)點(diǎn) X 為 42，根據(jù)上面的代碼，其左旋轉(zhuǎn)的具體過(guò)程如下：


image.png

顏色翻轉(zhuǎn)和右旋轉(zhuǎn)

在上一小節(jié)中，我們了解了變色和左旋轉(zhuǎn)?；谥暗睦?，當(dāng)我們?cè)偬砑右粋€(gè)節(jié)點(diǎn) 66 時(shí)，該節(jié)點(diǎn)會(huì)被添加到右邊成為右子節(jié)點(diǎn)，此時(shí)只需要做一下顏色的翻轉(zhuǎn)即可，如下所示：


image.png

對(duì)應(yīng)的代碼如下：

/**
 * 顏色翻轉(zhuǎn)
 */
private void flipColors(Node node) {
    node.color = RED;
    node.left.color = BLACK;
    node.right.color = BLACK;
}

我們?cè)倏戳硪环N添加節(jié)點(diǎn)的情況，就是添加的節(jié)點(diǎn)比左子節(jié)點(diǎn)還要小，此時(shí)該節(jié)點(diǎn)就會(huì)掛到左子節(jié)點(diǎn)下：


image.png

對(duì)于這種情況，我們就要進(jìn)行右旋轉(zhuǎn)：

  • 順時(shí)針旋轉(zhuǎn)紅黑樹(shù)的兩個(gè)節(jié)點(diǎn)，使得父節(jié)點(diǎn)被自己的左子節(jié)點(diǎn)取代，而自己成為自己的右子節(jié)點(diǎn)
image.png

在上圖中，身為左子節(jié)點(diǎn)的Y取代了X的位置，而X變成了自己的右子節(jié)點(diǎn)，因此為右旋轉(zhuǎn)。

對(duì)于上面那種情況，右旋轉(zhuǎn)的流程如下：


image.png

還有一種情況就是添加的元素比 node 和 X 都要大，此時(shí)就會(huì)掛載到 X 的右邊，此時(shí)就需要多做一步左旋轉(zhuǎn)操作。如下所示：


image.png

右旋轉(zhuǎn)的實(shí)現(xiàn)代碼如下：

//     node                   x
//    /   \     右旋轉(zhuǎn)       /  \
//   x    T2   ------->   y   node
//  / \                       /  \
// y  T1                     T1  T2
private Node rightRotate(Node node) {
    Node x = node.left;
    // 右旋轉(zhuǎn)
    node.left = x.right;
    x.right = node;

    x.color = node.color;
    node.color = RED;

    return x;
}

紅黑樹(shù)中添加新元素

經(jīng)過(guò)以上小節(jié)，現(xiàn)在我們已經(jīng)知道了紅黑樹(shù)維持平衡所需的變色和旋轉(zhuǎn)操作，以及相應(yīng)的實(shí)現(xiàn)代碼。這些都屬于添加、刪除節(jié)點(diǎn)時(shí)用于維持平衡的子流程，所以接下來(lái)，就讓我們實(shí)現(xiàn)一下往紅黑樹(shù)中添加新元素的代碼。如下：

/**
 * 向紅黑樹(shù)中添加新的元素(key, value)
 */
public void add(K key, V value) {
    root = add(root, key, value);
    // 保證根節(jié)點(diǎn)始終為黑色節(jié)點(diǎn)
    root.color = BLACK;
}

/**
 * 向以node為根的紅黑樹(shù)中插入元素(key, value)，遞歸算法
 * 返回插入新節(jié)點(diǎn)后紅黑樹(shù)的根
 */
private Node add(Node node, K key, V value) {
    if (node == null) {
        size++;
        // 默認(rèn)插入紅色節(jié)點(diǎn)
        return new Node(key, value);
    }

    if (key.compareTo(node.key) < 0) {
        node.left = add(node.left, key, value);
    } else if (key.compareTo(node.key) > 0) {
        node.right = add(node.right, key, value);
    } else {
        node.value = value;
    }

    // 是否需要左旋轉(zhuǎn)
    if (isRed(node.right) && !isRed(node.left)) {
        node = leftRotate(node);
    }

    // 是否需要右旋轉(zhuǎn)
    if (isRed(node.left) && isRed(node.left.left)) {
        node = rightRotate(node);
    }

    // 是否需要翻轉(zhuǎn)下顏色
    if (isRed(node.left) && isRed(node.right)) {
        flipColors(node);
    }

    return node;
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容