Java中的TreeSet

TreeSet是Java中SortedSet接口最重要的实现之一，它使用树来存储。元素的排序是通过使用它们的自然排序来维护的，无论是否提供了显式比较器。如果要正确实现Set接口，则必须与equals保持一致。

Java中的TreeSet

根据所使用的构造函数，它也可以通过在设置创建时提供比较器进行排序。TreeSet通过继承AbstractSet类实现NavigableSet接口。

Java中的TreeSet

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

注意：

如果对应的类实现了 Comparable接口 ，则对象才能被称为可比较的。
String、StringBuffer类和所有包装器类已经实现了Comparable接口，因此我们不会得到ClassCastException异常。但是，如果我们创建的是用户定义的类或任何不实现可比较接口的Java类的TreeSet，我们将得到ClassCastException异常。为了解决这个问题，我们可以在用户定义的类中实现Comparable，或在创建集合时将Comparator对象传递给构造函数。
对于一个空的TreeSet，在尝试将null插入为第一个值时，会从JDK 7中得到NPE。从JDK 7开始，TreeSet根本不接受null。但是，在JDK 6之前，null被接受为第一个值，但任何更多的空值插入TreeSet都会导致NullPointerException。因此，它被认为是一个bug，并在JDK 7中被删除了。
TreeSet是存储大量经过排序的信息并应快速访问的优秀选择，因为它具有更快的访问和检索时间。
将null值插入TreeSet会引发NullPointerException，因为在插入null时，它会与现有元素进行比较，而null不能与任何值进行比较。

TreeSet如何在内部工作？

TreeSet基本上是自平衡二叉搜索树的一种实现，例如红黑树。因此，添加、删除和搜索等操作需要O(log(N))时间。原因是在自平衡树中，确保树的高度在所有操作中始终为O(log(N))。因此，这被认为是存储巨大排序数据并对其执行操作的最有效的数据结构之一。但是，像以排序顺序打印N个元素这样的操作需要O(N)时间。

现在让我们先讨论同步的TreeSet TreeSet的实现不是同步的。这意味着如果多个线程同时访问一个树集，并且其中至少一个线程修改了该集合，则必须在外部进行同步。通常这是通过同步一些自然封装了集合的对象来实现的。如果不存在这样的对象，则应使用Collections.synchronizedSortedSet方法“包装”集合。最好在创建时完成此操作，以防止意外未同步访问集合。可以如下所示实现：

TreeSet ts = new TreeSet(); 
Set syncSet = Collections.synchronziedSet(ts);

TreeSet类的构造函数如下：

为了创建一个TreeSet，我们需要创建一个TreeSet类的对象。TreeSet类包含各种构造函数，允许可能创建TreeSet。以下是此类中可用的构造函数：

TreeSet(): 此构造函数用于构建一个空的TreeSet对象，其中元素将以默认自然排序顺序存储。

语法： 如果我们希望创建一个名为ts的空TreeSet，则可以创建如下：

TreeSet ts = new TreeSet();

TreeSet(Comparator): 此构造函数用于构建一个空的TreeSet对象，其中元素需要外部指定排序顺序。

语法： 如果我们希望创建一个名为ts的空TreeSet，并具有外部排序现象，则可以创建如下：

TreeSet ts = new TreeSet(Comparator comp);

TreeSet(Collection): 此构造函数用于构建包含给定集合中所有元素的TreeSet对象，其中元素将以默认自然排序顺序存储。简而言之，此构造函数用于将任何Collection对象转换为TreeSet对象时使用。

语法： 如果我们希望创建具有名称ts的TreeSet，则可以创建如下：

TreeSet t = new TreeSet(Collection col);

TreeSet(SortedSet): 此构造函数用于构建包含给定sortedset中所有元素的TreeSet对象，其中元素将以默认自然排序顺序存储。简而言之，此构造函数用于将SortedSet对象转换为TreeSet对象。

语法： 如果我们希望创建具有名称ts的TreeSet，则可以创建如下：

TreeSet t = new TreeSet(SortedSet s);

TreeSet类中的方法如下所示： 在表格格式中展示，后面将实现展示在实现部分中。 TreeSet实现了SortedSet，因此具有Collection、Set和SortedSet接口中所有方法的可用性。以下是Treeset接口中的方法。在下表中，“?”表示该方法适用于任何类型的对象，包括用户定义的对象。

