一、TreeSet 类的介绍

TreeSet是使用Tree进行存储的Java中SortedSet接口最重要的实现之一。无论是否提供显式comparator，元素的顺序都由一个集合使用它们的自然顺序来维护。如果要正确实现Set接口，这必须与equals保持一致。

它还可以通过在创建set时提供的Comparator进行排序，这取决于使用的是哪个构造函数。TreeSet通过继承AbstractSet类实现了NavigableSet接口。

从上图可以清楚地看出，导航集扩展了排序集接口。因为集合不保留插入顺序，所以可导航的集合接口提供了通过集合导航的实现。实现可导航集的类是TreeSet，它是一个自平衡树的实现。因此，该接口为我们提供了一种通过该树导航的方法。

Java TreeSet类实现了使用树进行存储的Set接口。它继承了AbstractSet类并实现了NavigableSet接口。TreeSet类的对象按升序存储。

Java TreeSet类的要点如下:

• TreeSet类只包含HashSet这样的唯一元素。
• TreeSet类访问和检索的时间非常快。
• TreeSet类不允许空元素。
• TreeSet类是非同步的。
• TreeSet类保持升序。
• TreeSet类只包含像HashSet一样的唯一元素。
• TreeSet只能允许具有可比性的泛型类型。例如，Comparable接口是由StringBuffer类实现的。

TreeSet类的内部工作：
TreeSet是使用二叉搜索树实现的，它像红黑树一样是自平衡的。因此，搜索、删除、添加等操作需要花费O(log(N))的时间。这背后的原因在于自平衡树。它的存在是为了确保所有提到的操作的树高度不超过O(log(N))。因此，它是一种高效的数据结构，可以保存已排序的大数据并对其进行操作。

TreeSet类的同步：
如上所述，TreeSet类不是同步的。这意味着如果多个线程并发访问一个树集，并且其中一个访问线程修改它，那么必须手动完成同步。通常通过封装集合的对象同步来实现。但是，如果没有找到这样的对象，则必须借助Collections.synchronizedSet()方法包装集合。建议在创建时使用该方法，以避免对集合的非同步访问。下面的代码片段显示了同样的情况。

TreeSet类声明：

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, Serializable    
1

TreeSet类的构造函数：

二、TreeSet 类的操作

2.1 添加操作

为了向TreeSet添加元素，可以使用add()方法。但是，插入顺序不保留在TreeSet中。在内部，对每个元素的值进行比较并按升序排序。我们需要注意的是，不允许重复元素，并且忽略所有重复元素。而且，TreeSet不接受Null值。

实例：

    public static void main(String[] args) {
        //创建集合
        TreeSet<String> ts=new TreeSet<String>();

        //添加元素
        ts.add("广州");
        ts.add("深圳");
        ts.add("佛山");
        ts.add("banana");
        ts.add("apple");
        ts.add("orange");

        // 输出 集合
        System.out.println(ts);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

输出：升序输出

[apple, banana, orange, 佛山, 广州, 深圳]

1
2

2.2 访问操作

添加元素后，如果想访问元素，可以使用内置方法，如contains()、first()、last()等。

 public static void main(String[] args) {
        //创建集合
        TreeSet<String> ts=new TreeSet<String>();

        //添加元素
        ts.add("广州");
        ts.add("深圳");
        ts.add("佛山");


        ts.add("banana");
        ts.add("apple");
        ts.add("orange");

        // 输出 集合
        System.out.println(ts);

        System.out.println("Contains:" + " "
                + ts.contains("佛山"));

        // 输出首元素
        System.out.println("首元素 " + ts.first());

        // 输出尾元素
        System.out.println("尾元素 " + ts.last());

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

输出：

[apple, banana, orange, 佛山, 广州, 深圳]
Contains: true
首元素 apple
尾元素 深圳
1
2
3
4

2.3 删除操作

可以使用remove()方法从TreeSet中删除这些值。还有其他各种方法可用于删除第一个值或最后一个值。
实例：

public static void main(String[] args) {
        //创建集合
        TreeSet<String> ts=new TreeSet<String>();

        //添加元素
        ts.add("广州");
        ts.add("深圳");
        ts.add("佛山");


        ts.add("banana");
        ts.add("apple");
        ts.add("orange");

        // 输出 集合
        System.out.println(ts);

        ts.remove("佛山");

        // 输出 删除 “佛山"
        System.out.println("删除 ”佛山“： " + ts);

        // 删除首个元素
        ts.pollFirst();

        // 输出 删除首个：
        System.out.println("删除首部： " + ts);

        // 删除 尾部元素
        ts.pollLast();

        //
        System.out.println("删除尾部" + ts);



    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

输出：

[apple, banana, orange, 佛山, 广州, 深圳]
删除后的： [apple, banana, orange, 广州, 深圳]
删除首部： [banana, orange, 广州, 深圳]
删除尾部[banana, orange, 广州]
1
2
3
4

2.4 迭代操作

有多种方法可以遍历TreeSet。最著名的方法是使用增强的for循环。对于极客来说，当你在TreeSet上练习问题时，你会用这种方法迭代元素，因为这是最常用的树，地图和图形问题。

实例：

    public static void main(String[] args) {
        //创建集合
        TreeSet<String> ts=new TreeSet<String>();

        //添加元素
        ts.add("广州");
        ts.add("深圳");
        ts.add("佛山");


        ts.add("banana");
        ts.add("apple");
        ts.add("orange");

        // 输出 集合
        System.out.println(ts);

        for (String value : ts)

            // 输出
            System.out.print(value + ", ");

        System.out.println();



    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

输出：

[apple, banana, orange, 佛山, 广州, 深圳]
apple, banana, orange, 佛山, 广州, 深圳, 
1
2

三、TreeSet 类的源码分析

待续