数据结构与算法 / 系统课时
红黑树原理
红黑树原理
红黑树不是追求每个节点都接近绝对平衡,而是通过颜色规则限制最长路径与最短路径的比例。它允许局部高度差存在,却仍把整体树高控制在 ,因此常用于需要频繁插入和删除的有序集合与映射。
学习目标
- 能准确说明红黑树的五条核心性质及其对树高的约束。
- 能解释插入时旋转与重新着色分别解决什么问题。
- 能运行并验证一个包含插入修复逻辑的红黑树实现。
颜色约束与插入修复
红黑树仍满足二叉搜索树顺序,同时具有五条性质:每个节点为红或黑;根节点为黑;所有空叶子视为黑;红节点的孩子必须为黑;从任意节点到其后代空叶子的每条路径包含相同数量的黑节点。最后一项通常称为黑高一致。
这些约束意味着一条根到叶路径不可能连续出现两个红节点,最长路径至多是最短路径的两倍,可推出含 n 个内部节点的红黑树高度不超过 。因此查找、插入和删除的渐进时间复杂度都是 。
插入首先按普通二叉搜索树规则放置新节点,并把新节点设为红色。这样不会立即增加路径黑高;真正可能被破坏的是“红节点不能有红孩子”。修复过程围绕父节点、叔叔节点和祖父节点展开:
| 条件 | 主要动作 | 目的 |
|---|---|---|
| 父节点为黑 | 无需修复 | 所有性质仍成立 |
| 父节点与叔叔节点都为红 | 父、叔变黑,祖父变红并向上继续 | 消除局部红红冲突且保持黑高 |
| 父节点为红、叔叔节点为黑,方向呈折线 | 先旋转父节点 | 转换为直线结构 |
| 父节点为红、叔叔节点为黑,方向呈直线 | 旋转祖父并交换相关颜色 | 消除红红冲突并恢复局部黑高 |