方法	描述
add(Object o)	根据创建TreeSet时给定的排序顺序，将指定元素添加到集合中。重复的元素不会被添加。
addAll(Collection c)	将指定Collection中所有元素添加到集合中。Collection中的元素应该是同类型的，否则会抛出ClassCastException异常。重复的元素将不会被添加到TreeSet中。
ceiling?(E e)	返回集合中大于或等于指定元素的最小元素，如果该元素不存在则返回null。
clear()	删除集合中的所有元素。
clone()	返回集合的浅层副本。
Comparator comparator()	返回用于对TreeSet进行排序的比较器，如果使用默认的自然排序，则返回null。
contains(Object o)	如果指定元素在TreeSet中存在，则返回true，否则返回false。
descendingIterator?()	返回一个迭代器，该迭代器以降序遍历集合中的元素。
descendingSet?()	返回TreeSet中包含元素的逆序视图。
first()	如果TreeSet不为空，则返回TreeSet中的第一个元素，否则抛出NoSuchElementException异常。
floor?(E e)	返回集合中小于或等于指定元素的最大元素，如果该元素不存在则返回null。
headSet(Object toElement)	返回小于指定元素的元素组成的TreeSet子集。
higher?(E e)	返回严格大于指定元素的最小元素，如果该元素不存在，则返回null。
isEmpty()	如果该集合为空，则返回true，否则返回false。
Iterator iterator()	返回用于迭代集合元素的迭代器。
last()	如果TreeSet不为空，则返回TreeSet中的最后一个元素，否则抛出NoSuchElementException异常。
lower?(E e)	返回严格小于指定元素的最大元素，如果该元素不存在，则返回null。
pollFirst?()	获取并删除集合中的第一个（最低）元素，如果集合为空，则返回null。
pollLast?()	获取并删除集合中的最后一个（最高）元素，如果集合为空，则返回null。
remove(Object o)	从集合中删除指定元素。
size()	返回集合的大小或集合中元素的数量。
spliterator()	以后期绑定和快速失败机制遍历集合元素并创建Spliterator。
	subSet(Object fromElement, Object toElement) \| 此方法将返回从fromElement到toElement的元素。fromElement是包含的，而toElement是不包含的。
—	—
tailSet(Object fromElement)	此方法将返回TreeSet中大于或等于指定元素的元素。

Illustration: 下面的实现演示了如何创建和使用TreeSet。

// Java程序演示TreeSet的工作原理
  
// 导入所需的工具类
import java.util.*;
  
// 主类
class GFG {
  
    // 主驱动程序
    public static void main(String[] args)
    {
        // 使用TreeSet创建Set接口的引用
        Set<String> ts1 = new TreeSet<>();
  
        // 使用add()方法添加元素
        ts1.add("A");
        ts1.add("B");
        ts1.add("C");
  
        // 重复元素不会插入
        ts1.add("C");
  
        // 元素按默认的自然排序
        // 存储顺序升序排列
        System.out.println(ts1);
    }
}

输出:

[A, B, C]

Implementation:

在这里，我们将对TreeSet对象执行各种操作，以熟悉TreeSet在Java中的方法和概念。让我们看看如何在TreeSet上执行几个经常使用的操作。它们列在下面：

添加元素
访问元素
删除元素
遍历元素

现在让我们逐个讨论每个操作，同时借助简洁的Java程序进行理解。

Operation 1: 添加元素

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

示例

// Java代码演示将元素添加到TreeSet中
  
// 导入工具类
import java.util.*;
  
// 主类
class GFG {
  
    // 主驱动程序
    public static void main(String[] args)
    {
        // 创建Set接口，
        // 引用TreeSet类
        // 声明字符串类型的对象
        Set<String> ts = new TreeSet<>();
  
        // 使用add()方法添加元素
        ts.add("Geek");
        ts.add("For");
        ts.add("Geeks");
  
        // 打印对象中的所有元素
        System.out.println(ts);
    }
}

输出:

[For, Geek, Geeks]

Operation 2: 访问元素

添加元素后，如果我们希望访问元素，我们可以使用类似contains()，first()，last()等内置方法。

示例

// 用Java代码阐述TreeSet的工作方式，通过访问TreeSet的元素

// 导入实用类
import java.util.*;

// 主类
class GFG {

