treemap基于红黑树实现有序存储，操作时间复杂度为o(log n)，节点含key、value、左右子节点、父节点和颜色字段，严格遵循五条红黑性质以保证平衡与有序。
TreeMap 在 Java 中通过红黑树（Red-Black Tree）实现键的有序存储和高效查找，其核心是维护一棵自平衡二叉搜索树，所有操作（put、get、remove）时间复杂度均为 O(log n)。
红黑树结构保证有序与平衡
TreeMap 内部使用一个私有静态类 Entry 表示红黑树节点，每个节点包含 key、value、left、right、parent 和 color（布尔值，true 表示红色）字段。它严格遵循红黑树五条性质：
- 每个节点非红即黑
- 根节点为黑色
- 所有叶子（null 节点）视为黑色
- 红色节点的两个子节点必须为黑色（即不能有两个连续的红节点）
- 从任一节点到其每个叶子的所有路径上，黑色节点数量相同（黑高一致）
这些规则确保树的高度始终保持在约 2log₂(n) 以内，从而避免退化为链表，保障有序性和性能。
插入时自动排序与再平衡
调用 put(K key, V value) 时，TreeMap 先按 key 的自然顺序（或指定 Comparator）找到插入位置（类似 BST 查找），然后新建红色节点插入。插入后可能破坏红黑性质，于是触发 fixAfterInsertion 方法：
- 若父节点为黑色，直接结束
- 若父节点为红色，则根据叔节点颜色和插入方向，执行左旋、右旋、变色等操作（共 6 种情况）
- 最终将根设为黑色，确保整棵树合规
例如：插入序列 [5, 3, 7, 2, 4] 后，TreeMap 构建的红黑树逻辑结构保持中序遍历为 2→3→4→5→7，且高度均衡。
键必须可比较，否则抛异常
TreeMap 要求 key 实现 Comparable 接口（如 String、Integer），或构造时传入 Comparator。若 key 为 null 且无显式 Comparator，或 key 类型不支持比较（如未实现 Comparable 且无 Comparator），调用 put 会立即抛出 NullPointerException 或 ClassCastException。
建议始终明确指定 Comparator，尤其当 key 是自定义类时：
TreeMap<person string> map = new TreeMap((p1, p2) -> p1.age - p2.age);</person>
天然支持范围查询和顺序遍历
得益于红黑树的中序遍历特性，TreeMap 提供了高效范围视图方法：
- headMap(K toKey)：返回 key 小于 toKey 的子映射
- tailMap(K fromKey)：返回 key 大于等于 fromKey 的子映射
- subMap(K fromKey, K toKey)：返回 fromKey ≤ key
- 迭代器（keySet().iterator()）按升序返回键，无需额外排序
这些操作不是拷贝数据，而是返回底层共享结构的“视图”，时间和空间开销都很低。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
