forked from RongleXie/Play-with-Data-Structures-Ronglexie
-
Notifications
You must be signed in to change notification settings - Fork 0
/
RedBlackTree.java
438 lines (398 loc) · 8.7 KB
/
RedBlackTree.java
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
/**
* 红黑树
*
* @author ronglexie
* @version 2018/9/2
*/
public class RedBlackTree<K extends Comparable<K>,V> {
public static final boolean RED = true;
public static final boolean BLACK = false;
private Node root;
private int size;
public RedBlackTree() {
root = null;
size = 0;
}
/**
* 左旋转
*
* @param node
* @return RedBlackTree<K,V>.Node
* @author ronglexie
* @version 2018/9/2
*/
// node x
// / \ 左旋转 / \
// T1 x ---------> node T3
// / \ / \
// T2 T3 T1 T2
private Node leftRotate(Node node){
Node x = node.right;
//左旋转操作
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
/**
* 颜色翻转
*
* @param node
* @return void
* @author ronglexie
* @version 2018/9/2
*/
private void flipColors(Node node){
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
/**
* 右旋转
*
* @param node
* @return RedBlackTree<K,V>.Node
* @author ronglexie
* @version 2018/9/2
*/
// node x
// / \ 右旋转 / \
// x T2 -------> y node
// / \ / \
// y T1 T1 T2
private Node rightRotate(Node node){
Node x = node.left;
//右旋转操作
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
/**
* 判断当前节点是否为红色
*
* @param node
* @return boolean
* @author ronglexie
* @version 2018/9/2
*/
public boolean isRed(Node node) {
if(node == null){
return BLACK;
}
return node.color;
}
/**
* 向红黑树中插入元素
*
* @param key
* @param value
* @return void
* @author ronglexie
* @version 2018/9/2
*/
public void add(K key, V value) {
root = add(root,key,value);
root.color = BLACK;//根节点为黑色节点
}
/**
* 向node为根元素的红黑树中插入元素
* 递归算法
*
* @param node
* @param key
* @param value
* @return void
* @author ronglexie
* @version 2018/8/19
*/
private Node add(Node node, K key, V value){
//递归终止条件,返回结果为null
if(node == null){
size ++;
return new Node(key,value);
}
if(key.compareTo(node.key) < 0){
node.left = add(node.left,key,value);
}else if(key.compareTo(node.key) > 0){
node.right = add(node.right,key,value);
}else {
node.value = value;
}
/**==========维护红黑树性质 Start==========*/
//判断是否需要左旋转
if(isRed(node.right) && !isRed(node.left)){
node = leftRotate(node);
}
//判断是否需要右旋转
if(isRed(node.left) && isRed(node.left.left)){
node = rightRotate(node);
}
//判断是否需要颜色翻转
if(isRed(node.left) && isRed(node.right)){
flipColors(node);
}
/**==========维护红黑树性质 End==========*/
return node;
}
/**
* 查找红黑树的最小值
*
* @param
* @return V
* @author ronglexie
* @version 2018/8/18
*/
public V minimum(){
if(isEmpty()){
throw new IllegalArgumentException("BinarySearchTree is empty !");
}
return minimum(root).value;
}
/**
* 查找以node为根节点红黑树的最小节点
* 深度优先遍历,递归实现
*
* @param node
* @return BinarySearchTree<E>.Node
* @author ronglexie
* @version 2018/8/18
*/
private Node minimum(Node node) {
if(isEmpty()){
throw new IllegalArgumentException("BinarySearchTree is empty !");
}
if(node.left == null){
return node;
}
return minimum(node.left);
}
/**
* 查找红黑树的最大值
*
* @param
* @return V
* @author ronglexie
* @version 2018/8/18
*/
public V maximize(){
if(isEmpty()){
throw new IllegalArgumentException("BinarySearchTree is empty !");
}
return maximize(root).value;
}
/**
* 查找以node为根节点红黑树的最大节点
* 深度优先遍历,递归实现
*
* @param node
* @return BinarySearchTree<E>.Node
* @author ronglexie
* @version 2018/8/18
*/
private Node maximize(Node node) {
if(isEmpty()){
throw new IllegalArgumentException("BinarySearchTree is empty !");
}
if(node.right == null){
return node;
}
return minimum(node.right);
}
/**
* 删除红黑树的最大值
*
* @param
* @return V
* @author ronglexie
* @version 2018/8/18
*/
public V removeMax(){
V maximize = maximize();
removeMax(root);
return maximize;
}
/**
* 删除以node为根的红黑树的最大节点
* 深度优先遍历,递归实现
*
* @param node
* @return BinarySearchTree<E>.Node
* @author ronglexie
* @version 2018/8/18
*/
private Node removeMax(Node node){
if(node.right == null){
Node leftNode = node.left;
node.left = null;
size --;
return leftNode;
}
node.right = removeMin(node.right);
return node;
}
/**
* 删除红黑树的最小值
*
* @param
* @return BinarySearchTree<E>.Node
* @author ronglexie
* @version 2018/8/18
*/
public V removeMin(){
V minimum = minimum();
removeMin(root);
return minimum;
}
/**
* 删除以node为根的红黑树的最小节点
* 深度优先遍历,递归实现
*
* @param node
* @return BinarySearchTree<E>.Node
* @author ronglexie
* @version 2018/8/18
*/
private Node removeMin(Node node){
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
public V remove(K key) {
Node node = getNode(root,key);
if(node != null){
root = remove(root, key);
return node.value;
}
return null;
}
/**
* 删除以node为根的红黑树中的指定元素
* 深度优先遍历,递归实现
*
* @param node
* @param key
* @return BinarySearchTree<E>.Node
* @author ronglexie
* @version 2018/8/18
*/
private Node remove(Node node, K key) {
if(node == null){
return null;
}
if(key.compareTo(node.key) < 0){
node.left = remove(node.left,key);
return node;
}else if(key.compareTo(node.key) > 0){
node.right = remove(node.right,key);
return node;
}else /*if(key.compareTo(node.key) == 0)*/{
// 删除右子树为空的情况
if(node.right == null){
Node leftNode = node.left;
node.left = null;
size --;
return leftNode;
}
// 删除左子树为空的情况
else if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}
// 删除左子树、右子树均不为空的情况
else {
// 1、删除后用后继节点替代该位置(后继节点即待删除节点右子树中的最小节点)
// 获得后继节点
Node successor = minimum(node.right);
// 删除后继节点,并让待删除节点的右子树成为后继节点的右子树
successor.right = removeMin(node);
// 让待删除节点的左子树成为后继节点的左子树
successor.left = node.left;
// 将待删除节点的左、右子节点置为空
node.left = node.right = null;
return successor;
/**
// 2、删除后用前驱节点替代该位置(前驱节点即待删除节点左子树中的最大节点)
// 获得前驱节点
Node predecessor = maximize(node.left);
// 删除前驱节点,并让待删除节点的左子树成为前驱节点的左子树
predecessor.left = removeMax(node);
// 让待删除节点的右子树成为前驱节点的右子树
predecessor.right = node.right;
// 将待删除节点的左、右子节点置为空
node.left = node.right = null;
return predecessor;
*/
}
}
}
public boolean contains(K key) {
return getNode(root,key) != null;
}
public V get(K key) {
Node node = getNode(root, key);
return node != null ? node.value : null;
}
public void set(K key, V value) {
Node node = getNode(root, key);
if(node == null){
throw new IllegalArgumentException("Set failed. key is not exists!");
}
node.value = value;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
/**
* 根据key获取Node
*
* @param node
* @param key
* @return Node
* @author ronglexie
* @version 2018/8/19
*/
public Node getNode(Node node,K key){
if(node == null){
return null;
}
if(key.compareTo(node.key) == 0){
return node;
}else if(key.compareTo(node.key) < 0){
return getNode(node.left,key);
}else{
return getNode(node.right,key);
}
}
/**
* 节点类
*
* @author ronglexie
* @version 2018/8/18
*/
private class Node{
public K key;
public V value;
public Node left,right;
public boolean color;
public Node(K key, V value){
this.key = key;
this.value = value;
left = null;
right = null;
color = RED;
}
}
}