红黑树
2025/12/3大约 6 分钟
红黑树
一、什么是红黑树？
红黑树是一种自平衡的二叉查找树，它在二叉查找树的基础上增加了颜色属性和平衡规则，确保树的高度始终保持在O(log n)级别，从而保证各种操作的时间复杂度为O(log n)。
二、红黑树的五大特性
红黑树必须满足以下五个核心特性：
- 节点颜色特性：每个节点要么是红色，要么是黑色
- 根节点特性：根节点必须是黑色
- 叶子节点特性：所有叶子节点（NIL节点）都是黑色
- 红色节点特性：红色节点的两个子节点都必须是黑色（即不能有连续的红色节点）
- 黑色高度特性：从任意节点到其所有后代叶子节点的路径上，黑色节点的数量必须相同
三、为什么需要红黑树？
二叉查找树的问题
- 普通二叉查找树在极端情况下会退化为链表（时间复杂度O(n)）
- 插入顺序严重影响树的平衡性
红黑树的优势
- 平衡性：保证最坏情况下时间复杂度为O(log n)
- 高效性：查找、插入、删除操作都很高效
- 稳定性：适合需要频繁插入删除的场景
四、红黑树的基本结构
class RBNode<K, V> {
K key; // 键
V value; // 值
RBNode<K, V> left; // 左子节点
RBNode<K, V> right; // 右子节点
RBNode<K, V> parent; // 父节点
boolean color; // 颜色（true=红，false=黑）
}五、红黑树的操作原理
1. 查找操作
查找操作与普通二叉查找树完全相同：
- 从根节点开始比较
- 小于当前节点则向左子树查找
- 大于当前节点则向右子树查找
- 等于当前节点则返回
时间复杂度：O(log n)
2. 插入操作
插入操作分为两个阶段：
第一阶段：普通BST插入
- 按照二叉查找树的规则插入新节点
- 新插入的节点默认为红色
第二阶段：平衡调整
当插入后违反红黑树特性时，需要进行旋转和重新着色：
情况1：叔叔节点是红色
- 将父节点和叔叔节点变为黑色
- 祖父节点变为红色
- 将祖父节点作为新的当前节点继续调整
情况2：叔叔节点是黑色，当前节点是右孩子
- 以父节点为支点进行左旋
- 转换为情况3
情况3：叔叔节点是黑色，当前节点是左孩子
- 将父节点变为黑色
- 祖父节点变为红色
- 以祖父节点为支点进行右旋
3. 删除操作
删除操作是最复杂的，分为三个阶段：
第一阶段：普通BST删除
- 找到要删除的节点
- 根据子节点数量处理：
- 无子节点：直接删除
- 一个子节点：用子节点替代
- 两个子节点：用后继节点替代
第二阶段：处理双黑问题
当删除黑色节点后，可能出现"双黑"问题，需要通过旋转和重新着色解决：
情况1：兄弟节点是红色
- 将兄弟节点变为黑色
- 父节点变为红色
- 对父节点进行左旋/右旋
情况2：兄弟节点是黑色，且兄弟的两个子节点都是黑色
- 将兄弟节点变为红色
- 将父节点作为新的当前节点
情况3：兄弟节点是黑色，且兄弟的左孩子是红色，右孩子是黑色
- 将兄弟节点变为红色
- 兄弟的左孩子变为黑色
- 对兄弟节点进行右旋
情况4：兄弟节点是黑色，且兄弟的右孩子是红色
- 将兄弟节点的颜色设为父节点的颜色
- 将父节点设为黑色
- 将兄弟的右孩子设为黑色
- 对父节点进行左旋
六、旋转操作详解
1. 左旋（Left Rotation）
以节点x为支点进行左旋：
x y
/ \ / \
a y → x c
/ \ / \
b c a b2. 右旋（Right Rotation）
以节点y为支点进行右旋：
y x
/ \ / \
x c → a y
/ \ / \
a b b c七、红黑树的应用场景
1. Java集合框架
- TreeMap：基于红黑树实现的有序映射
- TreeSet：基于红黑树实现的有序集合
2. 数据库系统
- 数据库索引（如B+树的节点内部使用红黑树）
- 内存数据库的索引结构
3. 操作系统
- Linux内核的进程调度
- 虚拟内存管理
4. 网络系统
- 路由表管理
- 定时器实现
八、红黑树 vs AVL树
| 特性 | 红黑树 | AVL树 |
|---|---|---|
| 平衡性 | 相对平衡 | 严格平衡 |
| 插入删除 | 旋转次数较少 | 旋转次数较多 |
| 查找性能 | 稍慢 | 更快 |
| 适用场景 | 频繁插入删除 | 频繁查找 |
| 实现复杂度 | 相对简单 | 相对复杂 |
九、红黑树的性能分析
时间复杂度
- 查找：O(log n)
- 插入：O(log n)
- 删除：O(log n)
- 旋转操作：O(1)
空间复杂度
- O(n) - 需要存储n个节点
十、实际代码示例（Java）
public 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 value;
Node left, right;
boolean color;
Node(K key, V value, boolean color) {
this.key = key;
this.value = value;
this.color = color;
}
}
private Node root;
// 判断节点颜色
private boolean isRed(Node node) {
if (node == null) return BLACK;
return node.color == RED;
}
// 左旋操作
private Node rotateLeft(Node h) {
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = RED;
return x;
}
// 右旋操作
private Node rotateRight(Node h) {
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = RED;
return x;
}
// 颜色翻转
private void flipColors(Node h) {
h.color = RED;
h.left.color = BLACK;
h.right.color = BLACK;
}
// 插入操作
public void put(K key, V value) {
root = put(root, key, value);
root.color = BLACK; // 根节点始终为黑色
}
private Node put(Node h, K key, V value) {
if (h == null) return new Node(key, value, RED);
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = put(h.left, key, value);
else if (cmp > 0) h.right = put(h.right, key, value);
else h.value = value;
// 平衡调整
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
if (isRed(h.left) && isRed(h.right)) flipColors(h);
return h;
}
}十一、总结
红黑树是一种非常实用的自平衡二叉查找树，它通过简单的颜色规则和旋转操作，在保持较好平衡性的同时，提供了高效的插入和删除性能。虽然它的平衡性不如AVL树严格，但在实际应用中，红黑树往往更适合需要频繁更新数据的场景。
关键要点：
- 理解五大特性是掌握红黑树的基础
- 插入和删除的平衡调整需要熟练掌握各种情况
- 红黑树在工程实践中应用广泛，是重要的数据结构
- 相比AVL树，红黑树更适合写多读少的场景
红黑树的设计体现了计算机科学中"以空间换时间"和"局部调整保证全局平衡"的重要思想，是数据结构与算法学习中的重要内容。