Java 中的树集

Java 提供了大量的数据结构来有效地处理元素集合。其中一种数据结构是 TreeSet，它是 Java 中红黑树的实现。TreeSet维护存储唯一元素的排序顺序。初学者可能会发现最初使用 Java TreeSet类有点困难。在本文中，我们将了解如何使用TreeSet，解释其核心概念并提供代码示例来帮助您开始将TreeSet合并到 Java 项目中。

TreeSet结构：红黑树

正如我们之前提到的，Java TreeSet类结构被实现为一种称为红黑树的自平衡二叉搜索树。让我们解释一下这是什么...红黑树代表一种平衡的二分搜索数据结构，通常用于存储和组织排序数据。它的名字来源于维持其平衡的特性：

• 树中的每个节点都是红色或黑色。
• 红黑树的根始终是黑色的。
• 所有叶节点（NIL 节点或空链接）都是黑色的。
• 如果树的一个节点是红色的，那么它的子节点是黑色的。
• 从节点到其后代节点的每条简单路径都包含相同数量的黑色节点。

红黑树通过确保平衡，在插入、删除和元素查找操作方面表现出高效的性能。这保证了树的高度与它所包含的节点数的对数成正比，从而导致操作的时间复杂度为对数。红黑树在各个领域都有广泛的应用，包括编程语言中平衡搜索树的实现、数据库（例如内部索引结构）以及其他需要对排序数据进行高效存储和操作的场景。

TreeSet的特点和缺点

TreeSet提供了几个关键功能，使其成为以排序方式管理对象集合的宝贵工具。优点：

• 按排序顺序自动维护元素。添加或删除元素时，树结构会进行调整以保持它们的排序。这消除了手动排序的需要，并提供了按升序或降序排列的高效访问。
• 高效的搜索、插入和删除操作。它利用二叉搜索树结构，使这些操作的时间复杂度为O(log N)。这里N是元素的数量。
• TreeSet通过利用元素的自然顺序或自定义Comparator来保证元素的唯一性。当处理需要不同元素的集合时，这非常有用。

限制：

• 由于保持排序顺序，比HashSet稍慢。
• 不允许空元素，因为它依赖于自然排序或自定义比较器进行元素比较。

Java TreeSet：主要操作示例

现在让我们演示如何在 Java 中创建TreeSet、获取集合的大小、向其中添加元素、从中删除元素以及检查元素是否在 TreeSet中。这些代码示例演示了使用TreeSet时的主要操作：创建实例、添加元素、删除元素、检查元素是否存在以及获取 TreeSet 的大小。创建TreeSet实例并添加元素：

// Creating a TreeSet of Integer type
TreeSet<Integer> numbers = new TreeSet<>();

// Adding elements to the TreeSet
numbers.add(18);
numbers.add(2);
numbers.add(7);
numbers.add(28);

System.out.println(numbers); // Output: [2, 7, 18, 28]

这里我们使用add()方法在TreeSet中添加 4 个数字。如果我们创建一个main方法并运行该程序，输出将按排序顺序 (2, 7, 18, 28)。从TreeSet中删除元素：

TreeSet<String> names = new TreeSet<>();

names.add("Johnny");
names.add("Ivy");
names.add("David");
names.add("Ricky");

// Removing an element from the TreeSet
names.remove("David");

System.out.println(names); // Output: [Ivy, Johnny, Ricky]

检查TreeSet 中是否存在元素：

TreeSet<String> musicalInstrument = new TreeSet<>();

musicalInstrument.add("Piano");
musicalInstrument.add("Drums");
musicalInstrumentfruits.add("Violin");
musicalInstrument.add("Double Bass");

// Checking if an element exists in the TreeSet
boolean containsPiano = musicalInstrument.contains("Piano");
boolean containsCello = musicalInstrument.contains("Cello");

System.out.println(containsPiano); // Output: true
System.out.println(containsCello); // Output: false

获取TreeSet 的大小：

TreeSet<Character> letters = new TreeSet<>();

letters.add('A');
letters.add('B');
letters.add('C');
letters.add('D');

// Getting the size of the TreeSet
int size = letters.size();

System.out.println(size); // Output: 4

TreeSet 中的排序和迭代

