JavaTreeMap和TreeSet：基于红黑树的有序集合
TreeMap和TreeSet是 Java 集合框架中的两种重要数据结构，它们都基于红黑树（Red-Black Tree）实现，提供了有序的元素存储和操作方式。TreeMap用于存储键值对（key-value），而TreeSet用于存储不重复的元素。它们的底层实现原理非常相似，但由于存储结构和用途的不同，具体实现也有所区别。
1. 红黑树数据结构的基础
红黑树概述
红黑树是一种自平衡的二叉查找树，具有以下特点：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 每个叶子节点（NIL 节点）是黑色。
- 如果一个红色节点的父节点是红色的，则违反红黑树规则，因此红色节点的子节点必须是黑色。
- 从根节点到每个叶子节点的路径上，黑色节点的数量必须相同。
- 红黑树的高度是平衡的，因此它的查找、插入和删除操作的时间复杂度为O(log n)。
2.TreeMap的实现原理
TreeMap 基本结构
TreeMap实现了NavigableMap接口，而NavigableMap继承自SortedMap。TreeMap的核心数据结构是一个红黑树。每个树节点包含一个键值对（key 和 value），并根据 key 进行排序。
TreeMap 插入过程
TreeMap中的插入操作通过红黑树实现，在插入新节点时会保持红黑树的平衡。插入的过程包括：
- 查找位置：根据 key 比较找到合适的位置。
- 插入节点：找到位置后创建新的节点，并插入到树中。
- 平衡调整：插入后调用
fixAfterInsertion来确保红黑树的平衡性。
fixAfterInsertion：插入后平衡树
- 颜色调整：如果父节点是红色节点，需要进行颜色调整。
- 旋转调整：通过左旋或右旋来保持红黑树的平衡。
3.TreeSet的实现原理
TreeSet和TreeMap非常相似，不同之处在于TreeSet不存储值，只存储键。内部结构使用TreeMap来实现，而TreeMap中的 key 就是TreeSet中的元素。
TreeSet 的实现
TreeSet底层通过TreeMap来存储元素，所有的操作（如添加、删除、查找等）都会通过TreeMap实现。TreeMap存储元素的同时保证它们的有序性。
4. 查找与删除操作
查找操作
TreeMap和TreeSet的查找操作都基于红黑树的查找方式。通过compare()方法来比较键值，查找时间复杂度是O(log n)。
删除操作
删除操作需要先找到要删除的节点，然后通过旋转和颜色调整来保持红黑树的平衡。
示例代码：TreeMap的删除操作
java复制
public V remove(Object key) { Entry<K, V> p = getEntry(key); if (p == null) return null; deleteEntry(p); return p.value; } private void deleteEntry(Entry<K, V> p) { if (p.left != null && p.right != null) { Entry<K, V> s = successor(p); p.key = s.key; p.value = s.value; p = s; } Entry<K, V> replacement = (p.left != null ? p.left : p.right); if (replacement != null) { replacement.parent = p.parent; if (p.parent == null) root = replacement; else if (p == p.parent.left) p.parent.left = replacement; else p.parent.right = replacement; p.left = p.right = p.parent = null; } else if (p.parent == null) { root = null; } else { if (p == p.parent.left) p.parent.left = null; else p.parent.right = null; p.parent = null; } size--; modCount++; }5. 总结
TreeMap和TreeSet都基于红黑树实现，提供了高效的查找、插入和删除操作。TreeMap存储键值对，TreeSet只存储键。- 插入和删除操作会触发红黑树的旋转和颜色调整，以保证树的平衡性。
TreeSet是TreeMap的一个封装，利用TreeMap来实现元素的有序存储。
