TreeSet 与红黑树排序 | JavaSE

TreeSet 与红黑树排序

一、学习目标

完成本章学习后，你应该能够：

  • 能够解释 TreeSet 的核心定位：去重 + 自动排序。
  • 能够说明 TreeSet 与 TreeMap、红黑树之间的关系。
  • 能够使用 TreeSet 对 Integer、Double、String 等具有自然顺序的元素进行排序。
  • 能够解释自然排序（Natural Ordering）与外部比较器排序的基本区别。
  • 能够解释 TreeSet 为什么不能随意保存“不具备比较规则”的自定义对象。
  • 能够理解 TreeSet 判断集合意义上的重复依赖比较结果。
  • 能够解释“比较结果为 0”为什么直接影响 TreeSet 去重。
  • 能够理解 TreeSet 基本操作为什么能够达到 O(log n) 级别。
  • 能够区分 TreeSet 的红黑树与 HashSet 中“哈希桶树化”的红黑树。

二、核心知识

2.1 TreeSet 是什么

TreeSet<E> 是 Set 集合体系中的一个重要实现类。

它的核心特点可以概括为：

不重复
+
无 List 式索引
+
根据比较规则排序

例如：

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

set.add(30);
set.add(10);
set.add(50);
set.add(20);

System.out.println(set);

TreeSet 不会按照：

30 → 10 → 50 → 20

保存遍历顺序。

而会根据整数自身的比较规则形成：

10 → 20 → 30 → 50

因此：

TreeSet 是一个排序 Set。

2.2 TreeSet 与前三种 Set 的区别

可以先整体比较：

| 集合 | 去重 | 遇见顺序 | 自动排序 | | --------------- | ---- | -------------- | -------- | | HashSet | 是 | 不保证 | 否 | | LinkedHashSet | 是 | 确定 | 否 | | TreeSet | 是 | 由比较规则决定 | 是 |

因此数据结构选择的核心问题不同：

只关心去重
→ HashSet

去重 + 保留遇见顺序
→ LinkedHashSet

去重 + 根据大小规则排序
→ TreeSet

2.3 TreeSet 底层依赖 TreeMap

与 HashSet 类似，TreeSet 并没有独立重新实现所有树结构逻辑。

TreeSet 底层基于：

TreeMap

可以建立：

TreeSet
   │
   │ 底层使用
   ▼
TreeMap
   │
   ▼
红黑树

因此：

TreeSet 本质上借助 TreeMap 的 key 排序能力实现有序 Set。

类似 HashSet：

HashSet
↓
HashMap

TreeSet：

TreeSet
↓
TreeMap

这是集合框架中非常漂亮的一种复用设计。

2.4 TreeMap 底层是红黑树

TreeMap 是：

基于红黑树（Red-Black Tree）的有序 Map 实现。

因此 TreeSet 底层最终也利用红黑树维护元素顺序。

抽象成：

          30
        /    \
      10      50
        \    /
        20  40

这不是普通二叉搜索树的简单版本，而是：

一种带有平衡约束的自平衡二叉搜索树。

它通过：

节点颜色
+
旋转
+
重新着色

等机制控制树的高度。

本章的目标不是从零手写红黑树，而是理解：

TreeSet 为什么能持续保持“可排序 + 较高查询效率”。

2.5 为什么不能使用普通二叉搜索树就结束

如果普通二叉搜索树依次插入：

10
20
30
40
50

可能退化为：

10
 \
  20
   \
    30
     \
      40
       \
        50

这已经非常像：

链表

树高可能达到：

O(n)

查找性能也随之下降。

而红黑树通过平衡规则让树高保持在受控范围，从而使：

add
remove
contains

拥有稳定的：

O(log n)

级别性能。

2.6 TreeSet 排序必须有比较规则

如果 TreeSet 想决定：

A 放左边还是右边？

就必须知道：

A 和 B 谁大谁小？

所以 TreeSet 中的元素必须：

能够相互比较。

比较规则来源主要有两种：

元素自己的自然排序
或
TreeSet 外部提供的 Comparator

完整的 Comparable 与 Comparator 体系将在下一章专门学习。

本章先建立 TreeSet 使用模型。

2.7 什么是自然排序

有一些 Java 类型本身已经定义了：

Comparable

因此具有自然顺序。

例如：

Integer
Double
String

它们可以直接放入：

new TreeSet<>()

