您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

TreeMap 源碼深度解析：紅黑樹實現、自然序與定製序、關鍵操作遞歸圖解

編輯：Java 綜合教學

TreeMap 源碼深度解析：紅黑樹實現、自然序與定製序、關鍵操作遞歸圖解

TreeMap 是 Java 集合框架中基於紅黑樹實現的有序 Map，保證鍵有序、單次操作 O(log n)。本文從比較器策略、節點結構、插入/刪除/查找核心邏輯、紅黑樹修復旋轉、遍歷迭代器五大維度，配合源碼片段與 ASCII 圖解，徹底講透 TreeMap 內部機制。

一、兩種排序策略：Comparable vs Comparator

// 構造函數決定比較策略
public TreeMap() { comparator = null; } // 自然序：鍵需實現 Comparable
public TreeMap(Comparator comparator) { this.comparator = comparator; } // 定製序

// put 時的比較邏輯
Comparator cpr = comparator;
if (cpr != null) {
    cmp = cpr.compare(key, t.key); // 定製比較器
} else {
    @SuppressWarnings("unchecked")
    Comparable k = (Comparable) key;
    cmp = k.compareTo(t.key); // 自然序
}

選型指南

自然序：鍵類型固有排序語義 (Integer、String、LocalDate 等)，實現 Comparable，通用性強
定製序：需多種排序規則、鍵不可修改 (第三方類)、臨時排序邏輯，傳入 Comparator 策略模式

二、紅黑樹節點結構：雙向鏈表 + 顏色標記

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;
    }
}

紅黑樹五大性質 (不變量)

節點非紅即黑
根節點黑
葉子節點 (null/NIL) 黑
紅節點的子節點必黑 (無連續紅)
任一節點到所有葉子的黑高度相等

三、插入操作：BST 定位 + 紅黑修復

流程圖解

put(key, value)
  ↓
根為空? → 創建根節點 (黑) → 返回
  ↓
BST 查找定位父節點 parent
  ↓
鍵已存在? → 更新值 → 返回舊值
  ↓
創建新節點 e (紅)，掛在 parent 左/右
  ↓
fixAfterInsertion(e) → 紅黑修復核心
  ↓
size++ → 返回 null

修復邏輯三種情況 (叔父節點顏色決定)

while (e != root && e.parent.color == RED) {
    if (e.parent == e.parent.parent.left) { // 父是左孩子
        Entry y = e.parent.parent.right; // 叔父
        if (y != null && y.color == RED) { // 情況1：叔父紅 → 變色
            e.parent.color = BLACK;
            y.color = BLACK;
            e.parent.parent.color = RED;
            e = e.parent.parent; // 向上繼續檢查
        } else { // 叔父黑/無
            if (e == e.parent.right) { // 情況2：內側插入 → 左旋轉父
                e = e.parent;
                rotateLeft(e);
            }
            // 情況3：外側插入 → 變色 + 右旋轉祖父
            e.parent.color = BLACK;
            e.parent.parent.color = RED;
            rotateRight(e.parent.parent);
        }
    } else { // 父是右孩子，鏡像邏輯
        // ... 左右互換
    }
}
root.color = BLACK; // 根永遠黑

四、刪除操作：後繼節點替換 + 紅黑修復

關鍵步驟

BST 查找目標節點 p
若 p 有雙子節點 → 找直接後繼 s (右子樹最左) → 複製 s 數據到 p → 轉而刪除 s (s 至多一個子節點)
replacement = p 的非空子節點 (或 null)
用 replacement 替換 p 在父節點中的位置
若 p 原為黑 → fixAfterDeletion(replacement)

刪除修復四種情況

while (x != root && colorOf(x) == BLACK) {
    if (x == x.parent.left) { // x 是左孩子
        Entry w = x.parent.right; // 兄弟
        if (colorOf(w) == RED) { // 情況1：兄弟紅 → 變色 + 左旋父
            w.color = BLACK;
            x.parent.color = RED;
            rotateLeft(x.parent);
            w = x.parent.right;
        }
        if (colorOf(w.left) == BLACK && colorOf(w.right) == BLACK) { // 情況2：兄弟雙黑子 → 兄弟變紅 + 向上
            w.color = RED;
            x = x.parent;
        } else {
            if (colorOf(w.right) == BLACK) { // 情況3：兄弟左紅右黑 → 兄弟右旋 + 變色
                w.left.color = BLACK;
                w.color = RED;
                rotateRight(w);
                w = x.parent.right;
            }
            // 情況4：兄弟右紅 → 父色給兄弟 + 父變黑 + 右侄變黑 + 左旋父
            w.color = colorOf(x.parent);
            x.parent.color = BLACK;
            w.right.color = BLACK;
            rotateLeft(x.parent);
            x = root; // 結束循環
        }
    } else { // 鏡像邏輯
        // ...
    }
}
if (x != null) x.color = BLACK;

五、遍歷迭代器：中序遍歷 + 雙向鏈表


場景建議


頻繁範圍查詢TreeMap 優於 HashMap + 排序
高併發寫入ConcurrentSkipListMap (跳表，無鎖/細粒度鎖)
鍵為自定義對象必須實現 Comparable 或傳 Comparator，保證一致性 (equals 與 compareTo 一致)
大量鍵重複插入put 返回舊值，避免創建新 Entry 對象
序列化/反序列化紅黑樹結構序列化開銷大，考慮 JSON 扁平化存儲




「TreeMap 將紅黑樹這一經典數據結構工程化為通用集合，其源碼中『雙向導航 + 顏色標記 + 旋轉修復』的模式，是學習平衡樹實現的最佳教材。掌握其修復邏輯，面試手寫紅黑樹插入/刪除不再是夢魘。」