Java 集合源碼剖析：TreeMap 紅黑樹實現深度解析

TreeMap 基於紅黑樹實現，保證鍵有序、單操作 O(log n) 復雜度。本文剖析節點結構、構造器策略、插入刪除調整、與 HashMap 核心差異。

紅黑樹性質回顧

1. 節點非紅即黑
2. 根節點黑
3. 葉子節點 (NIL) 黑
4. 紅節點子節點必黑 (無連續紅)
5. 任一節點到所有葉子的黑高度相等

→ 任意路徑長度 ≤ 2 × 最短路徑，近似平衡。

Entry 節點結構

static final class Entry implements Map.Entry {
    K key; V value;
    Entry left, right, parent;
    boolean color = BLACK;  // 新節點默認紅，構造器中設置
    
    Entry(K key, V value, Entry parent) {
        this.key = key; this.value = value; this.parent = parent;
    }
    // getKey/setValue/getValue 等 Map.Entry 方法
}

四大構造器策略

批量構建優化：buildFromSorted

// SortedMap 構造器調用
buildFromSorted(size, iterator, null, null);
// 利用已有序序列，線性時間構建平衡紅黑樹
// 避免逐個插入的 O(n log n) 開銷

插入操作：put()

1. 空樹 → 新節點作根，染黑
2. 非空樹 → BST 插入找到父節點，新節點染紅
3. 調用 fixAfterInsertion(entry) 恢復紅黑性質

// 旋轉 + 重著色核心邏輯
private void fixAfterInsertion(Entry x) {
    x.color = RED;
    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(grandParentOf(x))) {
            Entry y = rightOf(grandParentOf(x)); // 叔節點
            if (colorOf(y) == RED) {  // Case 1: 叔紅 → 父/叔染黑、祖父染紅、向上繼續
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(grandParentOf(x), RED);
                x = grandParentOf(x);
            } else {
                if (x == rightOf(parentOf(x))) { // Case 2: 內側插入 → 先左旋轉父
                    x = parentOf(x);
                    rotateLeft(x);
                }
                // Case 3: 外側插入 → 父染黑、祖父染紅、右旋轉祖父
                setColor(parentOf(x), BLACK);
                setColor(grandParentOf(x), RED);
                rotateRight(grandParentOf(x));
            }
        } else { // 鏡像情況：父是右孩子
            // 對稱邏輯...
        }
    }
    root.color = BLACK;
}

刪除操作：deleteEntry()

1. 雙子節點 → 找後繼節點替換鍵值，轉為刪除後繼節點 (最多單子)
2. 單/無子節點 → 直接用子節點 (或 null) 替換被刪節點
3. 若被刪節點黑 → fixAfterDeletion(replacement) 恢復黑高平衡

刪除調整最複雜，涉及 4 大情況、兄弟節點顏色、侄節點顏色組合，核心思想：向下傳遞黑色額外權重，通過旋轉/重著色消化。

TreeMap vs HashMap 核心差異

TreeSet 關係

TreeSet 內部持有 NavigableMap (實為 TreeMap)，所有操作委託給 Map，PRESENT = new Object() 作為統一 Value。

性能調優建議

• 大批量構建 → 用 TreeMap(SortedMap) 或先排序數組再 buildFromSorted
• 頻繁範圍查詢 → 善用 subMap/headMap/tailMap 視圖，無需複製
• 併發環境 → 無線程安全版本，需外部同步或用 ConcurrentSkipListMap
• Key 為長字符串 → 考慮自定義 Comparator 避免重複比較開銷