然后 TreeSet 使用元素自身的：

compareTo()

进行比较。

例如：

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

numbers.add(30);
numbers.add(10);
numbers.add(20);

结果：

10
20
30

2.8 Double 的自然排序

例如：

TreeSet<Double> numbers = new TreeSet<>();

numbers.add(3.14);
numbers.add(1.5);
numbers.add(9.8);
numbers.add(2.6);

TreeSet 会使用 Double 的自然比较规则排列元素。

2.9 String 是如何排序的

原始教学资料常把 String 简化描述成：

按首字符编号排序。

这不够准确。

String 的自然顺序实际上采用：

字典序比较（Lexicographical Comparison）

例如：

TreeSet<String> words = new TreeSet<>();

words.add("ab");
words.add("aa");
words.add("b");
words.add("a");

排序不能只看：

第一个字符

如果第一个字符相同，还会继续比较后面的字符。

概念上：

"a"
"aa"
"ab"
"b"

会按照整个字符串的字典序进行比较。

因此：

TreeSet 排序 String 不是“只比较第一个字符”。

2.10 自定义对象为什么可能无法直接加入 TreeSet

例如：

class Student {
    private String name;
    private int age;
}

然后：

TreeSet<Student> students = new TreeSet<>();

students.add(new Student("张三", 20));
students.add(new Student("李四", 18));

问题出现了：

张三和李四到底谁应该排在前面？

可以：

  • 按年龄；
  • 按姓名；
  • 按成绩；
  • 按学号；

TreeSet 无法凭空猜测你的业务规则。

因此，如果没有能够使用的比较规则，运行时可能出现：

ClassCastException

所以：

自定义对象进入 TreeSet 前，必须解决“如何比较”这个问题。

2.11 TreeSet 的两种排序来源

当前先建立基本结构：

方式一：自然排序

类自己实现：

Comparable<T>

提供：

compareTo()

方式二：比较器排序

创建 TreeSet 时传入：

Comparator<T>

例如：

TreeSet<Student> students =
        new TreeSet<>(comparator);

详细语法、设计原则、多字段排序将在下一章系统展开。

2.12 TreeSet 的“重复”由比较规则决定

这是 TreeSet 与 HashSet 最大的思维差异之一。

HashSet 重点依赖：

hashCode
+
equals

TreeSet 则通过：

compareTo
或
Comparator.compare

比较元素。

如果比较结果：

< 0

说明第一个元素排在第二个之前。

如果：

> 0

说明第一个元素排在第二个之后。

而如果：

== 0

TreeSet 会把两个元素从排序集合角度视为：

同一位置上的元素

因此只保留一个。

这意味着：

TreeSet 的排序规则同时影响排序，也影响去重。

这是本章最重要的知识点之一。

三、使用方法

3.1 Integer 排序

import java.util.TreeSet;

public class TreeSetDemo {
    public static void main(String[] args) {
        TreeSet<Integer> numbers = new TreeSet<>();

        numbers.add(30);
        numbers.add(10);
        numbers.add(50);
        numbers.add(20);
        numbers.add(30);

        System.out.println(numbers);
    }
}

其中第二个：

30

不会形成重复元素。

3.2 String 排序

TreeSet<String> names = new TreeSet<>();

names.add("Tom");
names.add("Alice");
names.add("Bob");
names.add("Amy");

System.out.println(names);

String 自身具有自然比较规则，因此可以直接排序。

3.3 获取最小和最大元素

TreeSet 不只是普通 Set。

它实现了：

NavigableSet

因此具有大量“导航式”查询能力。

例如：

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

numbers.add(10);
numbers.add(30);
numbers.add(20);
numbers.add(40);

System.out.println(numbers.first());
System.out.println(numbers.last());

其中：

first()

返回当前比较顺序中的最小元素。

last()

返回最大元素。

3.4 lower()

numbers.lower(30);

表示：

查找严格小于 30 的最大元素。

例如集合：

10 20 30 40

结果为：

20

3.5 floor()

numbers.floor(30);

表示：

查找小于等于 30 的最大元素。

可能返回：

30

3.6 higher()

numbers.higher(30);

表示：

查找严格大于 30 的最小元素。

结果：

40

3.7 ceiling()

numbers.ceiling(30);

表示：

查找大于等于 30 的最小元素。

可能返回：

30

可以把四个 API 记成：

lower    <
floor    <=

