红黑树是一种自平衡的二叉搜索树，被广泛应用于各种语言的标准库中，如Java的TreeMap/TreeSet、C++的std::map/std::set等。本文详细介绍红黑树的原理、性质和操作。
为什么需要红黑树
普通二叉搜索树的问题
普通BST在最坏情况下会退化成链表：
1
2
3
4
5
6
7
8
9
10
11
12
13
| 插入序列：1, 2, 3, 4, 5
1
\
2
\
3
\
4
\
5
查找时间复杂度退化为O(n)
|
解决方案：自平衡
红黑树通过着色规则和旋转操作保持树的平衡，确保最坏情况下查找、插入、删除的时间复杂度都是O(log n)。
红黑树的定义
红黑树是满足以下五条性质的二叉搜索树：
- 节点着色：每个节点是红色或黑色
- 根节点为黑：根节点必须是黑色
- 叶子为黑：所有叶子节点（NIL节点）是黑色
- 红色节点的子节点为黑：红色节点的两个子节点都是黑色（不能有连续的红节点）
- 黑高相同：从任一节点到其所有后代叶子节点的路径上，黑色节点数量相同
1
2
3
4
5
6
7
8
9
| 8(B)
/ \
4(R) 12(R)
/ \ / \
2(B) 6(B) 10(B) 14(B)
/ \ / \ / \ / \
N N N N N N N N
B = Black, R = Red, N = NIL(黑色叶子)
|
为什么这些性质能保证平衡？
关键推论：从根到叶子的最长路径不会超过最短路径的2倍。
证明：
- 最短路径：全是黑节点
- 最长路径：红黑交替（因为不能连续红）
- 由于黑高相同，最长路径最多是黑节点数的2倍
因此，n个节点的红黑树高度最多为2log(n+1)，保证O(log n)复杂度。
节点结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class RBNode<K, V> {
K key;
V value;
RBNode<K, V> left;
RBNode<K, V> right;
RBNode<K, V> parent;
boolean isRed;
RBNode(K key, V value) {
this.key = key;
this.value = value;
this.isRed = true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| template<typename K, typename V>
struct RBNode {
K key;
V value;
RBNode* left;
RBNode* right;
RBNode* parent;
bool isRed;
RBNode(K k, V v) : key(k), value(v), left(nullptr),
right(nullptr), parent(nullptr), isRed(true) {}
};
|
旋转操作
旋转是红黑树维持平衡的核心操作，分为左旋和右旋。
左旋（Left Rotate）
将节点X的右子节点Y提升为X的父节点，X变为Y的左子节点。
1
2
3
4
5
| X Y
/ \ 左旋 / \
a Y ------> X c
/ \ / \
b c a b
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void leftRotate(RBNode<K, V> x) {
RBNode<K, V> y = x.right;
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;
}
|
右旋（Right Rotate）
将节点Y的左子节点X提升为Y的父节点，Y变为X的右子节点。
1
2
3
4
5
| Y X
/ \ 右旋 / \
X c ------> a Y
/ \ / \
a b b c
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void rightRotate(RBNode<K, V> y) {
RBNode<K, V> x = y.left;
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;
}
|
旋转的性质
旋转操作保持二叉搜索树的性质：
- 左旋/右旋后，中序遍历结果不变
- 时间复杂度O(1)
查找操作
红黑树的查找与普通BST完全相同：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| V get(K key) {
RBNode<K, V> node = root;
while (node != null) {
int cmp = key.compareTo(node.key);
if (cmp < 0) {
node = node.left;
} else if (cmp > 0) {
node = node.right;
} else {
return node.value;
}
}
return null;
}
|
插入操作
插入步骤
- 按BST规则找到插入位置
- 插入新节点（默认红色）
- 修复红黑树性质
为什么新节点是红色？ 因为插入红节点不会违反性质5（黑高相同），只可能违反性质4（连续红节点），修复更简单。
插入修复
插入红色节点后，可能出现以下情况需要修复：
设新插入节点为N，父节点为P，叔节点为U，祖父节点为G。
情况1：父节点是黑色
无需修复，所有性质都满足。
情况2：父节点是红色（需要修复）
此时违反性质4（连续红节点）。根据叔节点颜色分类处理：
Case 2.1：叔节点是红色
1
2
3
4
5
| G(B) G(R) ← 变红，继续向上修复
/ \ / \
P(R) U(R) ==> P(B) U(B) ← 变黑
/ /
N(R) N(R)
|
操作：P和U变黑，G变红，然后以G为新节点继续向上修复。
Case 2.2：叔节点是黑色，N是P的右子节点（P是G的左子节点）
1
2
3
4
5
| G(B) G(B)
/ \ / \
P(R) U(B) ==> N(R) U(B) 然后变成Case 2.3
\ /
N(R) P(R)
|
操作：对P左旋，转化为Case 2.3。
Case 2.3：叔节点是黑色，N是P的左子节点（P是G的左子节点）
1
2
3
4
5
| G(B) P(B)
/ \ / \
P(R) U(B) ==> N(R) G(R)
/ \
N(R) U(B)
|
操作：P变黑，G变红，对G右旋。
插入修复代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| void insertFixup(RBNode<K, V> node) {
while (node.parent != null && node.parent.isRed) {
if (node.parent == node.parent.parent.left) {
RBNode<K, V> uncle = node.parent.parent.right;
if (uncle != null && uncle.isRed) {
node.parent.isRed = false;
uncle.isRed = false;
node.parent.parent.isRed = true;
node = node.parent.parent;
} else {
if (node == node.parent.right) {
node = node.parent;
leftRotate(node);
}
node.parent.isRed = false;
node.parent.parent.isRed = true;
rightRotate(node.parent.parent);
}
} else {
RBNode<K, V> uncle = node.parent.parent.left;
if (uncle != null && uncle.isRed) {
node.parent.isRed = false;
uncle.isRed = false;
node.parent.parent.isRed = true;
node = node.parent.parent;
} else {
if (node == node.parent.left) {
node = node.parent;
rightRotate(node);
}
node.parent.isRed = false;
node.parent.parent.isRed = true;
leftRotate(node.parent.parent);
}
}
}
root.isRed = false;
}
|
插入示例
依次插入：10, 20, 30, 15, 25, 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| 插入10（根节点，变黑）：
10(B)
插入20：
10(B)
\
20(R)
插入30（触发修复，Case 2.3）：
10(B) 20(B)
\ 右旋后 / \
20(R) ------> 10(R) 30(R)
\
30(R)
插入15：
20(B)
/ \
10(R) 30(R)
\
15(R)
叔节点30是红色（Case 2.1），变色：
20(B)
/ \
10(B) 30(B)
\
15(R)
插入25：
20(B)
/ \
10(B) 30(B)
\ /
15(R) 25(R)
插入5：
20(B)
/ \
10(B) 30(B)
/ \ /
5(R) 15(R) 25(R)
|
删除操作
删除是红黑树最复杂的操作。
删除步骤
- 按BST规则删除节点
- 如果删除的是黑色节点，需要修复
BST删除回顾
- 叶子节点：直接删除
- 只有一个子节点：子节点替代
- 有两个子节点：找后继（或前驱）替代，然后删除后继
删除修复
只有删除黑色节点才需要修复（因为黑高变了）。
设被删节点的替代者为N，兄弟为S，父为P。
Case 1：兄弟S是红色
1
2
3
4
5
| P(B) S(B)
/ \ / \
N(B) S(R) ==> P(R) SR(B)
/ \ / \
SL(B) SR(B) N(B) SL(B)
|
操作：S变黑，P变红，对P左旋。转化为其他情况。
Case 2：兄弟S是黑色，S的两个子节点都是黑色
1
2
3
4
5
6
7
| P(?) P(?)
/ \ / \
N(B) S(B) ==> N(B) S(R)
/ \ / \
SL(B) SR(B) SL(B) SR(B)
然后以P为新的N继续修复
|
操作：S变红，以P为新节点继续向上修复。
Case 3：兄弟S是黑色，S的左子红，右子黑
1
2
3
4
5
6
7
| P(?) P(?)
/ \ / \
N(B) S(B) ==> N(B) SL(B)
/ \ \
SL(R) SR(B) S(R)
\
SR(B)
|
操作：SL变黑，S变红，对S右旋。转化为Case 4。
Case 4：兄弟S是黑色，S的右子是红色
1
2
3
4
5
| P(?) S(?)
/ \ / \
N(B) S(B) ==> P(B) SR(B)
/ \ / \
SL(?) SR(R) N(B) SL(?)
|
操作：S变为P的颜色，P变黑，SR变黑，对P左旋。修复完成。
删除修复代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| void deleteFixup(RBNode<K, V> node, RBNode<K, V> parent) {
while (node != root && (node == null || !node.isRed)) {
if (node == parent.left) {
RBNode<K, V> sibling = parent.right;
if (sibling.isRed) {
sibling.isRed = false;
parent.isRed = true;
leftRotate(parent);
sibling = parent.right;
}
if ((sibling.left == null || !sibling.left.isRed) &&
(sibling.right == null || !sibling.right.isRed)) {
sibling.isRed = true;
node = parent;
parent = node.parent;
} else {
if (sibling.right == null || !sibling.right.isRed) {
if (sibling.left != null) {
sibling.left.isRed = false;
}
sibling.isRed = true;
rightRotate(sibling);
sibling = parent.right;
}
sibling.isRed = parent.isRed;
parent.isRed = false;
if (sibling.right != null) {
sibling.right.isRed = false;
}
leftRotate(parent);
node = root;
}
} else {
}
}
if (node != null) {
node.isRed = false;
}
}
|
红黑树 vs AVL树
| 特性 |
红黑树 |
AVL树 |
| 平衡条件 |
黑高相同 |
左右子树高度差≤1 |
| 平衡程度 |
相对宽松 |
严格平衡 |
| 查找效率 |
O(log n) |
O(log n)，略快 |
| 插入效率 |
最多2次旋转 |
最多2次旋转 |
| 删除效率 |
最多3次旋转 |
可能O(log n)次旋转 |
| 适用场景 |
插入删除频繁 |
查找频繁 |
为什么Java/C++选择红黑树？
- 删除效率更稳定：红黑树删除最多3次旋转，AVL可能需要O(log n)次
- 实现相对简单：红黑树的平衡条件更宽松
- 综合性能好：虽然查找略慢，但插入删除更快
实际应用
Java中的红黑树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
TreeMap<String, Integer> map = new TreeMap<>();
map.put("banana", 2);
map.put("apple", 1);
map.put("cherry", 3);
TreeSet<Integer> set = new TreeSet<>();
set.add(3);
set.add(1);
set.add(2);
HashMap<String, Integer> hashMap = new HashMap<>();
|
C++中的红黑树
1
2
3
4
5
6
7
8
9
10
11
|
std::map<std::string, int> map;
map["banana"] = 2;
map["apple"] = 1;
std::set<int> set;
set.insert(3);
set.insert(1);
|
Linux内核中的红黑树
Linux内核广泛使用红黑树：
- 进程调度（CFS调度器）
- 内存管理（虚拟内存区域）
- 文件系统（ext3的目录索引）
时间复杂度总结
| 操作 |
平均 |
最坏 |
| 查找 |
O(log n) |
O(log n) |
| 插入 |
O(log n) |
O(log n) |
| 删除 |
O(log n) |
O(log n) |
| 旋转次数（插入） |
O(1) |
O(1) |
| 旋转次数（删除） |
O(1) |
O(1) |
总结
红黑树的核心要点：
- 五条性质保证树的平衡（最长路径不超过最短路径的2倍）
- 新节点默认红色，只可能违反”不能连续红”的规则
- 插入修复：通过变色和旋转消除连续红节点
- 删除修复：通过变色和旋转恢复黑高平衡
- 旋转操作：左旋和右旋，O(1)时间，保持BST性质
红黑树是工程实践中最常用的平衡树，理解其原理有助于更好地使用TreeMap、TreeSet等数据结构。
