实现一个红黑树

前言

感受一下红黑树的死亡旋转。

正文

红黑树的特性:

根节点为黑色

叶子节点(也就是 null)为黑色

如果某个节点为红色,那么他的两个子节点必须都是黑色的

从某个结点出发,经历任何一种路径,其中经历的黑色节点数量是相同的

这几个特性保证了红黑树不会像普通的二叉查找树那样产生退化成链表的情况。
另外,后两个特性保证了从红黑树的任意节点到其每个叶子节点的路径最长不会超过最短路径的 2 倍。

代码实现:

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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
package io.since1986.demo;

import static io.since1986.demo.BlackRedTree.Node.Color.BLACK;
import static io.since1986.demo.BlackRedTree.Node.Color.RED;

/**
* 首先红黑树要满足二叉查找树的性质,也就是某个节点的左子节点的值比其值小,右子节点的值比其值大
* <p>
* 然后红黑树有四条特殊性质需要满足:
* 1. 根节点为黑色
* 2. 叶子节点为黑色
* 3. 如果某个节点为红色,那么他的两个子节点必须都是黑色的
* 4. 从某个结点出发,经历任何一种路径,其中经历的黑色节点数量是相同的
*/
public class BlackRedTree {

public static void main(String[] args) {
BlackRedTree blackRedTree = new BlackRedTree();
blackRedTree.add(1);
blackRedTree.add(3);
blackRedTree.add(2);
blackRedTree.add(4);
blackRedTree.add(5);
blackRedTree.add(6);
}

private Node root;

static class Node {

enum Color {
BLACK, RED
}

Color color;

int value;

Node leftChild;

Node rightChild;

Node parent;

Node(Color color, int value, Node leftChild, Node rightChild, Node parent) {
this.color = color;
this.value = value;
this.leftChild = leftChild;
this.rightChild = rightChild;
this.parent = parent;
}

public void setColor(Color color) {
this.color = color;
}

public void setValue(int value) {
this.value = value;
}

public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}

public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}

public void setParent(Node parent) {
this.parent = parent;
}

@Override
public String toString() {
return color.name() + String.format("(%s)", value);
}
}

/**
* 新插入节点均要是红色的,这样处理起来比较容易
*/
public void add(int value) {
if (root == null) {
// 如果当前根节点不存在,那么新节点就是根节点,根节点恒定为黑色节点
root = new Node(BLACK, value, null, null, null);
} else {
// 如果当前根节点已经存在(注意此时树中不一定只有根节点,还可能有若干根节点的子节点)

// 二分查找当前添加的值 value 在当前树中的位置,如果某个结点的值与value相等,那么这个value就不能再插入为新的节点了,如果没找到相等的,则最后找到的节点即为要插入节点的父节点
Node _current = root;
Node parent;
do {
parent = _current;
if (value == _current.value) {
return; // 二叉查找树中不允许出现重复值
}
if (value < _current.value) {
_current = _current.leftChild;
} else {
_current = _current.rightChild;
}
} while (_current != null); // currentNode 要是 null 的话就意味着当前已经到了叶子节点了(叶子节点就是空节点)就不需要再找下去了

// 将value和上一步找到的父节点的值相比较,如果大于则新插入节点为父节点的右子节点,反之为左子节点(二叉查找树的性质)
Node newNode = new Node(RED, value, null, null, parent); // 新插入的节点一开始为红色
if (value < parent.value) {
parent.leftChild = newNode;
} else {
parent.rightChild = newNode;
}
// 然后需要根据四条特性进行修正
fix(newNode);
}
}

/**
* 二分查找(红黑树本身也是二叉查找树,因此当然可以二分查找)
*/
public Node binarySearch(int value) {
Node current = root;
do {
if (value == current.value) {
return current;
}
if (value < current.value) {
current = current.leftChild;
} else {
current = current.rightChild;
}
} while (current != null);
return null;
}