higher   >
ceiling  >=

3.8 降序视图

TreeSet 可以得到：

descendingSet()

例如：

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

numbers.add(10);
numbers.add(20);
numbers.add(30);

System.out.println(numbers.descendingSet());

原顺序：

10 20 30

降序视图：

30 20 10

3.9 使用简单 Comparator

例如暂时需要整数降序：

TreeSet<Integer> numbers =
        new TreeSet<>((a, b) -> Integer.compare(b, a));

这样 TreeSet 的排序方向就被改变。

但是：

Comparator 的完整规范、Lambda 写法、多字段排序和规则组合属于下一章 05-13。

本章只需要知道：

TreeSet 可以从构造器获得外部比较规则。

四、原理与进阶

4.1 TreeSet 添加元素的大致流程

考虑：

set.add(30);
set.add(10);
set.add(50);
set.add(20);

可以概念化为：

准备加入新元素
      ↓
与树中元素比较
      ↓
小于当前节点？
  ↓          ↓
是          否
向左       向右
      ↓
不断比较定位
      ↓
找到插入位置
      ↓
插入节点
      ↓
必要时进行红黑树平衡调整

所以 TreeSet 不需要：

先全部存进去
最后统一 sort()

而是在集合结构维护过程中持续保持比较顺序。

4.2 红黑树的核心目标

红黑树并不是为了：

让所有路径绝对一样高

它是一种近似平衡结构。

核心目标是：

防止普通二叉搜索树严重退化。

因此 TreeSet 的：

add()
contains()
remove()

可以稳定在：

O(log n)

级别。

4.3 TreeSet 的红黑树与 HashSet 的红黑树有什么区别

这是非常重要的区别。

HashSet

核心结构首先是：

哈希表

只有当：

某个哈希桶冲突严重

并达到特定条件时，这个桶才可能：

链表 → 红黑树

红黑树属于：

哈希冲突优化结构。

TreeSet

TreeSet 本身就是：

基于 TreeMap

而 TreeMap 的核心数据结构就是：

红黑树

TreeSet 使用红黑树的目的主要是：

维持比较顺序
+
高效查找

所以二者虽然都出现：

红黑树

但场景完全不同。

4.4 为什么比较结果为 0 会影响去重

假设两个 Student：

张三 18岁
李四 18岁

如果比较器只写：

Integer.compare(s1.getAge(), s2.getAge())

那么两个对象年龄相同：

compare == 0

TreeSet 就会认为：

在这套排序规则中二者等价。

第二个对象可能无法加入。

这意味着：

如果你的业务希望两个同龄学生都保留下来，比较规则不能只比较年龄。

通常还需要：

年龄
↓
姓名
↓
学号

等后续条件继续比较。

详细的“多级比较器设计”将在下一章完成。

4.5 TreeSet 与 equals 的关系

普通 Set 契约从：

equals()

角度定义元素是否相等。

但 TreeSet 实际排序、查找和元素等价判断使用的是：

compareTo()

或者：

Comparator.compare()

因此官方建议：

TreeSet 使用的排序规则应该尽量与 equals 保持一致。

所谓：

consistent with equals

大致要求：

compare(a, b) == 0

与：

a.equals(b)

表达相同的相等关系。

如果二者不一致，TreeSet 本身仍然可能运行，但可能违反一般 Set 契约所期待的相等性语义。

4.6 TreeSet 是否依赖 hashCode

TreeSet 的核心元素定位不是：

hashCode → 哈希桶

而是：

比较 → 左子树 / 右子树

所以：

HashSet

和：

TreeSet

是两套不同的数据结构模型。

可以记成：

HashSet
→ hashCode + equals
→ 哈希表

TreeSet
→ compareTo / Comparator
→ 红黑树

4.7 String 排序为什么不是“只比较首字符”

例如：

"aa"
"ab"

首字符都是：

'a'

如果真的只比较首字符，它们就无法区分。

String 的字典序会继续比较下一字符：

'a' == 'a'
 ↓
继续

'a' < 'b'

于是：

"aa" < "ab"

如果前面所有字符都相同：

"a"
"aa"

较短的字符串排在前面。

因此：

String 自然排序比较的是完整字符序列。

4.8 null 与 TreeSet

自然排序 TreeSet：

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

通常不能直接加入：

null

因为 TreeSet 需要比较元素，而：

null

没有自然排序能力。

