TreeSet简介
1| 概述
java.util.TreeSet<E> 是 可自动排序、不允许重复元素 的集合，实现了 NavigableSet<E>、Cloneable、Serializable。
核心特点：
| 特性 | 说明 |
|---|---|
| 有序 | 元素按 自然顺序（Comparable）或 自定义 Comparator 升序排列 |
| 底层结构 | 红黑树（内部其实是包装了一棵 TreeMap<E,Object>） |
| 操作复杂度 | 增删查 O(logn) |
| 接口丰富 | 支持最值、邻近、范围视图、反序视图等导航操作 |
2|底层原理 & 数据结构
2.1 红黑树 (Red‑Black Tree)
- 每个节点保存：
key、左子/右子、父节点、颜色位 - 插入/删除后通过 左旋/右旋 + 重新着色 保证：
- 根为黑
- 所有叶子（NIL）为黑
- 红节点的子节点都为黑
- 根到每个叶子路径的黑节点数相同
- 树高 ≤
2log2(n+1)⇒ 操作最坏O(logn)
2.2 TreeSet = TreeMap ⤴︎
public class TreeSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable {
private transient NavigableMap<E,Object> m; private static final Object PRESENT = new Object(); ... public boolean add(E e) { return m.put(e, PRESENT)==null; }}
3| 排序规则
- 默认：元素必须实现
Comparable<E>，按compareTo升序。 - 自定义：构造时传入
Comparator<? superE>；允许存储 “不具可比性” 的对象或自定义排序（降序、按长度等）。
⚠️ 无论哪种排序，一旦确定就应“不可变”：比较规则改变或元素自身值变动会破坏树形结构。
4| 常用 API 速览
| 分类 | 方法 | 说明 |
|---|---|---|
| 增删查 | add(e) / remove(o) / contains(o) |
|
addAll(c) / clear() / size() |
||
| 最值 | first() / last() |
最小 / 最大 |
| 邻近 | lower(e) / higher(e) |
<e / >e |
floor(e) / ceiling(e) |
≤e / ≥e |
|
| 区间视图 | subSet(fromIncl, toExcl) |
[from, to) |
headSet(toExcl) / tailSet(fromIncl) |
||
| 反序 | descendingSet() / descendingIterator() |
|
| 遍历 | iterator() (升序) |
Fail‑fast |
| 并行流 (8+) | stream() / parallelStream() |
5| 复杂度与性能
| 操作 | 复杂度 | 说明 |
|---|---|---|
add / remove / contains |
O(logn) | 红黑树查找深度 |
first / last / floor / ceiling |
O(logn) | |
遍历 (iterator) |
O(n) | 元素按排序顺序输出 |
5.1 TreeSet vs. 其他集合
| 需求 | 首选 |
|---|---|
| 唯一性 + 无序快速查找 | HashSet (O(1) 平均) |
| 唯一性 + 有序/邻近/区间 | TreeSet (O(logn)) |
| 并发 + 有序 | ConcurrentSkipListSet (跳表) |
常数因子：
TreeSet内部节点对象多 1 个引用 + 1 byte 颜色，占用更高，速度略低于HashSet。
6|线程安全 & Fail‑fast
- 非线程安全：多线程并发写需显式加锁或使用
Collections.synchronizedSortedSet(set)包装，或改用ConcurrentSkipListSet。 - Fail‑fast：迭代期间结构若被 其他线程或方法 修改，迭代器抛
ConcurrentModificationException（早期发现 BUG，不保证强一致）。
7| 易踩坑注意事项
| ⚠️ 事项 | 说明 |
|---|---|
禁止 null 元素 |
若使用自然顺序，插入 null 抛 NullPointerException（JDK≥1.8）；若自定义 Comparator 必须显式处理 null。 |
| 元素可变性 | 将“会变的字段”作为排序关键时，修改后集合顺序被破坏，影响查找——典型 坑。 ➜ 元素应当不可变或 删除‑修改‑再插入。 |
| 比较器一致性 | compare(a,b)==0 必须等价于 a.equals(b)，否则“看似重复”元素会并存。 |
| 子视图联动 | 通过 subSet / headSet 返回的是 实时视图，对其操作会同步影响原集合，反之亦然。 |
8| 典型使用场景
- 最近值 / 最近房价
int target = 100;
Integer lo = set.floor(target); // <=100 的最大
Integer hi = set.ceiling(target); // >=100 的最小
```2. **滑动窗口 + 单调有序**
统计区间最小/最大值：维护 `TreeSet<Integer>` 或 `TreeMap<Integer, Integer>` 计数。
3. **区间调度**
会议室安排、日程冲突检测：用 `floor` 查看前一场结束时间是否 > 新场开始。
4. **去重排序**
读取大量字符串后按字典序输出且无重复。
5. **近似搜索 / 前缀索引**
`subSet("abc", "abd")` 获取所有 `"abc*"` 前缀匹配词。
6. **合并区间 / 连通块**
利用 `lower` / `floor` 找相邻区间，快速合并。
---
## 9| 示例代码
```java
import java.util.*;
public class TreeSetDemo {
public static void main(String[] args) { // 1⃣️ 价格排行榜（升序）
TreeSet<Integer> prices = new TreeSet<>(Arrays.asList(105, 98, 120, 110)); System.out.println("最低价：" + prices.first()); // 98
System.out.println("最高价：" + prices.last()); // 120
// 2⃣️ 找最接近 108 的价格
int target = 108; Integer lower = prices.floor(target); // 105 Integer higher = prices.ceiling(target); // 110 System.out.println(lower + ", " + higher);
// 3⃣️ 区间视图：100~115 的价格
System.out.println(prices.subSet(100, true, 115, true)); // [105, 110]
// 4⃣️ 滑动窗口最大值 (k=3)：
int[] nums = {4, 2, 12, 3, 8, 5}; int k = 3; TreeMap<Integer, Integer> window = new TreeMap<>(); for (int i = 0; i < nums.length; i++) { window.merge(nums[i], 1, Integer::sum); if (i >= k) { // 移除窗口左端
int out = nums[i - k]; window.merge(out, -1, (old, n) -> old + n == 0 ? null : old + n); } if (i >= k - 1) System.out.print(window.lastKey() + " "); // 12 12 12 8 } }}
10| 总结
- 红黑树实现的有序集合：所有操作
O(logn)，支持最值/邻近/区间检索 - 应用：最近值查询、窗口最值、日程冲突检测、去重排序
- 注意：禁止
null、避免“可变键”、多线程需同步 - 与
HashSet比：牺牲常数速度，换来 排序 + 导航；与PriorityQueue比：支持删除任意元素与邻近搜索 - 对于并发高读写且需有序，可选
ConcurrentSkipListSet（跳表）。
🌟 如果你需要“唯一 + 排序 + 范围操作”这三件套，
TreeSet基本就是 Java 标准库里最顺手的工具。