理解红黑树的原理
简单的类比
想象你在盖一座形状奇特的摩天大楼。为了保证大楼不倒，建筑局（红黑树协议）做了下面的规定：
- 黑色节点 = 承重钢梁：黑色节点是整座大楼的硬骨架。无论你走哪条楼梯，从顶楼到地面的黑色承重梁数量必须完全一样。
- 红色节点 = 柔性连接件：红色节点是挂在承重钢架上的连接支架，两个红色支架决不能直接连在一起。因为红红不能相连，大楼最坏的情况也只是 “黑-红-黑-红”，这就保证了最长的那条路（红黑相间）顶多是短的那条路（全黑）的两倍。
为什么变色就能解决问题
当你要往楼里塞一个新的红色支架（新节点）时，如果它撞上了另一个红支架，结构就违规了。
- 场景A：上边的 “叔叔节点” 也是红色。想象你正要把一个红支架塞到左边，你发现上边一层叔叔位置的节点也是红色的，这说明叔叔这层的 “压力” 很大。你应该把这一层的两个红支架都涂成黑色，把它们变成坚固的承重梁。同时，为了保持 “每条路径黑色总量不变”，你必须把支撑它们的更上一层梁（爷爷）涂成红色，变成柔性件。这就像是在做一个 “压力的向上平移”。我们没有大动干戈去拆楼（旋转），只是重新分配了哪一层承担重量，哪一层负责柔韧。
- 场景B：叔叔是黑色或不存在（必须旋转）。如果右边没东西或者已经是死板的黑梁了，压力没地方排。这时候只能通过 “物理改造”，把局部结构重新焊接，改变支撑角度。
红黑颜色的本质
颜色代表了一种 “空间折叠”。
- 黑色节点：是树的 “脊梁骨”。红黑树最核心的规则是 “从根到叶子的每一条路径，黑色节点的数量必须相同”，这确保了树的基本平衡。
- 红色节点：是黑色的 “附属”。你可以把红色节点看作是与其父黑色节点 “合并” 在一起的一个大节点。
红黑树的哲学
红黑树不追求 AVL 树那种 “绝对的公平”，它追求的是 “大致的平衡”。
- 变色：是优先选择的轻量级调解。
- 旋转：是调解无效后的最后手段。
这种 “能动口（变色）绝不动手（旋转）” 的策略，使得红黑树在处理频繁的数据变动时，整体效率极高。
五大核心准则
在说红黑树的核心准则之前，我们需要澄清一个概念，那就是红黑树中的叶子节点。红黑树世界中的叶子节点和我们常说的普通叶子节点并不一样，比如1-2-3 这棵树中的 1 和 3，在普通二叉树里，我们把节点1和节点3叫叶子节点，但在红黑树的数学定义里，为了保证算法的严谨性，每一个 “末端节点” 下面还挂着两个看不见的、不存数据的空节点（NIL 节点），它们才是红黑树中真正的叶子结点。
1
2
3
4
5
| 2[黑]
/ \
1[红] 3[红]
/ \ / \
[N] [N] [N] [N] <-- 这些[N]才是规则3说的黑色叶子
|
有了这个概念的铺垫，我们再来看红黑树的五大铁律：
- ① 所有节点非黑即红：这就像是零件的分类，黑色是承重钢梁，红色是连接挂件，没有灰色地带。
- ② 根节点必须是黑色：大楼的地基必须是最稳固的黑色钢梁。即使变色过程把压力推到了顶端，最后也要强行把根节点漆回黑色。
- ③ 叶子节点必为黑色：所有的空叶子节点（NIL 节点）都是黑色的，大楼的所有末梢（死胡同）都用黑色的封条封死，确保算法在边界处也能逻辑自洽。
- ④ 红色节点不可连续：这是限高令的核心。红支架后面必须跟着黑钢梁。这条规则限制了树的“虚胖”，确保了红色节点被黑色节点隔开。
- ⑤ 黑色节点完美平衡：从任一节点到其每个叶子的路径，必须包含相同数量的黑色节点。这是红黑树最神圣的一条，它要求无论你怎么走，脚底踩过的 “钢梁” 数量必须一致。这在本质上保证了树的 “重力平衡”。
红黑树核心代码
以下是红黑树的核心实现：
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
public class MyRBTree {
private static final boolean RED = true;
private static final boolean BLACK = false;
private static final TreeNode NIL;
static {
NIL = new TreeNode(-1, BLACK);
NIL.left = NIL.right = NIL.p = NIL;
}
private TreeNode root = NIL;
public static class TreeNode {
int value;
boolean color;
TreeNode left, right, p;
public TreeNode(int value, boolean color) {
this.value = value;
this.color = color;
}
}
public boolean insert(int value) {
TreeNode y = NIL;
TreeNode x = this.root;
while (x != NIL) {
y = x;
if (value < x.value) x = x.left;
else if (value > x.value) x = x.right;
else return false;
}
TreeNode z = new TreeNode(value, RED);
z.p = y;
if (y == NIL) root = z;
else if (z.value < y.value) y.left = z;
else y.right = z;
z.left = NIL;
z.right = NIL;
fixAfterInsertion(z);
return true;
}
private void fixAfterInsertion(TreeNode z) {
while (z.p.color == RED) {
if (z.p == z.p.p.left) {
TreeNode y = z.p.p.right;
if (y.color == RED) {
z.p.color = BLACK;
y.color = BLACK;
z.p.p.color = RED;
z = z.p.p;
} else {
if (z == z.p.right) {
z = z.p;
leftRotate(z);
}
z.p.color = BLACK;
z.p.p.color = RED;
rightRotate(z.p.p);
}
} else {
TreeNode y = z.p.p.left;
if (y.color == RED) {
z.p.color = BLACK;
y.color = BLACK;
z.p.p.color = RED;
z = z.p.p;
} else {
if (z == z.p.left) {
z = z.p;
rightRotate(z);
}
z.p.color = BLACK;
z.p.p.color = RED;
leftRotate(z.p.p);
}
}
}
root.color = BLACK;
NIL.color = BLACK;
}
private void leftRotate(TreeNode x) {
TreeNode y = x.right;
x.right = y.left;
if (y.left != NIL) y.left.p = x;
y.p = x.p;
if (x.p == NIL) root = y;
else if (x == x.p.left) x.p.left = y;
else x.p.right = y;
y.left = x;
x.p = y;
}
private void rightRotate(TreeNode y) {
TreeNode x = y.left;
y.left = x.right;
if (x.right != NIL) x.right.p = y;
x.p = y.p;
if (y.p == NIL) root = x;
else if (y == y.p.left) y.p.left = x;
else y.p.right = x;
x.right = y;
y.p = x;
}
public boolean contains(int value) {
TreeNode x = root;
while (x != NIL) {
if (value == x.value) return true;
x = value < x.value ? x.left : x.right;
}
return false;
}
public void displayTree() {
printTree(root, 0);
}
private void printTree(TreeNode node, int level) {
if (node == NIL) return;
printTree(node.right, level + 1);
String color = node.color == RED ? "(R)" : "(B)";
System.out.println("|\t".repeat(Math.max(0, level)) + "|---" + node.value + color);
printTree(node.left, level + 1);
}
public static void main(String[] args) {
MyRBTree rbt = new MyRBTree();
int[] nodes = {10, 20, 30, 15, 25};
for (int v : nodes) {
System.out.println(">>> 插入节点: " + v);
rbt.insert(v);
rbt.displayTree();
System.out.println("-------------------------");
}
System.out.println(rbt.contains(15));
System.out.println(rbt.contains(99));
}
}
|
测试结果：
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
| >>> 插入节点: 10
|---10(B)
-------------------------
>>> 插入节点: 20
| |---20(R)
|---10(B)
-------------------------
>>> 插入节点: 30
| |---30(R)
|---20(B)
| |---10(R)
-------------------------
>>> 插入节点: 15
| |---30(B)
|---20(B)
| | |---15(R)
| |---10(B)
-------------------------
>>> 插入节点: 25
| |---30(B)
| | |---25(R)
|---20(B)
| | |---15(R)
| |---10(B)
-------------------------
true
false
|