TreeSet 实现：红黑树上的人生

TreeSet 是 HashSet 的「树版本」

和 HashSet 一样，TreeSet 也是个「空壳」——它把全部操作转发给了 TreeMap：

public class TreeSet<E> extends AbstractSet<E>
        implements NavigableSet<E> {

    private transient NavigableMap<E, Object> m;

    private static final Object PRESENT = new Object();

    // 默认使用 TreeMap（自然顺序）
    public TreeSet() {
        m = new TreeMap<>();
    }

    // 指定比较器
    public TreeSet(Comparator<? super E> comparator) {
        m = new TreeMap<>(comparator);
    }

    public boolean add(E e) {
        return m.put(e, PRESENT) == null;
    }

    public boolean remove(Object o) {
        return m.remove(o) == PRESENT;
    }

    public boolean contains(Object o) {
        return m.containsKey(o);
    }
}

唯一区别是：HashSet 用 HashMap 作底座，TreeSet 用 TreeMap 作底座。

---

为什么需要 TreeMap

TreeSet 解决 HashSet 解决不了的问题：

需求	HashSet	TreeSet
去重	✅	✅
按自然顺序遍历	❌	✅
范围查询（如 > 100 的元素）	❌	✅
找到最大/最小值	❌	✅
找到某个元素的最近邻居	❌	✅

TreeSet 解决的核心问题：需要排序和有序操作时。

---

红黑树：O(log n) 的保证

TreeMap 底层是红黑树——一种自平衡的二叉搜索树。

为什么不用普通二叉搜索树？因为普通 BST 可能退化成链表：

普通 BST（极端情况：已排序数据插入）：
  1
   \
    2
     \
      3
       \
        4     ← 退化成链表，查找 O(n)

红黑树（自动平衡）：
      2（黑）
     / \
   1(红) 3(红)    ← 自动旋转平衡，查找 O(log n)

红黑树通过以下规则保持平衡：

1. 节点非红即黑
2. 根节点是黑
3. 红节点的子节点必须是黑（不能有两个连续红节点）
4. 从根到叶子的每条路径，黑高相同

这些规则保证了：从根到最深叶子 ≤ 最浅叶子 2 倍 → O(log n)。

---

红黑树操作图解

添加元素

TreeSet 添加 8 个整数：5, 3, 7, 1, 4, 6, 8, 2

第1步：插入 5（根节点）
        5

第2步：插入 3（比 5 小，左子树）
        5
       /
      3

第3步：插入 7（比 5 大，右子树）
        5
       / \
      3   7

第4步：插入 1（比 3 小，继续左）
        5
       / \
      3   7
     /
    1
    ...红黑树会自动旋转调整平衡...

有序遍历

红黑树的中序遍历天然有序：

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

// 中序遍历（左 → 根 → 右）
Iterator<Integer> it = set.iterator();
while (it.hasNext()) {
    System.out.print(it.next() + " ");
}
// 输出：1 2 3 4 5 6 7 8  ← 天然升序

---

TreeSet 独有的导航操作

TreeSet 实现了 NavigableSet 接口，提供丰富的导航方法：

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

System.out.println(set.first());           // 1  最小的
System.out.println(set.last());            // 9  最大的

System.out.println(set.lower(5));          // 3  小于 5 的最大
System.out.println(set.higher(5));         // 7  大于 5 的最小

System.out.println(set.floor(6));           // 5  ≤ 6 的最大
System.out.println(set.ceiling(6));        // 7  ≥ 6 的最小

// 范围视图
System.out.println(set.subSet(3, 7));      // [3, 5]  3 ≤ x < 7
System.out.println(set.headSet(5));        // [1, 3]  x < 5
System.out.println(set.tailSet(5));        // [5, 7, 9]  x ≥ 5

HashSet 完全做不到这些操作。

---

两种排序方式

自然排序（元素实现 Comparable）

// Integer、String 等都实现了 Comparable
TreeSet<Integer> natural = new TreeSet<>();
natural.add(3); natural.add(1); natural.add(2);
System.out.println(natural); // [1, 2, 3]

TreeSet<String> words = new TreeSet<>();
words.add("banana"); words.add("apple"); words.add("cherry");
System.out.println(words); // [apple, banana, cherry]

自定义排序（提供 Comparator）

// 按字符串长度排序
TreeSet<String> byLen = new TreeSet<>(
    Comparator.comparingInt(String::length)
);
byLen.add("hi"); byLen.add("banana"); byLen.add("apple");
System.out.println(byLen); // [hi, apple, banana]

// 降序排列
TreeSet<Integer> desc = new TreeSet<>(Collections.reverseOrder());
desc.addAll(Arrays.asList(3, 1, 2, 5, 4));
System.out.println(desc); // [5, 4, 3, 2, 1]

---

null 元素：为什么 TreeSet 不允许

HashSet 允许 null（因为只需 equals 比较）。TreeSet 不允许 null，因为需要比较。

TreeSet<String> set = new TreeSet<>();
set.add(null); // NullPointerException

根因：红黑树需要用比较结果决定元素位置。没有比较规则，null 放不进去。

// 内部比较逻辑（简化）
int compareResult = comparator.compare(existing, newElement);
if (compareResult == 0) { /* 重复 */ }
else if (compareResult < 0) { /* 去左子树 */ }
else { /* 去右子树 */ }
// null 无法参与 compare → NullPointerException

---

线程安全性

TreeSet 非线程安全：

// ❌ 并发修改
TreeSet<Integer> set = new TreeSet<>();
// 线程1: set.add(1)
// 线程2: set.add(2)
// 结果不确定，可能 ConcurrentModificationException

// ✅ 方案：Collections.synchronizedSortedSet
Set<Integer> safe = Collections.synchronizedSortedSet(new TreeSet<>());

// ✅ 更好的方案：ConcurrentSkipListSet（无锁并发）
Set<Integer> concurrent = new ConcurrentSkipListSet<>();

ConcurrentSkipListSet 是 TreeSet 的并发版本，基于跳表实现，支持无锁操作。

---

性能总结

操作	时间复杂度	说明
add	O(log n)	插入到红黑树
remove	O(log n)	从红黑树删除
contains	O(log n)	二叉搜索
first/last	O(log n)	最值查询
lower/higher	O(log n)	邻居查询
遍历	O(n)	中序遍历所有节点

---

总结

要点	说明
本质	TreeMap 的 key 集合
核心能力	排序 + 有序导航操作
底层结构	红黑树（自平衡 BST）
时间复杂度	O(log n)，稳定
null 支持	不允许（需要比较）
线程安全	非安全，用 ConcurrentSkipListSet

一句话：HashSet 管「有没有」，TreeSet 管「排第几」。

---

相关链接

• HashMap 底层实现
• TreeMap 详解
• TreeSet 排序机制
• ConcurrentSkipListSet