-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathredBlackTree.java
More file actions
532 lines (496 loc) · 19.5 KB
/
redBlackTree.java
File metadata and controls
532 lines (496 loc) · 19.5 KB
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
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
package algorithmUtils;
import lombok.*;
/**
* *********************************************************************
* <br/>
* 红黑树 数据结构
*
* @date 2019/2/13 15:42
* *********************************************************************
*/
public class RedBlackTree {
/**
* 红黑树性质四点：
* <p>
* 1、每个节点要么是红色，要么是黑色。
* 2、根节点必须是黑色
* 3、 红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
* 4、对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。
* 隐藏性质：左右子树高度差不超过一倍，自平衡
* 中序遍历单调递增
*/
private static final boolean RED = false;
private static final boolean BLACK = true;
private transient TreeNode root;
/**
* 新增节点后的调整操作
* （1）判断父节点是否左儿子
* （2）判断叔叔节点是否为红色：是就变黑
* （3）判断X节点是否为右节点：是就左旋，最后右旋
* <p>
* x 表示新增节点
*/
private void fixAfterInsert(TreeNode x) {
/**
* 新增节点的颜色设置为红色
*/
x.color = RED;
//循环 :直到 x是根节点，且x的父节点不为红色
while (x != null && x != root && x.parent.color == RED) {
/**
* 判断父亲是否是爷爷的左儿子：产生的两种情况是完全对称的
* 对称情况一：若父亲节点为左儿子
*/
//如果X的父节点（P）是其爷爷节点（G）的左节点
if (parentOf(x) == leftOf(grandpaOf(x))) {
//获取X的叔叔节点(U)
TreeNode U = rightOf(grandpaOf(x));
/**
* 如果X的叔节点（U） 为红色（情况一）
* 最简单情况：变色
* @when
*/
if (colorOf(U) == RED) {
//将X的父节点（P）设置为黑色
setColor(parentOf(x), BLACK);
//将X的叔节点（U）设置为黑色
setColor(U, BLACK);
//将X的爷爷节点（G）设置红色
setColor(grandpaOf(x), RED);
x = grandpaOf(x);
}
//如果X的叔节点（U为黑色）；这里会存在两种情况（情况二、情况三）分别判断X为左节点还是右节点
else {
/**
* 如果X节点为其父节点（P）的右子树，则进行左旋转（情况二）
* 左旋
* @when
*/
if (x == rightOf(parentOf(x))) {
//将X的父节点作为X 赋值给X
x = parentOf(x);
/**
* 以父节点为中心旋转 /左旋转
*/
rotateLeft(x);
}
/**
* （情况三）如果X节点为其父节点（P）的左子树
* 将X的父节点（P）设置为黑色
* @when
*/
setColor(parentOf(x), BLACK);
//将X的爷爷节点（G）设置红色
setColor(grandpaOf(x), RED);
//以X的爷爷节点（G）为中心右旋转
rotateRight(grandpaOf(x));
}
}
/**
* 对称情况二：若父亲节点为右儿子
*/
//如果X的父节点（P）是其父节点的父节点（G）的右节点
else {
//获取X的叔节点（U）
TreeNode y = leftOf(grandpaOf(x));
//如果X的叔节点（U） 为红色（情况一）
if (colorOf(y) == RED) {
//将X的父节点（P）设置为黑色
setColor(parentOf(x), BLACK);
//将X的叔节点（U）设置为黑色
setColor(y, BLACK);
//将X的父节点的父节点（G）设置红色
setColor(grandpaOf(x), RED);
x = grandpaOf(x);
}
//如果X的叔节点（U为黑色）；这里会存在两种情况（情况二、情况三）
else {
//如果X节点为其父节点（P）的右子树，则进行左旋转（情况二）
if (x == leftOf(parentOf(x))) {
//将X的父节点作为X
x = parentOf(x);
//右旋转
rotateRight(x);
}
//（情况三）
//将X的父节点（P）设置为黑色
setColor(parentOf(x), BLACK);
//将X的父节点的父节点（G）设置红色
setColor(grandpaOf(x), RED);
//以X的父节点的父节点（G）为中心左旋转
rotateLeft(grandpaOf(x));
}
}
/**
* 完成一遍调整：重复操作
*/
}
//将根节点G强制设置为黑色
root.color = BLACK;
}
/**
* 删除节点后的调整操作
* （1）判断删除节点X为父节点的左儿子
* (2)判断兄弟节点friend是否为红 ：为红就变黑左旋
* （3）判断兄弟节点friend是否二个黑子节点：直接变黑friend节点
* （4）判断兄弟节点friend右节点是否为黑：最后左旋
* x 表示删除节点
*/
private void fixAfterDelete(TreeNode x) {
// 删除节点需要一直迭代， 直到 x 是根节点，且 x 的颜色是黑色
while (x != root && colorOf(x) == BLACK) {
/**
*
* 对称情况一：若X节点为左儿子
*/
if (x == leftOf(parentOf(x))) {
//获取其兄弟节点
TreeNode friend = rightOf(parentOf(x));
/**
* 情况一：如果兄弟节点为红色----
* 黑 红
* =》》
* 黑 红 黑 黑
* 策略：改变兄弟节点和父节点的颜色，然后进行一次左旋转
* =>导致后面 兄弟节点一定为黑色
*/
if (colorOf(friend) == RED) {
setColor(friend, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
friend = rightOf(parentOf(x));
}
/**
* 情况二：若兄弟节点的两个子节点都为黑色----
* 策略：将兄弟节点变成红色
*/
if (colorOf(leftOf(friend)) == BLACK &&
colorOf(rightOf(friend)) == BLACK) {
setColor(friend, RED);
x = parentOf(x);
}
/**
* 若兄弟节点的其中一个子节点为黑色，或者全为红----
* @when 2019/4/17
*/
else {
/**
* 情况三：如果兄弟节点只有右子树为黑色----
* 策略：将兄弟节点与其左子树进行颜色互换然后进行右旋转
* 这时情况会转变为情况四
*/
if (colorOf(rightOf(friend)) == BLACK) {
setColor(leftOf(friend), BLACK);
setColor(friend, RED);
rotateRight(friend);
friend = rightOf(parentOf(x));
}
/**
* 情况四：排除前两种情况下都要执行：若兄弟节点的右节点为红
*策略：交换兄弟节点和父节点的颜色，
* 实际上就是父节点变为黑，兄弟节点变为红
*同时将兄弟节点右子树设置为黑色，最后左旋转
*/
setColor(friend, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(friend), BLACK);
rotateLeft(parentOf(x));
x = root;
}
}
/**
* 对称情况二：若X节点为右儿子
*/
else {
TreeNode friend = leftOf(parentOf(x));
if (colorOf(friend) == RED) {
setColor(friend, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
friend = leftOf(parentOf(x));
}
if (colorOf(rightOf(friend)) == BLACK &&
colorOf(leftOf(friend)) == BLACK) {
setColor(friend, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(friend)) == BLACK) {
setColor(rightOf(friend), BLACK);
setColor(friend, RED);
rotateLeft(friend);
friend = leftOf(parentOf(x));
}
setColor(friend, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(friend), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
/**
* 删除节点：找到一个真后继节点C来替代P，然后直接删除C，最后调整这棵红黑树。下面代码是寻找替代节点、删除替代节点。主要为了方便删除：没有儿子的节点
* （1）处是寻找替代节点replacement，其实现方法为successor()
* （2）处是删除该节点过程。它主要分为上面提到的三种情况（分为二种情况即可），它与上面的if…else if… else一一对应 。如下：
* <p>
* 1、节点D有两个儿子。用儿子节点C(2)替代待删除节点D，然后删除子节点C(2)即可。
* <p>
* 2、节点D没有儿子，即为叶结点。直接把父结点的对应儿子指针设为NULL，删除儿子结点就OK了。
* <p>
* 3、节点D只有一个儿子。那么节点D的父节点的儿子指针->指向节点D的儿子 ;节点D的儿子指针指向->节点D的父节点，删除节点D也OK了。
* <p>
* （3）删除该节点后调整：
* 4、 删除完节点D，D如果为黑色，就要根据情况来对红黑树进行调整：fixAfterDelete(D)。
*/
private void delete(TreeNode p) {
/**
* 寻找真后继节点并替换P节点操作：
*/
/*
* 被删除节点的左子树和右子树都不为空，那么就用 p节点的中序后继节点代替 p 节点
* successor(P)方法：寻找真后继节点：
* successor(P)方法为寻找P的替代节点。规则是:右分支不为空？：1、右分支最左边，否则 2、左分支最右边的节点
* -----------------------（1）
*/
if (p.left != null && p.right != null) {
/**
* 找到真后继
* @when 2019/4/16
*/
TreeNode s = successor(p);
/*这里要知道是值传递,传递的内存地址：KV为泛型*/
/**
* 替换P
* @when 2019/4/16
*/
p.value = s.value;
p = s;
/**
* 这个时候=>P节点只会有一个子节点
* @when 2019/4/19
*/
}
/**
* 以下是删除操作：实际上就是用左儿子（优先级更高）或者右儿子去替换P节点
* 那么另外一个节点去哪里了？(实际上最多只会有一个节点：要么左子节点或者右子节点)
*/
//replacement为替代节点，如果P的左子树存在那么就用左子树替代，否则用右子树替代
TreeNode replacement = (p.left != null ? p.left : p.right);
/*
* 删除节点，分为上面提到的三种情况
* -----------------------（2）
*/
//如果替代节点不为空
/**
* 情况一：P节点包含儿子：则replacement不为空
*/
if (replacement != null) {
/**
* 1：父指针指向同一个
*/
replacement.parent = p.parent;
/**
* 2：儿子指针指向replacement
*/
//若P没有父节点，则跟节点直接变成replacement
if (p.parent == null) {
root = replacement;
}
//如果P为左节点，则用replacement来替代为左节点
else if (p == p.parent.left) {
p.parent.left = replacement;
}
//如果P为右节点，则用replacement来替代为右节点
else {
p.parent.right = replacement;
}
/**
* 3：删除P节点
*/
//同时将P节点从这棵树中剔除掉
p.left = p.right = p.parent = null;
/**
* 若P为红色直接删除，红黑树保持平衡
* 但是若P为黑色，则需要调整红黑树使其保持平衡
*/
/**
* 4：判断删除后节点颜色进行调整树平衡
*/
/*这里p没有置空，color属性还在*/
if (p.color == BLACK) {
/*一：replacement不为空，P已经删除指针了*/
/**
* replacement：颜色是没有变的，replacement可能是红色也不需要调整，因为判断的是P节点颜色
*/
fixAfterDelete(replacement);
}
}
/**
* 特殊情况：P为根节点，直接置空
*/
//p没有父节点，表示为P根节点，直接删除即可
else if (p.parent == null) {
root = null;
}
/**
* 情况二：P节点不包含儿子（叶子节点）：则replacement为空
*/
//P节点不存在子节点，直接删除即可
else {
//如果P节点的颜色为黑色，对红黑树进行调整
if (p.color == BLACK) {
/*二：replacement为空，调整P*/
fixAfterDelete(p);
}
//删除P节点
if (p.parent != null) {
if (p == p.parent.left) {
p.parent.left = null;
} else if (p == p.parent.right) {
p.parent.right = null;
}
p.parent = null;
}
}
}
/**
* 找真后继节点方法
* <p>
* 1、寻找右子树的最左叶子节点 2、或者左子树的最右叶子节点
*/
static TreeNode successor(TreeNode t) {
if (t == null)
return null;
/*
* 寻找右子树的最左子树
*/
else if (t.right != null) {
TreeNode p = t.right;
while (p.left != null)
p = p.left;
return p;
}
/*
* 选择左子树的最右子树
*/
else {
TreeNode p = t.parent;
TreeNode ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
/**
* From CLR
* P => N
* A N P b
* a b A a
*/
/* 所谓左旋转，就是将新增节点（N）当做其父节点（P），将其父节点P当做新增节点（N）的左子节点。即：G.left ---> N ,N.left ---> P。*/
private void rotateLeft(TreeNode p) {
if (p != null) {
//获取P的右子节点，其实这里就相当于新增节点N（情况四而言）
TreeNode r = p.right;
//将R的左子树设置为P的右子树
p.right = r.left;
//若R的左子树不为空，则将P设置为R左子树的父亲
if (r.left != null)
r.left.parent = p;
//将P的父亲设置R的父亲
r.parent = p.parent;
//如果P的父亲为空，则将R设置为跟节点
if (p.parent == null)
root = r;
//如果P为其父节点（G）的左子树，则将R设置为P父节点(G)左子树
else if (p.parent.left == p)
p.parent.left = r;
//否则R设置为P的父节点（G）的右子树
else
p.parent.right = r;
//将P设置为R的左子树
r.left = p;
//将R设置为P的父节点
p.parent = r;
}
}
/**
* From CLR
*/
/* 所谓右旋转即，左节点.right ---> 父节点、父节点.parent ---> 左节点。*/
private void rotateRight(TreeNode p) {
if (p != null) {
//将L设置为P的左子树
TreeNode l = p.left;
//将L的右子树设置为P的左子树
p.left = l.right;
//若L的右子树不为空，则将P设置L的右子树的父节点
if (l.right != null)
l.right.parent = p;
//将P的父节点设置为L的父节点
l.parent = p.parent;
//如果P的父节点为空，则将L设置根节点
if (p.parent == null)
root = l;
//若P为其父节点的右子树，则将L设置为P的父节点的右子树
else if (p.parent.right == p)
p.parent.right = l;
//否则将L设置为P的父节点的左子树
else
p.parent.left = l;
//将P设置为L的右子树
l.right = p;
//将L设置为P的父节点
p.parent = l;
}
}
/**
* <p>
* 常用方法
* algorithms.
*/
private static boolean colorOf(TreeNode p) {
return (p == null ? BLACK : p.color);
}
private static TreeNode parentOf(TreeNode p) {
return (p == null ? null : p.parent);
}
private static void setColor(TreeNode p, boolean c) {
if (p != null)
p.color = c;
}
private static TreeNode leftOf(TreeNode p) {
return (p == null) ? null : p.left;
}
private static TreeNode rightOf(TreeNode p) {
return (p == null) ? null : p.right;
}
private static TreeNode grandpaOf(TreeNode p) {
return (p == null) ? null : p.parent.parent;
}
/**
*
*
*/
@Data
@NoArgsConstructor
@AllArgsConstructor
@ToString
@EqualsAndHashCode
static final class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode parent;
boolean color = BLACK;
TreeNode(int value, TreeNode parent) {
this.value = value;
this.parent = parent;
}
}
/////auto
}