在Java集合框架中，TreeSet是一个有序的、不允许元素重复的集合。它基于红黑树（Red-Black Tree）数据结构实现，这种数据结构能够确保元素在插入、删除后仍然保持有序状态。红黑树是一种自平衡的二叉查找树，它通过一系列的旋转和颜色调整来保证树的高度相对较低，从而保证了操作的效率。
一、TreeSet的特点
- 有序性：
TreeSet中的元素按照升序排列。默认情况下，元素按照自然顺序（即Comparable接口定义的顺序）进行排序，也可以通过构造函数提供一个自定义的Comparator来决定元素的排序方式。 - 不允许重复：如果试图向
TreeSet中添加一个已经存在的元素（根据比较规则判断为相等），则这个操作不会有任何效果，集合保持不变。 - 非线程安全：
TreeSet是非线程安全的，如果多个线程同时修改一个TreeSet实例，并且至少有一个线程修改了该实例的结构，那么它必须保持外部同步。这通常是通过在某个自然封装了该集合的对象上进行同步来完成的。 - 性能：由于
TreeSet基于红黑树实现，因此它的添加、删除、查找等操作的时间复杂度都接近O(log n)。这比基于哈希表的集合（如HashSet）要慢一些，但是TreeSet提供了有序的特性。
二、使用示例
下面是一个简单的TreeSet使用示例，展示了如何创建一个TreeSet、向其中添加元素以及遍历元素：
import java.util.TreeSet; import java.util.Set; public class TreeSetExample { public static void main(String[] args) { // 创建一个空的TreeSet实例，元素按照自然顺序排序 Set<Integer> treeSet = new TreeSet<>(); // 向TreeSet中添加元素 treeSet.add(5); treeSet.add(2); treeSet.add(8); treeSet.add(1); treeSet.add(4); // 试图添加一个已存在的元素，不会有任何效果 treeSet.add(5); // 重复元素不会被添加 // 遍历TreeSet中的元素（有序） for (Integer number : treeSet) { System.out.println(number); // 输出顺序：1, 2, 4, 5, 8 } // 创建一个自定义排序的TreeSet实例 Set<String> customSortedSet = new TreeSet<>(String.CASE_INSENSITIVE_ORDER); customSortedSet.add("Apple"); customSortedSet.add("banana"); customSortedSet.add("Orange"); customSortedSet.add("pear"); customSortedSet.add("apple"); // 重复元素（不区分大小写）不会被添加 // 遍历自定义排序的TreeSet中的元素（有序且不区分大小写） for (String fruit : customSortedSet) { System.out.println(fruit); // 输出顺序可能是：Apple, banana, Orange, pear（顺序可能因JVM实现而异） } } }
在这个示例中，我们首先创建了一个空的TreeSet实例，并向其中添加了一些整数。由于TreeSet会自动对元素进行排序，因此遍历集合时输出的是有序的元素列表。然后，我们创建了一个自定义排序的TreeSet实例，使用了一个不区分大小写的比较器（String.CASE_INSENSITIVE_ORDER），并向其中添加了一些字符串。同样地，遍历集合时输出的是有序且不区分大小写的元素列表。需要注意的是，由于红黑树的特性，相同元素的添加操作会被忽略。
三、TreeSet的内部实现
TreeSet的内部实现基于红黑树，这是一种自平衡的二叉查找树。在二叉查找树中，每个节点都有一个键（以及相关联的值），任何节点的键都大于其左子树中的所有节点的键，而小于其右子树中的所有节点的键。然而，普通的二叉查找树在最坏的情况下可能会退化成链表（例如，当元素按升序或降序插入时），导致操作的时间复杂度增加到O(n)。
为了解决这个问题，红黑树引入了一些额外的属性来保持树的平衡：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 所有叶子节点（NIL或空节点）是黑色。
- 如果一个节点是红色的，则它的两个子节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
- 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数量的黑色节点（称为黑高度）。
这些属性确保了从根到叶子的最长可能路径不会超过最短可能路径的两倍长。由于操作最坏的情况就是找到位于树的最深层的节点，因此这种保证使得在红黑树上进行插入、删除和查找操作的时间复杂度为O(log n)。
四、自定义排序
除了使用元素的自然顺序外，TreeSet还允许通过构造函数提供一个Comparator来定义元素的排序方式。Comparator是一个接口，它定义了一个compare方法，该方法用于比较两个对象并确定它们的顺序。
下面是一个使用自定义Comparator的示例：
import java.util.Comparator; import java.util.TreeSet; import java.util.Set; public class CustomSortedSetExample { public static void main(String[] args) { // 创建一个自定义排序的TreeSet实例，使用自定义的Comparator Set<String> customSortedSet = new TreeSet<>(new CustomComparator()); // 向TreeSet中添加元素，它们将按照自定义Comparator定义的顺序排序 customSortedSet.add("Apple"); customSortedSet.add("banana"); customSortedSet.add("Orange"); customSortedSet.add("pear"); // 遍历TreeSet中的元素（按照自定义的顺序） for (String fruit : customSortedSet) { System.out.println(fruit); // 输出顺序取决于CustomComparator的实现 } } // 自定义Comparator实现类 static class CustomComparator implements Comparator<String> { @Override public int compare(String s1, String s2) { // 这里可以根据需要定义比较逻辑，例如按照字符串长度排序 return Integer.compare(s1.length(), s2.length()); } } }
在这个示例中，我们创建了一个自定义的Comparator实现类CustomComparator，它按照字符串的长度来比较元素。然后，我们使用这个比较器创建了一个TreeSet实例，并向其中添加了一些字符串。遍历集合时，元素将按照字符串长度的升序排列。
