Java TreeSet

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

Java中的TreeSet

它也可以通过在集合创建时提供的比较器来排序，这取决于使用哪个构造函数。TreeSet通过继承AbstractSet类实现了一个NavigableSet接口。

Java中的TreeSet

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

注意

当且仅当相应的类实现了一个可比较的接口时，一个对象才被称为可比较的。
String, StringBuffer类和所有的Wrapper类已经实现了Comparable接口，因此，我们不会得到ClassCastException。但如果我们创建的是用户定义的类或任何没有实现Comparable接口的Java类的TreeSet，我们会得到ClassCastException。要解决这个问题，我们可以在用户定义的类中实现Comparable，或者在创建集合时在构造器中传递Comparator对象。
对于一个空树形集合，当试图插入null作为第一个值时，从JDK 7开始会得到NPE。从JDK 7开始，TreeSet完全不接受null。然而，直到JDK 6，null被接受为第一个值，但在TreeSet中插入更多的null值会导致NullPointerException。因此，它被认为是一个错误，所以在JDK 7中被删除了。
TreeSet是存储大量分类信息的最佳选择，因为它的访问和检索速度较快，所以应该被快速访问。
在TreeSet中插入空值会引发NullPointerException，因为在插入空值的时候，它会与现有的元素进行比较，而空值不能与任何值进行比较。

TreeSet是 如何在内部工作 的？

TreeSet基本上是一个自我平衡的二进制搜索树的实现，就像Red-Black Tree。因此，像添加、删除和搜索这样的操作需要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对象，其中的元素将需要一个外部的指定排序顺序。

语法： 如果我们希望创建一个空的TreeSet，名称为ts，有一个外部的排序现象，那么，它可以被创建为。

TreeSet ts = new TreeSet(Comparator comp);

TreeSet(Collection): 这个构造函数用来建立一个TreeSet对象，其中包含来自给定集合的所有元素，这些元素将以默认的自然排序顺序被存储。简而言之，当需要从任何集合对象转换为TreeSet对象时，就可以使用这个构造函数。

语法： 如果我们希望创建一个名称为ts的TreeSet，那么，它可以按如下方式创建。

TreeSet t = new TreeSet(Collection col);

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

语法： 如果我们希望创建一个名称为ts的TreeSet，那么，它可以按如下方式创建。

TreeSet t = new TreeSet(SortedSet s);

下面是TreeSet类中的方法 ，以表格的形式 描述了 这些方法，以后我们将在实现部分进行展示。

TreeSet实现了SortedSet，因此它可以使用Collection、Set和SortedSet接口中的所有方法。以下是Treeset接口中的方法。在下面的表格中，”？”表示该方法适用于任何类型的对象，包括用户定义的对象。

方法	说明
add(Object o)	这个方法将按照创建TreeSet时提到的相同的排序顺序添加指定的元素。重复的条目将不会被添加。
addAll(Collection c)	这个方法将把指定集合的所有元素添加到集合中。集合中的元素应该是同质的，否则将抛出ClassCastException。集合中重复的条目将不会被添加到TreeSet中。
ceiling?(E e)	该方法返回该集合中大于或等于给定元素的最小元素，如果没有这样的元素，则返回null。
clear()	此方法将删除所有的元素。
clone()	该方法用于返回该集合的一个浅层拷贝，这只是一个简单的复制的集合。
比较器 comparator()	该方法将返回用于对TreeSet中的元素进行排序的比较器，如果使用默认的自然排序顺序，则返回null。
contains(Object o)	如果给定的元素存在于TreeSet中，该方法将返回true，否则将返回false。
descendingIterator?()	该方法返回该集合中元素的迭代器，并以降序排列。
descendingSet?()	此方法返回此集合中包含的元素的反向顺序视图。
first()	如果TreeSet不是空的，该方法将返回TreeSet中的第一个元素，否则将抛出NoSuchElementException。
floor?(E e)	这个方法返回这个集合中小于或等于给定元素的最大元素，如果没有这样的元素，则返回空。
headSet(Object toElement)	此方法将返回TreeSet中小于指定元素的元素。
higher?(E e)	此方法将返回此集合中严格大于给定元素的最小元素，如果没有这样的元素，则返回null。
isEmpty()	如果这个集合不包含任何元素或者是空的，这个方法用来返回真，反之则返回假。
迭代器 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中大于或等于指定元素的元素。

说明： 下面的实现演示了如何创建和使用一个TreeSet。

// Java program to Illustrate Working of  TreeSet 
  
// Importing required utility classes
import java.util.*;
  
// Main class
class GFG {
  
    // Main driver method
    public static void main(String[] args)
    {
        // Creating a Set interface with reference to
        // TreeSet
        Set<String> ts1 = new TreeSet<>();
  
        // Elements are added using add() method
        ts1.add("A");
        ts1.add("B");
        ts1.add("C");
  
        // Duplicates will not get insert
        ts1.add("C");
  
        // Elements get stored in default natural
        // Sorting Order(Ascending)
        System.out.println(ts1);
    }
}

