红黑树详解
一、介绍
作为一颗红黑树，它是一颗特殊的AVL树，也就是一颗特殊的平衡二叉树。
对于平衡二叉树而言，它的定义是，对于任何二叉树的任何一个节点，它的左子树和右子树的高度差不能大于1。
而为什么红黑树比较特殊，它除了满足平衡二叉树的特点之外，还有以下的几个特征
-
每一个节点都有一个状态，红色或者黑色
-
根节点是黑色
-
红黑树的叶子节点默认都是空引用的对象，默认都是黑色
-
==红色==节点的两个子节点都是黑色，也就是说**红色**节点不能相连
-
从任意节点，到叶子节点，其经过的路径上，黑色节点的个数都是一致的
AVL树是通过自旋转来完成的平衡
但是红黑树却不全是这样，它虽然有自旋，但主要是节点特性，加上任意节点到叶子节点经过的黑色节点数量来保证了树的子平衡。
出发点不同，则实现的方式完全不同
二、示例
首先，我们针对以上五个特性，先画一个红黑树
再次讲解一下特性
-
不是黑就是红，没什么好说的
-
根节点是黑的，也没什么好说的
-
叶子节点都是null节点，这我认为是模拟出来的节点，仅作为第5点平衡计算使用
-
红色节点的子节点一定是黑的，也就是说不能出现红红相连的情况
-
重点讲讲第五点
从任意节点，到叶子节点，其经过的路径上，黑色节点的个数都是一致的
-
比如说5这个节点，到达叶子节点一共有4种走法，每一种走法的黑色节点个数都是2个
5->4->null，其中5、null为黑色节点5->6->null，其中5、null为黑色节点
-
比如说10这个节点，到达叶子节点一共有6种走法，每一种走法的黑色节点个数都是3个
10->5->4->null，其中10、5、null为黑色节点10->5->6->null，其中10、5、null为黑色节点10->15->null，其中10、15、null为黑色节点
三、新增节点
当有新的元素插入时，红黑树是如何保证自身平衡的呢？
如果说AVL树是靠左旋和右旋保证平衡的，那么红黑树是靠左旋、右旋和变色来保证平衡
-
左旋：和AVL树一样进行向左旋转，保证高度差
-
右旋：和AVL树一样进行向右旋转，保证高度差
-
变色：红色节点变成黑色节点，黑色节点变成红色节点
假设我们对上面示例的红黑树进行插入，可以分为以下这几种情况
1）当前红黑树是空树
这种没什么好说的，直接把插入的节点设置成根节点即可，注意是黑色节点
2）如果插入节点的key已存在
找到节点，更新替换掉即可
3）当插入节点的父节点是黑色节点
保证插入节点是红色节点，直接插入即可，无需要额外的处理
为什么要保证插入节点是红色的？
假设有下面这个红黑树，将插入一个值为13的节点，那么直接就成为在黑色节点的子节点即可
| 开始 |
结果 |
 |
 |
那么插入的是黑色节点呢，那一定会破坏红黑树特性五，任一节点到根节点的路径上，其中黑色个数是一致的
那么如果是红色节点呢，就向上面的情况一样，说不定什么都不用处理
还有种情况就是，红色节点会遇到红色节点，出现红红相连的情况，违反了红黑树的特性四。
所以针对上面的情况，我们就默认新插入的节点就是红色的
4）当插入节点的父节点是红色节点时
根据特性二，根节点一定是黑色的，所以我们插入的节点一定有爷爷节点，包含祖宗三代。
由于插入节点是红色的，所以在本小节一定会出现红红相连的情况，根据不同的添加位置，我们有以下这几种情况
4.1）双红，且叔叔节点存在
看下面这个红黑色，当我们插入3节点后，出现双红的情况，也就是两个红色节点连接在了一起
| 开始 |
双红，且有叔叔节点 |
 |
 |