旋转只改变局部结构,负责修正路径形状;重新着色不改变键的位置,负责恢复颜色与黑高约束。二者经常组合使用,不能把“旋转后有序”误认为“红黑性质已经自动成立”。
完整可运行示例
下面的 Java 17 示例实现经典红黑树插入。代码把 null 当作黑色空叶子,使用父指针寻找叔叔与祖父,并对左右方向编写镜像修复分支;重复键直接忽略。
import java.util.ArrayList;
import java.util.List;
public class RedBlackTreeDemo {
private enum Color {
RED, BLACK
}
private static class Node {
int key;
// 新插入节点先设为红色,避免立即改变所有路径的黑高。
Color color = Color.RED;
Node left;
Node right;
Node parent;
Node(int key) {
this.key = key;
}
}
private Node root;
public void insert(int key) {
Node parent = null;
Node current = root;
while (current != null) {
parent = current;
if (key < current.key) {
current = current.left;
} else if (key > current.key) {
current = current.right;
} else {
return;
}
}
Node inserted = new Node(key);
inserted.parent = parent;
if (parent == null) {
root = inserted;
} else if (key < parent.key) {
parent.left = inserted;
} else {
parent.right = inserted;
}
// 普通 BST 插入完成后,只修复可能出现的红红冲突。
fixAfterInsert(inserted);
}
private void fixAfterInsert(Node node) {
// 只要父节点为红,就违反了红节点不能有红孩子的约束。
while (node != root && colorOf(node.parent) == Color.RED) {
Node parent = node.parent;
Node grandparent = parent.parent;
if (parent == grandparent.left) {
Node uncle = grandparent.right;
if (colorOf(uncle) == Color.RED) {
// 父叔同红时重新着色,并把检查点上移到祖父。
parent.color = Color.BLACK;
uncle.color = Color.BLACK;
grandparent.color = Color.RED;
node = grandparent;
} else {
if (node == parent.right) {
// 折线结构先旋转父节点,转换为可统一处理的直线结构。
node = parent;
rotateLeft(node);
parent = node.parent;
grandparent = parent.parent;
}
parent.color = Color.BLACK;
grandparent.color = Color.RED;
rotateRight(grandparent);
}
} else {
Node uncle = grandparent.left;
if (colorOf(uncle) == Color.RED) {
// 右侧分支与左侧分支完全镜像。
parent.color = Color.BLACK;
uncle.color = Color.BLACK;
grandparent.color = Color.RED;
node = grandparent;
} else {
if (node == parent.left) {
node = parent;
rotateRight(node);
parent = node.parent;
grandparent = parent.parent;
}
parent.color = Color.BLACK;
grandparent.color = Color.RED;
rotateLeft(grandparent);
}
}
}
// 修复传播到根时,最终强制根节点为黑色。
root.color = Color.BLACK;
}
private void rotateLeft(Node top) {
// 旋转只改变局部连接,不改变中序遍历中的键顺序。
Node newTop = top.right;
top.right = newTop.left;
if (newTop.left != null) {
newTop.left.parent = top;
}
newTop.parent = top.parent;
replaceParentLink(top, newTop);
newTop.left = top;
top.parent = newTop;
}
private void rotateRight(Node top) {
Node newTop = top.left;
top.left = newTop.right;
if (newTop.right != null) {
newTop.right.parent = top;
}
newTop.parent = top.parent;
replaceParentLink(top, newTop);
newTop.right = top;
top.parent = newTop;
}
private void replaceParentLink(Node oldChild, Node newChild) {
if (oldChild.parent == null) {
root = newChild;
} else if (oldChild == oldChild.parent.left) {
oldChild.parent.left = newChild;
} else {
oldChild.parent.right = newChild;
}
}
private Color colorOf(Node node) {
return node == null ? Color.BLACK : node.color;
}
public void printSummary() {
List<String> ordered = new ArrayList<>();
collectInOrder(root, ordered);
System.out.println("中序遍历: " + ordered);
System.out.println("根节点颜色: " + root.color);
System.out.println("树高: " + height(root));
System.out.println("无连续红节点: " + hasNoRedRed(root));
System.out.println("黑高一致: " + (blackHeight(root) >= 0));
}
private void collectInOrder(Node node, List<String> ordered) {
if (node == null) {
return;
}
collectInOrder(node.left, ordered);
ordered.add(node.key + (node.color == Color.RED ? "R" : "B"));
collectInOrder(node.right, ordered);
}
private int height(Node node) {
return node == null ? 0 : Math.max(height(node.left), height(node.right)) + 1;
}
private boolean hasNoRedRed(Node node) {
if (node == null) {
return true;
}
if (node.color == Color.RED
&& (colorOf(node.left) == Color.RED || colorOf(node.right) == Color.RED)) {
return false;
}
return hasNoRedRed(node.left) && hasNoRedRed(node.right);
}
private int blackHeight(Node node) {
if (node == null) {
return 1;
}
int left = blackHeight(node.left);
int right = blackHeight(node.right);
if (left < 0 || right < 0 || left != right) {
return -1;
}
return left + (node.color == Color.BLACK ? 1 : 0);
}
public static void main(String[] args) {
RedBlackTreeDemo tree = new RedBlackTreeDemo();
int[] values = {10, 20, 30, 15, 25, 5, 1};
for (int value : values) {
tree.insert(value);
}
tree.printSummary();
}
}将代码保存为 RedBlackTreeDemo.java,然后编译运行:
javac RedBlackTreeDemo.java
java RedBlackTreeDemo预期输出:
中序遍历: [1R, 5B, 10R, 15B, 20B, 25R, 30B]
根节点颜色: BLACK
树高: 4
无连续红节点: true
黑高一致: true输出中的 R 与 B 分别表示红色和黑色。中序键值递增验证搜索树顺序,后两项验证没有红红相邻,并且各根到空叶路径的黑节点数量一致。
常见错误与练习
实现旋转时最容易遗漏父指针或祖父到新子树根的连接,结果可能出现环、丢失节点或后续空指针异常。另一个常见误区是只检查根为黑和没有连续红节点,却未验证黑高一致;这两项通过仍不足以证明整棵树合法。
- 将输入改为
{30, 20, 10},记录发生的旋转和重新着色,并验证最终根节点为黑。 - 在每次插入后调用性质校验,要求一旦黑高不一致就立即抛出异常并打印当前插入键。
- 比较同一组递增数据在普通二叉搜索树、AVL 树和红黑树中的高度,验收时分别解释三者的平衡强度与更新成本差异。
本课总结
- 红黑树以颜色和黑高约束实现近似平衡,树高上界保证核心操作为 。
- 插入红节点可避免立即改变黑高;父叔同红主要靠重新着色,叔黑场景通常需要旋转与着色配合。
- 验证红黑树不能只看形状,还必须同时检查搜索顺序、根颜色、红红约束和黑高一致。
下一课预告
下一阶段将继续比较平衡搜索树在查询频率、更新频率、内存占用以及外部存储场景中的工程取舍。