type
Post
status
Published
date
Oct 16, 2020 15:33
slug
summary
解析 TreeMap 的红黑树实现：5 条规则保证树高 O(log n)，CRUD 操作映射到插入修复（叔红变色上推，叔黑旋转变色）与删除修复，最后对齐 OpenJDK 源码中的 fixAfterInsertion/deleteEntry 关键逻辑。
tags
Data Structure
Java
category
CS Basic
icon
password
wordCount
1561
前言
TreeMap 是 Java 中常用的有序映射实现。它在保证键有序的同时，提供了对数时间复杂度的查找、插入与删除。本文先用理论建立直觉，再从 CRUD 视角串起来，最后回到源码把细节对齐。
你将收获什么
- 红黑树规则，以及为什么它能保持近似平衡
- TreeMap 的增删改查路径（先理解，再看实现）
- TreeMap 源码中的关键字段、节点结构与核心方法
概述
TreeMap 实现了 SortedMap / NavigableMap，因此它是一个「按 key 排序」的 Map。其底层数据结构是 红黑树（Red-Black Tree）。
为什么用红黑树？
- 相比普通二叉搜索树，红黑树通过规则约束保证树高近似对数级。
- 因此
get/put/remove在平均与最坏情况下都能维持较稳定的性能（通常可视作 $O(log n)$）。
红黑树的性质
下面规则决定了红黑树不会退化成链表。
- 每个节点非红即黑
- 根节点永远是黑色
- 所有叶子（空节点 NIL）视为黑色
- 红节点的两个子节点必须是黑色（不允许连续红）
- 任意节点到其所有后代 NIL 节点路径上，黑节点数量相同（黑高相等）
为什么树高不会爆炸？
- 规则 4 限制红节点不能连续。
- 规则 5 限制任一路径的黑节点数量一致。
- 两者结合，使最长路径不会超过最短路径的两倍量级，从而保持近似平衡。
增删改查（CRUD）
先用“做什么”的视角把行为串起来，再看“怎么做”的源码会更清晰。
一眼记住
- 查（Query）：按 BST 规则向下比较 key，直到命中或走到空。
- 增（Create）：把新节点挂到叶子，然后做插入修复。
- 改（Update）：仍然走
put；当比较结果为 0 时覆盖 value。
- 删（Delete）：先把删除降维（2 孩子 -> 0/1 孩子），再做删除修复。
查（Query）
- 从根开始比较 key。
- 小则去左子树，大则去右子树，相等则命中。
增 / 改（Create / Update）
- 与查询类似，先定位插入点。
- 若命中相同 key：直接覆盖 value。
- 否则插入新节点，并执行插入修复。
插入修复的典型情形（配图）
新插入节点默认先标红。真正需要修复的前提是：父节点也是红色（违反“红节点不能相邻”）。
- 情形1：新插入节点是根节点，无需额外操作，直接把根置黑。
- 情形2：父节点为黑色，无需操作。
- 情形3：父红 + 叔红：变色并向上继续修复。
- 情形4：父红 + 叔黑，新节点在“内侧”：先旋转父节点，把结构调整成情形5。
- 情形5：父红 + 叔黑，新节点在“外侧”：变色 + 旋转祖父节点完成修复。
- 情形6/7：与 4/5 对称（父节点在祖父右侧时的镜像情况）。
删（Delete）
- 0 个孩子：直接摘除。
- 1 个孩子：用孩子顶替。
- 2 个孩子：用后继（或前驱）替换 key/value，再删除后继（后继至多 1 个孩子）。
源码对齐：TreeMap 关键结构与核心流程
下面进入源码，把上面的理论与 CRUD 逐一映射到实现。
继承关系
实现接口
TreeMap 基本属性
comparator 的意义
comparator == null：走 key 的自然排序（key 必须实现 Comparable）。
comparator != null：走定制排序（key 不强制实现 Comparable）。
红黑树节点结构（Entry）
构造方法
自然排序 vs 定制排序对比
维度 | 自然排序（Comparable） | 定制排序（Comparator） |
比较来源 | key.compareTo(...) | comparator.compare(k1, k2) |
key 要求 | 必须实现 Comparable | 不强制实现 Comparable |
一致性风险 | compareTo 与 equals 不一致时，可能出现“逻辑重复 key” | comparator 与 equals 不一致时，同样可能出现“逻辑重复 key” |
查：getEntry（源码）
增 / 改：put（源码主流程）
读源码的小提示
- put 的“定位位置”阶段就是按 BST 规则向下走。
- 真正让 TreeMap 维持平衡的，是插入完成后的
fixAfterInsertion。
插入修复：fixAfterInsertion（源码）
把插入修复记成一句话
- 叔叔红：变色，上推。
- 叔叔黑：先“拐弯变直”（必要时旋转父节点），再“变色 + 旋转祖父节点”。
删：remove（源码主流程）
deleteEntry：三种删除情形
被删节点子树情况 | 处理方式 | 为什么这么做 |
0 个孩子 | 直接摘除 | 不涉及替换 |
1 个孩子 | 用孩子顶替该节点 | 保持二叉搜索树结构 |
2 个孩子 | 找后继（或前驱）替换 key/value，再删除后继（后继至多 1 个孩子） | 把“2 孩子删除”降维成“0/1 孩子删除” |
结尾
TreeMap 的核心价值是“有序 + 稳定性能”。从理解路径上看：
- 先掌握红黑树的规则，建立“为什么不会退化”的直觉。
- 再用 CRUD 串起行为。
- 最后对照源码，理解修复逻辑如何在实现层面维护这些规则。
参考
- OpenJDK TreeMap 源码（不同版本细节略有差异）：https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/TreeMap.java