Set 接口的实现类 TreeSet 的底层数据结构
TreeSet 是 Java 集合框架中的 Set 接口的一个实现类。它通过红黑树数据结构来存储和组织元素，以实现高效的增加、删除和查找操作。红黑树是一种自平衡的二叉搜索树，它具有以下性质：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 每个叶子节点（NIL 节点，即空节点）是黑色。
- 如果一个节点是红色的，则它的两个子节点都是黑色的。
- 对于每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑色节点。
TreeSet 内部的数据结构使用红黑树来维护元素的有序性。红黑树按照元素的自然顺序或者根据构造 TreeSet 时传入的 Comparator 来进行排序。通过这样的排序，TreeSet 可以在 O(log n) 的时间复杂度下执行增加、删除和查找操作。
当我们向 TreeSet 中添加新元素时，它会根据元素的值找到合适的位置插入节点，并根据红黑树的性质进行自平衡操作。这些自平衡操作包括颜色变换、左旋和右旋等操作，确保红黑树保持平衡，从而维护高效的查找性能。
TreeSet 还提供了一些其他方法，如获取第一个元素、获取最后一个元素、获取小于或等于给定元素的最大元素、获取大于或等于给定元素的最小元素等。这些方法都利用了红黑树的有序性，使得操作的时间复杂度为 O(log n)。
总结来说，TreeSet 的底层数据结构是一个红黑树，它通过自平衡操作保持树的平衡，以实现高效的增加、删除和查找操作。利用红黑树的有序性，TreeSet 还提供了一些额外的方法来获取有序集合中的元素。