TreeSet

ℹ️定位说明

Set 系列第 3 篇。红黑树实现：自动排序 + 范围查询。关键差异：去重依据是 compareTo()/compare() 返回 0，而不是 equals()——存自定义对象前先想清楚比较逻辑。数据结构基础见 04-Map系列/07-红黑树。

TreeSet 是 Java 集合框架中 NavigableSet 接口的实现类，基于 红黑树（Red-Black Tree） 数据结构实现，支持元素自然排序或定制排序，并提供高效的范围查询能力。

一、核心原理与数据结构

1. 底层实现

红黑树：TreeSet 基于 TreeMap 实现，元素作为键（Key）存储，值（Value）统一为静态占位符 PRESENT。红黑树是一种自平衡二叉搜索树，通过节点颜色标记和旋转操作保证树的高度平衡，确保插入、删除、查询操作的时间复杂度均为 O(log n)。
排序规则：
- 自然排序：元素需实现 Comparable 接口（如 Integer、String）。
- 定制排序：通过构造函数传入 Comparator 实现自定义排序逻辑。

TreeSet源码分析

2. 排序与比较逻辑

元素比较：

  // 自然排序示例（元素需实现 Comparable）
  TreeSet<Integer> set = new TreeSet<>(); // 按整数自然顺序排序
  set.add(3);
  set.add(1);
  set.add(2);
  System.out.println(set); // 输出 [1, 2, 3]

  // 定制排序示例（通过 Comparator 逆序）
  TreeSet<Integer> reversedSet = new TreeSet<>(Comparator.reverseOrder());
  reversedSet.add(3);
  reversedSet.add(1);
  reversedSet.add(2);
  System.out.println(reversedSet); // 输出 [3, 2, 1]

注意事项：
- 元素必须实现 Comparable 接口或通过 Comparator 指定比较规则，否则抛出 ClassCastException。
- equals() 与 compareTo() 的一致性：若元素的 compareTo() 方法与 equals() 逻辑不一致，可能导致TreeSet 中出现 “逻辑重复” 的元素（compareTo() 返回 0 但 equals() 返回 false）。

二、关键特性

1. 有序性与范围查询

有序遍历：元素按排序规则升序排列，遍历时按此顺序返回。
范围操作：

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

  // 范围查询
  SortedSet<Integer> subset = set.subSet(3, 7); // 返回 [3, 5]（左闭右开）
  NavigableSet<Integer> headSet = set.headSet(5, true); // 返回 ≤5 的元素：[1, 3, 5]

  // 边界查询
  Integer lower = set.lower(5); // 返回小于 5 的最大元素：3
  Integer higher = set.higher(5); // 返回大于 5 的最小元素：7
  Integer floor = set.floor(6); // 返回 ≤6 的最大元素：5
  Integer ceiling = set.ceiling(6); // 返回 ≥6 的最小元素：7

2. 性能表现

时间复杂度：插入、删除、查询操作均为 O(log n)，优于链表（O (n)），但略低于哈希表（O (1)）。
空间开销：每个节点需额外存储父节点、左右子节点及颜色标记，内存占用高于 HashSet 和 LinkedHashSet。

3. 线程安全性

非线程安全：多线程环境下需手动同步（如使用 Collections.synchronizedSortedSet() 包装）。

三、适用场景

1. 需要排序的去重场景

典型场景：数值统计（如排行榜）、时间戳去重（按时间顺序）。

  TreeSet<Integer> scores = new TreeSet<>();
  scores.addAll(Arrays.asList(85, 92, 78, 92, 88));
  System.out.println(scores); // 输出 [78, 85, 88, 92]（自动去重并排序）

2. 范围查询与边界查找

范围统计：如查询年龄在 20~30 岁之间的用户。

  TreeSet<Integer> ages = new TreeSet<>(Arrays.asList(22, 18, 25, 30, 35));
  Set<Integer> youngUsers = ages.subSet(20, 31); // 返回 [22, 25, 30]

3. 自然排序与定制排序

定制排序规则：

  // 按字符串长度排序
  TreeSet<String> words = new TreeSet<>(Comparator.comparingInt(String::length));
  words.addAll(Arrays.asList("apple", "banana", "grape", "kiwi"));
  System.out.println(words); // 输出 [kiwi, apple, grape, banana]

四、与其他 Set 实现类对比

维度	HashSet	LinkedHashSet	TreeSet
数据结构	哈希表（HashMap）	哈希表 + 双向链表（LinkedHashMap）	红黑树（TreeMap）
元素顺序	无序（不可预测）	按插入顺序有序	按自然 / 定制顺序排序
null 支持	允许 1 个 null	允许 1 个 null	不允许 null（插入抛 NPE）
时间复杂度	O (1)（插入 / 查询）	O (1)（插入 / 查询）	O (log n)（插入 / 查询）
空间开销	低（仅哈希表）	中（哈希表 + 链表指针）	高（树节点指针 + 颜色标记）
适用场景	快速去重、无需顺序	需保留插入顺序的去重	需排序或范围查询的场景

五、注意事项与最佳实践

元素必须可比较
- 自定义类需实现 Comparable 接口或通过 Comparator 指定比较规则。

   class User implements Comparable<User> {
       private int age;
       @Override
       public int compareTo(User other) {
           return Integer.compare(this.age, other.age); // 按年龄排序
       }
   }

避免使用 null
- TreeSet 不支持 null 元素，插入 null 会抛出 NullPointerException。
范围操作的性能
- 范围查询（如 subSet()）返回视图而非副本，操作效率高，但修改原集合可能影响视图。
合理选择集合类型
- 若无需排序，优先用 HashSet；若需插入顺序，用 LinkedHashSet；仅在需要排序或范围查询时使用 TreeSet。

总结

`TreeSet` 通过红黑树实现了有序集合，提供高效的排序和范围查询能力，适用于需要对元素进行自然排序或定制排序的场景。相比 `HashSet` 和 `LinkedHashSet`，其插入、查询性能略低，但支持强大的范围操作（如 `subSet()`、`lower()`、`higher()`）。合理利用 TreeSet 的排序特性，可简化业务逻辑（如排行榜、区间筛选），但需注意元素的可比性及性能开销。

⬅️ LinkedHashSet 🏠 00-Java ➡️ TreeSet源码分析

03-TreeSet