调用相关操作时可能抛出：

NullPointerException

如果显式 Comparator 专门设计了 null 比较规则，则属于另外一种情况。

因此不能机械记成：

所有 Set 都能存 null

必须看具体实现和比较器规则。

4.9 JDK 21 的 SequencedSet 与 TreeSet

JDK 21 中 TreeSet 也属于：

SequencedSet

因为它有明确遇见顺序：

按照比较规则从小到大

所以可以：

getFirst()
getLast()
removeFirst()
removeLast()
reversed()

但是 TreeSet 不允许你随意：

addFirst()
addLast()

因为：

TreeSet 中元素位置必须由比较规则决定。

例如：

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

set.addFirst(100);

不能强迫：

100

排在：

1

前面，因为这会破坏 TreeSet 的排序约束。

因此 JDK 21 中：

TreeSet.addFirst()
TreeSet.addLast()

会抛出：

UnsupportedOperationException

这是一个非常典型的：

“接口有这个能力，但具体实现因为语义限制不支持该可选操作”

的例子。

五、实践应用

5.1 不重复且自动排序的数字

例如：

考试分数集合

只希望保存不同分数，并自动按大小排列：

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

非常适合。

5.2 排名候选数据

如果对象：

不允许比较规则上的重复
+
需要持续保持排序

可以考虑 TreeSet。

但排行榜通常还涉及：

同分用户
排名规则
用户唯一性
排名变化

所以 TreeSet 是否适合，需要仔细设计 Comparator，而不能只说：

排行榜 = TreeSet

5.3 区间查询

TreeSet 实现：

NavigableSet

因此非常适合：

找到小于某值的最大元素
找到大于某值的最小元素
取某个范围的数据

例如：

价格区间
成绩区间
时间点集合
版本号集合

这些都属于有序集合擅长的问题。

5.4 TreeSet 与 HashSet 怎么选

如果业务是：

只需要唯一性 + 快速成员判断

优先考虑：

HashSet

如果业务是：

唯一性
+
必须始终保持比较顺序

考虑：

TreeSet

原因是 TreeSet 的基本操作：

O(log n)

而哈希分布良好的 HashSet 基本操作平均：

O(1)

因此：

不需要排序时，不要因为 TreeSet “更高级”就默认使用 TreeSet。

六、常见问题

6.1 TreeSet 是否按照添加顺序保存？

不是。

TreeSet 的顺序由：

自然排序
或
Comparator

决定。

与用户添加顺序无关。

6.2 TreeSet 默认都是升序吗？

如果使用：

new TreeSet<>()

则采用元素的自然排序。

很多常见数字类型的自然顺序表现为：

从小到大

但“默认升序”只是结果表现，真正的机制是：

使用元素的自然顺序。

6.3 String 是否只按照首字符排序？

不是。

String 使用完整字符串的：

字典序

比较。

6.4 为什么 Student 放入 TreeSet 可能报错？

如果：

Student 没有自然比较规则

同时 TreeSet 又没有获得：

Comparator<Student>

就无法确定 Student 之间的大小关系。

因此可能出现：

ClassCastException

6.5 TreeSet 如何判断重复？

它根据：

compareTo()

或者：

Comparator.compare()

的比较结果判断排序意义上的等价。

如果比较结果：

0

TreeSet 会将两个元素视为集合中的同一排序位置。

6.6 TreeSet 去重是否主要依赖 hashCode？

不是。

这是 HashSet 的思路。

TreeSet 核心依赖：

比较规则
+
红黑树

6.7 TreeSet 为什么基本操作不是 O(1)？

因为它不是哈希定位。

查找时需要沿：

红黑树

进行多层比较。

树高度是：

O(log n)

所以基本：

add
remove
contains

也是：

O(log n)

6.8 TreeSet 可以存 null 吗？

不能笼统回答。

自然排序 TreeSet 通常不能处理 null，因为 null 无法参加自然比较。

如果自定义 Comparator 明确支持 null，则需要根据那个 Comparator 的具体规则判断。

6.9 TreeSet 为什么不能 addFirst？

因为：

元素位置

必须由：

比较规则

决定。

程序不能一边要求：

从小到大

一边又强制：

把最大的元素塞到最前面

两种语义冲突。

七、练习与验收

