紅黑樹、TreeMap、TreeSet

• 2020 年 12 月 1 日
• 筆記
• treemap, 紅黑樹

事先聲明以下代碼基於JDK1.8版本

參考資料

大部分圖片引自//www.jianshu.com/p/e136ec79235c侵刪

//www.cnblogs.com/skywang12345/p/3245399.html#!comments

//www.cnblogs.com/CarpenterLee/p/5525688.html

//www.cnblogs.com/CarpenterLee/p/5503882.html

TreeMap用法

TreeMap這樣一種數據結構給了我們什麼：

1. 與map一樣的鍵值對結構存儲
2. TreeMap間接繼承自SortedMap，元素有序，有序的tree也意味着這是一顆二叉搜索樹，因此它的查詢是log(n)級別的
3. 不允許null的key
4. 不允許重複的key
5. 並不同步，如果需要同步，可以利用Collections包裝一下Collections.synchronizedSortedMap()

如果你有上述的需求，其實也就是快速搜索，可以考慮使用它

紅黑樹

為什麼是紅黑樹？二叉搜索樹？AVL?

TreeMap是通過什麼樣的數據結構來存儲數據的呢？紅黑樹

• 首先TreeMap要求有序，所以它至少是一顆二叉搜索樹

那為什麼二叉搜索樹又不行呢？

在一定的情況下，二叉搜索樹會退化成鏈表，失去了log(n)的搜索時間複雜度

如下圖所示，如果按照1，2，3，4這樣的順序去構成二叉搜索樹的話，它就會退化成一個鏈表，這樣的性能是沒法接收的

那麼AVL樹又如何呢？為什麼就選擇紅黑樹呢

紅黑樹由於其特性，它並不追求完全的平衡，更低的平衡要求對應着插入、刪除效率的提高（可能提高並不明顯甚至不如AVL，因為插入、刪除的第一步就是定位），搜索的效率降低，AVL相對紅黑樹而言，要求完全的平衡，自然插入、刪除需要進行的操作更多，效率更低，而由於完全的平衡，搜索的效率就更高，綜合而言，選擇了實現起來更為簡單，各方面更為均衡的紅黑樹，就是如此

紅黑樹的性質

1. 任何一個節點不是紅色就是黑色
2. 根節點是黑色
3. 任何兩個紅色節點不能直接相連
4. 每個葉子節點（Nil）節點都為黑色，也就是null節點為黑色
5. 從根節點出發，到任意一個葉子節點的簡單路徑（不包含葉子節點）的黑色節點數目要相同

推論

1. 如果一個節點存在黑色子節點，那麼它一定有兩個子節點，為了滿足性質5

左旋與右旋與着色

紅黑樹為了維持上述5個性質，需要做出一些努力，這些努力就是旋轉與着色

左旋示意圖：

語言總結一下就是：

左旋，右孩子成為旋轉中心的父親節點，旋轉中心成為右孩子的左孩子，此時旋轉中心的右孩子空缺，右孩子的左子樹失去了父親，把右孩子的左子樹置為旋轉中心的右孩子

對應的TreeMap的rotateLeft方法如下

private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right;
        //p的右孩子->r的左子樹
        p.right = r.left;
        if (r.left != null)
            //右孩子指向p.parent
            r.left.parent = p;
        r.parent = p.parent;
        //判斷p是否為root以及p在parent中的位置
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        //p成為r的左孩子，r成為p的父親
        r.left = p;
        p.parent = r;
    }
}

右旋示意圖

TreeMap中的右旋代碼

private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}

着色

Entry的color成員變量如下

boolean color = BLACK;

//上色方法如下
private static <K,V> void setColor(Entry<K,V> p, boolean c) {
    if (p != null)
        p.color = c;
}

紅黑樹的查找

紅黑樹本質還是一顆二叉搜索樹，自然與二叉搜索樹的查找方式相差無幾

TreeMap中的實現如下：

final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    if (comparator != null)
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
    //如果有，使用自定義的排序規則
    Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}

插入過程如何保持平衡？

插入過程的步驟

• 利用已有的紅黑樹結構找到插入位置
• 插入一個新的紅色節點
• 調整

為啥新插入的節點要是紅色呢？

由於性質5的存在，插入節點黑色勢必導致紅黑樹的性質5的不滿足，而插入紅色並不一定需要調整樹的結構

插入情景分類

1-3

