红黑树基础
⚠️ 内容不完整 - 原始网页使用 JavaScript 动态渲染，静态抓取仅获取部分内容。待补充完整内容。
原始资料
一句话总结
红黑树是自平衡的二叉搜索树，它的树高在任何时候都能保持在 $O(\log N)$ （完美平衡），这样就能保证增删查改的时间复杂度都是 $O(\log N)$ 。
核心要点
问题背景
二叉搜索树的应用及可视化 讲了普通的二叉搜索树存储键值对实现 TreeMap/TreeSet 的思路。
二叉搜索树的操作效率取决于树高：
- 树结构越平衡，树高越接近 $\log N$，增删查改效率越高
- 普通二叉搜索树的问题：不会自动对树进行平衡，特殊情况下会退化成链表，时间复杂度退化为 $O(N)$
红黑树解决方案
红黑树通过自平衡机制，保证树高在任何时候都能保持在 $O(\log N)$，从而确保增删查改的时间复杂度都是 $O(\log N)$。
可视化资源
- 算法可视化面板：https://labuladong.online/algo-visualize/tutorial/red-black-tree/
- 更新时间：2026/04/30 16:36
前置知识
阅读本文前需要掌握：
- 二叉树基础及常见类型
- 多叉树的递归/层序遍历
- 树和映射数据结构基础
相关概念
- 二叉搜索树（已存在于概念库）
- 红黑树（待第2篇来源后创建独立概念页）
- 自平衡树（待第2篇来源后创建独立概念页）
- TreeMap / TreeSet
红黑树的五条性质
红黑树通过以下五条性质来保持近似平衡：
- 每个节点要么是红色，要么是黑色
- 根节点是黑色的
- 所有叶子节点（NIL 空节点）是黑色的
- 红色节点的两个子节点都必须为黑色（不能有两个连续的红色节点）
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（黑高相同）
💡 为什么这五条性质能保证树高 O(logN)？ 性质 4 和 5 共同起作用：性质 4 保证没有两个相邻红节点，性质 5 保证任意路径黑节点数相同。可以证明，这样的树高最多是 2log₂(N+1)，即 O(logN)。
平衡操作：旋转与变色
当插入或删除节点破坏红黑树性质时，需要通过旋转和变色来恢复平衡。
左旋（leftRotate）
x y
/ \ / \
a y ,> x c
/ \ / \
b c a b
左旋操作：将节点 x 的右子节点 y 提升为新的子树根，x 成为 y 的左子节点。
右旋（rightRotate）
y x
/ \ / \
x c ,> a y
/ \ / \
a b b c
右旋操作：将节点 y 的左子节点 x 提升为新的子树根，y 成为 x 的右子节点。
插入操作
红黑树插入分为两步：
第一步：按 BST 规则插入
像普通二叉搜索树一样找到插入位置，新节点初始颜色设为红色（为什么？因为插入红色节点只会破坏性质 2 和 4，而插入黑色节点一定会破坏性质 5）。
第二步：修复红黑树性质
插入红色节点后，可能违反性质 2（根变红）或性质 4（出现连续红节点）。需要根据父节点、叔叔节点的颜色进行分类调整：
| 情况 | 描述 | 处理方式 |
|---|---|---|
| 情况1 | 父节点黑色 | 无需调整，直接结束 |
| 情况2 | 父节点红色，叔叔节点红色 | 父、叔变黑，祖父变红，继续向上修复 |
| 情况3 | 父节点红色，叔叔黑色，"内侧"插入 | 先旋转变成情况4 |
| 情况4 | 父节点红色，叔叔黑色，"外侧"插入 | 旋转+变色，修复完成 |
📝 口诀：叔叔红则变颜色向上传，叔叔黑则旋转+变色搞定。
删除操作（简要）
删除操作比插入更复杂，分为：
- 按 BST 删除规则删除节点（找到后继或前驱替换）
- 如果删除的是红色节点，不影响黑高，无需调整
- 如果删除的是黑色节点，需要通过旋转和变色来恢复黑高
删除的修复情况更多（约 8 种情况），这里不展开，核心思想是通过借节点或合并节点来恢复性质。
与 AVL 树的对比
| 对比项 | 红黑树 | AVL 树 |
|---|---|---|
| 平衡严格度 | 近似平衡（弱） | 严格平衡（强） |
| 树高上限 | 2log₂(N+1) | log₂(N+1) |
| 查询速度 | 稍慢（树高稍高） | 更快（树高更低） |
| 插入调整 | 最多 2 次旋转 | 可能需要 O(logN) 次旋转 |
| 删除调整 | 最多 3 次旋转 | 可能需要 O(logN) 次旋转 |
| 适用场景 | 插入删除频繁 | 查询频繁，修改少 |
| 典型应用 | Java TreeMap/TreeSet | 数据库索引 |
Java 代码框架
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;
boolean color; // RED or BLACK
Node(K key, V val, boolean color) {
this.key = key;
this.val = val;
this.color = color;
}
}
private Node root;
// 左旋
private Node leftRotate(Node x) {
Node y = x.right;
x.right = y.left;
y.left = x;
y.color = x.color;
x.color = RED;
return y;
}
// 右旋
private Node rightRotate(Node y) {
Node x = y.left;
y.left = x.right;
x.right = y;
x.color = y.color;
y.color = RED;
return x;
}
// 颜色翻转（父红，两个子黑 → 父黑，两个子红）
private void flipColors(Node h) {
h.color = BLACK;
h.left.color = RED;
h.right.color = RED;
}
// 插入
public void put(K key, V val) {
root = put(root, key, val);
root.color = BLACK; // 性质2：根节点始终为黑
}
private Node put(Node h, K key, V val) {
if (h == null) return new Node(key, val, RED);
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = put(h.left, key, val);
else if (cmp > 0) h.right = put(h.right, key, val);
else h.val = val;
// 修复红黑树性质
if (isRed(h.right) && !isRed(h.left)) h = leftRotate(h);
if (isRed(h.left) && isRed(h.left.left)) h = rightRotate(h);
if (isRed(h.left) && isRed(h.right)) flipColors(h);
return h;
}
private boolean isRed(Node x) {
if (x == null) return false;
return x.color == RED;
}
}
时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 查找 | O(log N) | 树高 O(logN) |
| 插入 | O(log N) | 最多 2 次旋转 |
| 删除 | O(log N) | 最多 3 次旋转 |
典型应用
- Java：
TreeMap、TreeSet底层实现 - C++：
std::map、std::set底层实现（通常是红黑树变种） - Linux：进程调度完全公平调度器（CFS）使用红黑树管理进程
- Epoll：Linux epoll 使用红黑树管理就绪事件
⚠️ 内容说明：由于原网页使用 JavaScript 动态渲染，静态抓取仅获取前言部分。以上内容基于红黑树通用知识补充，非 labuladong 原文完整内容。如需原文，请在浏览器中打开原网页复制完整内容。