269:
29:
1004:
291:, since 4-nodes are now prohibited. Sedgewick remarks that the implementations of LLRB 2–3 trees and LLRB 2–3–4 trees differ only in the position of a single line of code.
381:
299:
All of the red-black tree algorithms that have been proposed are characterized by a worst-case search time bounded by a small constant multiple of
1073:
451:
Linus Ek, Ola
Holmström and Stevan Andjelkovic. May 19, 2009. Formalizing Arne Andersson trees and Left-leaning Red–Black trees in Agda
455:
1049:
310:
keys, and the behavior observed in practice is typically that same multiple faster than the worst-case bound, close to the optimal
450:
741:
211:
57:
948:
260:
The left-leaning property reduces the number of cases that must be considered when implementing search tree operations.
492:
207:
287:
If we impose the additional requirement that a node may not have two red children, LLRB trees become isomorphic to
268:
1023:
1042:
367:
218:
and guarantees the same asymptotic complexity for operations, but is designed to be easier to implement.
573:
437:
371:
958:
514:
284:. This means that for every LLRB tree, there is a unique corresponding 2–3–4 tree, and vice versa.
444:
433:
1035:
243:
from a given node to any of its descendant NIL nodes goes through the same number of black nodes.
36:
456:
Julien Oster. March 22, 2011. An Agda implementation of deletion in Left-leaning Red–Black trees
280:. Unlike conventional red-black trees, the 3-nodes always lean left, making this relationship a
485:
1068:
652:
501:
642:
597:
409:
8:
756:
277:
240:
923:
882:
708:
698:
612:
577:
532:
465:
215:
28:
817:
518:
478:
376:
908:
163:
852:
602:
68:
460:
226:
A left-leaning red-black tree satisfies all the properties of a red-black tree:
1019:
1015:
805:
800:
683:
617:
72:
1062:
953:
933:
776:
665:
592:
288:
913:
877:
693:
688:
670:
582:
527:
321:
963:
928:
918:
832:
766:
761:
751:
660:
509:
461:
Kazu
Yamamoto. 2011.10.19. Purely Functional Left-Leaning Red–Black Trees
973:
943:
903:
746:
675:
622:
542:
470:
1011:
978:
938:
785:
713:
703:
385:
281:
317:
nodes examined that would be observed in a perfectly balanced tree.
983:
867:
857:
837:
810:
795:
557:
547:
382:
Open Data
Structures - Section 9.2.2 - Left-Leaning Red–Black Trees
356:
The average size of left subtree exhibits log-oscillating behavior.
968:
872:
847:
790:
637:
567:
562:
537:
887:
862:
842:
827:
736:
627:
552:
1003:
731:
632:
587:
377:
Robert
Sedgewick. 20 Apr 2008. Animations of LLRB operations
256:
If a node has only one red child, it must be the left child.
723:
419:. Department of Computer Science, Princeton University.
250:
Additionally, the left-leaning property states that:
328:random keys, Sedgewick's experiments suggest that:
263:
1060:
16:Self-balancing binary search tree data structure
466:Left-Leaning Red-Black Trees Considered Harmful
443:Robert Sedgewick. Left-Leaning Red–Black Trees
434:Robert Sedgewick. Left-leaning Red–Black Trees
272:Isomorphism between LLRB trees and 2–3–4 trees
1043:
486:
403:
401:
1050:
1036:
493:
479:
320:Specifically, in a left-leaning red-black
27:
407:
500:
398:
267:
1061:
474:
236:A red node does not have a red child.
1074:Algorithms and data structures stubs
998:
332:A random successful search examines
13:
246:The root is black (by convention).
230:Every node is either red or black.
14:
1085:
427:
346:The average tree height is about
208:self-balancing binary search tree
1002:
360:
264:Relation to 2–3 and 2–3–4 trees
233:A NIL node is considered black.
410:"Left-Leaning Red–Black Trees"
1:
391:
221:
1022:. You can help Knowledge by
417:Left-Leaning Red–Black Trees
370:implementation of LLRB from
7:
294:
22:Left-leaning red–black tree
10:
1090:
997:
408:Sedgewick, Robert (2008).
276:LLRB trees are isomorphic
896:
775:
722:
651:
508:
214:. It is a variant of the
169:
162:
139:
116:
93:
78:
67:
63:
53:
45:
35:
26:
21:
949:Left-child right-sibling
445:slides from October 2008
779:data partitioning trees
737:C-trie (compressed ADT)
255:
1018:-related article is a
273:
200:left-leaning red–black
282:1 to 1 correspondence
271:
959:Log-structured merge
502:Tree data structures
206:) tree is a type of
366:Robert Sedgewick's
924:Fractal tree index
519:associative arrays
438:Direct link to PDF
274:
1031:
1030:
992:
991:
196:
195:
192:
191:
1081:
1052:
1045:
1038:
1006:
999:
495:
488:
481:
472:
471:
421:
420:
414:
405:
352:
342:
327:
316:
309:
305:
212:Robert Sedgewick
210:, introduced by
188:
179:
164:Space complexity
158:
149:
135:
126:
112:
103:
65:
64:
58:Robert Sedgewick
31:
19:
18:
1089:
1088:
1084:
1083:
1082:
1080:
1079:
1078:
1059:
1058:
1057:
1056:
1016:data structures
995:
993:
988:
892:
771:
718:
647:
643:Weight-balanced
598:Order statistic
512:
504:
499:
430:
425:
424:
412:
406:
399:
394:
363:
347:
337:
333:
325:
311:
307:
300:
297:
266:
224:
182:
173:
152:
143:
129:
120:
106:
97:
69:Time complexity
17:
12:
11:
5:
1087:
1077:
1076:
1071:
1055:
1054:
1047:
1040:
1032:
1029:
1028:
1007:
990:
989:
987:
986:
981:
976:
971:
966:
961:
956:
951:
946:
941:
936:
931:
926:
921:
916:
911:
906:
900:
898:
894:
893:
891:
890:
885:
880:
875:
870:
865:
860:
855:
850:
845:
840:
835:
830:
825:
808:
803:
798:
793:
788:
782:
780:
773:
772:
770:
769:
764:
759:
757:Ternary search
754:
749:
744:
739:
734:
728:
726:
720:
719:
717:
716:
711:
706:
701:
696:
691:
686:
681:
673:
668:
663:
657:
655:
649:
648:
646:
645:
640:
635:
630:
625:
620:
615:
605:
600:
595:
590:
585:
580:
570:
565:
560:
555:
550:
545:
540:
535:
530:
524:
522:
506:
505:
498:
497:
490:
483:
475:
469:
468:
463:
458:
453:
448:
441:
429:
428:External links
426:
423:
422:
396:
395:
393:
390:
389:
388:
379:
374:
372:his 2008 paper
362:
359:
358:
357:
354:
344:
335:
296:
293:
265:
262:
258:
257:
254:
248:
247:
244:
237:
234:
231:
223:
220:
216:red–black tree
194:
193:
190:
189:
180:
171:
167:
166:
160:
159:
150:
141:
137:
136:
127:
118:
114:
113:
104:
95:
91:
90:
85:
80:
76:
75:
73:big O notation
61:
60:
55:
51:
50:
47:
43:
42:
39:
33:
32:
24:
23:
15:
9:
6:
4:
3:
2:
1086:
1075:
1072:
1070:
1067:
1066:
1064:
1053:
1048:
1046:
1041:
1039:
1034:
1033:
1027:
1025:
1021:
1017:
1013:
1008:
1005:
1001:
1000:
996:
985:
982:
980:
977:
975:
972:
970:
967:
965:
962:
960:
957:
955:
952:
950:
947:
945:
942:
940:
937:
935:
934:Hash calendar
932:
930:
927:
925:
922:
920:
917:
915:
912:
910:
907:
905:
902:
901:
899:
895:
889:
886:
884:
881:
879:
876:
874:
871:
869:
866:
864:
861:
859:
856:
854:
851:
849:
846:
844:
841:
839:
836:
834:
831:
829:
826:
823:
821:
815:
813:
809:
807:
804:
802:
799:
797:
794:
792:
789:
787:
784:
783:
781:
778:
774:
768:
765:
763:
760:
758:
755:
753:
750:
748:
745:
743:
740:
738:
735:
733:
730:
729:
727:
725:
721:
715:
712:
710:
709:van Emde Boas
707:
705:
702:
700:
699:Skew binomial
697:
695:
692:
690:
687:
685:
682:
680:
678:
674:
672:
669:
667:
664:
662:
659:
658:
656:
654:
650:
644:
641:
639:
636:
634:
631:
629:
626:
624:
621:
619:
616:
614:
610:
606:
604:
601:
599:
596:
594:
591:
589:
586:
584:
581:
579:
578:Binary search
575:
571:
569:
566:
564:
561:
559:
556:
554:
551:
549:
546:
544:
541:
539:
536:
534:
531:
529:
526:
525:
523:
520:
516:
511:
507:
503:
496:
491:
489:
484:
482:
477:
476:
473:
467:
464:
462:
459:
457:
454:
452:
449:
446:
442:
439:
435:
432:
431:
418:
411:
404:
402:
397:
387:
383:
380:
378:
375:
373:
369:
365:
364:
355:
351:
345:
340:
331:
330:
329:
323:
318:
315:
306:in a tree of
304:
292:
290:
285:
283:
279:
270:
261:
253:
252:
251:
245:
242:
238:
235:
232:
229:
228:
227:
219:
217:
213:
209:
205:
201:
186:
181:
177:
172:
168:
165:
161:
156:
151:
147:
142:
138:
133:
128:
124:
119:
115:
110:
105:
101:
96:
92:
89:
86:
84:
81:
77:
74:
70:
66:
62:
59:
56:
52:
48:
44:
40:
38:
34:
30:
25:
20:
1069:Search trees
1024:expanding it
1009:
994:
819:
811:
676:
609:Left-leaning
608:
515:dynamic sets
510:Search trees
416:
361:Bibliography
349:
338:
319:
313:
302:
298:
286:
275:
259:
249:
225:
203:
199:
197:
184:
175:
154:
145:
131:
122:
108:
99:
87:
82:
909:Exponential
897:Other trees
341:− 0.5
324:built from
278:2–3–4 trees
54:Invented by
1063:Categories
1012:algorithms
853:Priority R
603:Palindrome
392:References
222:Properties
88:Worst case
939:iDistance
818:implicit
806:Hilbert R
801:Cartesian
684:Fibonacci
618:Scapegoat
613:Red–black
386:Pat Morin
289:2–3 trees
79:Operation
954:Link/cut
666:Binomial
593:Interval
322:2–3 tree
295:Analysis
46:Invented
914:Fenwick
878:Segment
777:Spatial
694:Pairing
689:Leftist
611:)
583:Dancing
576:)
574:Optimal
83:Average
964:Merkle
929:Fusion
919:Finger
843:Octree
833:Metric
767:Y-fast
762:X-fast
752:Suffix
671:Brodal
661:Binary
343:nodes.
239:Every
153:O(log
144:O(log
140:Delete
130:O(log
121:O(log
117:Insert
107:O(log
98:O(log
94:Search
1010:This
974:Range
944:K-ary
904:Cover
747:Radix
732:Ctrie
724:Tries
653:Heaps
633:Treap
623:Splay
588:HTree
543:(a,b)
533:2–3–4
413:(PDF)
348:2 ln
170:Space
1020:stub
979:SPQR
858:Quad
786:Ball
742:Hash
714:Weak
704:Skew
679:-ary
368:Java
312:log
301:log
241:path
204:LLRB
49:2008
41:tree
37:Type
1014:or
984:Top
838:MVP
796:BSP
548:AVL
528:2–3
334:log
71:in
1065::
969:PQ
883:VP
873:R*
868:R+
848:PH
822:-d
814:-d
791:BK
638:UB
563:B*
558:B+
538:AA
436:.
415:.
400:^
384:,
198:A
183:O(
174:O(
1051:e
1044:t
1037:v
1026:.
888:X
863:R
828:M
824:)
820:k
816:(
812:k
677:d
628:T
607:(
572:(
568:B
553:B
521:)
517:/
513:(
494:e
487:t
480:v
447:.
440:.
353:.
350:N
339:N
336:2
326:N
314:N
308:N
303:N
202:(
187:)
185:n
178:)
176:n
157:)
155:n
148:)
146:n
134:)
132:n
125:)
123:n
111:)
109:n
102:)
100:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
