有了前面的经验，你肯定知道一个事实，TreeSet是对TreeMap的封装。名字里面带个“tree”，说明肯定与树形结构有关系。没错，底层实现就是大名鼎鼎的红黑树。

TreeMap实现了SortedMap接口，也就是说会按照key的大小顺序对Map中的元素进行排序，可以使用内部默认的排序规则，也可以传入自定义的比较器：

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
    private final Comparator<? super K> comparator;
    
    public TreeMap() {
        comparator = null;
    }

    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
}

TreeMap是非线程安全的。

由于底层实现是红黑树，所以这里不会做过多的讲解。（主要是我也不会手撕红黑树哇）

还记得前面说过的 LinkedHashMap嘛，它可以记录元素的插入顺序，而TreeMap是根据排序规则维护一棵有序的近似平衡的二叉查找树。

让我们看一下红黑树的效率如何吧：

1. 查找（Search）：O(log n)，其中n是树中节点的数量。这是因为红黑树是二叉查找树，查找操作的时间复杂度与树的高度成正比，而红黑树的高度被限制在O(log n)。
2. 插入（Insert）：O(log n)。插入操作包括找到插入位置、插入节点、重新着色和可能的旋转操作。由于树的高度是O(log n)，因此插入操作的时间复杂度也是O(log n)。
3. 删除（Delete）：O(log n)。删除操作包括找到要删除的节点、移除节点、重新着色和可能的旋转操作。同样，由于树的高度是O(log n)，删除操作的时间复杂度也是O(log n)。
4. 最小值/最大值查找（Min/Max Search）：O(log n)。找到最小值或最大值需要遍历到树的叶子节点，这需要O(log n)的时间。
5. 成功查找的前驱/后继查找（Predecessor/Successor Search）：O(log n)。找到某个节点的前驱或后继可能需要遍历树，这也需要O(log n)的时间。
6. 范围查询（Range Query）：O(k + log n)，其中k是查询结果中的元素数量。范围查询需要遍历树并返回所有满足条件的节点，因此时间复杂度取决于结果集的大小和树的高度。

（非常牛逼的数据结构，不过也比较消耗内存，空间换时间嘛）

对于 TreeSet，这里不做过多赘述。

这两个数据结构，平时用得也不是特别多，用得最多的地方可能就是 LeetCode 吧。

---

2024.10.29

writeBy kaiven