由于违反特性四，我们需要做一定的处理
-
首先需要变色
- 将父节点和叔叔节点变成黑色
- 爷爷节点变成红色
-
如果爷爷节点又出现了双红的情况，那再根据情况对应再进行处理即可
| 步骤 |
图解 |
| 双红的情况 |
 |
变色，
将父节点和叔叔节点变成黑色，
爷爷节点变成红色 |
 |
| 由于爷爷是根节点，这里需要变回黑色 |
 |
完成，又是一颗红黑树
4.2）左左红，且叔叔节点不存在
看下面这个红黑色，当我们插入3节点后，出现左左红的情况，也就是父节点是左节点，自己插入的位置也是左边。
并且注意它3节点没有叔叔节点
| 开始 |
左左红，且没有叔叔节点 |
 |
 |
由于违反特性四，我们需要做一定的处理
-
首先需要变色
- 将父节点变成黑色
- 爷爷节点变成红色
-
将爷爷节点进行右旋
-
如果爷爷节点又出现了双红的情况，那再根据情况对应再进行处理即可
左旋，右旋在AVL树有详细的讲解，
二叉树详解 | 半月无霜 (banmoon.top)
| 步骤 |
图解 |
| 左左红，且没有叔叔节点 |
 |
先变色，
将父节点变成黑色，
将爷爷节点变成红色 |
 |
| 再进行右旋 |
 |
完成，又是一颗红黑树
4.3）左右红，且叔叔节点不存在
看下面这个红黑色，当我们插入6节点后，出现左右红的情况，也就是父节点是左节点，自己插入的位置却是右边
| 开始 |
左右红，且叔叔节点不存在 |
 |
 |
红红相连，我们采用下面步骤进行处理
-
对父节点进行左旋
- 左旋完成后，你会发现左右红的情况，会变成左左红的情况，后面的步骤就是应对左左红的情况
-
变色
- 父节点变成黑色
- 爷爷节点变成红色
-
将爷爷节点进行右旋
-
如果爷爷节点又出现了双红的情况，那再根据情况对应再进行处理即可
| 步骤 |
图解 |
| 左右红，且叔叔节点不存在 |
 |
对父节点进行左旋
出现左左红的情况 |
 |
变色，
将父节点变成黑色，
将爷爷节点变成红色 |
 |
| 再进行右旋 |
 |
完成，又是一颗红黑树
4.4）右右红，且叔叔节点不存在
看下面这个红黑色，当我们插入11节点后，出现右右红的情况，也就是父节点是右节点，自己插入的位置也是右边
| 开始 |
右右红，且叔叔节点不存在 |
 |
 |
红红相连，我们采用下面步骤进行处理
-
变色
- 父节点变成黑色
- 爷爷节点变成红色
-
将爷爷节点进行左旋
-
如果爷爷节点又出现了双红的情况，那再根据情况对应再进行处理即可
| 步骤 |
图解 |
| 右右红，且叔叔节点不存在 |
 |
变色，
将父节点变成黑色，
将爷爷节点变成红色 |
 |
| 再进行右旋 |
 |
完成，又是一颗红黑树
4.5）右左红，且叔叔节点不存在
看下面这个红黑色，当我们插入11节点后，出现右右红的情况，也就是父节点是右节点，自己插入的位置也是右边
| 开始 |
右左红，且叔叔节点不存在 |
 |
 |
红红相连，我们采用下面步骤进行处理
-
变色
- 父节点变成黑色
- 爷爷节点变成红色
-
将爷爷节点进行左旋
-
如果爷爷节点又出现了双红的情况，那再根据情况对应再进行处理即可
| 步骤 |
图解 |
| 右左红，且叔叔节点不存在 |
 |
先对父节点进行右旋
出现右右红的情况 |
 |
变色，
将父节点变成黑色，
将爷爷节点变成红色 |
 |
| 再进行左旋 |
 |
