Java集合框架中TreeMap与Red-Black树的关系

P粉602998670 2026-01-16 00:00:00 次阅读

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树的多路分支特性。关键权衡点在于：

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 put(K key, V value) {
    Entry t = root;
    if (t == null) {
        root = new Entry<>(key, value, null);
        size = 1;
        return null;
    }
    // ... 查找插入位置
    // 插入后调用 fixAfterInsertion(e) 维护红黑性质
}