深入理解 Java 中的 TreeSet 集合

深入理解 Java 中的 TreeSet 集合

TreeSet 是 Java 集合框架中的一种集合类，它基于 TreeMap 实现，底层使用了红黑树这一平衡二叉搜索树结构。TreeSet 提供了一种确保元素有序且不重复的集合，它在排序和去重方面非常有用。在这篇文章中，我们将深入了解 TreeSet 的特点、基本用法、以及如何通过自然排序和比较器排序进行元素排序。

---

TreeSet 集合概述和特点

• 不可存储重复元素：TreeSet 不允许存储重复的元素。如果试图添加重复的元素，则会被忽略。
• 没有索引：与 ArrayList 不同，TreeSet 不能通过索引访问元素。它是基于树结构的集合，所有的操作（如查找、插入、删除）都遵循树的规则。
• 有序存储：TreeSet 可以将元素按照一定的规则进行排序，主要有以下两种方式：
  • TreeSet()：默认使用元素的自然排序（Comparable）。
  • TreeSet(Comparator comparator)：通过自定义比较器（Comparator）进行排序。

TreeSet 集合基本使用

我们先来看一个简单的例子，如何使用 TreeSet 存储 Integer 类型的元素，并遍历它们：

import java.util.TreeSet;public class TreeSetDemo01 {public static void main(String[] args) {// 创建集合对象TreeSet<Integer> ts = new TreeSet<Integer>();// 添加元素ts.add(10);ts.add(40);ts.add(30);ts.add(50);ts.add(20);ts.add(30); // 重复元素，不会被添加// 遍历集合for (Integer i : ts) {System.out.println(i); // 输出结果：[10, 20, 30, 40, 50]}}
}

在上面的例子中，TreeSet 自动对元素进行排序，并确保集合中没有重复的元素。

---

自然排序（Comparable）的使用

接下来我们看一个更复杂的例子，如何使用 TreeSet 存储自定义对象。在此案例中，我们存储 Student 对象并要求按年龄升序排序，若年龄相同，则按姓名的字母顺序排序。

实现步骤

第一步：添加第一个元素 wangwu (25)

• 添加对象：new Student("wangwu", 25)

• 树的状态：

  • 这是树中的第一个节点，因此 wangwu 作为根节点。
  • 根据红黑树的性质，根节点必须是黑色。

  图示：

  

  • 初始插入时，wangwu (25) 是红色节点。
  • 由于是第一个节点，调整为黑色节点。

    wangwu (25, 黑)

第二步：添加第二个元素 lisi (24)

• 添加对象：new Student("lisi", 24)

• 插入过程：

  • 与根节点 wangwu (25) 进行比较：
    • 24 < 25，lisi 应该插入到 wangwu 的左子树中。
    • 新插入的节点默认是红色。

  图示：

  

  • 插入后，lisi (24) 为红色节点，wangwu (25) 仍然为黑色。

      wangwu (25, 黑)/lisi (24, 红)

第三步：添加第三个元素 zhangsan (23)

• 添加对象：new Student("zhangsan", 23)

• 插入过程：

  

  • 首先与根节点 wangwu (25) 比较：
    • 23 < 25，继续向左，进入左子树。
  • 再与 lisi (24) 比较：
    • 23 < 24，因此 zhangsan 应插入到 lisi 的左子树中。
    • 新插入的节点默认是红色。
  • 此时，lisi 和 zhangsan 都是红色，违反了红黑树中不能有两个连续红色节点的规则，需要进行调整。

调整过程：

• 对 lisi (24) 进行右旋，lisi 变为黑色，zhangsan (23) 保持红色。

图示：

      lisi (24, 黑)/     \
zhangsan (23, 红)   wangwu (25, 红)

第四步：添加第四个元素 zhaoliu (26)

• 添加对象：new Student("zhaoliu", 26)
• 插入过程：
  • 首先与根节点 lisi (24) 比较：
    • 26 > 24，因此向右，进入右子树。
  • 再与 wangwu (25) 比较：
    • 26 > 25，所以 zhaoliu 应插入到 wangwu 的右子树中。
    • 新插入的节点默认是红色。

调整过程：

• 此时 wangwu 为红色，zhaoliu 也是红色，违反了两个连续红色节点的规则。
• 为了修复此违反，执行以下步骤：
  • 将 wangwu (25) 变为黑色，将根节点 lisi (24) 变为红色，zhaoliu (26) 保持红色。

图示：

        lisi (24, 红)/       \
zhangsan (23, 黑) wangwu (25, 黑)\zhaoliu (26, 红)

代码实现

学生类：

public class Student implements Comparable<Student> {private String name;private int age;public Student(String name, int age) {this.name = name;this.age = age;}public String getName() {return name;}public int getAge() {return age;}@Overridepublic String toString() {return "Student{" +"name='" + name + '\'' +", age=" + age +'}';}@Overridepublic int compareTo(Student o) {// 按照年龄排序int result = this.age - o.age;// 如果年龄相同，按姓名的字母顺序排序return result == 0 ? this.name.compareTo(o.getName()) : result;}
}

测试类：

import java.util.TreeSet;public class MyTreeSet2 {public static void main(String[] args) {// 创建集合对象TreeSet<Student> ts = new TreeSet<>();// 添加学生对象ts.add(new Student("wangwu", 25));ts.add(new Student("lisi", 24));ts.add(new Student("zhangsan", 23));ts.add(new Student("zhaoliu", 26));// 遍历集合for (Student student : ts) {System.out.println(student);}}
}

在这个示例中，我们使用 compareTo 方法来定义排序规则：首先按年龄排序，若年龄相同，则按姓名字母顺序排序。这样，TreeSet 会自动对 Student 对象进行排序。

---

比较器排序（Comparator）的使用

有时，我们希望能够动态指定排序规则，而不是在类中实现 Comparable 接口。这时可以使用 Comparator 接口，利用 TreeSet 的带参构造函数传入排序规则。

案例需求

存储 Teacher 对象，并要求按年龄升序排序，若年龄相同，则按姓名字母顺序排序。

实现步骤

1. 使用 TreeSet 的带参构造方法，传递 Comparator 对象来指定排序规则。
2. 重写 compare 方法，定义排序规则。

代码实现

老师类：

public class Teacher {private String name;private int age;public Teacher(String name, int age) {this.name = name;this.age = age;}public String getName() {return name;}public int getAge() {return age;}@Overridepublic String toString() {return "Teacher{" +"name='" + name + '\'' +", age=" + age +'}';}
}

测试类：

import java.util.Comparator;
import java.util.TreeSet;public class MyTreeSet4 {public static void main(String[] args) {// 创建集合对象，使用比较器排序TreeSet<Teacher> ts = new TreeSet<>(new Comparator<Teacher>() {@Overridepublic int compare(Teacher o1, Teacher o2) {// 按照年龄排序int result = o1.getAge() - o2.getAge();// 如果年龄相同，按姓名字母顺序排序return result == 0 ? o1.getName().compareTo(o2.getName()) : result;}});// 添加老师对象ts.add(new Teacher("zhangsan", 23));ts.add(new Teacher("lisi", 22));ts.add(new Teacher("wangwu", 24));ts.add(new Teacher("zhaoliu", 24));// 遍历集合for (Teacher teacher : ts) {System.out.println(teacher);}}
}

在这个示例中，我们通过 TreeSet 的构造函数传递 Comparator 对象，从而定义排序规则。这样，即使不修改 Teacher 类，我们也能灵活地对其进行排序。

---

两种比较方式总结

1. 自然排序 (Comparable)：

   • 让自定义类实现 Comparable 接口，并重写 compareTo 方法来定义排序规则。
   • 适用于对象的类本身具备稳定的排序逻辑。

2. 比较器排序 (Comparator)：

   • 在创建 TreeSet 对象时传递 Comparator 的实现类对象来定义排序规则。
   • 适用于需要灵活更改排序逻辑，或者类本身不方便实现 Comparable 的情况。

返回值规则

• 返回值为负数：表示当前存入的元素较小，存储在左子树。
• 返回值为0：表示当前存入的元素与已有元素重复，不存储。
• 返回值为正数：表示当前存入的元素较大，存储在右子树。

总结

compareTo` 方法来定义排序规则。

• 适用于对象的类本身具备稳定的排序逻辑。

2. 比较器排序 (Comparator)：
   • 在创建 TreeSet 对象时传递 Comparator 的实现类对象来定义排序规则。
   • 适用于需要灵活更改排序逻辑，或者类本身不方便实现 Comparable 的情况。

返回值规则

• 返回值为负数：表示当前存入的元素较小，存储在左子树。
• 返回值为0：表示当前存入的元素与已有元素重复，不存储。
• 返回值为正数：表示当前存入的元素较大，存储在右子树。

总结

TreeSet 是 Java 中非常有用的集合类，可以用来对元素进行自动排序和去重。它的两种排序方式（自然排序和比较器排序）使得 TreeSet 在处理复杂对象的排序时非常灵活。理解并灵活运用 Comparable 和 Comparator，可以帮助我们更好地控制集合中的元素顺序和行为。