7.1 知识问答

  1. TreeSet 的三个核心特征是什么？
  2. TreeSet 底层基于哪个 Map？
  3. TreeMap 底层是什么数据结构？
  4. 为什么使用红黑树而不是任意普通二叉搜索树？
  5. TreeSet 的基本 add/remove/contains 时间复杂度是什么？
  6. 什么是自然排序？
  7. Integer 为什么可以直接放进 TreeSet？
  8. String 为什么可以直接放入 TreeSet？
  9. String 的排序是不是只比较第一个字符？
  10. 自定义对象为什么可能无法直接放入 TreeSet？
  11. TreeSet 的比较规则来自哪两种方式？
  12. 比较结果小于 0、等于 0、大于 0 分别意味着什么？
  13. 为什么比较结果为 0 会影响 TreeSet 去重？
  14. TreeSet 与 HashSet 判断重复的主要机制有何区别？
  15. TreeSet 的红黑树和 HashSet 桶树化有什么区别？
  16. 为什么 TreeSet 的排序规则最好与 equals 一致？
  17. JDK 21 下为什么 TreeSet 的 addFirst() 不被支持？

7.2 代码阅读

不运行：

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

set.add(30);
set.add(10);
set.add(20);
set.add(30);
set.add(5);

System.out.println(set);
System.out.println(set.first());
System.out.println(set.last());

回答：

  1. 最终集合有几个元素？
  2. 为什么两个 30 只保留一个？
  3. 遍历顺序是什么？
  4. first() 是什么？
  5. last() 是什么？
  6. 这些结论与添加顺序有什么关系？

7.3 手写代码

任务一：数字排序

使用 TreeSet 保存：

50 20 10 30 50 40 20

要求：

  • 自动去重；
  • 自动排序；
  • 输出最小值；
  • 输出最大值；
  • 输出降序视图。

任务二：String 字典序

加入：

ab
aa
b
a
abc

要求：

  1. 先禁止运行，预测顺序；
  2. 解释为什么不能只看第一个字符；
  3. 再运行验证。

任务三：导航查询

建立：

TreeSet<Integer>

包含：

10 20 30 40 50

分别执行：

lower(30)
floor(30)
higher(30)
ceiling(30)

关闭资料写出结果并解释。

7.4 Debug

下面代码：

class Student {
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
}

TreeSet<Student> students = new TreeSet<>();

students.add(new Student("张三", 20));
students.add(new Student("李四", 18));

回答：

  1. 代码为什么可能运行失败？
  2. TreeSet 缺少什么信息？
  3. 有哪两种基本解决方向？
  4. 为什么 TreeSet 无法自己猜测“按年龄还是按姓名”？
  5. 如果只按年龄比较，同龄学生可能出现什么问题？

7.5 综合训练

设计一个课程成绩集合。

Student：

name
age
score

业务要求：

成绩高的排前面
成绩相同，年龄小的排前面
年龄仍然相同，再按姓名决定顺序

要求：

  1. 使用 TreeSet；
  2. 给 TreeSet 提供比较规则；
  3. 加入至少 6 个学生；
  4. 至少设计两个成绩相同的学生；
  5. 验证所有学生是否都能保留；
  6. 故意删除最后一个姓名比较条件；
  7. 观察某些学生为什么可能“消失”。

本题重点观察：

排序规则同时影响 TreeSet 的元素唯一性。

完整的多条件 Comparator 写法将在下一章系统掌握。

7.6 本章验收

关闭资料和 AI 自动补全：

  • [ ] 能准确说出 TreeSet 的核心特点。
  • [ ] 能画出 TreeSet → TreeMap → 红黑树的关系。
  • [ ] 能解释红黑树为什么需要平衡。
  • [ ] 能说出 TreeSet 基本操作的 O(log n) 复杂度。
  • [ ] 能使用 Integer、Double、String 完成自然排序。
  • [ ] 能解释 String 的字典序。
  • [ ] 能解释为什么 Student 默认可能无法排序。
  • [ ] 能说出 Comparable 与 Comparator 两种排序来源。
  • [ ] 能解释比较结果为 0 对 TreeSet 去重的影响。
  • [ ] 能区分 HashSet 的 hashCode/equals 与 TreeSet 的比较规则。
  • [ ] 能区分 TreeSet 红黑树与 HashSet 哈希桶树化。
  • [ ] 能使用 first、last、lower、floor、higher、ceiling。
  • [ ] 能解释 JDK 21 中 TreeSet 为什么不能显式 addFirst/addLast。