Java TreeSet

TreeSet 是基於 TreeMap 實作的有序集合，元素會自動排序且不重複。

引入套件

import java.util.TreeSet;

建立 TreeSet

// 自然排序
TreeSet<Integer> set1 = new TreeSet<>();

// 自訂排序（反向）
TreeSet<Integer> set2 = new TreeSet<>(Comparator.reverseOrder());

// 從其他集合建立
TreeSet<Integer> set3 = new TreeSet<>(Arrays.asList(3, 1, 2));

基本操作

TreeSet<Integer> set = new TreeSet<>();

// 新增
set.add(3);
set.add(1);
set.add(2);

// 自動排序
System.out.println(set);  // [1, 2, 3]

// 檢查與移除
boolean has = set.contains(2);  // true
set.remove(2);

導航方法

TreeSet<Integer> set = new TreeSet<>(Arrays.asList(1, 3, 5, 7, 9));

// 第一個和最後一個
Integer first = set.first();  // 1
Integer last = set.last();    // 9

// 比較
Integer lower = set.lower(5);    // 3（< 5）
Integer higher = set.higher(5);  // 7（> 5）
Integer floor = set.floor(4);    // 3（<= 4）
Integer ceiling = set.ceiling(4); // 5（>= 4）

// 取得並移除
Integer pollFirst = set.pollFirst();  // 1
Integer pollLast = set.pollLast();    // 9

範圍操作

TreeSet<Integer> set = new TreeSet<>(Arrays.asList(1, 2, 3, 4, 5));

// 子集合
SortedSet<Integer> sub = set.subSet(2, 4);  // [2, 3]

// 含兩端
NavigableSet<Integer> sub2 = set.subSet(2, true, 4, true);  // [2, 3, 4]

// 小於
SortedSet<Integer> head = set.headSet(3);  // [1, 2]

// 大於等於
SortedSet<Integer> tail = set.tailSet(3);  // [3, 4, 5]

// 反向
NavigableSet<Integer> desc = set.descendingSet();  // [5, 4, 3, 2, 1]

自訂排序

// 字串按長度排序
TreeSet<String> set = new TreeSet<>(
    Comparator.comparingInt(String::length)
        .thenComparing(Comparator.naturalOrder())
);

set.add("AAA");
set.add("A");
set.add("BB");
set.add("B");

System.out.println(set);  // [A, B, BB, AAA]

HashSet vs TreeSet

實用範例

自動排序的排行榜

record Player(String name, int score) implements Comparable<Player> {
    @Override
    public int compareTo(Player other) {
        return Integer.compare(other.score, this.score);  // 高分在前
    }
}

TreeSet<Player> leaderboard = new TreeSet<>();
leaderboard.add(new Player("Alice", 100));
leaderboard.add(new Player("Bob", 150));
leaderboard.add(new Player("Charlie", 80));

leaderboard.forEach(System.out::println);
// Player[name=Bob, score=150]
// Player[name=Alice, score=100]
// Player[name=Charlie, score=80]

重點整理

• TreeSet 自動排序且不重複
• 基於紅黑樹，操作為 O(log n)
• 提供導航方法（first, last, lower, higher...）
• 支援範圍查詢
• 元素不能為 null
• 需要排序的集合使用 TreeSet