深入浅出 红黑树：如何手写红黑树（基于TreeMap，算法导论的实现）
红黑树
红黑树是一种自平衡的二叉搜索树，它通过以下性质来保证树的平衡：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 所有叶子节点（NIL节点，空节点）都是黑色。
- 每个红色节点的两个子节点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
- 从任一节点到其每个叶子的所有简单路径都包含相同数量的黑色节点。
因为红色节点的不能相邻，所以任何一条路径黑色节点至少是总数的一半，任何一条L长的路径，黑色至少占 L/2。
假设红黑树高 h，因此黑色节点至少 h/2。
又因为每条路径的黑色节点都是一样的，因此至少有 h/2 的满二叉树（因为每条路径至少 h/2 的 黑色节点），所以红黑树一定是 h = log n 的高度。
一颗 log n 高度的二叉搜索树，查询、插入 和 删除 复杂度自然是 log n。
TreeMap 的整体结构与红黑树实现
TreeMap 是 Java 集合框架中基于红黑树实现的有序 Map。它的核心数据结构是一个红黑树，每个节点存储键值对，并保证树的平衡和有序性。实现基于算法导论。
主要内部类和字段
- Entry<K,V>：TreeMap 的核心节点类，每个 Entry 代表红黑树的一个节点，包含了 key、value、left/right/parent、color（颜色标记，true 为红色，false 为黑色）。【Tree Map实现红黑树没有显式的NIL哨兵，但是逻辑上null可以视为黑色】
private static <K,V> boolean colorOf(Entry<K,V> p) {return (p == null ? BLACK : p.color);
}- root：指向红黑树的根节点。
- size：记录元素数量。
Entry 结构
static final class Entry<K,V> implements Map.Entry<K,V> {K key;V value;Entry<K,V> left;Entry<K,V> right;Entry<K,V> parent;boolean color = BLACK; // 默认黑色// ...
}
- TreeMap 通过 Entry<K,V> 节点类实现红黑树，每个节点有颜色、父子指针。
- 插入操作后用 fixAfterInsertion 保证平衡，核心是“红红冲突”修正和旋转。相当于双红节向上移动，如果到根节点还是双红，直接染成黑色，黑高加1。
- 删除操作后用 fixAfterDeletion 保证平衡，核心是“黑高不平衡”修正和旋转。相当于双黑节点上移，如果到根节点还是双黑，直接去掉一重黑，黑高减一。
旋转操作
-
左旋：将节点
p的右子节点r移动到p的位置，并将p作为r的左子节点。private void rotateLeft(Entry<K,V> p) {if (p != null) {Entry<K,V> r = p.right;p.right = r.left;if (r.left != null)r.left.parent = p;r.parent = p.parent;if (p.parent == null)root = r;else if (p.parent.left == p)p.parent.left = r;elsep.parent.right = r;r.left = p;p.parent = r;} } -
右旋：将节点
p的左子节点l移动到p的位置，并将p作为l的右子节点。private void rotateRight(Entry<K,V> p) {if (p != null) {Entry<K,V> l = p.left;p.left = l.right;if (l.right != null) l.right.parent = p;l.parent = p.parent;if (p.parent == null)root = l;else if (p.parent.right == p)p.parent.right = l;else p.parent.left = l;l.right = p;p.parent = l;} }
插入操作（put）
插入分为两步：
- 二叉查找树方式定位插入点。
- 插入后执行红黑树的自平衡操作（修正颜色和结构）。
定位插入点
- 沿根节点查找，比较 key 的大小，找到合适的叶子位置插入新节点。
- 新节点初始为 红色 节点。
插入后的修正（fixAfterInsertion）源码核心方法如下：
private void fixAfterInsertion(Entry<K,V> x) {x.color = RED;while (x != null && x != root && x.parent.color == RED) {if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {Entry<K,V> y = rightOf(parentOf(parentOf(x)));if (colorOf(y) == RED) {setColor(parentOf(x), BLACK);setColor(y, BLACK);setColor(parentOf(parentOf(x)), RED);x = parentOf(parentOf(x));} else {if (x == rightOf(parentOf(x))) {x = parentOf(x);rotateLeft(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateRight(parentOf(parentOf(x)));}} else {// 与上面对称（左右互换）}}root.color = BLACK;
}
初始着色：新插入的节点 x 被着色为红色。
循环修正：当节点 x 不是根节点且它的父节点是红色时，进入循环进行修正。
while (x != null && x != root && x.parent.color == RED) {
父节点是红色，祖先节点一定是黑色
-
情况判断：根据
x的父节点是其祖父节点的左子节点还是右子节点，分为两种情况处理。-
父节点是左子节点：
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {Entry<K,V> y = rightOf(parentOf(parentOf(x)));-
叔叔节点是红色：将父节点和叔叔节点着色为黑色，祖父节点着色为红色，并将
x更新为祖父节点（递归思想），继续循环。if (colorOf(y) == RED) {setColor(parentOf(x), BLACK);setColor(y, BLACK);setColor(parentOf(parentOf(x)), RED);x = parentOf(parentOf(x)); } -
叔叔节点是黑色：根据
x是父节点的左子节点还是右子节点，进行不同的处理。x是右子节点：对x的父节点进行左旋，将x更新为它的父节点。（经过这一步，x一定是左子节点，进入后面一种情况）if (x == rightOf(parentOf(x))) {x = parentOf(x);rotateLeft(x); }x是左子节点：对x的祖父节点进行右旋，并交换父节点和祖父节点的颜色。这一步虽然没有重新赋值 x，但是因为对祖父右旋，x离根节点距离减少了1
setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x)));
-
-
父节点是右子节点：与父节点是左子节点的情况对称处理。
else {Entry<K,V> y = leftOf(parentOf(parentOf(x)));if (colorOf(y) == RED) {setColor(parentOf(x), BLACK);setColor(y, BLACK);setColor(parentOf(parentOf(x)), RED);x = parentOf(parentOf(x));} else {if (x == leftOf(parentOf(x))) {x = parentOf(x);rotateRight(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateLeft(parentOf(parentOf(x)));} }
-
-
根节点着色：循环结束后，将根节点着色为黑色。
删除操作（remove）
删除比插入复杂，分为删除节点和修正红黑树结构两步。
删除节点
- 若节点有两个子节点，用后继节点（右子树最小节点）替换，然后删除后继节点（后继最多只有一个子节点）。
- 若节点有一个或零个子节点，直接用子节点替换。
deleteEntry
这个函数的实现有自身的考虑，不是必然逻辑
private void deleteEntry(Entry<K,V> p) {modCount++;size--;// If strictly internal, copy successor's element to p and then make p// point to successor.if (p.left != null && p.right != null) {Entry<K,V> s = successor(p);p.key = s.key;p.value = s.value;p = s;} // p has 2 children// Start fixup at replacement node, if it exists.Entry<K,V> replacement = (p.left != null ? p.left : p.right);if (replacement != null) {// Link replacement to parentreplacement.parent = p.parent;if (p.parent == null)root = replacement;else if (p == p.parent.left)p.parent.left = replacement;elsep.parent.right = replacement;// Null out links so they are OK to use by fixAfterDeletion.p.left = p.right = p.parent = null;// Fix replacementif (p.color == BLACK)fixAfterDeletion(replacement);} else if (p.parent == null) { // return if we are the only node.root = null;} else { // No children. Use self as phantom replacement and unlink.if (p.color == BLACK)fixAfterDeletion(p);if (p.parent != null) {if (p == p.parent.left)p.parent.left = null;else if (p == p.parent.right)p.parent.right = null;p.parent = null;}}}
successor的逻辑只有在有右孩子的时候，后继才是只有一个节点，这就是这里判断做的
if (p.left != null && p.right != null) {Entry<K,V> s = successor(p);p.key = s.key;p.value = s.value;p = s;} // p has 2 children做了这一步，p 只有一个子节点，因为 s 的值被保留了，所以现在要删除 p = s
如果有一个孩子，这里进入的时候，p已经被删除了，颜色是需要补偿的
Entry<K,V> replacement = (p.left != null ? p.left : p.right);if (replacement != null) {// Link replacement to parentreplacement.parent = p.parent;if (p.parent == null)root = replacement;else if (p == p.parent.left)p.parent.left = replacement;elsep.parent.right = replacement;// Null out links so they are OK to use by fixAfterDeletion.p.left = p.right = p.parent = null;// Fix replacementif (p.color == BLACK)fixAfterDeletion(replacement);}没孩子是类似的
successor
找到的是右子树的最左节点。
如果没有右孩子，会找到最近祖先p，使得 t 是 p 的左子树节点，因此这个时候 p 可能有两个子节点
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {if (t == null)return null;else if (t.right != null) {Entry<K,V> p = t.right;while (p.left != null)p = p.left;return p;} else {Entry<K,V> p = t.parent;Entry<K,V> ch = t;while (p != null && ch == p.right) {ch = p;p = p.parent;}return p;}}删除后的修正（fixAfterDeletion）
源码核心方法如下：
private void fixAfterDeletion(Entry<K,V> x) {while (x != root && colorOf(x) == BLACK) {if (x == leftOf(parentOf(x))) {Entry<K,V> sib = rightOf(parentOf(x));if (colorOf(sib) == RED) {setColor(sib, BLACK);setColor(parentOf(x), RED);rotateLeft(parentOf(x));sib = rightOf(parentOf(x));}if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {setColor(sib, RED);x = parentOf(x);} else {if (colorOf(rightOf(sib)) == BLACK) {setColor(leftOf(sib), BLACK);setColor(sib, RED);rotateRight(sib);sib = rightOf(parentOf(x));}setColor(sib, colorOf(parentOf(x)));setColor(parentOf(x), BLACK);setColor(rightOf(sib), BLACK);rotateLeft(parentOf(x));x = root;}} else {// 左右对称的处理}}setColor(x, BLACK);
}
关键点说明
- 删除黑色节点可能导致红黑树黑高不一致，通过兄弟节点的颜色和结构旋转、变色修正。
- 主要有四种情况，代码参考算法导论的实现，这里与红黑树的标准修正操作对应。
最透彻的分析 删除后修正
当删除一个黑色节点时，会破坏黑高平衡，需要进行修复。
注意：在进入函数之后，x是不需要被删除的【见deleteEntry中的讨论】，只是从根到 x 这条路径路径少了一个黑色，所以可以把 x 视为 外面多了一层黑的节点，如果x是红色，显然把x赋值为黑色就结束了，如果x是根，直接丢掉这个多出来的黑就行。
理解这一点才能明白后面的条件判断 和 赋值。
主循环条件
while (x != root && colorOf(x) == BLACK)
x是待修复的节点（通常是被删除节点的替代节点）- 只有当
x是黑色且不是根节点时才需要修复
修复策略（以左孩子为例，x == leftOf(parentOf(x)) ）
Entry<K,V> sib = rightOf(parentOf(x));
情况1：兄弟节点是红色（此时兄弟节点的孩子 一定是黑色，null节点被视为黑色）
左旋x的父节点，使得 sib 的左孩子变为 x 的 兄弟
if (colorOf(sib) == RED) {setColor(sib, BLACK); setColor(parentOf(x), RED);rotateLeft(parentOf(x)); // 左旋父节点sib = rightOf(parentOf(x)); // 更新兄弟节点
}
目的：将红色兄弟转换为黑色兄弟的情况
情况2：兄弟节点是黑色，且兄弟的两个子节点都是黑色
if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {setColor(sib, RED); // 兄弟变红x = parentOf(x); // 向上递归
}
通过将兄弟变红，让原本是 root->x 需要多一重黑，现在 root->sib 也要多一重黑，因此等价于 root->p 要多一层黑，因此 x = parent(x) 向上传递 。
情况3：兄弟是黑色，兄弟的右子节点是黑色，左子节点是红色
if (colorOf(rightOf(sib)) == BLACK) {setColor(leftOf(sib), BLACK); // 兄弟左子节点变黑setColor(sib, RED); // 兄弟变红rotateRight(sib); // 右旋兄弟sib = rightOf(parentOf(x)); // 更新兄弟节点
}
目的：转换为情况4【sib的左孩子原来的左孩子一定是黑色，旋转后，原来的sib变为红色，是一个右子节点的红色】
情况4：兄弟是黑色，兄弟的右子节点是红色
setColor(sib, colorOf(parentOf(x))); // 兄弟继承父节点颜色
setColor(parentOf(x), BLACK); // 父节点变黑
setColor(rightOf(sib), BLACK); // 兄弟右子节点变黑
rotateLeft(parentOf(x)); // 左旋父节点
x = root; // 修复完成，退出循环
这里实际做的是
- 交换 sib 和 父节点p 的颜色，因此 root->sib 黑高不变。
- sib的右孩子（原本是红色，情况4的条件），变为黑色，因此 root->sib.right需要删除一层黑
- 左旋父节点，
- 原本 root->p->x 的路径 变为 root->sib->p->x，因此这条路径被补偿了黑色（注意多了sib的颜色，sib原来颜色是黑的）；
- 另一条路径 root->p->sib，变为 root->sib->sib.right 颜色上等价于 root->原来的p->black，因此黑高不变
- 恢复黑高平衡，x=root直接跳出循环
循环外：setColor(x, BLACK)确保最终节点为黑色。（容易证明，不管什么情况，这一赋值不会破坏红黑树的性质，而且能够修复root变为红色的情况，因为这一点，在循环内部没必要考虑root是不是变为了红色）