输出

[A, B, C]

实现。

这里我们将对TreeSet对象进行各种操作，以熟悉java中TreeSet的方法和概念。让我们看看如何在TreeSet上执行一些常用的操作。它们被列举如下。

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

现在让我们逐一讨论每一个操作，然后在一个干净的java程序的帮助下进行掌握。

操作1： 添加元素

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

例子

// Java code to Illustrate Addition of Elements to TreeSet
  
// Importing utility classes
import java.util.*;
  
// Main class
class GFG {
  
    // Main driver method
    public static void main(String[] args)
    {
        // Creating a Set interface with
        // reference to TreeSet class
        // Declaring object of string type
        Set<String> ts = new TreeSet<>();
  
        // Elements are added using add() method
        ts.add("Geek");
        ts.add("For");
        ts.add("Geeks");
  
        // Print all elements inside object
        System.out.println(ts);
    }
}

输出

[For, Geek, Geeks]

操作2： 访问元素

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

例子

// Java code to Illustrate Working of TreeSet by
// Accessing the Element of TreeSet
  
// Importing utility classes
import java.util.*;
  
// Main class 
class GFG {
  
    // Main driver method 
    public static void main(String[] args)
    {
        // Creating a NavigableSet object  with 
      // reference to TreeSet class 
        NavigableSet<String> ts = new TreeSet<>();
  
        // Elements are added using add() method
        ts.add("Geek");
        ts.add("For");
        ts.add("Geeks");
  
         // Printing the elements inside the TreeSet object 
        System.out.println("Tree Set is " + ts);
  
        String check = "Geeks";
  
        // Check if the above string exists in
        // the treeset or not
        System.out.println("Contains " + check + " "
                           + ts.contains(check));
  
        // Print the first element in
        // the TreeSet
        System.out.println("First Value " + ts.first());
  
        // Print the last element in
        // the TreeSet
        System.out.println("Last Value " + ts.last());
  
        String val = "Geek";
  
        // Find the values just greater
        // and smaller than the above string
        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 Program to Illustrate Removal of Elements
// in a TreeSet
  
// Importing utility classes
import java.util.*;
  
// Main class
class GFG {
  
    // Main driver method
    public static void main(String[] args)
    {
        // Creating an object of NavigableSet
        // with reference to TreeSet class
        // Declaring object of string type
        NavigableSet<String> ts = new TreeSet<>();
  
        // Elements are added
        // using add() method
        ts.add("Geek");
        ts.add("For");
        ts.add("Geeks");
        ts.add("A");
        ts.add("B");
        ts.add("Z");
  
        // Print and display initial elements of TreeSet
        System.out.println("Initial TreeSet " + ts);
  
        // Removing a specific existing element inserted
        // above
        ts.remove("B");
  
        // Printing the updated TreeSet
        System.out.println("After removing element " + ts);
  
        // Now removing the first element
        // using pollFirst() method
        ts.pollFirst();
  
        // Again printing the updated TreeSet
        System.out.println("After removing first " + ts);
  
        // Removing the last element
        // using pollLast() method
        ts.pollLast();
  
        // Lastly printing the elements of TreeSet remaining
        // to figure out pollLast() method
        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 Program to Illustrate Working of TreeSet
  
// Importing utility classes
import java.util.*;
  
// Main class
class GFG {
  
    // Main driver method
    public static void main(String[] args)
    {
        // Creating an object of Set with reference to
        // TreeSet class
  
        // Note: You can refer above media if geek
        // is confused in programs why we are not
        // directly creating TreeSet object
        Set<String> ts = new TreeSet<>();
  
        // Adding elements in above object
        // using add() method
        ts.add("Geek");
        ts.add("For");
        ts.add("Geeks");
        ts.add("A");
        ts.add("B");
        ts.add("Z");
  
        // Now we will be using for each loop in order
        // to iterate through the TreeSet
        for (String value : ts)
  
            // Printing the values inside the object
            System.out.print(value + ", ");
  
        System.out.println();
    }
}

输出

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

TreeSet的特点

TreeSet实现了SortedSet接口。所以，不允许有重复的值。
TreeSet中的对象是以排序和升序的方式存储的。
TreeSet不保留元素的插入顺序，但元素是按键进行排序的。
如果我们依靠默认的自然排序顺序，被插入到树中的对象应该是同质的和可比较的。TreeSet不允许插入异质的对象。如果我们试图添加异质对象，它会在Runtime抛出一个classCastException。
TreeSet只能接受具有可比性的通用类型。
例如，StringBuffer类实现了可比较接口

// Java code to illustrate What if Heterogeneous 
// Objects are Inserted
  
// Importing all utility classes
import java.util.*;
  
// Main class
class GFG {
  
    // Main driver method
    public static void main(String[] args)
    {
  
        // Object creation
        Set<StringBuffer> ts = new TreeSet<>();
  
        // Adding elements to above object
        // using add() method
        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));
  
        // Note: StringBuffer implements Comparable
        // interface
  
        // Printing the elements
        System.out.println(ts);
    }
}

输出