Java 中的TreeSet提供了用于对元素集合进行排序和迭代的强大功能。在本节中，我们将探索对元素进行排序、迭代TreeSet以及使用subSet()、headSet()和tailSet()方法执行基于范围的搜索的各种技术。默认情况下，TreeSet自动按排序顺序维护元素。但是，我们可以通过在TreeSet创建期间提供Comparator来自定义排序行为。让我们看一个例子：

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetSortingExample {
  public static void main(String[] args) {
    // Create a TreeSet with custom sorting
    TreeSet<Integer> numbers = new TreeSet<>(Comparator.reverseOrder());

    // Add elements to the TreeSet
    numbers.add(5);
    numbers.add(3);
    numbers.add(7);
    numbers.add(1);

    System.out.println(numbers); // Output: [7, 5, 3, 1]
  }
}

在上面的代码中，我们创建了一个Integer类型的TreeSet ，并使用Comparator.reverseOrder()提供了一个自定义Comparator来按降序对元素进行排序。生成的TreeSet将包含元素[7, 5, 3, 1]。有多种方法可以迭代TreeSet。我们可以使用迭代器或利用增强的for-each循环。让我们看一下这两种方法的示例：

import java.util.TreeSet;
import java.util.Iterator;

public class TreeSetIterationExample {
  public static void main(String[] args) {
    TreeSet<String> names = new TreeSet<>();

    names.add("Johnny");
    names.add("Ivy");
    names.add("Ricky");
    names.add("David");

    // Iterating using an iterator
    Iterator<String> iterator = names.iterator();
    while (iterator.hasNext()) {
      String name = iterator.next();
      System.out.println(name);
    }

    // Iterating using the enhanced for-each loop
    for (String name : names) {
      System.out.println(name);
    }
  }
}

在上面的代码中，我们创建了一个名为names的TreeSet并添加了一些元素。然后，我们演示了两种迭代 TreeSet 的方法：使用迭代器和利用增强的 for-each 循环。TreeSet 提供了执行基于范围的搜索的方法，使我们能够根据特定条件检索元素子集。基于范围的搜索的三种主要方法是：

• subSet(E fromElement, E toElement) ：返回从fromElement（包含）到toElement （不包含）的元素子集。
• headSet(E toElement)：返回小于toElement的元素子集。
• tailSet(E fromElement)：返回大于或等于fromElement的元素子集。

让我们看一个例子：

import java.util.TreeSet;

public class TreeSetRangeSearchExample {
  public static void main(String[] args) {
    TreeSet<Integer> numbers = new TreeSet<>();

    numbers.add(1);
    numbers.add(3);
    numbers.add(5);
    numbers.add(7);
    numbers.add(9);

    // Performing range-based search using subSet()
    TreeSet<Integer> subset = new TreeSet<>(numbers.subSet(3, 8));
    System.out.println(subset); // Output: [3, 5, 7]

    // Performing range-based search using headSet()
    TreeSet<Integer> headSet = new TreeSet<>(numbers.headSet(6));
    System.out.println(headSet); // Output: [1, 3, 5]

    // Performing range-based search using tailSet()
     TreeSet<Integer> tailSet = new TreeSet<>(numbers.tailSet(5));
    System.out.println(tailSet); // Output: [5, 7, 9]
  }
}

在上面的代码中，我们创建了一个名为numbers的TreeSet并添加了一些元素。然后，我们使用subSet()、headSet()和tailSet()方法演示基于范围的搜索。

• 子集 TreeSet包含 3（含）和 8（不含）之间的元素，即[3, 5, 7]。
• headSet TreeSet包含少于 6 个元素，即[1 , 3, 5]。
• tailSet TreeSet包含大于或等于 5 的元素，即[5, 7, 9 ] 。

这些基于范围的搜索方法允许我们根据特定条件检索元素子集，从而提供处理排序数据的灵活性。

TreeSet 中的比较器：使用自定义标准排序

除了自然排序之外，您还可以使用自定义Comparator对TreeSet进行排序。在本节中，我们将深入研究比较器的概念及其在TreeSet中的作用。我们将探索如何使用自定义比较器创建TreeSet并提供代码示例来演示根据特定条件对 TreeSet进行排序。

什么是比较器？

比较器是 Java 中的一个接口，允许对对象进行自定义排序。它提供了一种根据特定属性或属性定义元素顺序的方法。通过实现Comparator接口并重写其compare()方法，我们可以指定元素在 TreeSet 中的排序方式。

