treeset（TreeSet：Java中最有用的数据结构）

作者：旎旎生活时间：2023-06-15T12:22:31 阅读数：88079人阅读

TreeSet是Java Collection Framework（JCF）的一部分，它实现了Set接口（无序，不允许重复元素），并能够自动按照自然顺序或指定顺序进行排序。它内部采用红黑树（Red-Black Tree）这种自平衡二叉搜索树（Self-Balanced Binary Search Tree），因此具有快速添加、删除、查询等操作的特点。本文将介绍TreeSet的基本用法以及其他几个使用TreeSet的有用案例。

基本用法

使用TreeSet非常简单，只需按如下步骤即可：

创建一个TreeSet。
添加元素到TreeSet中。
使用Iterator（迭代器）或者for-each语句遍历集合。

按照自然顺序排序

Java中的所有基本类型都实现了Comparable接口，因此可以使用这个接口定义的compareTo方法来比较对象。基于这个接口，TreeSet默认按照自然顺序排序。例如，下面的代码将按照升序排列元素：

TreeSet<Integer> set = new TreeSet<>();
set.add(3);
set.add(1);
set.add(2);
for (int i : set) {
    System.out.println(i);
}

上述代码将输出1，2，3。

按顺序排列

除了按照自然顺序排序，TreeSet还可以按照指定的顺序排序。为了实现这个功能，TreeSet的构造函数可以接受一个Comparator参数。Comparator是一个函数式接口，定义了一个用于比较两个对象的方法。例如，下面的代码依靠Comparator来按照长度排序字符串：

TreeSet<String> set = new TreeSet<>(new Comparator<String>() {
    @Override
    public int compare(String s1, String s2) {
        return Integer.compare(s1.length(), s2.length());
    }
});
set.add(\"fox\");
set.add(\"dog\");
set.add(\"elephant\");
for (String s : set) {
    System.out.println(s);
}

上述代码将输出\"fox\"，\"dog\"，\"elephant\"。请注意，set的元素不是按照字符串本身的自然顺序排列的，而是按照长度进行排列的。

使用TreeSet实现基于时间的调度

TreeSet非常适合实现基于时间的调度程序。下面的代码演示如何使用TreeSet实现一个简单的调度程序：

class Task implements Comparable<Task> {
    private long time;
    private String name;
    public Task(long time, String name) {
        this.time = time;
        this.name = name;
    }
    public String getName() {
        return name;
    }
    public long getTime() {
        return time;
    }
    @Override
    public int compareTo(Task o) {
        return Long.compare(time, o.time);
    }
}
public class Schedule {
    private TreeSet<Task> set = new TreeSet<>();
    public void addTask(long time, String name) {
        set.add(new Task(time, name));
    }
    public void run(long currenttime) {
        while (!set.isEmpty() && set.first().getTime() <= currenttime) {
            Task t = set.pollFirst();
            System.out.println(currenttime + \": \" + t.getName());
        }
    }
    public static void main(String[] args) {
        Schedule s = new Schedule();
        s.addTask(1000, \"Task 1\");
        s.addTask(2000, \"Task 2\");
        s.addTask(1500, \"Task 3\");
        s.run(1500);
    }
}

上述代码会在调用run方法时输出\"1500: Task 1\"和\"1500: Task 3\"。这个程序通过不断地把最早进行的任务从TreeSet中取出来来实现调度。

使用TreeSet实现排行榜

还可以使用TreeSet来实现排行榜。下面的代码演示了如何使用TreeSet实现一个TopK问题，即从一堆数据中找出最大的K个数：

public class TopK {
    private final int K;
    private TreeSet<Integer> set = new TreeSet<>();
    public TopK(int K) {
        this.K = K;
    }
    public void add(int n) {
        set.add(n);
        if (set.size() > K) {
            set.pollFirst();
        }
    }
    public List<Integer> result() {
        return new ArrayList<>(set);
    }
    public static void main(String[] args) {
        TopK t = new TopK(3);
        t.add(2);
        t.add(3);
        t.add(1);
        t.add(4);
        t.add(7);
        t.add(5);
        System.out.println(t.result());
    }
}

上述代码将输出[5, 7, 4]，这是输入中的最大的3个数。