完成，又是一颗红黑树
四、编码
1）基础
这里面只有最基本的代码
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
| package com.banmoon.datastructure;
import lombok.Data;
import static java.util.Objects.nonNull;
public class BRTree<K, V> {
public static final Boolean RED = true;
public static final Boolean BLACK = false;
public BRTreeNode<K, V> root;
public BRTree(K key, V value) {
root = new BRTreeNode<>(key, value, BLACK);
}
public void middleShow() {
if (nonNull(root)) {
root.middleShow();
}
}
@Data
public static class BRTreeNode<K, V> {
private K key;
private V value;
private Boolean color;
private BRTreeNode<K, V> parent;
private BRTreeNode<K, V> left;
private BRTreeNode<K, V> right;
public BRTreeNode(K key, V value) {
this(key, value, RED);
}
public BRTreeNode(K key, V value, Boolean color) {
this.key = key;
this.value = value;
this.color = color;
}
public void middleShow() {
if (nonNull(left))
left.middleShow();
System.out.println("key：" + key + "，value：" + value);
if (nonNull(right))
right.middleShow();
}
}
}
|
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
|
private void leftRotate(BRTreeNode<K, V> node) {
BRTreeNode<K, V> right = node.right;
BRTreeNode<K, V> parent = node.parent;
BRTreeNode<K, V> leftByRight = right.left;
if (nonNull(parent)) {
right.parent = parent;
parent.right = right;
} else {
right.parent = null;
this.root = right;
}
right.left = node;
node.parent = right;
node.right = leftByRight;
if (nonNull(leftByRight)) {
leftByRight.parent = node;
}
}
private void rightRotate(BRTreeNode<K, V> node) {
BRTreeNode<K, V> left = node.left;
BRTreeNode<K, V> parent = node.parent;
BRTreeNode<K, V> rightByLeft = left.right;
if (nonNull(parent)) {
left.parent = parent;
parent.left = left;
} else {
left.parent = null;
this.root = left;
}
left.right = node;
node.parent = left;
node.left = rightByLeft;
if (nonNull(rightByLeft)) {
rightByLeft.parent = node;
}
}
|
3）插入节点
这里插入节点，采用了这种模式，如果节点key相等，则进行节点的替换
大家可可以根据自己的策略需要来理解红黑树
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
|
public V add(K key, V value) {
if (Objects.isNull(this.root)) {
this.root = new BRTreeNode<>(key, value);
this.root.toggleColor();
return null;
} else {
return Optional.ofNullable(root.insert(new BRTreeNode<>(key, value), this))
.map(BRTreeNode::getValue)
.orElse(null);
}
}
@Data
public static class BRTreeNode<K extends Comparable<K>, V> {
public BRTreeNode<K, V> insert(BRTreeNode<K, V> node, BRTree<K, V> tree) {
K thisKey = this.key;
K insertKey = node.getKey();
int compare = thisKey.compareTo(insertKey);
if (compare == 0) {
node.parent = this.parent;
if (Objects.isNull(this.parent)) {
tree.root = node;
}
if (nonNull(this.left)) {
this.left.parent = node;
node.setLeft(this.left);
}
if (nonNull(this.right)) {
this.right.parent = node;
node.setRight(this.right);
}
node.setColor(this.color);
return this;
}
else if (compare > 0) {
if (nonNull(this.left)) {
this.left.insert(node, tree);
} else {
this.left = node;
node.parent = this;
node.balanceTree(true, tree);
}
}
else {
if (nonNull(this.right)) {
this.right.insert(node, tree);
} else {
this.right = node;
node.parent = this;
node.balanceTree(false, tree);
}
}
return null;
}
public void toggleColor() {
this.color = !this.color;
}
public void balanceTree(boolean left, BRTree<K, V> tree) {
boolean doubleRed = RED.equals(this.parent.getColor());
BRTreeNode<K, V> grandParentNode = this.parent.parent;
BRTreeNode<K, V> uncleNode = null;
boolean existsUncle = nonNull(grandParentNode) && nonNull(uncleNode = left ? grandParentNode.getRight() : grandParentNode.getLeft());
if (doubleRed && existsUncle) {
this.toggleTreeColor(uncleNode, tree);
} else if (doubleRed) {
boolean parentLeft = grandParentNode.getLeft() == this.parent;
if (parentLeft && left) {
leftLeftRed(tree);
}
else if (parentLeft) {
tree.leftRotate(this.parent);
this.left.leftLeftRed(tree);
}
else if (!left) {
rightRightRed(tree);
}
else {
tree.rightRotate(this.parent);
this.right.rightRightRed(tree);
}
}
}
private void toggleTreeColor(BRTreeNode<K, V> uncleNode, BRTree<K, V> tree) {
this.parent.toggleColor();
uncleNode.toggleColor();
BRTreeNode<K, V> grandParentNode = this.parent.parent;
grandParentNode.toggleColor();
if (Objects.isNull(grandParentNode.parent)) {
grandParentNode.toggleColor();
} else {
grandParentNode.balanceTree(grandParentNode.parent.getLeft() == grandParentNode, tree);
}
}
private void leftLeftRed(BRTree<K, V> tree) {
this.parent.toggleColor();
BRTreeNode<K, V> grandParentNode = this.parent.parent;
grandParentNode.toggleColor();
tree.rightRotate(grandParentNode);
if (nonNull(grandParentNode.parent)) {
grandParentNode.balanceTree(grandParentNode.parent.getLeft() == grandParentNode, tree);
}
}
private void rightRightRed(BRTree<K, V> tree) {
this.parent.toggleColor();
BRTreeNode<K, V> grandParentNode = this.parent.parent;
grandParentNode.toggleColor();
tree.leftRotate(grandParentNode);
if (nonNull(grandParentNode.parent)) {
grandParentNode.balanceTree(grandParentNode.parent.getLeft() == grandParentNode, tree);
}
}
}
|
五、完整代码
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
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
| package com.banmoon.datastructure.RedBlackTree;
import lombok.Data;
import java.util.Objects;
import java.util.Optional;
import static java.util.Objects.nonNull;
public class BRTree<K extends Comparable<K>, V> {
public static final Boolean RED = true;
public static final Boolean BLACK = false;
public BRTreeNode<K, V> root;
public BRTree(K key, V value) {
root = new BRTreeNode<>(key, value, BLACK);
}
public String middleShow() {
if (nonNull(root)) {
return root.middleShow();
}
return null;
}
private void leftRotate(BRTreeNode<K, V> node) {
BRTreeNode<K, V> right = node.right;
BRTreeNode<K, V> parent = node.parent;
BRTreeNode<K, V> leftByRight = right.left;
if (nonNull(parent)) {
right.parent = parent;
parent.right = right;
} else {
right.parent = null;
this.root = right;
}
right.left = node;
node.parent = right;
node.right = leftByRight;
if (nonNull(leftByRight)) {
leftByRight.parent = node;
}
}
private void rightRotate(BRTreeNode<K, V> node) {
BRTreeNode<K, V> left = node.left;
BRTreeNode<K, V> parent = node.parent;
BRTreeNode<K, V> rightByLeft = left.right;
if (nonNull(parent)) {
left.parent = parent;
parent.left = left;
} else {
left.parent = null;
this.root = left;
}
left.right = node;
node.parent = left;
node.left = rightByLeft;
if (nonNull(rightByLeft)) {
rightByLeft.parent = node;
}
}
public V add(K key, V value) {
if (Objects.isNull(this.root)) {
this.root = new BRTreeNode<>(key, value);
this.root.toggleColor();
return null;
} else {
return Optional.ofNullable(root.insert(new BRTreeNode<>(key, value), this))
.map(BRTreeNode::getValue)
.orElse(null);
}
}
@Data
public static class BRTreeNode<K extends Comparable<K>, V> {
private K key;
private V value;
private Boolean color;
private BRTreeNode<K, V> parent;
private BRTreeNode<K, V> left;
private BRTreeNode<K, V> right;
public BRTreeNode(K key, V value) {
this(key, value, RED);
}
public BRTreeNode(K key, V value, Boolean color) {
this.key = key;
this.value = value;
this.color = color;
}
public String middleShow() {
StringBuilder sb = new StringBuilder();
if (nonNull(left))
sb.append(left.middleShow());
System.out.println(String.format("value: %s, 颜色: %s", value, color ? "红" : "黑"));
sb.append(value + " ");
if (nonNull(right))
sb.append(right.middleShow());
return sb.toString();
}
public BRTreeNode<K, V> insert(BRTreeNode<K, V> node, BRTree<K, V> tree) {
K thisKey = this.key;
K insertKey = node.getKey();
int compare = thisKey.compareTo(insertKey);
if (compare == 0) {
node.parent = this.parent;
if (Objects.isNull(this.parent)) {
tree.root = node;
}
if (nonNull(this.left)) {
this.left.parent = node;
node.setLeft(this.left);
}
if (nonNull(this.right)) {
this.right.parent = node;
node.setRight(this.right);
}
node.setColor(this.color);
return this;
}
else if (compare > 0) {
if (nonNull(this.left)) {
this.left.insert(node, tree);
} else {
this.left = node;
node.parent = this;
node.balanceTree(true, tree);
}
}
else {
if (nonNull(this.right)) {
this.right.insert(node, tree);
} else {
this.right = node;
node.parent = this;
node.balanceTree(false, tree);
}
}
return null;
}
public void toggleColor() {
this.color = !this.color;
}
public void balanceTree(boolean left, BRTree<K, V> tree) {
boolean doubleRed = RED.equals(this.parent.getColor());
BRTreeNode<K, V> grandParentNode = this.parent.parent;
BRTreeNode<K, V> uncleNode = null;
boolean existsUncle = nonNull(grandParentNode) && nonNull(uncleNode = left ? grandParentNode.getRight() : grandParentNode.getLeft());
if (doubleRed && existsUncle) {
this.toggleTreeColor(uncleNode, tree);
} else if (doubleRed) {
boolean parentLeft = grandParentNode.getLeft() == this.parent;
if (parentLeft && left) {
leftLeftRed(tree);
}
else if (parentLeft) {
tree.leftRotate(this.parent);
this.left.leftLeftRed(tree);
}
else if (!left) {
rightRightRed(tree);
}
else {
tree.rightRotate(this.parent);
this.right.rightRightRed(tree);
}
}
}
private void toggleTreeColor(BRTreeNode<K, V> uncleNode, BRTree<K, V> tree) {
this.parent.toggleColor();
uncleNode.toggleColor();
BRTreeNode<K, V> grandParentNode = this.parent.parent;
grandParentNode.toggleColor();
if (Objects.isNull(grandParentNode.parent)) {
grandParentNode.toggleColor();
} else {
grandParentNode.balanceTree(grandParentNode.parent.getLeft() == grandParentNode, tree);
}
}
private void leftLeftRed(BRTree<K, V> tree) {
this.parent.toggleColor();
BRTreeNode<K, V> grandParentNode = this.parent.parent;
grandParentNode.toggleColor();
tree.rightRotate(grandParentNode);
if (nonNull(grandParentNode.parent)) {
grandParentNode.balanceTree(grandParentNode.parent.getLeft() == grandParentNode, tree);
}
}
private void rightRightRed(BRTree<K, V> tree) {
this.parent.toggleColor();
BRTreeNode<K, V> grandParentNode = this.parent.parent;
grandParentNode.toggleColor();
tree.leftRotate(grandParentNode);
if (nonNull(grandParentNode.parent)) {
grandParentNode.balanceTree(grandParentNode.parent.getLeft() == grandParentNode, tree);
}
}
}
}
|
六、最后
红黑树确实有点难理解，但只要了解其特性，就可以完美手撕红黑树！
上面的代码不是很全，因为差了删除节点的操作，但情况都是一样的。
简单叙述一下
-
删除一个节点
- 如果它有左节点的话，左节点上位，来到删除节点的位置，来代替他
-
接着就是判断是不是双红的情况了
-
如果是双红，走上面那个平衡的方法就好了
我是半月，你我一同共勉！！！
