1.4.3 Red-Black Tree

樹的平衡: 所謂樹的平衡指的是, 樹中每個節點的左邊後代的數目應該與其右邊後代的數目大致相等(不用完全一樣多).

對於用隨機數構成的二元樹, 一般來說是大致平衡的, 但是對於有順序的資料, 就可能導致二元樹極度的不平衡了. 在最極端的情況下, 甚至會退化成list, 此時的時間複雜度會退化到O(n), 而不再是平衡樹的O(logn)了.

紅黑樹(R-B Tree): 紅黑樹是增加了某些特性的二元搜尋樹, 它可以保持樹的大致平衡. 主要的思路為: 在插入或刪除節點的時候, 檢查是否破壞了樹的某些特徵, 若破壞了, 則進行糾正, 進而保持樹的平衡.

在JDK中, 以紅黑樹為實作基礎的資料結構如: TreeSet, TreeMap以及最新的HashTable

紅黑樹的特徵:

1. 節點都有顏色(紅/黑)

2. 在插入和刪除的過程中, 要遵循保持這些顏色的不同排列的規則

紅黑樹的規則(紅黑規則):

1. 每個節點不是紅就是黑的(廢話)

2. 根總是黑色的

3. 若節點是紅色的, 則其子節點必為黑色, 反之不必為真(亦即若節點是黑色, 則其子節點可為紅也可為黑), 這條規則其實也是在說明就垂直方向來看, 紅色節點不可以相連

4. 每個空子節點都是黑色的: 所謂的空子節點指的是, 對非葉節點而言, 本可能有, 但實際沒有的那個子節點. 譬如一個節點只有右子節點, 那麼其空缺的左子節點就是空子節點

5. 從根節點到葉節點或空子節點的每條路徑(簡單路徑), 必須包含相同數目的黑色節點(這些黑色節點的數目也稱為黑色高度)

一個滿足紅黑樹規則的二元搜尋樹大概長得像這樣:

紅黑樹的修正手段:

1. 改變節點顏色

2. 執行旋轉操作

旋轉操作示意圖:

以下是紅黑樹的節點程式碼:

package idv.carl.datastructures.rbtree;

/**
 * @author Carl Lu
 */
public class RbNode {

    private int id;
    private int data;
    private boolean red = true;
    private RbNode parent;
    private RbNode left;
    private RbNode right;

    public RbNode(int id, int data) {
        super();
        this.id = id;
        this.data = data;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public boolean isRed() {
        return red;
    }

    public void setRed(boolean red) {
        this.red = red;
    }

    public RbNode getParent() {
        return parent;
    }

    public void setParent(RbNode parent) {
        this.parent = parent;
    }

    public RbNode getLeft() {
        return left;
    }

    public void setLeft(RbNode left) {
        this.left = left;
    }

    public RbNode getRight() {
        return right;
    }

    public void setRight(RbNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "RbNode{" + "id=" + id + ", data=" + data + ", red=" + red + '}';
    }
}