TreeMap 与红黑树：从原理到 CRUD，再到源码

Words 1570Read Time≈ 4 min
2020-10-16
2026-2-11
cover
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)$）。

红黑树的性质

下面规则决定了红黑树不会退化成链表。
  1. 每个节点非红即黑
  1. 根节点永远是黑色
  1. 所有叶子（空节点 NIL）视为黑色
  1. 红节点的两个子节点必须是黑色（不允许连续红）
  1. 任意节点到其所有后代 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：父红 + 叔红：变色并向上继续修复。
notion image
  • 情形4：父红 + 叔黑，新节点在“内侧”：先旋转父节点，把结构调整成情形5。
notion image
  • 情形5：父红 + 叔黑，新节点在“外侧”：变色 + 旋转祖父节点完成修复。
notion image
  • 情形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 串起行为。
  • 最后对照源码，理解修复逻辑如何在实现层面维护这些规则。

参考

Loading...