红黑树
定义
红黑树是一种自平衡二叉搜索树（BST），通过给每个节点着色（红/黑）并遵守5条性质，保证树的高度始终为 O(log N)，从而保证所有操作（查找/插入/删除）的时间复杂度为 O(log N)。
红黑树的5条性质
- 每个节点要么是红色，要么是黑色
- 根节点是黑色
- 所有叶子节点（NIL节点）是黑色
- 红色节点的两个子节点都是黑色（无连续红节点）
- 从任一节点到其所有后代 NIL 节点的路径上，包含相同数量的黑色节点
如何保持自平衡
红黑树不要求左右子树高度差严格相等，而是用黑高一致和不能连续出现红节点来限制树高。
- 性质 5 保证从任一节点出发，每条到 NIL 叶子的路径都有相同数量的黑节点
- 性质 4 保证红节点不能相邻，因此最长路径至多是在每个黑节点之间都插入一个红节点
- 结果是最长路径长度不会超过最短路径的 2 倍，树高上界为 O(log N)
插入和删除可能破坏这些性质，红黑树只在受影响路径附近做两类修复：
- 变色：调整红黑关系，通常用于把冲突向上层传播或消除双黑问题
- 旋转：局部改变父子关系，同时保持二叉搜索树的中序顺序不变
关键操作代码
下面代码使用 Java 风格展示标准红黑树的关键操作。为突出平衡逻辑，示例把 null 叶子视为黑色；工程实现中也常用一个共享的黑色 NIL 哨兵节点。
基础结构与辅助方法
class RedBlackTree<K extends Comparable<K>, V> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node {
K key;
V val;
Node left, right, parent;
boolean color;
Node(K key, V val, boolean color, Node parent) {
this.key = key;
this.val = val;
this.color = color;
this.parent = parent;
}
}
private Node root;
private boolean colorOf(Node x) {
return x == null ? BLACK : x.color;
}
private boolean isRed(Node x) {
return colorOf(x) == RED;
}
private Node parentOf(Node x) {
return x == null ? null : x.parent;
}
private Node leftOf(Node x) {
return x == null ? null : x.left;
}
private Node rightOf(Node x) {
return x == null ? null : x.right;
}
private void setColor(Node x, boolean color) {
if (x != null) {
x.color = color;
}
}
}
旋转
左旋把右子节点提升为子树根，右旋把左子节点提升为子树根。旋转不会改变节点的中序顺序，所以仍然满足 BST 的大小关系。
左旋图解
对节点 x 左旋时，x 的右孩子 y 会升上来，y 原来的左子树 B 会转移成 x 的右子树。
左旋 x：
x y
/ \ / \
A y ,> x C
/ \ / \
B C A B
关键指针变化只有两步：
x.right = y.left，也就是让B接到x的右边y.left = x，也就是让x成为y的左孩子
为什么这样仍然是 BST？因为左旋前的大小关系是：
A < x < B < y < C
左旋后从左到右仍然是：
A < x < B < y < C
所以旋转只改变局部高度，不改变中序顺序。
数字例子：
左旋 10：
10 20
/ \ / \
5 20 ,> 10 30
/ \ / \
15 30 5 15
15 原本在 20 的左边，说明 15 < 20；同时它又在 10 的右子树里，说明 15 > 10。所以左旋后把 15 接到 10.right 正好合法。
右旋图解
右旋是左旋的镜像操作。对节点 y 右旋时，y 的左孩子 x 会升上来，x 原来的右子树 B 会转移成 y 的左子树。
右旋 y：
y x
/ \ / \
x C ,> A y
/ \ / \
A B B C
关键指针变化也只有两步：
y.left = x.right，也就是让B接到y的左边x.right = y，也就是让y成为x的右孩子
右旋前后的中序顺序同样不变：
A < x < B < y < C
数字例子：
右旋 20：
20 10
/ \ / \
10 30 ,> 5 20
/ \ / \
5 15 15 30
15 原本在 10 的右边，说明 15 > 10；同时它又在 20 的左子树里，说明 15 < 20。所以右旋后把 15 接到 20.left 正好合法。
private void rotateLeft(Node x) {
Node y = x.right;
if (y == null) {
return;
}
x.right = y.left;
if (y.left != null) {
y.left.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
root = y;
} else if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
y.left = x;
x.parent = y;
}
private void rotateRight(Node y) {
Node x = y.left;
if (x == null) {
return;
}
y.left = x.right;
if (x.right != null) {
x.right.parent = y;
}
x.parent = y.parent;
if (y.parent == null) {
root = x;
} else if (y == y.parent.left) {
y.parent.left = x;
} else {
y.parent.right = x;
}
x.right = y;
y.parent = x;
}
插入与插入后修复
新节点默认插入为红色。原因是插入红节点不会改变任何路径的黑高，只可能破坏“根为黑”或“红节点不能有红孩子”；如果插入黑节点，则几乎一定会破坏黑高一致。
public void put(K key, V val) {
Node parent = null;
Node cur = root;
int cmp = 0;
while (cur != null) {
parent = cur;
cmp = key.compareTo(cur.key);
if (cmp < 0) {
cur = cur.left;
} else if (cmp > 0) {
cur = cur.right;
} else {
cur.val = val;
return;
}
}
Node x = new Node(key, val, RED, parent);
if (parent == null) {
root = x;
} else if (cmp < 0) {
parent.left = x;
} else {
parent.right = x;
}
fixAfterInsert(x);
}
private void fixAfterInsert(Node x) {
while (x != root && isRed(parentOf(x))) {
Node p = parentOf(x);
Node g = parentOf(p);
if (p == leftOf(g)) {
Node uncle = rightOf(g);
if (isRed(uncle)) {
// 父红、叔红：父叔变黑，祖父变红，问题上移到祖父。
setColor(p, BLACK);
setColor(uncle, BLACK);
setColor(g, RED);
x = g;
} else {
if (x == rightOf(p)) {
// 左右型：先左旋父节点，转成左左型。
x = p;
rotateLeft(x);
p = parentOf(x);
g = parentOf(p);
}
// 左左型：父变黑、祖父变红，再右旋祖父。
setColor(p, BLACK);
setColor(g, RED);
rotateRight(g);
}
} else {
Node uncle = leftOf(g);
if (isRed(uncle)) {
setColor(p, BLACK);
setColor(uncle, BLACK);
setColor(g, RED);
x = g;
} else {
if (x == leftOf(p)) {
// 右左型：先右旋父节点，转成右右型。
x = p;
rotateRight(x);
p = parentOf(x);
g = parentOf(p);
}
// 右右型：父变黑、祖父变红，再左旋祖父。
setColor(p, BLACK);
setColor(g, RED);
rotateLeft(g);
}
}
}
setColor(root, BLACK);
}
插入修复可以记成：
| 情况 | 处理 |
|---|---|
| 父节点是黑色 | 没有破坏红黑性质，直接结束 |
| 父节点和叔叔节点都是红色 | 父、叔变黑，祖父变红，继续向上修复 |
| 父节点红、叔叔黑，且新节点是“内侧”孩子 | 先旋转父节点，转成外侧情况 |
| 父节点红、叔叔黑，且新节点是“外侧”孩子 | 父变黑、祖父变红，再旋转祖父 |
删除后的平衡修复
删除先按普通 BST 的方式处理：如果目标节点有两个孩子，用后继或前驱替换；真正从树中移走的是至多只有一个孩子的节点。
- 移走红节点：不会影响黑高，通常无需修复
- 移走黑节点：某条路径少了一个黑节点，会产生“双黑”问题，需要从替换节点开始修复
删除修复的核心是观察兄弟节点：兄弟红就先旋转换成兄弟黑；兄弟黑且两个孩子都黑，就把兄弟染红并把问题上移；兄弟黑且至少有一个红孩子，就通过旋转和变色补回缺失的黑高。
private void fixAfterDelete(Node x, Node parent) {
while (x != root && colorOf(x) == BLACK) {
if (parent == null) {
break;
}
if (x == leftOf(parent)) {
Node sibling = rightOf(parent);
if (isRed(sibling)) {
setColor(sibling, BLACK);
setColor(parent, RED);
rotateLeft(parent);
sibling = rightOf(parent);
}
if (!isRed(leftOf(sibling)) && !isRed(rightOf(sibling))) {
setColor(sibling, RED);
x = parent;
parent = parentOf(x);
} else {
if (!isRed(rightOf(sibling))) {
setColor(leftOf(sibling), BLACK);
setColor(sibling, RED);
rotateRight(sibling);
sibling = rightOf(parent);
}
setColor(sibling, colorOf(parent));
setColor(parent, BLACK);
setColor(rightOf(sibling), BLACK);
rotateLeft(parent);
x = root;
parent = null;
}
} else {
Node sibling = leftOf(parent);
if (isRed(sibling)) {
setColor(sibling, BLACK);
setColor(parent, RED);
rotateRight(parent);
sibling = leftOf(parent);
}
if (!isRed(leftOf(sibling)) && !isRed(rightOf(sibling))) {
setColor(sibling, RED);
x = parent;
parent = parentOf(x);
} else {
if (!isRed(leftOf(sibling))) {
setColor(rightOf(sibling), BLACK);
setColor(sibling, RED);
rotateLeft(sibling);
sibling = leftOf(parent);
}
setColor(sibling, colorOf(parent));
setColor(parent, BLACK);
setColor(leftOf(sibling), BLACK);
rotateRight(parent);
x = root;
parent = null;
}
}
}
setColor(x, BLACK);
}
删除修复可以理解为“向兄弟借黑色”：
| 情况 | 处理 |
|---|---|
| 兄弟节点是红色 | 兄弟变黑、父变红，旋转父节点，把问题转成兄弟黑的情况 |
| 兄弟黑，且兄弟两个孩子都黑 | 兄弟变红，当前子树黑高补平，双黑问题上移到父节点 |
| 兄弟黑，兄弟近侧孩子红、远侧孩子黑 | 先旋转兄弟节点，转成远侧孩子红 |
| 兄弟黑，兄弟远侧孩子红 | 兄弟继承父颜色，父和远侧孩子变黑，旋转父节点，修复结束 |
与AVL树对比
| 维度 | 红黑树 | AVL树 |
|---|---|---|
| 平衡严格度 | 较宽松（允许黑高差） | 严格（左右子树高度差 ≤1） |
| 插入/删除旋转次数 | 较少 | 较多 |
| 查找速度 | 稍慢（树高略高） | 更快（树高更平衡） |
| 适用场景 | 插入删除频繁的场景（如Java TreeMap） | 查找频繁的场景 |
应用场景
- Java：
TreeMap、TreeSet的底层实现 - C++：
std::map、std::set的底层实现（部分编译器） - Linux：完全公平调度器（CFS）的进程优先级管理