treemap底层就是红黑树实现，其内部entry包含key、value、left、right和color字段，通过fixafterinsertion等私有方法封装着色与旋转，确保满足红黑树五条性质，维持o(log n)时间复杂度。
TreeMap底层就是Red-Black树实现
Java标准库里的TreeMap不是“基于”红黑树，它本身就是用红黑树（Red-Black Tree）作为底层数据结构实现的。JDK源码里，TreeMap内部维护一个Entry类型的根节点，每个Entry包含key、value、left、right和color字段——这个color就是红黑树最关键的着色标记。
为什么选红黑树而不是AVL或B树
红黑树在插入/删除时平均旋转次数比AVL少，更适合频繁修改的场景；而TreeMap定位是通用有序映射，不是专为磁盘I/O设计，所以不需要B树的多路分支特性。关键权衡点在于：
Java JDK 25
下载
Java JDK 25 来自 OpenJDK 官方归档，版本为 JDK 25，本条下载地址已指向官方 Windows x64 zip 安装包直链，适合调试旧项目或兼容旧版 Java 运行环境。
-
TreeMap的put()和remove()平均时间复杂度是O(log n)，最坏也是O(log n)，靠的就是红黑树的自平衡能力 - 红黑树对“读多写少”和“读写均衡”两类场景都较友好，不像AVL那样为严格平衡付出更多调整开销
- JDK选择的是左倾红黑树（Left-Leaning Red-Black Tree）的变种，简化了部分修复逻辑，但对外行为完全符合红黑树五条性质
红黑树性质在TreeMap中的体现
你不需要手动维护颜色或旋转，但理解这些能帮你预判行为。比如：
- 所有
null叶子节点（即Entry的left/right为null）都被视为黑色——TreeMap不存null键，但空子树逻辑仍遵守此规则 - 从根到任意叶子的路径上，黑色节点数量相同——这保证了高度差不超过2倍，是O(log n)性能的根基
- 如果一个
Entry是红色，它的父节点必须是黑色——这是TreeMap在fixAfterInsertion()中反复检查并修正的条件
别把TreeMap和TreeSet的实现混为一谈
虽然TreeSet也有序、也用红黑树，但它底层复用的是TreeMap：实际持有一个TreeMap实例，把元素当key，统一用PRESENT对象作value。所以：
-
TreeSet的迭代顺序、比较逻辑、线程不安全性，全部继承自它包装的TreeMap - 如果你看到
TreeSet里出现NullPointerException，大概率是TreeMap的comparator或key本身不支持null比较 - 二者都不能直接暴露红黑树节点——没有public的
getRoot()或getColor()方法，所有树操作都被封装在私有方法如rotateLeft()、balanceInsertion()里
// JDK 17 TreeMap#put 源码片段节选（简化）
final Entry<k> put(K key, V value) {
Entry<k> t = root;
if (t == null) {
root = new Entry(key, value, null);
size = 1;
return null;
}
// ... 查找插入位置
// 插入后调用 fixAfterInsertion(e) 维护红黑性质
}
</k></k>
红黑树的细节被彻底封装，但每次put、remove、ceilingKey等操作，都在悄悄执行着色、旋转、重链接——这些动作是否触发，取决于你传入的key和当前树结构，而不是API表面看起来那么“静态”。Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
