本文github地址

本文以Java TreeMap為例，從源代碼層面，結合詳細的圖解，剝繭抽絲地講解紅黑樹（Red-Black tree）的插入，刪除以及由此產生的調整過程。

總體介紹

Java TreeMap實現了SortedMap接口，也就是說會按照key的大小順序對Map中的元素進行排序，key大小的評判可以通過其本身的自然順序（natural ordering），也可以通過構造時傳入的比較器（Comparator）。

TreeMap底層通過紅黑樹（Red-Black tree）實現，也就意味著containsKey(), get(), put(), remove()都有著log(n)的時間復雜度。其具體算法實現參照了《算法導論》。

出于性能原因，TreeMap是非同步的（not synchronized），如果需要在多線程環境使用，需要程序員手動同步；或者通過如下方式將TreeMap包裝成（wrapped）同步的：

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

紅黑樹是一種近似平衡的二叉查找樹，它能夠確保任何一個節點的左右子樹的高度差不會超過二者中較低那個的一陪。具體來說，紅黑樹是滿足如下條件的二叉查找樹（binary search tree）：

1. 每個節點要么是紅色，要么是黑色。
2. 根節點必須是黑色
3. 紅色節點不能連續（也即是，紅色節點的孩子和父親都不能是紅色）。
4. 對于每個節點，從該點至null（樹尾端）的任何路徑，都含有相同個數的黑色節點。

在樹的結構發生改變時（插入或者刪除操作），往往會破壞上述條件3或條件4，需要通過調整使得查找樹重新滿足紅黑樹的條件。

預備知識

前文說到當查找樹的結構發生改變時，紅黑樹的條件可能被破壞，需要通過調整使得查找樹重新滿足紅黑樹的條件。調整可以分為兩類：一類是顏色調整，即改變某個節點的顏色；另一類是結構調整，集改變檢索樹的結構關系。結構調整過程包含兩個基本操作：左旋（Rotate Left），右旋（RotateRight）。

左旋

左旋的過程是將x的右子樹繞x逆時針旋轉，使得x的右子樹成為x的父親，同時修改相關節點的引用。旋轉之后，二叉查找樹的屬性仍然滿足。

TreeMap中左旋代碼如下：

右旋

右旋的過程是將x的左子樹繞x順時針旋轉，使得x的左子樹成為x的父親，同時修改相關節點的引用。旋轉之后，二叉查找樹的屬性仍然滿足。

TreeMap中右旋代碼如下：

方法剖析

get()

get(Object key)方法根據指定的key值返回對應的value，該方法調用了getEntry(Object key)得到相應的entry，然后返回entry.value。因此getEntry()是算法的核心。算法思想是根據key的自然順序（或者比較器順序）對二叉查找樹進行查找，直到找到滿足k.compareTo(p.key) == 0的entry。

具體代碼如下：

//getEntry()方法
final Entry<K,V> getEntry(Object key) {
    
    if (key == null)//不允許key值為null
        throw new NullPointerException();
    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;
}

put()

put(K key, V value)方法是將指定的key, value對添加到map里。該方法首先會對map做一次查找，看是否包含該元組，如果已經包含則直接返回，查找過程類似于getEntry()方法；如果沒有找到則會在紅黑樹中插入新的entry，如果插入之后破壞了紅黑樹的約束，還需要進行調整（旋轉，改變某些節點的顏色）。

public V put(K key, V value) {
    
    int cmp;
    Entry<K,V> parent;
    if (key == null)
        throw new NullPointerException();
    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);//創建并插入新的entry
    if (cmp < 0) parent.left = e;
    else parent.right = e;
    fixAfterInsertion(e);//調整
    size++;
    return null;
}

上述代碼的插入部分并不難理解：首先在紅黑樹上找到合適的位置，然后創建新的entry并插入（當然，新插入的節點一定是樹的葉子）。難點是調整函數fixAfterInsertion()，前面已經說過，調整往往需要1.改變某些節點的顏色，2.對某些節點進行旋轉。

調整函數fixAfterInsertion()的具體代碼如下，其中用到了上文中提到的rotateLeft()和rotateRight()函數。通過代碼我們能夠看到，情況2其實是落在情況3內的。情況4～情況6跟前三種情況是對稱的，因此圖解中并沒有畫出后三種情況，讀者可以參考代碼自行理解。

remove()

remove(Object key)的作用是刪除key值對應的entry，該方法首先通過上文中提到的getEntry(Object key)方法找到key值對應的entry，然后調用deleteEntry(Entry<K,V> entry)刪除對應的entry。由于刪除操作會改變紅黑樹的結構，有可能破壞紅黑樹的約束，因此有可能要進行調整。

有關remove()的具體講解將放到下一篇博文當中，敬請期待！