使用自定义比较器创建 TreeSet

要创建具有自定义比较器的TreeSet ，我们需要在创建TreeSet实例时提供比较器作为参数。让我们看一个例子：

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetComparatorExample {
  public static void main(String[] args) {
    // Create a TreeSet with a custom comparator
    TreeSet<String> names = new TreeSet<>(new LengthComparator());

    // Add elements to the TreeSet
    names.add("Johnny");
    names.add("Ivy");
    names.add("Rick");
    names.add("David");

    System.out.println(names); // Output: [Ivy, Johnny, David, Rick]
  }
}

class LengthComparator implements Comparator<String> {
  @Override
  public int compare(String s1, String s2) {
    return Integer.compare(s1.length(), s2.length());
  }
}

在上面的代码中，我们创建了一个名为名称的TreeSet和一个名为LengthComparator的自定义比较器。LengthComparator比较两个字符串的长度并相应地对它们进行排序。结果，TreeSet根据字符串的长度进行排序，得到输出[Ivy, Rick, David, Johnny]。

使用比较器对 TreeSet 进行排序的示例

除了使用自定义比较器创建TreeSet之外，我们还可以使用比较器对TreeSet进行临时排序，而无需修改其自然顺序。让我们看一个例子：

import java.util.Comparator;
import java.util.TreeSet;

  public class TreeSetTest {
    public static void main(String[] args) {
      TreeSet<String> names = new TreeSet<>();

      names.add("Johnny");
      names.add("Ivy");
      names.add("Ricky");
      names.add("David");

      // Sort TreeSet temporarily using a comparator
      TreeSet<String> sortedNames = new TreeSet<>(Comparator.reverseOrder());
      sortedNames.addAll(names);

      System.out.println(sortedNames); // Output: [Ricky, Johnny, Ivy, David]
      System.out.println(names); // Output: [David, Ivy, Johnny, Ricky]
    }
  }

在上面的代码中，我们创建了一个名为names的TreeSet并添加了一些元素。然后，我们使用自定义比较器Comparator.reverseOrder()创建一个名为sortedNames的新TreeSet。通过将原始名称TreeSet中的所有元素添加到排序名称中，我们获得了TreeSet的临时排序版本。

TreeSet 与其他数据结构的比较

TreeSet 与 HashSet 的比较

TreeSet和HashSet都是Java中Set接口的实现。然而，它们之间存在显着差异。 TreeSet：TreeSet按排序顺序存储唯一元素。它使用自平衡二叉搜索树（通常是红黑树）来维护排序顺序，从而导致插入、删除和搜索等操作的对数时间复杂度。TreeSet对于维护排序集合和执行基于范围的操作非常有效。然而，由于树结构，它的内存开销较高，并且不允许空元素。 HashSet：HashSet内部使用哈希码和哈希表以无序的方式存储唯一元素。它为插入、删除和搜索等基本操作提供恒定的时间复杂度。HashSet对于快速元素查找非常有效，并且不会为维护顺序施加任何额外的内存开销。但是，它不保证元素的任何特定顺序。

何时使用 TreeSet：

• 当您需要自动按排序顺序维护元素时。
• 当您需要基于范围的操作或需要高效地查找特定范围内的元素时。
• 当不允许重复元素且唯一性至关重要时。
• 当您愿意牺牲稍高的内存使用量来换取自动排序和范围操作的好处时。

TreeSet 与 ArrayList 的比较

ArrayList是Java中的动态数组实现。以下是TreeSet和ArrayList之间的主要区别：

• TreeSet：TreeSet按排序顺序存储唯一元素，为维护排序集合和执行基于范围的搜索提供有效的操作。它的运算时间复杂度为对数。TreeSet不适合随机访问或维护插入顺序。
• ArrayList：ArrayList按插入顺序存储元素，使用索引提供对元素的快速随机访问。通过索引访问元素时，大多数操作具有恒定的时间复杂度。然而，从列表中间插入或删除元素具有线性时间复杂度，因为它需要移动元素。

何时考虑其他数据结构

• 如果不需要按排序顺序维护元素，并且需要快速元素查找或无序集合，则HashSet可能是更好的选择。
• 如果需要频繁通过索引随机访问元素或者需要维护插入顺序，ArrayList会更合适。