定義
紅黑樹(shù)（英語(yǔ)：red–black tree）是一種自平衡二叉查找樹(shù)，是在計(jì)算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)，典型的用途是實(shí)現(xiàn)關(guān)聯(lián)數(shù)組。
紅黑樹(shù)的另一種定義是含有紅黑鏈接并滿足下列條件的二叉查找樹(shù)：
紅鏈接均為左鏈接；沒(méi)有任何一個(gè)結(jié)點(diǎn)同時(shí)和兩條紅鏈接相連；該樹(shù)是完美黑色平衡的，即任意空鏈接到根結(jié)點(diǎn)的路徑上的黑鏈接數(shù)量相同。
滿足這樣定義的紅黑樹(shù)和相應(yīng)的2-3樹(shù)是一一對(duì)應(yīng)的。
旋轉(zhuǎn)
旋轉(zhuǎn)又分為左旋和右旋。通常左旋操作用于將一個(gè)向右傾斜的紅色鏈接旋轉(zhuǎn)為向左鏈接。對(duì)比操作前后，可以看出，該操作實(shí)際上是將紅線鏈接的兩個(gè)節(jié)點(diǎn)中的一個(gè)較大的節(jié)點(diǎn)移動(dòng)到根節(jié)點(diǎn)上。
左旋操作如下圖：
右旋旋操作如下圖：
即：
復(fù)雜度
紅黑樹(shù)的平均高度大約為lgn。
下圖是紅黑樹(shù)在各種情況下的時(shí)間復(fù)雜度，可以看出紅黑樹(shù)是2-3查找樹(shù)的一種實(shí)現(xiàn)，他能保證最壞情況下仍然具有對(duì)數(shù)的時(shí)間復(fù)雜度。
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
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
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
|
import java.util.nosuchelementexception;import java.util.scanner;public class redblackbst<key extends="" key="">, value> { private static final boolean red = true; private static final boolean black = false; private node root; //root of the bst private class node { private key key; //key private value val; //associated data private node left, right; //links to left and right subtrees private boolean color; //color of parent link private int size; //subtree count public node(key key, value val, boolean color, int size) { this.key = key; this.val = val; this.color = color; this.size = size; } } //is node x red? private boolean isred(node x) { if(x == null) { return false; } return x.color == red; } //number of node in subtree rooted at x; 0 if x is null private int size(node x) { if(x == null) { return 0; } return x.size; } /** * return the number of key-value pairs in this symbol table * @return the number of key-value pairs in this symbol table */ public int size() { return size(root); } /** * is this symbol table empty? * @return true if this symbol table is empty and false otherwise */ public boolean isempty() { return root == null; } /** * return the value associated with the given key * @param key the key * @return the value associated with the given key if the key is in the symbol table, and null if it is not. */ public value get(key key) { if(key == null) { throw new nullpointerexception("argument to get() is null"); } return get(root, key); } //value associated with the given key in subtree rooted at x; null if no such key private value get(node x, key key) { while(x != null) { int cmp = key.compareto(x.key); if(cmp < 0) { x = x.left; } else if(cmp > 0) { x = x.right; } else { return x.val; } } return null; } /** * does this symbol table contain the given key? * @param key the key * @return true if this symbol table contains key and false otherwise */ public boolean contains(key key) { return get(key) != null; } /*************************************************************************** * red-black tree insertion. ***************************************************************************/ /** * inserts the specified key-value pair into the symbol table, overwriting the old * value with the new value if the symbol table already contains the specified key. * deletes the specified key (and its associated value) from this symbol table * if the specified value is null. * * @param key the key * @param val the value * @throws nullpointerexception if key is null */ public void put(key key, value val) { if (key == null) { throw new nullpointerexception("first argument to put() is null"); } if (val == null) { delete(key); return; } root = put(root, key, val); root.color = black; } // insert the key-value pair in the subtree rooted at h private node put(node h, key key, value val) { if(h == null) { return new node(key, val, red, 1); } int cmp = key.compareto(h.key); if(cmp < 0) { h.left = put(h.left, key, val); } else if(cmp > 0) { h.right = put(h.right, key, val); } else { h.val = val; } if(isred(h.right) && !isred(h.left)) { h = rotateleft(h); } if(isred(h.left) && isred(h.left.left)) { h = rotateright(h); } if(isred(h.left) && isred(h.right)) { flipcolors(h); } h.size = size(h.left) + size(h.right) + 1; return h; } /*************************************************************************** * red-black tree deletion. ***************************************************************************/ /** * removes the smallest key and associated value from the symbol table. * @throws nosuchelementexception if the symbol table is empty */ public void deletemin() { if (isempty()) { throw new nosuchelementexception("bst underflow"); } // if both children of root are black, set root to red if (!isred(root.left) && !isred(root.right)) root.color = red; root = deletemin(root); if (!isempty()) root.color = black; // assert check(); } // delete the key-value pair with the minimum key rooted at h // delete the key-value pair with the minimum key rooted at h private node deletemin(node h) { if (h.left == null){ return null; } if (!isred(h.left) && !isred(h.left.left)) { h = moveredleft(h); } h.left = deletemin(h.left); return balance(h); } /** * removes the largest key and associated value from the symbol table. * @throws nosuchelementexception if the symbol table is empty */ public void deletemax() { if (isempty()) { throw new nosuchelementexception("bst underflow"); } // if both children of root are black, set root to red if (!isred(root.left) && !isred(root.right)) root.color = red; root = deletemax(root); if (!isempty()) root.color = black; // assert check(); } // delete the key-value pair with the maximum key rooted at h // delete the key-value pair with the maximum key rooted at h private node deletemax(node h) { if (isred(h.left)) h = rotateright(h); if (h.right == null) return null; if (!isred(h.right) && !isred(h.right.left)) h = moveredright(h); h.right = deletemax(h.right); return balance(h); } /** * remove the specified key and its associated value from this symbol table * (if the key is in this symbol table). * * @param key the key * @throws nullpointerexception if key is null */ public void delete(key key) { if (key == null) { throw new nullpointerexception("argument to delete() is null"); } if (!contains(key)) { return; } //if both children of root are black, set root to red if(!isred(root.left) && !isred(root.right)) { root.color = red; } root = delete(root, key); if(!isempty()) { root.color = black; } } // delete the key-value pair with the given key rooted at h // delete the key-value pair with the given key rooted at h private node delete(node h, key key) { if(key.compareto(h.key) < 0) { if(!isred(h.left) && !isred(h.left.left)) { h = moveredleft(h); } h.left = delete(h.left, key); } else { if(isred(h.left)) { h = rotateright(h); } if (key.compareto(h.key) == 0 && (h.right == null)) { return null; } if (!isred(h.right) && !isred(h.right.left)) { h = moveredright(h); } if (key.compareto(h.key) == 0) { node x = min(h.right); h.key = x.key; h.val = x.val; h.right = deletemin(h.right); } else { h.right = delete(h.right, key); } } return balance(h); } /*************************************************************************** * red-black tree helper functions. ***************************************************************************/ // make a left-leaning link lean to the right // make a left-leaning link lean to the right private node rotateright(node h) { // assert (h != null) && isred(h.left); node x = h.left; h.left = x.right; x.right = h; x.color = x.right.color; x.right.color = red; x.size = h.size; h.size = size(h.left) + size(h.right) + 1; return x; } // make a right-leaning link lean to the left // make a right-leaning link lean to the left private node rotateleft(node h) { // assert (h != null) && isred(h.right); node x = h.right; h.right = x.left; x.left = h; x.color = x.left.color; x.left.color = red; x.size = h.size; h.size = size(h.left) + size(h.right) + 1; return x; } // flip the colors of a node and its two children // flip the colors of a node and its two children private void flipcolors(node h) { // h must have opposite color of its two children // assert (h != null) && (h.left != null) && (h.right != null); // assert (!isred(h) && isred(h.left) && isred(h.right)) // || (isred(h) && !isred(h.left) && !isred(h.right)); h.color = !h.color; h.left.color = !h.left.color; h.right.color = !h.right.color; } // assuming that h is red and both h.left and h.left.left // are black, make h.left or one of its children red. // assuming that h is red and both h.left and h.left.left // are black, make h.left or one of its children red. private node moveredleft(node h) { // assert (h != null); // assert isred(h) && !isred(h.left) && !isred(h.left.left); flipcolors(h); if (isred(h.right.left)) { h.right = rotateright(h.right); h = rotateleft(h); flipcolors(h); } return h; } // assuming that h is red and both h.right and h.right.left // are black, make h.right or one of its children red. // assuming that h is red and both h.right and h.right.left // are black, make h.right or one of its children red. private node moveredright(node h) { // assert (h != null); // assert isred(h) && !isred(h.right) && !isred(h.right.left); flipcolors(h); if (isred(h.left.left)) { h = rotateright(h); flipcolors(h); } return h; } // restore red-black tree invariant // restore red-black tree invariant private node balance(node h) { // assert (h != null); if (isred(h.right)) { h = rotateleft(h); } if (isred(h.left) && isred(h.left.left)) { h = rotateright(h); } if (isred(h.left) && isred(h.right)) { flipcolors(h); } h.size = size(h.left) + size(h.right) + 1; return h; } /*************************************************************************** * utility functions. ***************************************************************************/ /** * returns the height of the bst (for debugging). * @return the height of the bst (a 1-node tree has height 0) */ public int height() { return height(root); } private int height(node x) { if (x == null) { return -1; } return 1 + math.max(height(x.left), height(x.right)); } /*************************************************************************** * ordered symbol table methods. ***************************************************************************/ /** * returns the smallest key in the symbol table. * @return the smallest key in the symbol table * @throws nosuchelementexception if the symbol table is empty */ public key min() { if (isempty()) { throw new nosuchelementexception("called min() with empty symbol table"); } return min(root).key; } // the smallest key in subtree rooted at x; null if no such key private node min(node x) { // assert x != null; if (x.left == null) { return x; } else { return min(x.left); } } /** * returns the largest key in the symbol table. * @return the largest key in the symbol table * @throws nosuchelementexception if the symbol table is empty */ public key max() { if (isempty()) { throw new nosuchelementexception("called max() with empty symbol table"); } return max(root).key; } // the largest key in the subtree rooted at x; null if no such key private node max(node x) { // assert x != null; if (x.right == null) { return x; } else { return max(x.right); } } /** * returns the largest key in the symbol table less than or equal to key. * @param key the key * @return the largest key in the symbol table less than or equal to key * @throws nosuchelementexception if there is no such key * @throws nullpointerexception if key is null */ public key floor(key key) { if (key == null) { throw new nullpointerexception("argument to floor() is null"); } if (isempty()) { throw new nosuchelementexception("called floor() with empty symbol table"); } node x = floor(root, key); if (x == null) { return null; } else { return x.key; } } // the largest key in the subtree rooted at x less than or equal to the given key private node floor(node x, key key) { if (x == null) { return null; } int cmp = key.compareto(x.key); if (cmp == 0) { return x; } if (cmp < 0) { return floor(x.left, key); } node t = floor(x.right, key); if (t != null) { return t; } else { return x; } } /** * returns the smallest key in the symbol table greater than or equal to key. * @param key the key * @return the smallest key in the symbol table greater than or equal to key * @throws nosuchelementexception if there is no such key * @throws nullpointerexception if key is null */ public key ceiling(key key) { if (key == null) { throw new nullpointerexception("argument to ceiling() is null"); } if (isempty()) { throw new nosuchelementexception("called ceiling() with empty symbol table"); } node x = ceiling(root, key); if (x == null) { return null; } else { return x.key; } } // the smallest key in the subtree rooted at x greater than or equal to the given key private node ceiling(node x, key key) { if (x == null) { return null; } int cmp = key.compareto(x.key); if (cmp == 0) { return x; } if (cmp > 0) { return ceiling(x.right, key); } node t = ceiling(x.left, key); if (t != null) { return t; } else { return x; } } /** * return the kth smallest key in the symbol table. * @param k the order statistic * @return the kth smallest key in the symbol table * @throws illegalargumentexception unless k is between 0 and * <em>n</em> − 1 */ public key select(int k) { if (k < 0 || k >= size()) { throw new illegalargumentexception(); } node x = select(root, k); return x.key; } // the key of rank k in the subtree rooted at x private node select(node x, int k) { // assert x != null; // assert k >= 0 && k < size(x); int t = size(x.left); if (t > k) { return select(x.left, k); } else if (t < k) { return select(x.right, k-t-1); } else { return x; } } /** * return the number of keys in the symbol table strictly less than key. * @param key the key * @return the number of keys in the symbol table strictly less than key * @throws nullpointerexception if key is null */ public int rank(key key) { if (key == null) { throw new nullpointerexception("argument to rank() is null"); } return rank(key, root); } // number of keys less than key in the subtree rooted at x private int rank(key key, node x) { if (x == null) { return 0; } int cmp = key.compareto(x.key); if (cmp < 0) { return rank(key, x.left); } else if (cmp > 0) { return 1 + size(x.left) + rank(key, x.right); } else { return size(x.left); } } /*************************************************************************** * range count and range search. ***************************************************************************/ /** * returns all keys in the symbol table as an iterable. * to iterate over all of the keys in the symbol table named st, * use the foreach notation: for (key key : st.keys()). * @return all keys in the symbol table as an iterable */ public iterable<key> keys() { if (isempty()) { return new queue<key>(); } return keys(min(), max()); } /** * returns all keys in the symbol table in the given range, * as an iterable. * @return all keys in the symbol table between lo * (inclusive) and hi (exclusive) as an iterable * @throws nullpointerexception if either lo or hi * is null */ public iterable<key> keys(key lo, key hi) { if (lo == null) { throw new nullpointerexception("first argument to keys() is null"); } if (hi == null) { throw new nullpointerexception("second argument to keys() is null"); } queue<key> queue = new queue<key>(); // if (isempty() || lo.compareto(hi) > 0) return queue; keys(root, queue, lo, hi); return queue; } // add the keys between lo and hi in the subtree rooted at x // to the queue private void keys(node x, queue<key> queue, key lo, key hi) { if (x == null) { return; } int cmplo = lo.compareto(x.key); int cmphi = hi.compareto(x.key); if (cmplo < 0) { keys(x.left, queue, lo, hi); } if (cmplo <= 0 && cmphi >= 0) { queue.enqueue(x.key); } if (cmphi > 0) { keys(x.right, queue, lo, hi); } } /** * returns the number of keys in the symbol table in the given range. * @return the number of keys in the symbol table between lo * (inclusive) and hi (exclusive) * @throws nullpointerexception if either lo or hi * is null */ public int size(key lo, key hi) { if (lo == null) { throw new nullpointerexception("first argument to size() is null"); } if (hi == null) { throw new nullpointerexception("second argument to size() is null"); } if (lo.compareto(hi) > 0) { return 0; } if (contains(hi)) { return rank(hi) - rank(lo) + 1; } else { return rank(hi) - rank(lo); } } /*************************************************************************** * check integrity of red-black tree data structure. ***************************************************************************/ private boolean check() { if (!isbst()) system.out.println("not in symmetric order"); if (!issizeconsistent()) system.out.println("subtree counts not consistent"); if (!isrankconsistent()) system.out.println("ranks not consistent"); if (!is23()) system.out.println("not a 2-3 tree"); if (!isbalanced()) system.out.println("not balanced"); return isbst() && issizeconsistent() && isrankconsistent() && is23() && isbalanced(); } // does this binary tree satisfy symmetric order? // note: this test also ensures that data structure is a binary tree since order is strict private boolean isbst() { return isbst(root, null, null); } // is the tree rooted at x a bst with all keys strictly between min and max // (if min or max is null, treat as empty constraint) // credit: bob dondero's elegant solution private boolean isbst(node x, key min, key max) { if (x == null) { return true; } if (min != null && x.key.compareto(min) <= 0) { return false; } if (max != null && x.key.compareto(max) >= 0) { return false; } return isbst(x.left, min, x.key) && isbst(x.right, x.key, max); } // are the size fields correct? private boolean issizeconsistent() { return issizeconsistent(root); } private boolean issizeconsistent(node x) { if (x == null) { return true; } if (x.size != size(x.left) + size(x.right) + 1) { return false; } return issizeconsistent(x.left) && issizeconsistent(x.right); } // check that ranks are consistent private boolean isrankconsistent() { for (int i = 0; i < size(); i++) { if (i != rank(select(i))) { return false; } } for (key key : keys()) { if (key.compareto(select(rank(key))) != 0) { return false; } } return true; } // does the tree have no red right links, and at most one (left) // red links in a row on any path? private boolean is23() { return is23(root); } private boolean is23(node x) { if (x == null) { return true; } if (isred(x.right)) { return false; } if (x != root && isred(x) && isred(x.left)){ return false; } return is23(x.left) && is23(x.right); } // do all paths from root to leaf have same number of black edges? private boolean isbalanced() { int black = 0; // number of black links on path from root to min node x = root; while (x != null) { if (!isred(x)) black++; x = x.left; } return isbalanced(root, black); } // does every path from the root to a leaf have the given number of black links? private boolean isbalanced(node x, int black) { if (x == null) { return black == 0; } if (!isred(x)) { black--; } return isbalanced(x.left, black) && isbalanced(x.right, black); } /** * unit tests the redblackbst data type. */ public static void main(string[] args) { redblackbst<string, integer=""> st = new redblackbst<string, integer="">(); string data = "a b c d e f g h m n o p"; scanner sc = new scanner(data); int i = 0; while (sc.hasnext()) { string key = sc.next(); st.put(key, i); i++; } sc.close(); for (string s : st.keys()) system.out.println(s + " " + st.get(s)); system.out.println(); boolean result = st.check(); system.out.println("check: " + result); } } |
輸出：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
<code>a 0b 1c 2d 3e 4f 5g 6h 7m 8n 9o 10p 11 check: true</code> |
總結(jié)
以上就是本文關(guān)于java算法實(shí)現(xiàn)紅黑樹(shù)完整代碼示例的全部?jī)?nèi)容，希望對(duì)大家有所幫助。有什么問(wèn)題可以隨時(shí)留言，小編會(huì)及時(shí)回復(fù)大家的。感謝朋友們對(duì)本站的支持！
原文鏈接：https://www.2cto.com/kf/201608/541726.html
