TreeMap（ソートされた Map） — 範囲検索
TreeMap は Java の Map 実装のひとつで、キーを自動的にソートして保持するのが特徴です。
初心者が理解すべきポイントは「キーが常に昇順に並ぶ」「範囲検索が簡単にできる」ということです。ここでは例題を交えて解説します。
TreeMap の特徴
- 内部構造: 赤黒木（バランス木）で実装。
- キーが常にソートされる: デフォルトは昇順。
Comparatorを渡せば独自順序も可能。 - 検索性能: 基本操作（put/get/remove）は O(log n)。
- 範囲検索が得意:
subMap,headMap,tailMapで部分範囲を簡単に取得できる。 - 用途: 「ソート済みの辞書」「範囲検索」「ランキング管理」など。
基本コード例
1. 作成と追加
import java.util.TreeMap;
public class TreeMapDemo {
public static void main(String[] args) {
TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "Cherry");
map.put(1, "Apple");
map.put(2, "Banana");
System.out.println(map); // {1=Apple, 2=Banana, 3=Cherry}
}
}
👉 キーが自動的に昇順に並ぶ。
2. 範囲検索（部分取得）
TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "Ten");
map.put(20, "Twenty");
map.put(30, "Thirty");
map.put(40, "Forty");
// 20以上30未満の範囲
System.out.println(map.subMap(20, 30)); // {20=Twenty}
// 30以下の範囲
System.out.println(map.headMap(30)); // {10=Ten, 20=Twenty}
// 20以上の範囲
System.out.println(map.tailMap(20)); // {20=Twenty, 30=Thirty, 40=Forty}
3. 最小・最大キーの取得
System.out.println(map.firstKey()); // 10
System.out.println(map.lastKey()); // 40
4. 近いキーの検索
System.out.println(map.lowerKey(25)); // 20（指定値より小さい最大のキー）
System.out.println(map.higherKey(25)); // 30（指定値より大きい最小のキー）
System.out.println(map.floorKey(20)); // 20（指定値以下の最大キー）
System.out.println(map.ceilingKey(20)); // 20（指定値以上の最小キー）
👉 範囲検索や近似検索が簡単にできる。
性能の考え方
| 操作 | 計算量 | 特徴 |
|---|---|---|
| put/get/remove | O(log n) | 木構造で検索 |
| 範囲検索 | O(log n + k) | k は取得件数 |
| 順序付き走査 | O(n) | 昇順で取り出し可能 |
👉 HashMap より遅いが、順序や範囲検索が必要なら TreeMap が有利。
例題で練習
例題1: 成績管理（点数でソート）
TreeMap<Integer, String> scores = new TreeMap<>();
scores.put(85, "Tanaka");
scores.put(92, "Sato");
scores.put(74, "Suzuki");
// 80点以上の学生
System.out.println(scores.tailMap(80)); // {85=Tanaka, 92=Sato}
例題2: 日付ごとのイベント管理
import java.time.LocalDate;
import java.util.TreeMap;
TreeMap<LocalDate, String> events = new TreeMap<>();
events.put(LocalDate.of(2025, 12, 1), "Meeting");
events.put(LocalDate.of(2025, 12, 5), "Workshop");
events.put(LocalDate.of(2025, 12, 10), "Conference");
// 12月1日〜5日の範囲
System.out.println(events.subMap(
LocalDate.of(2025, 12, 1),
LocalDate.of(2025, 12, 6)
));
// {2025-12-01=Meeting, 2025-12-05=Workshop}
テンプレート集
作成
TreeMap<KeyType, ValueType> map = new TreeMap<>();
範囲検索
map.subMap(fromKey, toKey); // fromKey <= key < toKey
map.headMap(toKey); // key < toKey
map.tailMap(fromKey); // key >= fromKey
最小・最大キー
map.firstKey();
map.lastKey();
近似検索
map.lowerKey(key); // keyより小さい最大キー
map.higherKey(key); // keyより大きい最小キー
map.floorKey(key); // key以下の最大キー
map.ceilingKey(key); // key以上の最小キー
実務でのコツ
- 範囲検索が必要なら TreeMap: HashMap ではできない。
- 順序付きデータ: 日付・点数・IDなど「自然順序」があるキーに最適。
- Comparator で独自順序: 逆順や複雑な並び替えも可能。
- 大量データ: O(log n) なので、数百万件でも現実的。
まとめ
- TreeMap は「ソートされた Map」。
- 範囲検索や近似検索が簡単にできる。
- HashMap より遅いが、順序が必要なら TreeMap が有利。
👉 練習課題として「日付をキーにしたイベント管理」を作り、指定期間のイベントを範囲検索してみると、TreeMap の便利さが体感できます。