treemap和treeset的有序性由底层红黑树在插入、删除时动态维护，无需遍历排序；红黑树作为自平衡二叉搜索树，满足bst性质（左
TreeMap 和 TreeSet 的有序性不是靠每次遍历排序实现的，而是由底层红黑树在插入、删除的**每一步操作中动态维护**的。这种“边改边调”的机制，让它们始终处于有序状态，且无需额外排序开销。
红黑树如何天然支持有序性
红黑树首先是二叉查找树（BST），这就决定了它的基本结构约束：
- 任意节点的左子树所有键都小于该节点键；
- 任意节点的右子树所有键都大于该节点键；
- 中序遍历结果天然升序——TreeSet 迭代器、TreeMap 的 keySet() 遍历正是基于此。
但普通 BST 在频繁增删后会退化成链表，失去 O(log n) 性能。红黑树通过五条颜色与路径规则（如根为黑、无连续红节点、各路径黑高相等）把高度控制在 ≤ 2log₂(n+1)，从而**既保序，又保效**。
插入时怎么边加边平衡
新元素插入时，红黑树按 BST 规则找到位置，然后执行三步：
- 先将新节点染成红色（不改变黑高，减少修复难度）；
- 检查是否违反“红节点不能有红子节点”——若父节点也是红色，就触发修复；
- 根据叔叔节点颜色和新节点位置，分情况处理： • 叔叔为红 → 父、叔变黑，祖父变红，向上递归检查； • 叔叔为黑且新节点是“内侧” → 先旋转转为“外侧”； • 叔叔为黑且新节点是“外侧” → 父变黑、祖父变红、绕祖父旋转。
整个过程只涉及局部染色和最多两次旋转，不影响整体有序结构，也不破坏 BST 性质。
删除时如何不破坏顺序和平衡
删除比插入更复杂，核心难点是：删掉一个黑节点会导致某条路径黑高减 1，破坏平衡。
- 先按 BST 规则找到并替换待删节点（用前驱或后继）；
- 若被删的是黑节点，就进入“补偿修复”流程；
- 修复策略围绕“兄弟节点”展开：通过兄弟颜色、侄子颜色判断，决定是染色、旋转，还是把“黑缺失”上推到父节点继续处理。
无论哪种路径，最终都确保所有从根到叶的路径黑节点数一致，BST 结构完整，中序顺序不变。
TreeSet 是 TreeMap 的“一层封装”
TreeSet 内部直接持有一个 TreeMap 实例，它把元素作为 key，value 固定用一个静态 Object（如 PRESENT）占位：
- add(e) → map.put(e, PRESENT)；
- contains(e) → map.containsKey(e)；
- 迭代器遍历 → 遍历 map 的 keySet()，自然就是有序的。
所以 TreeSet 的有序性和平衡逻辑，完全复用 TreeMap 的红黑树实现，没有额外数据结构或排序逻辑。
