TreeMap 的自动排序由红黑树的插入与平衡机制天然保证，中序遍历即为 key 的升序；其节点依据 Comparable 或 Comparator 定义的顺序组织，左子节点小于父节点。

TreeMap 的自动排序不是靠“每次插入后调用 sort()”，而是由底层红黑树（Red-Black Tree）的插入、旋转与着色机制天然保证的。理解它，关键不在“排序结果”，而在“如何在维持平衡的前提下，让中序遍历恰好是升序”。

红黑树结构确保中序遍历 = Key 的自然顺序

TreeMap 的节点按 Comparable 接口实现 或 Comparator 比较器 定义的大小关系组织：左子节点 绝不破坏左。因此，无论怎么调整结构，中序遍历（左→根→右）始终输出 Key 的升序序列。

插入时的三步动作：定位 + 新建 + 平衡

当你 put(key, value)，TreeMap 内部实际执行：

• 递归查找插入位置：从根开始，按 key 比较结果向左或向右走，直到遇到 null —— 这就是新节点该挂载的位置（保持 BST 性质）；
• 新建红色节点插入：新节点默认涂成红色（减少对黑高影响），作为叶子插入；
• 自底向上修复红黑性质：若出现连续两个红节点（违反性质4），就通过变色（color flip）或旋转（left/right rotate）来修正，过程中所有子树的中序序列不变。

为什么不需要额外排序？关键在“比较时机”

TreeMap 不在遍历时排序，而是在每个操作原子中完成序关系的维护：

• get(key)：只比较路径上的 O(log n) 个节点，不涉及全局顺序；
• firstKey()/lastKey()：直接沿最左/最右链走到叶子，O(log n)，结果天然有序；
• keySet().iterator()：内部使用“左根右”中序迭代器，每一步都严格遵循树结构，无需临时排序。

自定义 Comparator 时的注意事项

如果你传入自己的 Comparator，务必保证它满足：自反性（compare(x,x)==0）、传递性、一致性（多次调用结果相同）。否则红黑树可能插入错位，导致 find 失败或遍历乱序。例如：

错误写法（非确定性）：
Comparator c = (a, b) -> Math.random() > 0.5 ? 1 : -1; // 危险！
正确写法（稳定可比）：
Comparator c = String::compareToIgnoreCase;