    // 主驱动程序方法
    public static void main(String[] args)
    {
        // 创建NavigableSet对象，引用TreeSet类
        NavigableSet<String> ts = new TreeSet<>();

        // 使用add()方法添加元素
        ts.add("Geek");
        ts.add("For");
        ts.add("Geeks");

        // 打印TreeSet对象内的元素
        System.out.println("Tree Set is " + ts);

        String check = "Geeks";

        // 检查上述字符串是否在TreeSet中
        System.out.println("Contains " + check + " " + ts.contains(check));

        // 打印TreeSet中的第一个元素
        System.out.println("First Value " + ts.first());

        // 打印TreeSet中的最后一个元素
        System.out.println("Last Value " + ts.last());

        String val = "Geek";

        // 找出比上述字符串更大和更小的值
        System.out.println("Higher " + ts.higher(val));
        System.out.println("Lower " + ts.lower(val));
    }
}

输出：

Tree Set is [For, Geek, Geeks]
Contains Geeks true
First Value For
Last Value Geeks
Higher Geeks
Lower For

操作3： 删除值

可以使用remove()方法从TreeSet中删除值。有多种其他方法可用于删除第一个值或最后一个值。

示例

// Java程序说明TreeSet中的元素删除

// 导入实用类
import java.util.*;

// 主类
class GFG {

    // 主驱动程序方法
    public static void main(String[] args)
    {
        // 创建NavigableSet对象，引用TreeSet类
        // 声明字符串类型对象
        NavigableSet<String> ts = new TreeSet<>();

        // 使用add()方法添加元素
        ts.add("Geek");
        ts.add("For");
        ts.add("Geeks");
        ts.add("A");
        ts.add("B");
        ts.add("Z");

        // 打印并显示TreeSet的初始元素
        System.out.println("Initial TreeSet " + ts);

        // 删除插入的特定现有元素
        ts.remove("B");

        // 打印更新后的TreeSet
        System.out.println("After removing element " + ts);

        // 现在使用pollFirst()方法删除第一个元素
        ts.pollFirst();

        // 再次打印更新后的TreeSet
        System.out.println("After removing first " + ts);

        // 使用pollLast()方法删除最后一个元素
        ts.pollLast();

        // 最后打印剩余TreeSet的元素，以找出pollLast()方法的作用
        System.out.println("After removing last " + ts);
    }
}

输出：

Initial TreeSet [A, B, For, Geek, Geeks, Z]
After removing element [A, For, Geek, Geeks, Z]
After removing first [For, Geek, Geeks, Z]
After removing last [For, Geek, Geeks]

操作4： 通过TreeSet迭代

有多种迭代TreeSet的方式。其中最著名的是使用增强的for循环。而且在练习使用TreeSet解决树、映射和图形问题时，大多数人都会使用这种方法迭代元素。

示例

 // Java程序演示TreeSet的工作原理
  
// 导入工具类
import java.util.*;
  
// 主类
class GFG {
  
    // 主方法
    public static void main(String[] args)
    {
        // 创建一个具有TreeSet类的引用的Set对象
  
        // 注意:如果Geek在程序中感到困惑，为什么我们不直接创建TreeSet对象，请参考上面的示例程序
        Set<String> ts = new TreeSet<>();
  
        // 使用add()方法将元素添加到以上对象中
        ts.add("Geek");
        ts.add("For");
        ts.add("Geeks");
        ts.add("A");
        ts.add("B");
        ts.add("Z");
  
        // 现在我们将使用forEach循环来遍历TreeSet
        for (String value : ts)
  
            // 打印对象中的值
            System.out.print(value + ", ");
  
        System.out.println();
    }
}

输出:

A, B, For, Geek, Geeks, Z,

TreeSet的特点:

TreeSet实现了 SortedSet 接口。所以不允许重复的值。
TreeSet中的对象按排序和升序存储。
TreeSet不保留元素的插入顺序，但按键排序元素。
如果我们依赖默认的自然排序顺序，则插入到树中的对象应该是同类的可比较的。TreeSet不允许插入异构对象。如果我们尝试添加异构对象，它将在运行时抛出 ClassCastException。
TreeSet只能接受可比较的泛型类型。
例如，StringBuffer类实现Comparable接口

 // Java示例：插入异构对象会发生什么
  
// 导入所有的工具类
import java.util.*;
  
// 主类
class GFG {
  
    // 主方法
    public static void main(String[] args)
    {
  
        // 对象创建
        Set<StringBuffer> ts = new TreeSet<>();
  
        // 使用add()方法将元素添加到以上对象中
        ts.add(new StringBuffer("A"));
        ts.add(new StringBuffer("Z"));
        ts.add(new StringBuffer("L"));
        ts.add(new StringBuffer("B"));
        ts.add(new StringBuffer("O"));
        ts.add(new StringBuffer(1));
  
        // 注意：StringBuffer实现Comparable接口
  
        // 打印元素
        System.out.println(ts);
    }
}