1. root為null，直接插入並且，着色為black即可
2. 插入節點的key已經存在，在TreeMap中，找到對應的節點直接修改value
3. 插入節點的父親節點為黑色節點，直接插入即可，不會違背任何一條性質
4. 插入節點的父親節點為紅色節點
   1. 父親為紅色，並且當且節點的祖父節點的另一個子結點即叔叔節點也是紅色
   2. 父親為紅色，叔叔節點為黑色（包括Nil），其父親為祖父節點的左孩子
      1. 插入節點為父親節點的左孩子
      2. 插入節點為父親節點的右孩子
   3. 父親為紅色，叔叔節點為黑色（包括Nil），其父親為祖父節點的右孩子
      1. 插入節點為父親節點的左孩子
      2. 插入節點為父親節點的右孩子

4.2與4.3完全對稱式的操作，以4.2為例

4.1父親為紅色，叔叔為紅色

操作如下

• 父親與叔叔節點置為黑色
• 祖父節點置為紅色
• 把祖父節點當成新插入的節點，向上遞歸

為什麼如此操作？

當前節點為紅，父親為紅，違背性質4，修改父親為黑，此時經過父親節點的路徑的黑色節點數量大於經過叔叔節點的路徑黑色節點數目，那就再把叔叔染黑，那麼此時父輩平衡，但是經過祖父的這條分支黑色節點數目多了一個，那麼再把祖父染紅即可，然後以祖父為新插入的節點再插入即可

效果如圖：

4.2.1 父親為紅色，叔叔為黑色（Nil），父親為祖父節點的左孩子，插入節點為父親節點的左孩子

操作如下

• 將父親置為黑色
• 將祖父置為紅色
• 以祖父為中心，右旋

效果如圖：

為什麼這麼操作？

不滿足性質4，修改父親為黑色，此時父親這邊的路徑黑色數量多1，那麼再修改祖父為紅色，但此時經過叔叔的路徑黑色數量少1，此時以祖父為中心，右旋，讓剛剛染色為黑色的節點成為父親，父親成為叔叔的父親，即可滿足平衡

4.2.2 父親為紅色，叔叔為黑色（Nil），父親為祖父節點的左孩子，插入節點為父親節點的右孩子

操作如下：

• 以父親節點為中心，左旋
• 達到4.2.1的效果，然後按照上面的操作來

效果如圖：

為什麼這麼操作？

就是為了變成4.2.1，然後按照4.2.1的操作進行即可

4.3是4.2的鏡像版本，對稱過去就好了

TreeMap中的插入代碼

put方法

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check
		//1 如果root為null，插入並返回即可
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                //2 如果找到了，直接修改value
                return t.setValue(value);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    Entry<K,V> e = new Entry<>(key, value, parent);
    //3 直接插入節點，默認color為黑色
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

fixAfterInsertion（）方法

