Java – 集合Set – TreeSet集合

简介

TreeSet是不重复、无索引、可排序的集合。可排序是按照元素的默认规则（从小到大）排序

TreeSet集合底层是基于红黑树的数据结构实现排序的，增删改查性能都较好。

TreeSet创建

TreeSet的创建和一般Set集合一样，但唯一不一样的地方是，TreeSet在添加成员后，就会把成员进行排序，所以当遍历输出时，就已是排序好了的状态，而排序所用到的数据结构为红黑树。

TreeSet<Integer> ts = new TreeSet<>();
    ts.add(2);
    ts.add(5);
    ts.add(3);
    ts.add(6);
    ts.add(1);
    ts.add(4);
System.out.println(ts);

此时输出的是 [1, 2, 3, 4, 5, 6]

我们再举个例子，使用字符串，它会以字符串的ASCII码表进行逐个排序

TreeSet<String> ts = new TreeSet<>();
   ts.add("aaa");
   ts.add("abc");
   ts.add("ab");
   ts.add("bcd");
   ts.add("cdc");
   ts.add("caa");
System.out.println(ts);

输出 [aaa, ab, abc, bcd, caa, cdc]

解析：ab排在abc前，是因为，在对比完a和b字符后，有一个串有字符c,而有一个串则没有，而c有对应的的ASCII码，所以认为abc比ab更靠后。

TreeSet排序自定义对象

我们知道TreeSet在添加的时候，就已经对成员进行排序了，添加Integer和String我们知道它的排序方式，可是当我们添加自定义对象时，又会如何呢？

TreeSet<Student> ts = new TreeSet<>();
    Student s1 = new Student("zhangsan",23);
    Student s2 = new Student("lisi",24);
    Student s3 = new Student("wanwu",25);
    Student s4 = new Student("zhaoliu",26);
    ts.add(s1);
    ts.add(s2);
    ts.add(s3);
    ts.add(s4);
System.out.println(ts);

会输出什么呢？答案是会报错的！

因为TreeSet并不知道我们的自定义对象要对比的是什么。

自定义对象实现TreeSet排序

要让自定义对TreeSet排序，需要实现一个排序接口Comparable<T>：

public class Student implements Comparable<Student> { }

@Override
public int compareTo(Student o) {
    return 0;
}

该方法是对比当前需要add() 对象和已在列中的数据进行自定义对比。

@Override
public int compareTo(Student o) {
    return this.getAge() - o.getAge();  
}

我们利用红黑树来对这一段代码进行分析。

1.创建4个红树节点

2.当我们把 ts.add(s1) 时，s1 将为整个红黑树的根节点：

3.当我们开始添加第二个对象时，会执行 compareTo() 方法进行对比

对比时，按照小的放左边，大放右边，0则丢弃的原则

会使 lisi 放在红黑树的右边：

4.接下来开始添加第三个成员 ts.add(s3)

s3 会调用一次 compareTo() 方法和 zhangsan - 23 对比，得出 2 大于 0 ,理应放在右边，但发现右边依然有成员，于是对下一个成员再一次进行对比：

最后对比出来，依然应放在右节点

此时红黑树要进行自平衡处理，

此时的条件是：父节点是红色，且存放在右节点上

我们知道，红黑树如果其下没有节点，那么就会使用黑色的Nil节点进行补充，所以实际上的节点如下：

相当于，叔节点是黑色的，按红黑树的操作，则是把父作为当前节点并左旋

为了保持红黑树平衡规定，把lisi为根节点必须为黑色，同时wanwu也因路径平衡改为黑色

5.最后添加 s4 也会对已存在的成员进行 compareTo() 对比，最后排列如下

关于红黑树知识点，请跳到以下文章进行阅读

Java – 数据结构 – 红黑树

简介 红黑树是一种自平衡的二叉查找树，是计算机科学中月到的一种数据结构 1972年出现，当时被称之为……

2022-12-11

最后附上

比较器 Comparator

通过实现 Comparator 接口可以实现 compareTo 方法不能实现的排序方法，如按字符数排序等等，如：

TreeSet<Student> ts = new TreeSet<>(new Comparator<Student>() {
   @Override
   public int compare(Student o1, Student o2) {
    // o1 为要加入的成员，o2 为已在红黑树中的成员
    // 选对名字的长度进行排序
    int i = o1.getName().length() - o2.getName().length();
    // 如果名字长度一样,则使用年龄进行排序
    i = i == 0 ? o1.getAge() - o2.getAge() : i;
    return i;
   }
  });
  
  Student s1 = new Student("zhangsan",23);
  Student s2 = new Student("lisi",24);
  Student s3 = new Student("wanwu",25);
  Student s4 = new Student("zhaoliu",26);
  ts.add(s1);
  ts.add(s2);
  ts.add(s3);
  ts.add(s4);
  System.out.println(ts);

对 new Comparator<Student> 实现接口进行 lambda 简化

TreeSet<Student> ts = new TreeSet<>((o1, o2)-> {
    // o1 为要加入的成员，o2 为已在红黑树中的成员
    // 选对名字的长度进行排序
    int i = o1.getName().length() - o2.getName().length();
    // 如果名字长度一样,则使用年龄进行排序
    i = i == 0 ? o1.getAge() - o2.getAge() : i;
    return i;
  });