TreeMap 是 Java 集合框架中基於紅黑樹實現的有序 Map，繼承 AbstractMap，實現 NavigableMap、Cloneable、Serializable 接口。它按鍵的自然順序或指定 Comparator 排序，核心操作（get、put、remove、containsKey）時間複雜度均為 O(log n)。與 HashMap 不同，TreeMap 不允許 null 鍵（自然排序時），但允許 null 值，且非線程安全，迭代器具備 fail-fast 特性。
紅黑樹是一種自平衡二叉搜索樹，TreeMap 內部節點定義如下：
static final class Entry<K,V> implements Map.Entry<K,V> {
K key; V value;
Entry<K,V> left, right, parent;
boolean color = BLACK; // RED = false, BLACK = true
// 構造器、getKey、getValue、setValue、equals、hashCode、toString...
}
樹的平衡通過左旋、右旋、插入修正、刪除修正四大操作維持，對應源碼方法：
rotateLeft(Entry<K,V> p)rotateRight(Entry<K,V> p)fixAfterInsertion(Entry<K,V> x)fixAfterDeletion(Entry<K,V> x)| 構造函數 | 排序方式 | 適用場景 |
|---|---|---|
TreeMap() | 鍵自然順序 | 鍵實現 Comparable |
TreeMap(Comparator<? super K> c) | 指定比較器 | 鍵不實現 Comparable 或需自定義順序 |
TreeMap(Map<? extends K,? extends V> m) | 自然順序 | 從無序 Map 構建有序 Map |
TreeMap(SortedMap<K,? extends V> m) | 沿用原比較器 | 從有序 Map 高效構建（buildFromSorted） |
buildFromSorted 遞歸取中間元素為根，構建平衡樹，僅最底層節點著紅色，其餘黑色，實現 O(n) 批量構建。
TreeMap 實現 NavigableMap，提供豐富的「鄰近查找」API：
| 方法 | 語義 | 返回 |
|---|---|---|
ceilingEntry(key) | ≥ key 的最小鍵值對 | Entry 或 null |
floorEntry(key) | ≤ key 的最大鍵值對 | Entry 或 null |
higherEntry(key) | > key 的最小鍵值對 | Entry 或 null |
lowerEntry(key) | < key 的最大鍵值對 | Entry 或 null |
firstEntry() / lastEntry() | 最小/最大鍵值對 | Entry 或 null |
pollFirstEntry() / pollLastEntry() | 獲取並移除首/尾條目 | Entry 或 null |
以 getCeilingEntry 為例，從根節點向下搜索，記錄候選答案：
final Entry<K,V> getCeilingEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) { // 目標在左子樹，p 可能是答案
if (p.left != null) p = p.left;
else return p;
} else if (cmp > 0) { // 目標在右子樹
if (p.right != null) p = p.right;
else { // 無右子樹，找父鏈中首個左祖先
Entry<K,V> parent = p.parent, ch = p;
while (parent != null && ch == parent.right) {
ch = parent; parent = parent.parent;
}
return parent;
}
} else return p; // 精確匹配
}
return null;
}
TreeMap 提供四類子映射工廠方法，返回視圖而非副本，操作會反映到原映射：
subMap(fromKey, fromInclusive, toKey, toInclusive)：雙邊界範圍headMap(toKey, inclusive)：首部範圍tailMap(fromKey, inclusive)：尾部範圍descendingMap()：逆序視圖（比較器反轉）內部由 NavigableSubMap 抽象類及其兩個實現 AscendingSubMap、DescendingSubMap 支撐，通過 tooLow/tooHigh 邊界檢查、absLowest/absHighest 邊界定位、fenceKey 終止迭代，實現高效範圍遍歷。
基類 PrivateEntryIterator 維護 next、lastReturned、expectedModCount。關鍵點：
successor(e)（右子樹最左或首個左祖先）predecessor(e)（左子樹最右或首個右祖先）remove() 刪除節點時，若被刪節點有雙子，將 next 指向自身，利用紅黑樹「刪雙子節點實為刪其後繼」特性，保證迭代不漏項writeObject：寫入比較器、大小、所有鍵值對（中序遍歷）readObject：讀取後調用 buildFromSorted 重建平衡樹clone()：淺拷貝比較器，再 buildFromSorted 深拷貝數據
// 1. 鍵值對（推薦）
for (Map.Entry<K,V> e : map.entrySet()) { ... }
// 2. 僅鍵
for (K k : map.keySet()) { V v = map.get(k); ... }
// 3. 僅值
for (V v : map.values()) { ... }
// 4. 逆序鍵
for (K k : map.descendingKeySet()) { ... }
// 5. 範圍遍歷
for (Map.Entry<K,V> e : map.subMap("a", true, "z", false).entrySet()) { ... }
import java.util.*;
public class TreeMapRangeQueryDemo {
public static void main(String[] args) {
TreeMap<Double, String> priceIndex = new TreeMap<>();
priceIndex.put(19.9, "商品A");
priceIndex.put(5.5, "商品B");
priceIndex.put(99.0, "商品C");
priceIndex.put(49.9, "商品D");
// 價格 10~50 區間（含左不含右）
NavigableMap<Double, String> range = priceIndex.subMap(10.0, true, 50.0, false);
System.out.println("10-50 元商品: " + range); // {19.9=商品A, 49.9=商品D}
// 最高價商品
System.out.println("最高價: " + priceIndex.lastEntry()); // 99.0=商品C
// 價格 ≤ 30 的最貴商品
System.out.println("≤30 最貴: " + priceIndex.floorEntry(30.0)); // 19.9=商品A
}
}
TreeMap 以紅黑樹為底座，提供 O(log n) 的有序存取與豐富的導航查詢能力。掌握其 NavigableMap 接口、子映射視圖機制、迭代器與修正算法，能優雅解決「最近鍵查找」「範圍統計」「有序流處理」等高頻業務問題。記住：非線程安全、自然排序拒絕 null 鍵、子映射為視圖 三大特性，生產環境多線程場景請配合 Collections.synchronizedSortedMap 或改用並發有序結構。