private void fixAfterInsertion(Entry<K,V> x) {
    //把color着色為紅
    x.color = RED;

    while (x != null && x != root && x.parent.color == RED) {
        //父親為祖父的左孩子
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            //y-叔叔節點
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                //叔叔為紅--4.1，修改父親和叔叔的節點為黑，祖父為紅
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                //將祖父設置為當前節點
                x = parentOf(parentOf(x));
            } else {
                //插入節點為右孩子，則先左旋一下，從4.2.2 --> 4.2.1
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                //4.2.1，修改父親為黑色，祖父為紅色，以祖父為中心右旋
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            //對稱的，父親為祖父的右孩子
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    //如果x為root，直接着色即可
    root.color = BLACK;
}

刪除過程如何保持平衡？

刪除過程分為兩步：

1. 定位到要刪除的節點，按照節點分類情況刪除
2. 通過旋轉、着色平衡紅黑樹

節點分類：

1. 沒有孩子節點，直接刪除即可
2. 有一個孩子節點，直接刪除該節點，用唯一子節點代替它的位置
3. 有兩個孩子，尋找後繼節點（第一個比它大的節點），把後繼節點的內容複製過來，刪除後繼節點，此時的後繼節點不可能有兩個孩子節點，有的話，後繼節點一定不是它，刪除後繼節點，按照情況1，2處理

後繼節點

後繼節點的選取，選投影到x軸上離它最近的兩個節點（肯定有兩個）中的任意一個都可以，這裡選擇第一個比刪除節點大的節點，對應到樹中的位置如下

• 如果刪除節點有右子樹，則對應着右子樹的最左節點

• 如果沒有則對應着第一個向右走的節點，如圖所示

  

  為什麼是後繼節點？

  1. 後繼節點來替換，它大於>待刪除節點>待刪除節點左子樹所有節點，它是第一個大於待刪除節點的節點，它小於<右子樹的所有節點，即滿足基本的二叉搜索樹的性質
  2. 只賦值，不修改顏色，即不破壞紅黑樹的性質，此時只需要考慮刪除後繼節點的影響即可

  後繼節點一定是樹末尾的節點，因為任何一個左右孩子非空的節點都不可能成為最終的後繼節點，它遞歸下去最終到樹梢的位置

  刪除過程對應如下：

  

現在完成了第一步，定位真正要刪除的節點，下面就是刪除這個節點之後如何平衡二叉樹？

刪除情況分類

1. 刪除節點為紅色
2. 刪除節點為黑色，且為父親節點的左孩子
   1. 兄弟節點為紅色，（此時父節點，兄弟節點的子節點都為黑色（Nil））
   2. 兄弟節點為黑色，兄弟節點的兩個子結點也是黑色（Nil）
   3. 兄弟節點為黑色，兄弟節點的左孩子為紅色，右孩子為黑色（Nil）
   4. 兄弟節點為黑色，兄弟節點的右孩子為紅色，左孩子任意
3. 刪除節點為黑色，且為父親節點的右孩子，和上面是對稱的
   1. 兄弟節點為紅色，（此時父節點，兄弟節點的子節點都為黑色（Nil））
   2. 兄弟節點為黑色，兄弟節點的兩個子結點也是黑色（Nil）
   3. 兄弟節點為黑色，兄弟節點的左孩子為紅色，右孩子為黑色（Nil）
   4. 兄弟節點為黑色，兄弟節點的右孩子為紅色，左孩子任意

只討論1，2的情況，3與2對稱操作

1 刪除節點為紅色

紅色節點死不足惜！！無需處理，刪除即可

2.2 刪除節點為黑色，且為父親節點的左孩子，兄弟節點為黑色，兄弟節點的兩個子結點都是黑色

操作如下

• 將兄弟節點置為紅色
• 將刪除節點的父親節點置為新的待刪除節點

效果如圖：

why

假設R刪除了，那麼為了達到平衡，P應該幫忙補一個黑色回來，那麼出問題了，任何包含P和S的路徑黑色就多出來1了，把S置為紅色即可達到局部的平衡，把需要補黑色的需求向上傳遞

2.1 刪除節點為黑色，且為父親節點的左孩子，兄弟節點為紅色

操作如下：

• 將兄弟置為黑色
• 將父親置為紅色
• 以父親節點為中心，左旋
• 左旋之後重新設置兄弟節點

效果如圖：

why

向2.2/2.3/2.4靠攏

2.4 刪除節點為黑色，且為父親節點的左孩子，兄弟節點為黑色，兄弟節點的右孩子為紅色，左孩子任意

操作如下：

• 父親節點的顏色賦值給兄弟節點
• 將父親節點置為黑色
• 將兄弟節點的右孩子置為黑色
• 以父親節點為中心左旋

效果如圖：

why

我們的最終目的就是為包含R的路徑補一個黑色節點

1. 修改P為黑色（不一定能保證補回一個黑色，有可能P就是黑色的）

2. 以P為中心左旋，讓S成為包含R路徑的新root，那麼包含S的路徑黑色節點沒變，包含R的路徑的黑色節點由於S的存在+1

左旋之後，P與SL為父子關係，而P與SL又都為任意顏色，不一定能保證性質4，所以在左旋之前將P與S顏色互換，但是此時包含SR（紅色）的右子樹黑色節點少1，將SR置為黑色即可

2.3 刪除節點為黑色，且為父親節點的左孩子，兄弟節點為黑色，兄弟節點的左孩子為紅色，右孩子為黑色（Nil）

操作如下：

• 將兄弟節點的左孩子置為黑色
• 將兄弟節點置為紅色
• 以兄弟節點為中心右旋得到2.4的情況
• 按照2.4的方法處理

效果如圖：

刪除節點為黑色，且為父親節點的右孩子節點的操作與上述操作對稱

TreeMap中的刪除代碼

remove()

    public V remove(Object key) {
        Entry<K,V> p = getEntry(key);
        if (p == null)
            return null;

        V oldValue = p.value;
        deleteEntry(p);
        return oldValue;
    }

deleteEntry()

private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;

    // If strictly internal, copy successor's element to p and then make p
    // point to successor.
    //left與right都非空，即尋找後繼節點
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);
        //將s的值賦值給p，然後讓p指向s
        p.key = s.key;
        p.value = s.value;
        p = s;
    } // p has 2 children

    // Start fixup at replacement node, if it exists.
    //left!=null則為left，right！=null則為right
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {
        // Link replacement to parent
        //把replace鏈接到parent上
        replacement.parent = p.parent;
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;

        // Null out links so they are OK to use by fixAfterDeletion.
        //for GC
        p.left = p.right = p.parent = null;

        // Fix replacement
        //如果刪除節點為黑色，則調整
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { // return if we are the only node.
        //唯一節點，root節點
        root = null;
    } else { //  No children. Use self as phantom replacement and unlink.
        //左右孩子均為null
        if (p.color == BLACK)
            fixAfterDeletion(p);
		//斷開p與parent的連接
        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

successor()

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        //右子樹的最左下節點
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        //第一個向右走的節點
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

fixAfterDeletion()

private void fixAfterDeletion(Entry<K,V> x) {
    while (x != root && colorOf(x) == BLACK) {
        //待刪除節點為父親節點的左孩子且為黑色
        if (x == leftOf(parentOf(x))) {
            //sib--兄弟節點
            Entry<K,V> sib = rightOf(parentOf(x));
			//2.1-->2.2/2.3/2.4
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }
			//2.2 設置兄弟節點為紅色，x修改為parent
            if (colorOf(leftOf(sib))  == BLACK &&
                colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                //2.3-->2.4
                if (colorOf(rightOf(sib)) == BLACK) {
                    setColor(leftOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateRight(sib);
                    sib = rightOf(parentOf(x));
                }
                //2.4
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(rightOf(sib), BLACK);
                rotateLeft(parentOf(x));
                x = root;
            }
        } else { // symmetric
            Entry<K,V> sib = leftOf(parentOf(x));

            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateRight(parentOf(x));
                sib = leftOf(parentOf(x));
            }

            if (colorOf(rightOf(sib)) == BLACK &&
                colorOf(leftOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    setColor(rightOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateLeft(sib);
                    sib = leftOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(leftOf(sib), BLACK);
                rotateRight(parentOf(x));
                x = root;
            }
        }
    }
	//如果x為red，直接設置為x，即可彌補回丟失的黑色節點，如果是黑色，沒法通過setColor來補回黑色，通過平衡的方式來補回黑色
    setColor(x, BLACK);
}

紅黑樹總結

總結來說，無論是插入也好，刪除也罷，紅黑樹保持平衡的策略是自底向下追求紅黑樹的平衡，把矛盾交給上層的節點解決。

TreeMap的keySet、EntrySet、values淺析

TreeMap紅黑樹的代碼已經混雜在上面，不再進行梳理

keySet()

public NavigableSet<K> navigableKeySet() {
    KeySet<K> nks = navigableKeySet;
    //如果已經創建了nks，直接返回，否則new一個內部類KeySet
    return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
}
//成員變量navigableKeySet
private transient KeySet<K> navigableKeySet;

KeySet

//成員變量m
private final NavigableMap<E, ?> m;
//構造方法，其實就把TreeMap傳入了
KeySet(NavigableMap<E,?> map) { m = map; }

//簡單看幾個方法，發現都是調用m的方法
public int size() { return m.size(); }
public boolean isEmpty() { return m.isEmpty(); }
public boolean contains(Object o) { return m.containsKey(o); }
public void clear() { m.clear(); }

//包括iterator也是通過m訪問另一個內部類
public Iterator<E> iterator() {
    if (m instanceof TreeMap)
        return ((TreeMap<E,?>)m).keyIterator();
    else
        return ((TreeMap.NavigableSubMap<E,?>)m).keyIterator();
}

EntrySet、Values的實現也都相差無幾，有點類似於外觀類，提供受限的方法調用

TreeSet簡析

看一下TreeSet的構造函數即可

public TreeSet() {
    this(new TreeMap<E,Object>());
}

TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

private transient NavigableMap<E,Object> m;

add()

private static final Object PRESENT = new Object();

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

顯然TreeSet基於TreeMap實現它的基本功能，可以說它就是一個TreeSet，只不過每次add的value是一個final的obj