Java 集合系列17之 TreeSet详细介绍(源码解析)和使用示例 

在 Java 中，TreeSet 是一个实现了 Set 接口的集合类，属于 Java 集合框架 的一部分，基于 红黑树（Red-Black Tree） 实现。它具有自动排序功能，因此可以非常方便地用于存储和检索有序的数据。与 HashSet 不同，TreeSet 会根据元素的自然顺序或者通过提供的比较器（Comparator）来对元素进行排序。

1. TreeSet 的特点

• 有序性：TreeSet 中的元素始终保持排序状态（根据元素的自然顺序，或者根据传入的比较器进行排序）。
• 不允许重复：由于它实现了 Set 接口，因此不允许存储重复元素。
• 性能：由于基于红黑树实现，TreeSet 提供了 O(log n) 的时间复杂度用于添加、删除和查询元素。
• 实现接口：TreeSet 实现了 NavigableSet 接口，该接口提供了一些额外的方法来操作集合中的元素，例如 lower(), higher(), ceiling() 等。

2. TreeSet 的构造方法

TreeSet 提供了多种构造方法，允许用户根据需求创建不同的 TreeSet 实例。

// 默认构造函数，使用元素的自然顺序
TreeSet<Type> treeSet1 = new TreeSet<Type>();

// 使用指定的 Comparator 对元素进行排序
TreeSet<Type> treeSet2 = new TreeSet<Type>(Comparator<Type> comparator);

// 创建一个包含指定元素的 TreeSet
TreeSet<Type> treeSet3 = new TreeSet<Type>(Collection<Type> collection);

3. TreeSet 的源码解析

TreeSet 内部通过 红黑树（Red-Black Tree） 实现自动排序。它继承自 AbstractSet 类并实现了 NavigableSet接口。

3.1 继承关系

TreeSet
  |
  |--> AbstractSet
        |
        |--> NavigableSet
              |
              |--> SortedSet

• TreeSet 类继承自 AbstractSet，实现了 NavigableSet 和 SortedSet 接口，SortedSet 接口提供了排序的相关方法。
• TreeSet 内部的元素存储结构是 红黑树，它是一种自平衡的二叉搜索树。每个节点都包含一个元素，并且根据树的结构，元素的顺序被维护。

3.2 红黑树的基本操作

红黑树是一种自平衡的二叉查找树，它在插入和删除节点时能够通过旋转来保持平衡，从而确保查询操作的时间复杂度为 O(log n)。

红黑树有以下特点：

• 每个节点是红色或黑色的。
• 根节点是黑色的。
• 所有叶节点都是黑色的（叶节点是 null）。
• 如果一个红色节点的子节点有红色节点，那么必须通过旋转使树重新平衡。

TreeSet 在插入、删除和查询操作时都会涉及到红黑树的旋转和调整，使得树的平衡得到保证。

4. TreeSet 常用方法

4.1 添加元素

TreeSet<Integer> set = new TreeSet<>();
set.add(10);  // 添加元素 10
set.add(5);   // 添加元素 5
set.add(20);  // 添加元素 20
System.out.println(set);  // 输出：[5, 10, 20]

4.2 删除元素

set.remove(10);  // 删除元素 10
System.out.println(set);  // 输出：[5, 20]

4.3 查询元素

System.out.println(set.contains(5));  // 输出：true
System.out.println(set.contains(10)); // 输出：false

4.4 获取第一个和最后一个元素

System.out.println(set.first());   // 输出：5
System.out.println(set.last());    // 输出：20

4.5 获取小于、等于、大于某个元素的值

TreeSet 提供了通过比较器或自然顺序获取与给定元素相关的值的方法。

System.out.println(set.lower(10));   // 输出：5  (小于10的最大值)
System.out.println(set.higher(10));  // 输出：20 (大于10的最小值)
System.out.println(set.ceiling(10)); // 输出：10 (大于或等于10的最小值)
System.out.println(set.floor(10));   // 输出：10 (小于或等于10的最大值)

4.6 遍历元素

由于 TreeSet 是有序的，我们可以按升序遍历集合中的元素：

for (Integer value : set) {
    System.out.println(value);
}

4.7 子集操作

TreeSet 还提供了通过指定区间返回子集的方法：

TreeSet<Integer> subset = (TreeSet<Integer>) set.subSet(5, true, 20, true);
System.out.println(subset);  // 输出：[5, 10, 20]

• subSet(fromElement, fromInclusive, toElement, toInclusive)：返回指定区间的子集。

4.8 清空集合

set.clear();  // 清空所有元素
System.out.println(set);  // 输出：[]

5. TreeSet 使用示例

以下是一个实际的例子，展示了如何使用 TreeSet 来处理一些常见的集合操作：

import java.util.*;

public class TreeSetExample {
    public static void main(String[] args) {
        // 创建 TreeSet 并添加元素
        TreeSet<Integer> treeSet = new TreeSet<>();
        treeSet.add(10);
        treeSet.add(5);
        treeSet.add(20);
        treeSet.add(15);
        treeSet.add(30);
        
        // 输出 TreeSet
        System.out.println("TreeSet: " + treeSet);  // 输出：[5, 10, 15, 20, 30]
        
        // 获取第一个和最后一个元素
        System.out.println("First Element: " + treeSet.first());   // 输出：5
        System.out.println("Last Element: " + treeSet.last());     // 输出：30
        
        // 获取小于、等于、大于某个元素的值
        System.out.println("Lower than 15: " + treeSet.lower(15));  // 输出：10
        System.out.println("Higher than 15: " + treeSet.higher(15)); // 输出：20
        System.out.println("Ceiling of 15: " + treeSet.ceiling(15)); // 输出：15
        System.out.println("Floor of 15: " + treeSet.floor(15));   // 输出：15
        
        // 遍历 TreeSet
        System.out.println("Iterating over TreeSet:");
        for (Integer num : treeSet) {
            System.out.println(num);
        }
        
        // 创建一个包含指定区间的子集
        TreeSet<Integer> subset = (TreeSet<Integer>) treeSet.subSet(10, true, 20, true);
        System.out.println("Subset (10 to 20): " + subset); // 输出：[10, 15, 20]
    }
}

6. 总结

TreeSet 是 Java 集合框架中非常有用的一个类，提供了有序集合的功能，适用于需要排序、查找或范围查询的场景。它基于红黑树实现，保证了 O(log n) 的性能，因此在处理大量数据时表现优异。如果需要按顺序存储元素并进行高效查询，TreeSet 是一个非常好的选择。