private void fix(Node node) {
// 修正以满足四特性,注意当前插入的新节点 node 必是红色
node.color = RED;

// 先分为两种情况
// 一. 当前节点的父节点为黑色时,无需修正
// 二. 当前节点的父节点为红色时,再分为两种情况:
while (node != null && node != root && node.parent.color == RED) {
Node nodeParent = parentOf(node);
Node grandpa = parentOf(nodeParent);

// 1. 当前节点的父节点 parent 为当前节点爷爷节点 grandpa 的左子节点
if (nodeParent == leftChildOf(grandpa)) {
// 再分为两种情况:
Node uncle = rightChildOf(grandpa);
// 1.1 当前节点的叔叔节点 uncle 为红色
if (colorOf(uncle) == RED) {
// 将父节点设置为黑色
setColor(nodeParent, BLACK);
// 将叔叔节点设置为黑色
setColor(uncle, BLACK);
// 将爷爷节点设置为红色
setColor(grandpa, RED);
// 将爷爷节点设置为当前节点(也就是带入下次循环)
node = grandpa;
}

// 1.2 当前节点的叔叔节点 uncle 为黑色
else {
// 如果当前节点是父节点的右子节点
if (node == rightChildOf(nodeParent)) {
// 将当前节点设置为父节点
node = nodeParent;
// 左旋
rotateToLeft(node);
}
// 设置当前节点的父节点为黑色(这里要重新获得一遍父节点,因为在前面有可能改变了当前节点)
setColor(parentOf(node), BLACK);
// 设置新的当前节点的爷爷节点为红色
setColor(parentOf(parentOf(node)), RED);
// 将当前节点的爷爷节右旋
rotateToRight(parentOf(parentOf(node)));
}
}

// 2. 当前节点的父节点 parent 为当前节点爷爷节点 grandpa 的右子节点
else {
Node uncle = leftChildOf(grandpa);
// 2.1 当前节点的叔叔节点 uncle 为红色(和1.1其实是一样得流程)
if (colorOf(uncle) == RED) {
// 将父节点设置为黑色
setColor(nodeParent, BLACK);
// 将叔叔节点设置为黑色
setColor(uncle, BLACK);
// 将爷爷节点设置为红色
setColor(grandpa, RED);
// 将爷爷节点设置为当前节点(也就是带入下次循环)
node = grandpa;
}
// 2.2 当前节点的叔叔节点 uncle 为黑色(涉及旋转的操作和2.1流程中正好反向)
// 如果当前节点是父节点的左节点
if (node == leftChildOf(nodeParent)) {
// 将当前节点设置为父节点
node = nodeParent;
// 右旋
rotateToRight(node);
}
// 设置当前节点的父节点为黑色(这里要重新获得一遍父节点,因为在前面有可能改变了当前节点)
setColor(parentOf(node), BLACK);
// 设置新的当前节点的爷爷节点为红色
setColor(parentOf(parentOf(node)), RED);
// 将当前节点的爷爷节左旋
rotateToLeft(parentOf(parentOf(node)));
}
}

// 最后无论如何要将根节点设置为黑色
setColor(root, BLACK);
}

private void setColor(Node node, Node.Color color) {
if (node != null) {
node.color = color;
}
}

private Node.Color colorOf(Node node) {
return node == null ? BLACK : node.color;
}

private Node parentOf(Node node) {
return node == null ? null : node.parent;
}

private Node leftChildOf(Node node) {
return node == null ? null : node.leftChild;
}

private Node rightChildOf(Node node) {
return node == null ? null : node.rightChild;
}

/**
* 左旋
*
* @param node 当前要操作的目标节点
*/
private void rotateToLeft(Node node) {
if (node == null) {
return;
}

// 对当前节点 node 进行左旋操作
Node rightChild = node.rightChild; // 当前节点的右子节点
Node leftChildOfRightChild = rightChild.leftChild; // 当前节点右子节点的左子节点

// 将当前节点的右子节点赋值为leftChildOfRightChild
node.rightChild = leftChildOfRightChild;

// 如果leftChildOfRightChild不为空,则将他的父节点赋值为当前节点
if (leftChildOfRightChild != null) {
leftChildOfRightChild.parent = node;
}

// 将当前节点的右子节点的父节点赋值为当前节点的父节点
rightChild.parent = node.parent;

// 如果当前节点的父节点为空则将根节点赋值为rightChild
if (node.parent == null) {
root = rightChild;
}
// 如果当前节点为其父节点的左节点则将当前节点父节点的左子节点赋值为rightChild
else if (node == node.parent.leftChild) {
node.parent.leftChild = rightChild;
}
// 否则将当前节点父节点的右子节点赋值为rightChild
else {
node.parent.rightChild = rightChild;
}

// 将rightChild的左子节点赋值为当前节点
rightChild.leftChild = node;
// 将当前节点的父节点赋值为rightChild
node.parent = rightChild;
}

/**
* 右旋
*
* @param node 当前要操作的目标节点
*/
private void rotateToRight(Node node) {
if (node == null) {
return;
}

// 对当前节点 node 进行右旋操作
Node leftChild = node.leftChild; // 当前节点的左子节点
Node rightChildOfLeftChild = leftChild.rightChild; // 当前节点左子节点的右子节点

// 将当前节点的左子节点赋值为rightChildOfLeftChild
node.leftChild = rightChildOfLeftChild;

// 如果rightChildOfLeftChild不为空,则将他的父节点赋值为当前节点
if (rightChildOfLeftChild != null) {
rightChildOfLeftChild.parent = node;
}

// 将当前节点的左子节点的父节点赋值为当前节点的父节点
leftChild.parent = node.parent;

// 如果当前节点的父节点为空则将根节点赋值为leftChild
if (node.parent == null) {
root = leftChild;
}
// 如果当前节点为其父节点的右子节点则将当前节点父节点的右子节点赋值为leftChild
else if (node == node.parent.rightChild) {
node.parent.rightChild = leftChild;
}
// 否则将当前节点父节点的左子节点赋值为leftChild
else {
node.parent.leftChild = leftChild;
}

// 将leftChild的右子节点赋值为当前节点
leftChild.rightChild = node;
// 将当前节点的父节点赋值为leftChild
node.parent = leftChild;
}
}

上边代码会生成这样的树: