通过分析 JDK 源代码研究 TreeMap 红黑树算法实现--转
TreeMap 和 TreeSet 是 Java Collection Framework 的兩個重要成員，其中 TreeMap 是 Map 接口的常用實現類，而 TreeSet 是 Set 接口的常用實現類。雖然 HashMap 和 HashSet 實現的接口規范不同，但 TreeSet 底層是通過 TreeMap 來實現的，因此二者的實現方式完全一樣。而 TreeMap 的實現就是紅黑樹算法。
TreeMap 的實現就是紅黑樹數據結構，也就說是一棵自平衡的排序二叉樹，這樣就可以保證當需要快速檢索指定節點。
TreeSet 和 TreeMap 的關系
為了讓大家了解 TreeMap 和 TreeSet 之間的關系，下面先看 TreeSet 類的部分源代碼：
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable { // 使用 NavigableMap 的 key 來保存 Set 集合的元素private transient NavigableMap<E,Object> m; // 使用一個 PRESENT 作為 Map 集合的所有 value。private static final Object PRESENT = new Object(); // 包訪問權限的構造器，以指定的 NavigableMap 對象創建 Set 集合TreeSet(NavigableMap<E,Object> m) { this.m = m; } public TreeSet() // ①{ // 以自然排序方式創建一個新的 TreeMap，// 根據該 TreeSet 創建一個 TreeSet，// 使用該 TreeMap 的 key 來保存 Set 集合的元素this(new TreeMap<E,Object>()); } public TreeSet(Comparator<? super E> comparator) // ②{ // 以定制排序方式創建一個新的 TreeMap，// 根據該 TreeSet 創建一個 TreeSet，// 使用該 TreeMap 的 key 來保存 Set 集合的元素this(new TreeMap<E,Object>(comparator)); } public TreeSet(Collection<? extends E> c) { // 調用①號構造器創建一個 TreeSet，底層以 TreeMap 保存集合元素this(); // 向 TreeSet 中添加 Collection 集合 c 里的所有元素addAll(c); } public TreeSet(SortedSet<E> s) { // 調用②號構造器創建一個 TreeSet，底層以 TreeMap 保存集合元素this(s.comparator()); // 向 TreeSet 中添加 SortedSet 集合 s 里的所有元素addAll(s); } //TreeSet 的其他方法都只是直接調用 TreeMap 的方法來提供實現... public boolean addAll(Collection<? extends E> c) { if (m.size() == 0 && c.size() > 0 && c instanceof SortedSet && m instanceof TreeMap) { // 把 c 集合強制轉換為 SortedSet 集合SortedSet<? extends E> set = (SortedSet<? extends E>) c; // 把 m 集合強制轉換為 TreeMap 集合TreeMap<E,Object> map = (TreeMap<E, Object>) m; Comparator<? super E> cc = (Comparator<? super E>) set.comparator(); Comparator<? super E> mc = map.comparator(); // 如果 cc 和 mc 兩個 Comparator 相等if (cc == mc || (cc != null && cc.equals(mc))) { // 把 Collection 中所有元素添加成 TreeMap 集合的 key map.addAllForTreeSet(set, PRESENT); return true; } } // 直接調用父類的 addAll() 方法來實現return super.addAll(c); } ... }從上面代碼可以看出，TreeSet 的 ① 號、② 號構造器的都是新建一個 TreeMap 作為實際存儲 Set 元素的容器，而另外 2 個構造器則分別依賴于 ① 號和 ② 號構造器，由此可見，TreeSet 底層實際使用的存儲容器就是 TreeMap。
與 HashSet 完全類似的是，TreeSet 里絕大部分方法都是直接調用 TreeMap 的方法來實現的，這一點讀者可以自行參閱 TreeSet 的源代碼，此處就不再給出了。
對于 TreeMap 而言，它采用一種被稱為“紅黑樹”的排序二叉樹來保存 Map 中每個 Entry —— 每個 Entry 都被當成“紅黑樹”的一個節點對待。例如對于如下程序而言：
public class TreeMapTest { public static void main(String[] args) { TreeMap<String , Double> map = new TreeMap<String , Double>(); map.put("ccc" , 89.0); map.put("aaa" , 80.0); map.put("zzz" , 80.0); map.put("bbb" , 89.0); System.out.println(map); } }當程序執行 map.put("ccc" , 89.0); 時，系統將直接把 "ccc"-89.0 這個 Entry 放入 Map 中，這個 Entry 就是該“紅黑樹”的根節點。接著程序執行 map.put("aaa" , 80.0); 時，程序會將 "aaa"-80.0 作為新節點添加到已有的紅黑樹中。
以后每向 TreeMap 中放入一個 key-value 對，系統都需要將該 Entry 當成一個新節點，添加成已有紅黑樹中，通過這種方式就可保證 TreeMap 中所有 key 總是由小到大地排列。例如我們輸出上面程序，將看到如下結果（所有 key 由小到大地排列）：
{aaa=80.0, bbb=89.0, ccc=89.0, zzz=80.0}回頁首
TreeMap 的添加節點
紅黑樹
紅黑樹是一種自平衡排序二叉樹，樹中每個節點的值，都大于或等于在它的左子樹中的所有節點的值，并且小于或等于在它的右子樹中的所有節點的值，這確保紅黑樹運行時可以快速地在樹中查找和定位的所需節點。
對于 TreeMap 而言，由于它底層采用一棵“紅黑樹”來保存集合中的 Entry，這意味這 TreeMap 添加元素、取出元素的性能都比 HashMap 低：當 TreeMap 添加元素時，需要通過循環找到新增 Entry 的插入位置，因此比較耗性能；當從 TreeMap 中取出元素時，需要通過循環才能找到合適的 Entry，也比較耗性能。但 TreeMap、TreeSet 比 HashMap、HashSet 的優勢在于：TreeMap 中的所有 Entry 總是按 key 根據指定排序規則保持有序狀態，TreeSet 中所有元素總是根據指定排序規則保持有序狀態。
為了理解 TreeMap 的底層實現，必須先介紹排序二叉樹和紅黑樹這兩種數據結構。其中紅黑樹又是一種特殊的排序二叉樹。
排序二叉樹是一種特殊結構的二叉樹，可以非常方便地對樹中所有節點進行排序和檢索。
排序二叉樹要么是一棵空二叉樹，要么是具有下列性質的二叉樹：
- 若它的左子樹不空，則左子樹上所有節點的值均小于它的根節點的值；
- 若它的右子樹不空，則右子樹上所有節點的值均大于它的根節點的值；
- 它的左、右子樹也分別為排序二叉樹。
圖 1 顯示了一棵排序二叉樹：
圖 1. 排序二叉樹
對排序二叉樹，若按中序遍歷就可以得到由小到大的有序序列。如圖 1 所示二叉樹，中序遍歷得：
{2，3，4，8，9，9，10，13，15，18}創建排序二叉樹的步驟，也就是不斷地向排序二叉樹添加節點的過程，向排序二叉樹添加節點的步驟如下：
掌握上面理論之后，下面我們來分析 TreeMap 添加節點（TreeMap 中使用 Entry 內部類代表節點）的實現，TreeMap 集合的 put(K key, V value) 方法實現了將 Entry 放入排序二叉樹中，下面是該方法的源代碼：
public V put(K key, V value) { // 先以 t 保存鏈表的 root 節點Entry<K,V> t = root; // 如果 t==null，表明是一個空鏈表，即該 TreeMap 里沒有任何 Entry if (t == null) { // 將新的 key-value 創建一個 Entry，并將該 Entry 作為 root root = new Entry<K,V>(key, value, null); // 設置該 Map 集合的 size 為 1，代表包含一個 Entry size = 1; // 記錄修改次數為 1 modCount++; return null; } int cmp; Entry<K,V> parent; Comparator<? super K> cpr = comparator; // 如果比較器 cpr 不為 null，即表明采用定制排序if (cpr != null) { do { // 使用 parent 上次循環后的 t 所引用的 Entry parent = t; // 拿新插入 key 和 t 的 key 進行比較cmp = cpr.compare(key, t.key); // 如果新插入的 key 小于 t 的 key，t 等于 t 的左邊節點if (cmp < 0) t = t.left; // 如果新插入的 key 大于 t 的 key，t 等于 t 的右邊節點else if (cmp > 0) t = t.right; // 如果兩個 key 相等，新的 value 覆蓋原有的 value，// 并返回原有的 value else return t.setValue(value); } while (t != null); } else { if (key == null) throw new NullPointerException(); Comparable<? super K> k = (Comparable<? super K>) key; do { // 使用 parent 上次循環后的 t 所引用的 Entry parent = t; // 拿新插入 key 和 t 的 key 進行比較cmp = k.compareTo(t.key); // 如果新插入的 key 小于 t 的 key，t 等于 t 的左邊節點if (cmp < 0) t = t.left; // 如果新插入的 key 大于 t 的 key，t 等于 t 的右邊節點else if (cmp > 0) t = t.right; // 如果兩個 key 相等，新的 value 覆蓋原有的 value，// 并返回原有的 value else return t.setValue(value); } while (t != null); } // 將新插入的節點作為 parent 節點的子節點Entry<K,V> e = new Entry<K,V>(key, value, parent); // 如果新插入 key 小于 parent 的 key，則 e 作為 parent 的左子節點if (cmp < 0) parent.left = e; // 如果新插入 key 小于 parent 的 key，則 e 作為 parent 的右子節點else parent.right = e; // 修復紅黑樹fixAfterInsertion(e); // ①size++; modCount++; return null; }上面程序中粗體字代碼就是實現“排序二叉樹”的關鍵算法，每當程序希望添加新節點時：系統總是從樹的根節點開始比較 —— 即將根節點當成當前節點，如果新增節點大于當前節點、并且當前節點的右子節點存在，則以右子節點作為當前節點；如果新增節點小于當前節點、并且當前節點的左子節點存在，則以左子節點作為當前節點；如果新增節點等于當前節點，則用新增節點覆蓋當前節點，并結束循環 —— 直到找到某個節點的左、右子節點不存在，將新節點添加該節點的子節點 —— 如果新節點比該節點大，則添加為右子節點；如果新節點比該節點小，則添加為左子節點。
回頁首
TreeMap 的刪除節點
當程序從排序二叉樹中刪除一個節點之后，為了讓它依然保持為排序二叉樹，程序必須對該排序二叉樹進行維護。維護可分為如下幾種情況：
（1）被刪除的節點是葉子節點，則只需將它從其父節點中刪除即可。
（2）被刪除節點 p 只有左子樹，將 p 的左子樹 pL 添加成 p 的父節點的左子樹即可；被刪除節點 p 只有右子樹，將 p 的右子樹 pR 添加成 p 的父節點的右子樹即可。
（3）若被刪除節點 p 的左、右子樹均非空，有兩種做法：
- 將 pL 設為 p 的父節點 q 的左或右子節點（取決于 p 是其父節點 q 的左、右子節點），將 pR 設為 p 節點的中序前趨節點 s 的右子節點（s 是 pL 最右下的節點，也就是 pL 子樹中最大的節點）。
- 以 p 節點的中序前趨或后繼替代 p 所指節點，然后再從原排序二叉樹中刪去中序前趨或后繼節點即可。（也就是用大于 p 的最小節點或小于 p 的最大節點代替 p 節點即可）。
圖 2 顯示了被刪除節點只有左子樹的示意圖：
圖 2. 被刪除節點只有左子樹
圖 3 顯示了被刪除節點只有右子樹的示意圖：
圖 3. 被刪除節點只有右子樹
圖 4 顯示了被刪除節點既有左子節點，又有右子節點的情形，此時我們采用到是第一種方式進行維護：
圖 4. 被刪除節點既有左子樹，又有右子樹
圖 5 顯示了被刪除節點既有左子樹，又有右子樹的情形，此時我們采用到是第二種方式進行維護：
圖 5. 被刪除節點既有左子樹，又有右子樹
TreeMap 刪除節點采用圖 5 所示右邊的情形進行維護——也就是用被刪除節點的右子樹中最小節點與被刪節點交換的方式進行維護。
TreeMap 刪除節點的方法由如下方法實現：
private void deleteEntry(Entry<K,V> p) { modCount++; size--; // 如果被刪除節點的左子樹、右子樹都不為空if (p.left != null && p.right != null) { // 用 p 節點的中序后繼節點代替 p 節點Entry<K,V> s = successor (p); p.key = s.key; p.value = s.value; p = s; } // 如果 p 節點的左節點存在，replacement 代表左節點；否則代表右節點。Entry<K,V> replacement = (p.left != null ? p.left : p.right); if (replacement != null) { replacement.parent = p.parent; // 如果 p 沒有父節點，則 replacemment 變成父節點if (p.parent == null) root = replacement; // 如果 p 節點是其父節點的左子節點else if (p == p.parent.left) p.parent.left = replacement; // 如果 p 節點是其父節點的右子節點else p.parent.right = replacement; p.left = p.right = p.parent = null; // 修復紅黑樹if (p.color == BLACK) fixAfterDeletion(replacement); // ①} // 如果 p 節點沒有父節點else if (p.parent == null) { root = null; } else { if (p.color == BLACK) // 修復紅黑樹fixAfterDeletion(p); // ②if (p.parent != null) { // 如果 p 是其父節點的左子節點if (p == p.parent.left) p.parent.left = null; // 如果 p 是其父節點的右子節點else if (p == p.parent.right) p.parent.right = null; p.parent = null; } } }回頁首
紅黑樹
排序二叉樹雖然可以快速檢索，但在最壞的情況下：如果插入的節點集本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉樹將變成鏈表：所有節點只有左節點（如果插入節點集本身是大到小排列）；或所有節點只有右節點（如果插入節點集本身是小到大排列）。在這種情況下，排序二叉樹就變成了普通鏈表，其檢索效率就會很差。
為了改變排序二叉樹存在的不足，Rudolf Bayer 與 1972 年發明了另一種改進后的排序二叉樹：紅黑樹，他將這種排序二叉樹稱為“對稱二叉 B 樹”，而紅黑樹這個名字則由 Leo J. Guibas 和 Robert Sedgewick 于 1978 年首次提出。
紅黑樹是一個更高效的檢索二叉樹，因此常常用來實現關聯數組。典型地，JDK 提供的集合類 TreeMap 本身就是一個紅黑樹的實現。
紅黑樹在原有的排序二叉樹增加了如下幾個要求：
Java 實現的紅黑樹
上面的性質 3 中指定紅黑樹的每個葉子節點都是空節點，而且并葉子節點都是黑色。但 Java 實現的紅黑樹將使用 null 來代表空節點，因此遍歷紅黑樹時將看不到黑色的葉子節點，反而看到每個葉子節點都是紅色的。
- 性質 1：每個節點要么是紅色，要么是黑色。
- 性質 2：根節點永遠是黑色的。
- 性質 3：所有的葉節點都是空節點（即 null），并且是黑色的。
- 性質 4：每個紅色節點的兩個子節點都是黑色。（從每個葉子到根的路徑上不會有兩個連續的紅色節點）
- 性質 5：從任一節點到其子樹中每個葉子節點的路徑都包含相同數量的黑色節點。
Java 中實現的紅黑樹可能有如圖 6 所示結構：
圖 6. Java 紅黑樹的示意
備注：本文中所有關于紅黑樹中的示意圖采用白色代表紅色。黑色節點還是采用了黑色表示。
根據性質 5：紅黑樹從根節點到每個葉子節點的路徑都包含相同數量的黑色節點，因此從根節點到葉子節點的路徑中包含的黑色節點數被稱為樹的“黑色高度（black-height）”。
性質 4 則保證了從根節點到葉子節點的最長路徑的長度不會超過任何其他路徑的兩倍。假如有一棵黑色高度為 3 的紅黑樹：從根節點到葉節點的最短路徑長度是 2，該路徑上全是黑色節點（黑節點 - 黑節點 - 黑節點）。最長路徑也只可能為 4，在每個黑色節點之間插入一個紅色節點（黑節點 - 紅節點 - 黑節點 - 紅節點 - 黑節點），性質 4 保證絕不可能插入更多的紅色節點。由此可見，紅黑樹中最長路徑就是一條紅黑交替的路徑。
紅黑樹和平衡二叉樹
紅黑樹并不是真正的平衡二叉樹，但在實際應用中，紅黑樹的統計性能要高于平衡二叉樹，但極端性能略差。
由此我們可以得出結論：對于給定的黑色高度為 N 的紅黑樹，從根到葉子節點的最短路徑長度為 N-1，最長路徑長度為 2 * (N-1)。
提示：排序二叉樹的深度直接影響了檢索的性能，正如前面指出，當插入節點本身就是由小到大排列時，排序二叉樹將變成一個鏈表，這種排序二叉樹的檢索性能最低：N 個節點的二叉樹深度就是 N-1。
紅黑樹通過上面這種限制來保證它大致是平衡的——因為紅黑樹的高度不會無限增高，這樣保證紅黑樹在最壞情況下都是高效的，不會出現普通排序二叉樹的情況。
由于紅黑樹只是一個特殊的排序二叉樹，因此對紅黑樹上的只讀操作與普通排序二叉樹上的只讀操作完全相同，只是紅黑樹保持了大致平衡，因此檢索性能比排序二叉樹要好很多。
但在紅黑樹上進行插入操作和刪除操作會導致樹不再符合紅黑樹的特征，因此插入操作和刪除操作都需要進行一定的維護，以保證插入節點、刪除節點后的樹依然是紅黑樹。
回頁首
添加節點后的修復
上面?put(K key, V value) 方法中①號代碼處使用fixAfterInsertion(e) 方法來修復紅黑樹——因此每次插入節點后必須進行簡單修復，使該排序二叉樹滿足紅黑樹的要求。
插入操作按如下步驟進行：
（1）以排序二叉樹的方法插入新節點，并將它設為紅色。
（2）進行顏色調換和樹旋轉。
插入后的修復
在插入操作中，紅黑樹的性質 1 和性質 3 兩個永遠不會發生改變，因此無需考慮紅黑樹的這兩個特性。
這種顏色調用和樹旋轉就比較復雜了，下面將分情況進行介紹。在介紹中，我們把新插入的節點定義為 N 節點，N 節點的父節點定義為 P 節點，P 節點的兄弟節點定義為 U 節點，P 節點父節點定義為 G 節點。
下面分成不同情形來分析插入操作
情形 1：新節點 N 是樹的根節點，沒有父節點
在這種情形下，直接將它設置為黑色以滿足性質 2。
情形 2：新節點的父節點 P 是黑色
在這種情況下，新插入的節點是紅色的，因此依然滿足性質 4。而且因為新節點 N 有兩個黑色葉子節點；但是由于新節點 N 是紅色，通過它的每個子節點的路徑依然保持相同的黑色節點數，因此依然滿足性質 5。
情形 3：如果父節點 P 和父節點的兄弟節點 U 都是紅色
在這種情況下，程序應該將 P 節點、U 節點都設置為黑色，并將 P 節點的父節點設為紅色（用來保持性質 5）。現在新節點 N 有了一個黑色的父節點 P。由于從 P 節點、U 節點到根節點的任何路徑都必須通過 G 節點，在這些路徑上的黑節點數目沒有改變（原來有葉子和 G 節點兩個黑色節點，現在有葉子和 P 兩個黑色節點）。
經過上面處理后，紅色的 G 節點的父節點也有可能是紅色的，這就違反了性質 4，因此還需要對 G 節點遞歸地進行整個過程（把 G 當成是新插入的節點進行處理即可）。
圖 7 顯示了這種處理過程：
圖 7. 插入節點后進行顏色調換
備注：雖然圖 11.28 繪制的是新節點 N 作為父節點 P 左子節點的情形，其實新節點 N 作為父節點 P 右子節點的情況與圖 11.28 完全相同。
情形 4：父節點 P 是紅色、而其兄弟節點 U 是黑色或缺少；且新節點 N 是父節點 P 的右子節點，而父節點 P 又是其父節點 G 的左子節點。
在這種情形下，我們進行一次左旋轉對新節點和其父節點進行，接著按情形 5 處理以前的父節點 P（也就是把 P 當成新插入的節點即可）。這導致某些路徑通過它們以前不通過的新節點 N 或父節點 P 的其中之一，但是這兩個節點都是紅色的，因此不會影響性質 5。
圖 8 顯示了對情形 4 的處理：
圖 8. 插入節點后的樹旋轉
備注：圖 11.29 中 P 節點是 G 節點的左子節點，如果 P 節點是其父節點 G 節點的右子節點，那么上?面的處理情況應該左、右對調一下。
情形 5：父節點 P 是紅色、而其兄弟節點 U 是黑色或缺少；且新節點 N 是其父節點的左子節點，而父節點 P 又是其父節點 G 的左子節點。
在這種情形下，需要對節點 G 的一次右旋轉，在旋轉產生的樹中，以前的父節點 P 現在是新節點 N 和節點 G 的父節點。由于以前的節點 G 是黑色，否則父節點 P 就不可能是紅色，我們切換以前的父節點 P 和節點 G 的顏色，使之滿足性質 4，性質 5 也仍然保持滿足，因為通過這三個節點中任何一個的所有路徑以前都通過節點 G，現在它們都通過以前的父節點 P。在各自的情形下，這都是三個節點中唯一的黑色節點。
圖 9 顯示了情形 5 的處理過程：
圖 9. 插入節點后的顏色調整、樹旋轉
備注：圖 11.30 中 P 節點是 G 節點的左子節點，如果 P 節點是其父節點 G 節點的右子節點，那么上面的處理情況應該左、右對調一下。
TreeMap 為插入節點后的修復操作由 fixAfterInsertion(Entry<K,V> x) 方法提供，該方法的源代碼如下：
// 插入節點后修復紅黑樹private void fixAfterInsertion(Entry<K,V> x) { x.color = RED; // 直到 x 節點的父節點不是根，且 x 的父節點不是紅色while (x != null && x != root && x.parent.color == RED) { // 如果 x 的父節點是其父節點的左子節點if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { // 獲取 x 的父節點的兄弟節點Entry<K,V> y = rightOf(parentOf(parentOf(x))); // 如果 x 的父節點的兄弟節點是紅色if (colorOf(y) == RED) { // 將 x 的父節點設為黑色setColor(parentOf(x), BLACK); // 將 x 的父節點的兄弟節點設為黑色setColor(y, BLACK); // 將 x 的父節點的父節點設為紅色setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } // 如果 x 的父節點的兄弟節點是黑色else { // 如果 x 是其父節點的右子節點if (x == rightOf(parentOf(x))) { // 將 x 的父節點設為 x x = parentOf(x); rotateLeft(x); } // 把 x 的父節點設為黑色setColor(parentOf(x), BLACK); // 把 x 的父節點的父節點設為紅色setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } // 如果 x 的父節點是其父節點的右子節點else { // 獲取 x 的父節點的兄弟節點Entry<K,V> y = leftOf(parentOf(parentOf(x))); // 如果 x 的父節點的兄弟節點是紅色if (colorOf(y) == RED) { // 將 x 的父節點設為黑色。setColor(parentOf(x), BLACK); // 將 x 的父節點的兄弟節點設為黑色setColor(y, BLACK); // 將 x 的父節點的父節點設為紅色setColor(parentOf(parentOf(x)), RED); // 將 x 設為 x 的父節點的節點x = parentOf(parentOf(x)); } // 如果 x 的父節點的兄弟節點是黑色else { // 如果 x 是其父節點的左子節點if (x == leftOf(parentOf(x))) { // 將 x 的父節點設為 x x = parentOf(x); rotateRight(x); } // 把 x 的父節點設為黑色setColor(parentOf(x), BLACK); // 把 x 的父節點的父節點設為紅色setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); } } } // 將根節點設為黑色root.color = BLACK; }回頁首
刪除節點后的修復
與添加節點之后的修復類似的是，TreeMap 刪除節點之后也需要進行類似的修復操作，通過這種修復來保證該排序二叉樹依然滿足紅黑樹特征。大家可以參考插入節點之后的修復來分析刪除之后的修復。TreeMap 在刪除之后的修復操作由 fixAfterDeletion(Entry<K,V> x) 方法提供，該方法源代碼如下：
// 刪除節點后修復紅黑樹private void fixAfterDeletion(Entry<K,V> x) { // 直到 x 不是根節點，且 x 的顏色是黑色while (x != root && colorOf(x) == BLACK) { // 如果 x 是其父節點的左子節點if (x == leftOf(parentOf(x))) { // 獲取 x 節點的兄弟節點Entry<K,V> sib = rightOf(parentOf(x)); // 如果 sib 節點是紅色if (colorOf(sib) == RED) { // 將 sib 節點設為黑色setColor(sib, BLACK); // 將 x 的父節點設為紅色setColor(parentOf(x), RED); rotateLeft(parentOf(x)); // 再次將 sib 設為 x 的父節點的右子節點sib = rightOf(parentOf(x)); } // 如果 sib 的兩個子節點都是黑色if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { // 將 sib 設為紅色setColor(sib, RED); // 讓 x 等于 x 的父節點x = parentOf(x); } else { // 如果 sib 的只有右子節點是黑色if (colorOf(rightOf(sib)) == BLACK) { // 將 sib 的左子節點也設為黑色setColor(leftOf(sib), BLACK); // 將 sib 設為紅色setColor(sib, RED); rotateRight(sib); sib = rightOf(parentOf(x)); } // 設置 sib 的顏色與 x 的父節點的顏色相同setColor(sib, colorOf(parentOf(x))); // 將 x 的父節點設為黑色setColor(parentOf(x), BLACK); // 將 sib 的右子節點設為黑色setColor(rightOf(sib), BLACK); rotateLeft(parentOf(x)); x = root; } } // 如果 x 是其父節點的右子節點else { // 獲取 x 節點的兄弟節點Entry<K,V> sib = leftOf(parentOf(x)); // 如果 sib 的顏色是紅色if (colorOf(sib) == RED) { // 將 sib 的顏色設為黑色setColor(sib, BLACK); // 將 sib 的父節點設為紅色setColor(parentOf(x), RED); rotateRight(parentOf(x)); sib = leftOf(parentOf(x)); } // 如果 sib 的兩個子節點都是黑色if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { // 將 sib 設為紅色setColor(sib, RED); // 讓 x 等于 x 的父節點x = parentOf(x); } else { // 如果 sib 只有左子節點是黑色if (colorOf(leftOf(sib)) == BLACK) { // 將 sib 的右子節點也設為黑色setColor(rightOf(sib), BLACK); // 將 sib 設為紅色setColor(sib, RED); rotateLeft(sib); sib = leftOf(parentOf(x)); } // 將 sib 的顏色設為與 x 的父節點顏色相同setColor(sib, colorOf(parentOf(x))); // 將 x 的父節點設為黑色setColor(parentOf(x), BLACK); // 將 sib 的左子節點設為黑色setColor(leftOf(sib), BLACK); rotateRight(parentOf(x)); x = root; } } } setColor(x, BLACK); }回頁首
檢索節點
當 TreeMap 根據 key 來取出 value 時，TreeMap 對應的方法如下：
public V get(Object key) { // 根據指定 key 取出對應的 Entry Entry>K,V< p = getEntry(key); // 返回該 Entry 所包含的 value return (p==null ? null : p.value); }從上面程序的粗體字代碼可以看出，get(Object key) 方法實質是由于 getEntry() 方法實現的，這個 getEntry() 方法的代碼如下：
final Entry<K,V> getEntry(Object key) { // 如果 comparator 不為 null，表明程序采用定制排序if (comparator != null) // 調用 getEntryUsingComparator 方法來取出對應的 key return getEntryUsingComparator(key); // 如果 key 形參的值為 null，拋出 NullPointerException 異常if (key == null) throw new NullPointerException(); // 將 key 強制類型轉換為 Comparable 實例Comparable<? super K> k = (Comparable<? super K>) key; // 從樹的根節點開始Entry<K,V> p = root; while (p != null) { // 拿 key 與當前節點的 key 進行比較int cmp = k.compareTo(p.key); // 如果 key 小于當前節點的 key，向“左子樹”搜索if (cmp < 0) p = p.left; // 如果 key 大于當前節點的 key，向“右子樹”搜索else if (cmp > 0) p = p.right; // 不大于、不小于，就是找到了目標 Entry else return p; } return null; }上面的 getEntry(Object obj) 方法也是充分利用排序二叉樹的特征來搜索目標 Entry，程序依然從二叉樹的根節點開始，如果被搜索節點大于當前節點，程序向“右子樹”搜索；如果被搜索節點小于當前節點，程序向“左子樹”搜索；如果相等，那就是找到了指定節點。
當 TreeMap 里的 comparator != null 即表明該 TreeMap 采用了定制排序，在采用定制排序的方式下，TreeMap 采用 getEntryUsingComparator(key) 方法來根據 key 獲取 Entry。下面是該方法的代碼：
final Entry<K,V> getEntryUsingComparator(Object key) { K k = (K) key; // 獲取該 TreeMap 的 comparator Comparator<? super K> cpr = comparator; if (cpr != null) { // 從根節點開始Entry<K,V> p = root; while (p != null) { // 拿 key 與當前節點的 key 進行比較int cmp = cpr.compare(k, p.key); // 如果 key 小于當前節點的 key，向“左子樹”搜索if (cmp < 0) p = p.left; // 如果 key 大于當前節點的 key，向“右子樹”搜索else if (cmp > 0) p = p.right; // 不大于、不小于，就是找到了目標 Entry else return p; } } return null; }其實 getEntry、getEntryUsingComparator 兩個方法的實現思路完全類似，只是前者對自然排序的 TreeMap 獲取有效，后者對定制排序的 TreeMap 有效。
通過上面源代碼的分析不難看出，TreeMap 這個工具類的實現其實很簡單。或者說：從內部結構來看，TreeMap 本質上就是一棵“紅黑樹”，而 TreeMap 的每個 Entry 就是該紅黑樹的一個節點。
?
原文地址：http://www.ibm.com/developerworks/cn/java/j-lo-tree/
轉載于:https://www.cnblogs.com/davidwang456/p/3631277.html
總結
以上是生活随笔為你收集整理的通过分析 JDK 源代码研究 TreeMap 红黑树算法实现--转的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 探索 ConcurrentHashMap
- 下一篇： Understanding Design