996:
11446:
13313:
13229:
13301:
13277:
13253:
13289:
13265:
13241:
6879:
4129:
3888:
616:
13217:
11422:
6644:
6502:
6149:
5954:
3522:
6158:
6135:
11434:
6653:
11458:
1580:
6888:
6865:
6630:
4138:
4115:
602:
5963:
5940:
3531:
3508:
6511:
6488:
3897:
3874:
7135:
1158:, there are corresponding red–black trees with data elements in the same order. The insertion and deletion operations on 2–3–4 trees are also equivalent to color-flipping and rotations in red–black trees. This makes 2–3–4 trees an important tool for understanding the logic behind red–black trees, and this is why many introductory algorithm texts introduce 2–3–4 trees just before red–black trees, even though 2–3–4 trees are not often used in practice.
14372:
object-oriented programmings and many other things. But one of the things that was invented there was laser printing and we were very excited to have nearby color laser printer that could print things out in color and out of the colors the red looked the best. So, that's why we picked the color red to distinguish red links, the types of links, in three nodes. So, that's an answer to the question for people that have been asking.
2085:
6965:
6742:
5504:
5454:
5421:
5368:
1997:
5650:
2073:
5644:
5511:
5495:
5463:
5430:
5389:
5382:
5354:
5340:
5333:
5315:
5308:
5301:
5277:
5270:
5263:
5239:
5232:
5194:
5153:
5139:
5132:
5090:
5083:
5076:
5069:
4908:
2965:
2951:
2923:
2916:
2889:
2882:
2840:
2833:
2806:
2695:
2649:
1991:
5470:
5437:
5375:
5347:
5294:
5256:
5225:
5218:
5201:
5185:
5146:
2958:
2909:
2875:
2826:
2781:
2702:
2688:
2512:
1985:
5625:
583:, leveraging Andersson’s idea that simplified the insert and delete operations. Sedgewick originally allowed nodes whose two children are red, making his trees more like 2–3–4 trees, but later this restriction was added, making new trees more like 2–3 trees. Sedgewick implemented the insert algorithm in just 33 lines, significantly shortening his original 46 lines of code.
660:
objects are in relation to other nodes that is relevant to the RB-structure, it may have parent, sibling (i.e., the other child of the parent), uncle, even nephew node; and may be child—but never parent—of another node. It is not really necessary to attribute a "color" to these end-of-path objects, because the condition "is
752:, is constant (alternatively, it could be defined as the black depth of any leaf node). The black height of a node is the black height of the subtree rooted by it. In this article, the black height of a NIL node shall be set to 0, because its subtree is empty as suggested by figure 2, and its tree height is also 0.
9942:
is created to replace c. The new node may invalidate the red–black invariant because at most three red nodes can appear in a row. This can be fixed with a double rotation. If double red issue propagates to the root, the root is then set to be black, restoring the properties. The cost of this function
1978:
The proposal breaks down both, insertion and removal (not mentioning some very simple cases), into six constellations of nodes, edges and colors, which are called cases. The proposal contains for both, insertion and removal, exactly one case that advances one black level closer to the root and loops,
659:
in figure 1) do not contain keys or data. These "leaves" need not be explicit individuals in computer memory: a NULL pointer can—as in all binary tree data structures— encode the fact that there is no child node at this position in the (parent) node. Nevertheless, by their position in the tree, these
803:
Some authors, e.g. Cormen & al., claim "the root is black" as fifth requirement; but not
Mehlhorn & Sanders or Sedgewick & Wayne. Since the root can always be changed from red to black, this rule has little effect on analysis. This article also omits it, because it slightly disturbs the
505:
Tracking the color of each node requires only one bit of information per node because there are only two colors (due to memory alignment present in some programming languages, the real memory consumption may differ). The tree does not contain any other data specific to it being a red–black tree, so
15221:
Moreover, these trees are binary trees that admit one and only one coloring conforming to the RB requirements 1 to 4. But there are further such trees, e.g. appending a child node to a black leaf always forces it to red. (A minimal RB tree of odd height allows to flip the root’s color from red to
1092:
search, insertion, and removal. AVL trees can be colored red–black, and thus are a subset of red-black trees. The worst-case height of AVL is 0.720 times the worst-case height of red-black trees, so AVL trees are more rigidly balanced. The performance measurements of Ben Pfaff with realistic test
7695:
For a red–black tree of a certain height to have minimal number of nodes, it must have exactly one longest path with maximal number of red nodes, to achieve a maximal tree height with a minimal black height. Besides this path all other nodes have to be black. If a node is taken off this tree it
15024:
The left columns contain far less nodes than the right ones, especially for removal. This indicates that some efficiency can be gained by pulling the first iteration out of the rebalancing loops of insertion and deletion, because many of the named nodes are NIL nodes in the first iteration and
10762:
Basic operations like insertion, removal or update can be parallelised by defining operations that process bulks of multiple elements. It is also possible to process bulks with several basic operations, for example bulks may contain elements to insert and also elements to remove from the tree.
1174:, or 2–3–4 trees, for any sequence of operations. The 2–3–4 tree isometry was described in 1978 by Sedgewick. With 2–3–4 trees, the isometry is resolved by a "color flip," corresponding to a split, in which the red color of two children nodes leaves the children and moves to the parent node.
14371:
A lot of people ask why did we use the name red–black. Well, we invented this data structure, this way of looking at balanced trees, at Xerox PARC that was the home of the personal computer and many other innovations that we live with today entering graphic user interfaces, Ethernet and
729:
As a conclusion, the fact that a child does not exist (is not a true node, does not contain data) can in all occurrences be specified by the very same NULL pointer or as the very same pointer to a sentinel node. Throughout this article, either choice is called NIL node and has the
408:
When the tree is modified, the new tree is rearranged and "repainted" to restore the coloring properties that constrain how unbalanced the tree can become in the worst case. The properties are designed such that this rearranging and recoloring can be performed efficiently.
9716:. With the new operations, the implementation of red–black trees can be more efficient and highly-parallelizable. In order to achieve its time complexities this implementation requires that the root is allowed to be either red or black, and that every node stores its own
1020:
variant makes this relationship exactly 1-to-1, by only allowing the left child representation. Since every 2–3–4 node has a corresponding black node, invariant 4 of red-black trees is equivalent to saying that the leaves of a 2–3–4 tree all lie at the same level.
7881:
9304:
11468:
The pseudo code shows a simple divide-and-conquer implementation of the join-based algorithm for bulk-insert. Both recursive calls can be executed in parallel. The join operation used here differs from the version explained in this article, instead
2186:
key compares less than the new node’s key, which in turn compares less than the key of its in-order successor. (Frequently, this positioning is the result of a search within the tree immediately preceding the insert operation and consists of a node
4343:(non-NIL), then we can swap its value with its in-order successor (the leftmost child of the right subtree), and then delete the successor instead. Since the successor is leftmost, it can only have a right child (non-NIL) or no child at all.
1169:
by eliminating a previously unspecified degree of freedom in the implementation. The LLRB maintains an additional invariant that all red links must lean left except during inserts and deletes. Red–black trees can be made isometric to either
12307:
approach. This can be done by breaking the task of processing a basic operation up into a sequence of subtasks. For multiple basic operations the subtasks can be processed in parallel by assigning each subtask to a separate processor.
13023:
If two nodes have different nearest black ancestors, they can be repaired in parallel. Since at most four nodes can have the same nearest black ancestor, the nodes at the lowest level can be repaired in a constant number of parallel
15657:
1011:
of order 4. In 2–3–4 trees, each node can contain between 1 and 3 values and have between 2 and 4 children. These 2–3–4 nodes correspond to black node – red children groups in red-black trees, as shown in figure 3. It is not a
1299:, because every red–black tree is a special case of a simple binary search tree. However, the immediate result of an insertion or removal may violate the properties of a red–black tree, the restoration of which is called
11895:
8567:
404:
noted for fast storage and retrieval of ordered information. The nodes in a red-black tree hold an extra "color" bit, often drawn as red and black, which help ensure that the tree is always approximately balanced.
7324:
8756:
8162:
2026:
A diagram contains three columns and two to four actions. The left column shows the first iteration, the right column the higher iterations, the middle column shows the segmentation of a case into its different
11996:
10778:. In the following different algorithms for bulk insert will be explained, but the same algorithms can also be applied to removal and update. Bulk insert is an operation that inserts each element of a sequence
7437:
11288:
11219:
10517:
13208:
Since all stages move up the black levels of the tree, they can be parallelised in a pipeline. Once a stage has finished processing one black level, the next stage is able to move up and continue at that
1024:
Despite structural similarities, operations on red–black trees are more economical than B-trees. B-trees require management of vectors of variable length, whereas red-black trees are simply binary trees.
553:
derived the red–black tree from the symmetric binary B-tree. The color "red" was chosen because it was the best-looking color produced by the color laser printer available to the authors while working at
10571:. This complexity is optimal in terms of the number of comparisons. More importantly, since the recursive calls to union, intersection or difference are independent of each other, they can be executed
11149:
8883:
12998:
possibly contains up to two consecutive red nodes at the end of the paths form the root to the leaves, which needs to be repaired. Note that, while repairing, the insertion position of elements
11093:
10998:
9504:
8052:
11708:
13684:
8395:
12973:
12919:
12291:
10439:
but without the middle key. Based on the new functions for union, intersection or difference, either one key or multiple keys can be inserted to or deleted from the red–black tree. Since
7731:
7520:
8642:
9121:
13985:
2065:
For both, insert and delete, there is (exactly) one case which iterates one black level closer to the root; then the reassigned constellation satisfies the respective loop invariant.
12502:
15213:
12848:
12805:
12762:
12719:
12631:
12588:
10946:
5632:
is a NIL node and left child) in the left column of the delete diagrams. As the operation proceeds also proper nodes (of black height ≥ 1) may become current (see e.g. case
13808:
8914:
7576:
9975:, all the subtrees on the left side are merged bottom-up using keys on the path as intermediate nodes from bottom to top to form the left tree, and the right part is symmetric.
7620:
7180:
3749:
15156:
14046:
13910:
13570:
13516:
13462:
13204:
12197:
12095:
11762:
11649:
10620:
9680:
3213:
15432:
10699:
9380:
1033:
Red–black trees offer worst-case guarantees for insertion time, deletion time, and search time. Not only does this make them valuable in time-sensitive applications such as
925:
822:
easily maintain requirements 1 and 2, but with respect to the other requirements some extra effort must be made, to avoid introducing a violation of requirement 3, called a
15472:
11595:
13732:
10745:
9093:
9052:
7356:
9407:
7958:
13856:
13156:
12143:
10028:
5765:
3176:
10569:
8260:
7686:
7122:
Because the algorithm transforms the input without using an auxiliary data structure and using only a small amount of extra storage space for auxiliary variables it is
5815:
is the height of the tree). Because the probability of escalation decreases exponentially with each iteration the total rebalancing cost is constant on average, indeed
4322:
Because the algorithm transforms the input without using an auxiliary data structure and using only a small amount of extra storage space for auxiliary variables it is
1340:
1265:
1149:
1090:
985:
500:
445:
378:
342:
299:
263:
220:
184:
15111:
12041:
9571:
12676:
8974:
7993:
8944:
7916:
13090:
13019:
12396:
11346:
11319:
8793:
8453:
8199:
7234:
15371:
3566:. Since any path through the parent or uncle must pass through the grandparent, the number of black nodes on these paths has not changed. However, the grandparent
3235:
is the height of the tree). Because the probability of escalation decreases exponentially with each step the total rebalancing cost is constant on average, indeed
1396:
1230:
111:
13605:
13406:
13376:
10646:
8308:
7723:
3775:
15391:
15342:
13346:
13114:
13067:
13044:
12996:
12868:
12651:
12542:
12522:
12456:
12436:
12416:
12373:
12353:
12330:
11787:
11549:
11413:
11386:
11366:
11041:
11021:
10911:
10888:
10864:
10844:
10816:
10796:
10719:
10537:
9636:
9608:
9328:
9113:
9010:
8669:
8588:
8474:
8329:
8281:
8220:
8076:
7640:
7544:
7462:
7200:
5813:
5793:
3233:
1364:
1285:
883:
859:
465:
10030:
order of the height of the tree. This algorithm actually has nothing to do with any special properties of a red–black tree, and may be used on any tree with a
568:
showed how to make the insert operation purely functional. Its balance function needed to take care of only 4 unbalanced cases and one default balanced case.
10766:
The algorithms for bulk operations aren't just applicable to the red–black tree, but can be adapted to other sorted sequence data structures also, like the
10826:
This approach can be applied to every sorted sequence data structure that supports efficient join- and split-operations. The general idea is to split
14331:
1037:, but it makes them valuable building blocks in other data structures that provide worst-case guarantees. For example, many data structures used in
5900:
is the new root. One black node has been removed from every path, so the RB-properties are preserved. The black height of the tree decreases by 1.
2000:
symbolises the color red or black of a non-NIL node, but the same color throughout the same diagram. NIL nodes are not represented in the diagrams.
15038:
Rotations have been placed before recoloring for reasons of clarity. But the two commute, so that it is free choice to move the rotation to the
718:
Instead, to save a marginal amount of execution time, these (possibly many) NIL leaves may be implemented as pointers to one unique (and black)
11795:
2202:
The newly inserted node is temporarily colored red so that all paths contain the same number of black nodes as before. But if its parent, say
8480:
5622:
is the NIL node replacing the node to be deleted. Because its location in parent’s node is the only thing of importance, it is symbolised by
1405:
If the example implementation below is not suitable, other implementations with explanations may be found in Ben Pfaff’s annotated C library
7240:
16564:
9708:
operations on insertions or deletions can be implemented based on these set functions. These set operations rely on two helper operations,
8675:
8081:
2063:, which then again carries a blue ring and relative to which other nodes may have to be reassigned also. This action is labeled "reassign".
15689:
715:. This way, these ends of the paths are also docking points for new nodes to be inserted, fully equivalent to the NIL leaves of figure 1.
15239:
11905:
814:
The read-only operations, such as search or tree traversal, do not affect any of the requirements. In contrast, the modifying operations
7362:
640:, such as text fragments or numbers (as e.g. the numbers in figures 1 and 2). The nodes carrying keys and/or data are frequently called
15529:
HiPC 2016, the 23rd IEEE International
Conference on High Performance Computing, Data, and Analytics, Hyderabad, India, December, 19-22
791:
has exactly one child, it must be a red child, because if it were black, its NIL descendants would sit at a different black depth than
467:
is the number of entries in the tree. The insert and delete operations, along with tree rearrangement and recoloring, also execute in
16240:
11225:
11156:
8984:
10457:
2059:
If there is still some need to repair, the cases make use of code of other cases and this after a reassignment of the current node
10754:
for red–black trees are parallel for bulk operations, including union, intersection, construction, filter, map-reduce, and so on.
14364:
15009:"Ben Pfaff (2007): Online HTML version of a well-documented collection of binary search tree and balanced tree library routines"
13312:
15652:
1093:
cases in 79 runs find AVL to RB ratios between 0.677 and 1.077, median at 0.947, and geometric mean 0.910. The performance of
16534:
15965:
15675:– Visualization of random and pre-sorted data insertions, in elementary binary search trees, and left-leaning red–black trees
15554:
15276:
15251:
Symposium on
Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016)
14878:
14780:
14760:
14682:
14616:
14602:
14576:
14547:
14531:
14511:
14439:
14360:
14305:
14188:
13300:
2080:) with a black height equal to the iteration level minus one, i.e. zero in the first iteration. Its root may be red or black.
1162:
550:
54:
14409:
13276:
13252:
1295:
The read-only operations, such as search or tree traversal, on a red–black tree require no modification from those used for
16172:
2088:
represents a red–black subtree with a black height one less, i.e. its parent has black height zero in the second iteration.
2032:
The action "entry" shows the constellation of nodes with their colors which defines a case and mostly violates some of the
11098:
10701:
time, depending on the computer model, if the number of processors available is asymptotically proportional to the number
10424:
is presumed to return two trees: one holding the keys less its input key, one holding the greater keys. (The algorithm is
8806:
11445:
11046:
10951:
9413:
7998:
558:. Another response from Guibas states that it was because of the red and black pens available to them to draw the trees.
15612:
14966:
11660:
10447:
but does not deal with the balancing criteria of red–black trees directly, such an implementation is usually called the
16608:
15716:
14643:
14282:
838:
835:
the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf
744:
of a node is defined as the number of black nodes from the root to that node (i.e. the number of black ancestors). The
13288:
13264:
13240:
13228:
841:. Since operations such as inserting, deleting, and finding values require worst-case time proportional to the height
575:
reduced that to 6 unbalanced cases. Sedgewick showed that the insert operation can be implemented in just 46 lines of
16473:
15503:
14735:
13613:
8335:
7876:{\displaystyle m_{1}=2^{\lfloor (1+1)/2\rfloor }\!+\!2^{\lfloor 1/2\rfloor }\!\!-\!\!2=2^{1}\!+\!2^{0}\!\!-\!\!2=1~.}
398:
14416:(Proceedings). Lecture Notes in Computer Science. Vol. 709. Springer-Verlag Berlin Heidelberg. pp. 60–71.
9689:
In addition to the single-element insert, delete and lookup operations, several set operations have been defined on
5823:
support constant amortized update costs." This is true for the rebalancing after a deletion, but not AVL insertion.)
9299:{\displaystyle m_{h}=3\cdot 2^{(h-1)/2}-2={\bigl (}3\cdot 2^{-3/2}{\bigr )}\cdot 2^{(h+2)/2}-2>2\cdot 2^{h/2}-2}
14551:
12210:
7471:
5584:
cannot be a NIL node in the first iteration, because it must have black height one, which was the black height of
16263:
15832:
14085:
10652:(DAG) as single-element insertion and deletion if the root of the larger tree is used to split the smaller tree.
10576:
8594:
7918:
has a root whose two child subtrees are of different height. The higher child subtree is also a minimal RB tree,
1203:, a red–black tree is used. This results in the improvement of time complexity of searching such an element from
1166:
731:
580:
11902:
This can be improved by using parallel algorithms for splitting and joining. In this case the execution time is
679:
Figure 2 shows the conceptually same red–black tree without these NIL leaves. To arrive at the same notion of a
16268:
15581:
14998:
The important thing about these tree rotations is that they preserve the in-order sequence of the tree’s nodes.
13923:
1181:, a type of tree optimised for fast searches, specifically uses red–black trees as part of its data structure.
14948:
12924:
5675:
The rows in the synopsis are ordered such that the coverage of all possible RB cases is easily comprehensible.
3084:
The rows in the synopsis are ordered such that the coverage of all possible RB cases is easily comprehensible.
1016:, because 3-nodes have two equivalent representations: the red child may lie either to the left or right. The
561:
In 1993, Arne
Andersson introduced the idea of a right leaning tree to simplify insert and delete operations.
16233:
12873:
11470:
861:
of the tree, this upper bound on the height allows red–black trees to be efficient in the worst case, namely
16342:
12461:
10660:
Parallel algorithms for constructing red–black trees from sorted lists of items can run in constant time or
5529: possible cases of color constellations are covered.
1979:
the other five cases rebalance the tree of their own. The more complicated cases are pictured in a diagram.
15161:
12810:
12767:
12724:
12681:
12593:
12550:
10916:
534:
from root to leaf with the same number of nodes, creating perfectly balanced trees. However, they were not
138:
5727:
determines exactly one case, this case is given as the subsequent one, otherwise there are question marks.
3132:
determines exactly one case, this case is given as the subsequent one, otherwise there are question marks.
3049:
are both left or both right children, whereas i (for "inner") means that the child direction changes from
538:
search trees. Bayer called them a "symmetric binary B-tree" in his paper and later they became popular as
16347:
16330:
14647:
14339:
13216:
10112:.color=black) and (T'.right.color=T'.right.right.color=red): T'.right.right.color=black;
7579:
1185:
1017:
948:, that is: in the order Left–Root–Right) of their elements. But they support also asymptotically optimal
576:
13752:
11421:
8888:
7557:
16613:
16546:
16313:
16308:
15797:
15672:
14717:
14580:
14174:
11433:
10751:
10448:
7591:
7157:
3717:
2056:
If some recoloring is considered useful, this is pictured in the next action, which is labeled "color".
15116:
4401:
is not the root, colored black and has no proper child (⇔ only NIL children). In the first iteration,
2985: possible cases of constellations are covered.
1116:
that can retain previous versions after mutations. The persistent version of red–black trees requires
16303:
16182:
13990:
13867:
13527:
13473:
13419:
13161:
12154:
12052:
11719:
11606:
10581:
10425:
9697:
9641:
8800:
5693:
before entering a subsequent iteration step. This possibly induces a reassignment of the other nodes
4918:
is one less than before the deletion, whereas it is unchanged on all other paths, so that there is a
3189:
1105:
1042:
719:
15396:
14665:
14422:
10663:
9340:
889:
748:
of a red–black tree is the number of black nodes in any path from the root to the leaves, which, by
16337:
16296:
16226:
15738:
15437:
14796:
14727:
14180:
11562:
6968:
in the diagram), which refers to the same color both before and after the transformation. This way
4901:
equals the iteration number minus one, which means that in the first iteration it is zero and that
2145:
13689:
10724:
9057:
9018:
7334:
3582:
is fulfilled so that the rebalancing can be iterated on one black level (= 2 tree levels) higher.
1398:, a constant number, of color changes (which are very quick in practice); and no more than three
995:
16577:
16554:
14059:
11457:
9386:
7933:
6727:
has a black sibling whose distant child is red, so the constellation is fit for case D6. Neither
6033:
is fulfilled so that the rebalancing can be iterated on one black level (= 1 tree level) higher.
784:
from a given node to any of its descendant NIL nodes goes through the same number of black nodes.
27:
14220:
13819:
13119:
12106:
9995:
5741:
3152:
16559:
16359:
15709:
14772:
14660:
14417:
10649:
10542:
8226:
8165:
8055:
7645:
1310:
1235:
1119:
1113:
1101:
1060:
1038:
955:
808:
470:
415:
348:
312:
269:
233:
190:
154:
15090:
14821:
12014:
9510:
5611:
to be on either side. The code samples cover both possibilities by means of the side variable
4389:, deleting it will create an imbalance, and requires a fixup, as covered in the next section.
3023:
to be on either side. The sample code covers both possibilities by means of the side variable
16603:
16598:
16485:
16440:
16402:
15876:
15725:
14238:
Bayer, Rudolf (1972). "Symmetric binary B-Trees: Data structure and maintenance algorithms".
11391:
Finally, the resulting trees will be joined to form the final result of the entire operation.
8953:
7965:
1013:
641:
32:
14764:
14205:
8919:
7895:
1416:
code, which uses the type definitions, macros below, and the helper function for rotations:
16425:
15866:
15821:
15542:
15158:
nodes and only for those. So the inequality is marginally more precise than the widespread
14705:
14162:
14074:
13072:
13001:
12378:
12304:
11324:
11297:
10572:
8771:
8431:
8177:
7212:
6013:
have the same number of black nodes, but one fewer than the paths that do not pass through
3102:
before entering a subsequent step. This possibly induces a reassignment of the other nodes
15591:
15347:
14849:
11415:
assure that in Step 5 the trees can be joined again and the resulting sequence is sorted.
1372:
1206:
87:
8:
15980:
15627:
15527:
Akhremtsev, Yaroslav; Sanders, Peter (2016). "Fast
Parallel Operations on Search Trees".
14064:
13580:
13381:
13351:
10625:
8765:
8287:
7702:
6878:
4128:
3887:
3754:
2116:
2099:
1034:
1004:
781:
680:
531:
15546:
15486:
Sanders, Peter (2019). Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (eds.).
12656:
1197:
16453:
16318:
16278:
16147:
16106:
15932:
15922:
15801:
15756:
15532:
15509:
15376:
15327:
15282:
15254:
14930:
14907:
14493:
14301:
14255:
14103:
13331:
13099:
13052:
13029:
12981:
12853:
12636:
12527:
12507:
12441:
12421:
12401:
12358:
12338:
12315:
11772:
11534:
11398:
11371:
11351:
11026:
11006:
10896:
10873:
10849:
10829:
10801:
10781:
10771:
10704:
10522:
9693:
9621:
9593:
9313:
9098:
8995:
8654:
8573:
8459:
8314:
8266:
8205:
8061:
7625:
7529:
7447:
7185:
7123:
5798:
5778:
4323:
3218:
2183:
2179:
2053:
is considered useful, this is pictured in the next action, which is labeled "rotation".
1349:
1296:
1270:
1155:
945:
941:
930:
868:
862:
844:
761:
629:
546:
539:
511:
450:
131:
50:
15318:
15301:
14654:
14384:
7582:) and there is no red–black tree of this tree height with fewer nodes—therefore it is
6643:
6501:
6148:
5953:
3521:
615:
16387:
16286:
16041:
15742:
15702:
15577:
15550:
15513:
15499:
15272:
14776:
14765:
14731:
14678:
14612:
14527:
14485:
14435:
14278:
14184:
13408:, otherwise it would be more efficient to construct the resulting tree from scratch.
1109:
644:, but to make this very specific they are also called non-NIL nodes in this article.
514:. In some cases, the added bit of information can be stored at no added memory cost.
14497:
14259:
6157:
6134:
16410:
16132:
15587:
15491:
15313:
15286:
15264:
14981:
14934:
14922:
14701:
14670:
14475:
14427:
14313:
14247:
14166:
14158:
13158:
and in every stage the subsequences are being cut in half, the number of stages is
6887:
6864:
6652:
6629:
4137:
4114:
1412:
The details of the insert and removal operations will be demonstrated with example
633:
507:
390:
73:
15607:
6236:, so the transformations in cases D4, D5, or D6 are able to restore the RB-shape.
4350:(non-NIL). In this case, just replace the node with its child, and color it black.
1579:
601:
16430:
16372:
16076:
15826:
15620:
14445:
12524:
that contains the elements whose insertion position would be to the left of node
8796:
5962:
5939:
3530:
3507:
1973:
119:
15243:
14412:. In Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola; Whitesides, Sue (eds.).
6510:
6487:
3896:
3873:
2503:
and initially the insertion node, is made the variable running through the loop.
16522:
16500:
16325:
16249:
16029:
16024:
15907:
15841:
15646:
15488:
Sequential and
Parallel Algorithms and Data Structures : The Basic Toolbox
15324:
Our parallel algorithm for constructing a red–black tree from a sorted list of
14713:
14523:
14516:
14170:
14121:
9701:
7134:
4890:
3820:’s color the tree is in RB-shape. The black height of the tree increases by 1.
2488:
1343:
401:
62:
15666:
15495:
14926:
14674:
14480:
14463:
14431:
1574:#define childDir(N) ( N == (N->parent)->right ? RIGHT : LEFT )
16592:
16495:
16392:
16377:
16177:
16157:
16000:
15889:
15816:
15684:
14962:
14639:
14489:
14069:
5712:
If something has been changed by the case, this is shown in the column group
3117:
If something has been changed by the case, this is shown in the column group
2050:
1399:
949:
565:
15268:
10172:(T'.color=red) and (T'.right.color=red): T'.color=black
6723:
are exchanged. All paths still have the same number of black nodes, but now
16137:
16101:
15917:
15912:
15894:
15806:
15751:
15661:
15235:
14310:
Proceedings of the 19th Annual
Symposium on Foundations of Computer Science
14099:
10767:
10747:. Fast search, insertion, and deletion parallel algorithms are also known.
9951:: To split a red–black tree into two smaller trees, those smaller than key
6984:
in the diagram) pass through the same number of black nodes as before, but
5657:
have one bullet less than the other paths. This means a black-violation at
3061:
1171:
1050:
723:
523:
15678:
14450:
10431:
The algorithm for intersection or difference is similar, but requires the
6554:, but it does add one to the number of black nodes on paths going through
5887:– all outside the loop. Therefore, at most three rotations occur in total.
3786:// Leaving the (do while)-loop (after having fallen through from Case_I2).
2165:-statements have to occur far less frequently if the proposal is realised.
16490:
16415:
16187:
16152:
16142:
16056:
15990:
15985:
15975:
15884:
15733:
13021:
have to be updated, if the corresponding nodes are affected by rotations.
11890:{\displaystyle \in O\left(\log k\log |T|+{\frac {|I|}{k}}\log |T|\right)}
10866:
in multiple parts and perform the insertions on these parts in parallel.
5723:
signifies that the rebalancing is complete with this step. If the column
4233:// Case_I6 (P red && U black && N outer grandchild of G):
4036:// Case_I5 (P red && U black && N inner grandchild of G):
3178:
tree levels or 1 black level higher in the tree, in that the grandfather
3128:
signifies that the rebalancing is complete with this step. If the column
3041:
indicates the change in child direction, i.e. o (for "outer") means that
14317:
3570:
may now violate requirement 3, if it has a red parent. After relabeling
16478:
16382:
16197:
16167:
16127:
15970:
15899:
15846:
15766:
15694:
14709:
14251:
14126:
13026:
This step will be applied successively to the black levels above until
10775:
8562:{\displaystyle (2^{\lfloor h/2\rfloor }+2^{\lfloor (h-1)/2\rfloor }-2)}
1193:
1178:
555:
15008:
7319:{\displaystyle =2^{\lfloor (h+1)/2\rfloor }+2^{\lfloor h/2\rfloor }-2}
6958:
is made black. The whole subtree still has the same color at its root
3558:
are red, then both of them can be repainted black and the grandparent
3071:. Thereby possible values in cells left empty are ignored. So in case
16420:
16367:
16202:
16162:
16009:
15937:
15927:
15571:
15039:
14723:
14136:
8751:{\displaystyle 2^{\lfloor h/2\rfloor }+2^{\lfloor (h+1)/2\rfloor }-2}
8157:{\displaystyle 2^{s}\!\!-\!\!1=2^{\lfloor (h-1)/2\rfloor }\!\!-\!\!1}
5819:. (Just as an aside: Mehlhorn & Sanders point out: "AVL trees do
3751:
times and the total height of the tree has increased by 1, now being
2076:
represents a red–black subtree (connected to its parent according to
1189:
1094:
648:
14985:
10257:(L',b,join(R',T.key,T.right)) (L',b,R') = split(T.right, k)
9963:
into the red–black tree. After this insertion, all values less than
5826:
Out of the body of the loop there are exiting branches to the cases
4367:(both NIL) and is the root, replace it with NIL. The tree is empty.
4220:
also remains satisfied, since all paths that went through the black
3781:
is the (red) root of the tree, and all RB-properties are satisfied.
3283:– outside the loop. Therefore, at most two rotations occur in total.
16517:
16463:
16291:
16207:
16091:
16081:
16061:
16034:
16019:
15781:
15771:
15537:
15259:
14107:
14090:
11991:{\displaystyle \in O\left(\log |T|+{\frac {|I|}{k}}\log |T|\right)}
10035:
9967:
will be found on the left of the path, and all values greater than
9943:
is the difference of the black heights between the two input trees.
6009:, have one less black node. Now all paths in the subtree rooted by
4848:// Here both nephews are == NIL (first iteration) or black (later).
2521:
is satisfied for all pairs node←parent with the possible exception
1200:
1054:
16218:
7432:{\displaystyle 2\cdot 2^{\tfrac {h}{2}}-2=2^{{\tfrac {h}{2}}+1}-2}
6996:
was added as a black grandparent. Thus, the paths passing through
2084:
1303:
so that red–black trees become self-balancing. It requires in the
16512:
16458:
16192:
16096:
16071:
16014:
15861:
15791:
15786:
15761:
14750:
Using Knuth’s definition of order: the maximum number of children
14115:
14111:
14079:
12458:
according to the insertion position of each element. For example
6964:
6741:
6550:
does not affect the number of black nodes on paths going through
5503:
5453:
5420:
5367:
3077:
the sample code covers both possibilities of child directions of
1996:
1008:
833:
The requirements enforce a critical property of red–black trees:
14606:
13049:
The steps 3 to 5 will be repeated on the new subsequences until
10454:
The complexity of each of union, intersection and difference is
5653:) in a delete diagram it can be observed that the paths through
16507:
16448:
16111:
16086:
16066:
16051:
15960:
15851:
15776:
14131:
14095:
13092:
has been inserted. Each application of these steps is called a
11283:{\displaystyle {\text{last}}(T_{j})<{\text{first}}(I_{j+1})}
11214:{\displaystyle {\text{last}}(I_{j})<{\text{first}}(T_{j+1})}
4889:
The rebalancing loop of the delete operation has the following
2487:
The rebalancing loop of the insert operation has the following
2042:
and the other nodes are labeled according to their relation to
545:
In a 1978 paper, "A Dichromatic
Framework for Balanced Trees",
527:
526:
invented a data structure that was a special order-4 case of a
412:
The (re-)balancing is not perfect, but guarantees searching in
10512:{\displaystyle O\left(m\log \left({n \over m}+1\right)\right)}
7331:
5649:
2072:
1974:
Notes to the sample code and diagrams of insertion and removal
1165:
introduced a simpler version of the red–black tree called the
999:
Figure 3: Similarities between 2–3–4 trees and red-black trees
15955:
15856:
15811:
15080:
Equality at the upper bound holds for the minimal RB trees RB
14906:
Demaine, E. D.; Harmon, D.; Iacono, J.; Pătraşcu, M. (2007).
10253:(k < T.key): (L',b,R') = split(T.left, k)
5860:
of its own has three different exiting branches to the cases
1413:
1046:
12303:
Another method of parallelizing bulk operations is to use a
8164:
black nodes—and no red node. Then the number of nodes is by
5682:
indicates whether a rotation contributes to the rebalancing.
5643:
5510:
5494:
5462:
5429:
5388:
5381:
5353:
5339:
5332:
5314:
5307:
5300:
5276:
5269:
5262:
5238:
5231:
5193:
5152:
5138:
5131:
5089:
5082:
5075:
5068:
4907:
3816:
is also red, requirement 3 is violated. But after switching
3091:
indicates whether a rotation contributes to the rebalancing.
2964:
2950:
2922:
2915:
2888:
2881:
2839:
2832:
2805:
2694:
2648:
1990:
16529:
15947:
14905:
10648:, the join-based implementation has the same computational
8979:
6972:
is preserved. The paths in the subtree not passing through
1151:
space for each insertion or deletion, in addition to time.
1028:
637:
15643:
14700:
14157:
12355:
the algorithm locates the according insertion position in
5672:. Thereby possible values in cells left empty are ignored.
5624:
5469:
5436:
5374:
5346:
5293:
5255:
5224:
5217:
5200:
5184:
5145:
2957:
2908:
2874:
2825:
2780:
2701:
2687:
2511:
2132:
Thereby, it must be kept in mind that both statements are
1984:
683:, one must notice that e.g., 3 paths run through the node
572:
12958:
12955:
12952:
12949:
12904:
12901:
12898:
12833:
12830:
12790:
12787:
12747:
12744:
12704:
12701:
12616:
12613:
12573:
12570:
12487:
12484:
12481:
3924:
is black. The ultimate goal is to rotate the parent node
621:
Figure 2: ... with implicit left and right docking points
15613:
San Diego State
University: CS 660: Red–Black tree notes
10304:. The following recursive function computes this union:
3248:
exits by itself and there are exiting branches to cases
2174:
Insertion begins by placing the new (non-NIL) node, say
12850:, those will be contained in a new set of subsequences
7929:
containing also a longest path that defines its height
6558:, making up for the deleted black node on those paths.
4897:
At the beginning of each iteration the black height of
3928:
to the grandparent position, but this will not work if
811:
that consists only of black nodes is a red–black tree.
14308:(1978). "A Dichromatic Framework for Balanced Trees".
7486:
7404:
7377:
5618:
At the beginning (in the first iteration) of removal,
4494:// side of P on which N is located (∈ { LEFT, RIGHT })
3722:
3194:
2070:
A possibly numbered triangle with a black circle atop
1406:
15490:. Springer eBooks. Cham: Springer. pp. 252–253.
15440:
15399:
15379:
15350:
15330:
15164:
15119:
15093:
13993:
13926:
13870:
13822:
13755:
13692:
13616:
13583:
13530:
13476:
13422:
13384:
13354:
13334:
13164:
13122:
13102:
13075:
13055:
13032:
13004:
12984:
12927:
12876:
12856:
12813:
12770:
12727:
12684:
12659:
12639:
12596:
12553:
12530:
12510:
12464:
12444:
12424:
12404:
12381:
12361:
12341:
12318:
12213:
12157:
12109:
12055:
12017:
11908:
11798:
11775:
11722:
11663:
11609:
11565:
11537:
11401:
11374:
11354:
11327:
11300:
11228:
11159:
11101:
11049:
11029:
11009:
10954:
10919:
10899:
10876:
10852:
10832:
10804:
10784:
10727:
10707:
10666:
10628:
10584:
10545:
10525:
10460:
9998:
9684:
9644:
9624:
9596:
9513:
9416:
9389:
9343:
9316:
9124:
9101:
9060:
9021:
8998:
8956:
8922:
8891:
8809:
8774:
8678:
8657:
8597:
8576:
8483:
8462:
8434:
8338:
8317:
8290:
8269:
8229:
8208:
8180:
8084:
8064:
8001:
7968:
7936:
7898:
7734:
7705:
7648:
7628:
7594:
7560:
7532:
7474:
7450:
7365:
7337:
7243:
7215:
7188:
7160:
5801:
5781:
5744:
3757:
3720:
3221:
3192:
3155:
1375:
1352:
1313:
1273:
1238:
1209:
1122:
1063:
958:
892:
871:
847:
510:
is almost identical to that of a classic (uncolored)
473:
453:
418:
351:
315:
272:
236:
193:
157:
90:
15234:
11479:(T, I, k): I.sort() bulklInsertRec(T, I, k)
11348:
sequentially. This step must be performed for every
11144:{\displaystyle j\in \mathbb {N} ^{+}|\,1\leq j<k}
10428:, but an in-place destructive version exists also.)
8878:{\displaystyle (h=2k\;|\;m_{2k}=2\cdot 2^{k}\!-\!2)}
7725:
with red root is minimal. This is in agreement with
5668:
defines the case, whose name is given in the column
4352:
The single child (non-NIL) must be red according to
3081:, although the corresponding diagram shows only one.
3067:
defines the case, whose name is given in the column
3008:
for its uncle. In the table a — sign indicates root.
1994:
a (non-NIL) black node (of black height ≥ 1),
1366:
is the number of objects in the tree, on average or
1287:
is the number of elements with colliding hashcodes.
571:
The original algorithm used 8 unbalanced cases, but
15576:. Reading, Mass. : Addison-Wesley. pp. 65–70.
12721:since by definition the insertion position of each
11088:{\displaystyle \langle T_{1},\cdots ,T_{k}\rangle }
10993:{\displaystyle \langle I_{1},\cdots ,I_{k}\rangle }
9499:{\displaystyle 2\log _{2}(n+2)-2=2\log _{2}(n/2+1)}
8047:{\displaystyle \lfloor (h\!\!-\!\!1)/2\rfloor =:s.}
7150:
each with minimal number 1,2,4,6 resp. 10 of nodes.
6212:’s grandparent. Then after reversing the colors of
4392:
3995:is preserved. Requirement 3 is restored in case 6.
2123:U != NIL && U->color == RED
15466:
15426:
15385:
15365:
15336:
15207:
15150:
15105:
14515:
14040:
13979:
13904:
13850:
13802:
13726:
13678:
13599:
13564:
13510:
13456:
13400:
13370:
13340:
13198:
13150:
13108:
13084:
13061:
13038:
13013:
12990:
12967:
12913:
12862:
12842:
12799:
12756:
12713:
12670:
12645:
12625:
12582:
12536:
12516:
12496:
12450:
12430:
12410:
12390:
12367:
12347:
12324:
12285:
12191:
12137:
12089:
12035:
11990:
11889:
11781:
11756:
11703:{\displaystyle \in O\left({\frac {|I|}{k}}\right)}
11702:
11643:
11589:
11543:
11407:
11395:Note that in Step 3 the constraints for splitting
11380:
11360:
11340:
11313:
11282:
11213:
11143:
11087:
11035:
11015:
10992:
10940:
10905:
10882:
10858:
10838:
10810:
10790:
10739:
10713:
10693:
10640:
10614:
10563:
10531:
10511:
10022:
9674:
9630:
9602:
9565:
9498:
9401:
9374:
9322:
9298:
9107:
9087:
9046:
9004:
8968:
8938:
8908:
8877:
8787:
8750:
8663:
8636:
8582:
8561:
8468:
8447:
8389:
8323:
8302:
8275:
8254:
8214:
8193:
8156:
8070:
8046:
7987:
7952:
7910:
7875:
7717:
7680:
7634:
7614:
7570:
7538:
7514:
7456:
7431:
7350:
7318:
7228:
7194:
7174:
5807:
5787:
5759:
4572:// side of parent P on which the node N is located
4356:, and the deleted node must be black according to
4165:(left of left child or right of right child). Now
3769:
3743:
3420:// the side of parent G on which node P is located
3227:
3207:
3170:
1493:// RIGHT := 1, if (key > parent->key)
1490:// LEFT := 0, if (key < parent->key)
1390:
1358:
1334:
1279:
1259:
1224:
1143:
1100:Red–black trees are also particularly valuable in
1084:
979:
919:
877:
853:
494:
459:
439:
372:
336:
293:
257:
214:
178:
105:
15621:"Performance Analysis of BSTs in System Software"
15526:
14656:Algorithms and Data Structures: The Basic Toolbox
14385:"Where does the term "Red/Black Tree" come from?"
12807:contains elements to the left or to the right of
8868:
8864:
8150:
8149:
8145:
8144:
8101:
8100:
8096:
8095:
8017:
8016:
8012:
8011:
7946:
7945:
7941:
7940:
7857:
7856:
7852:
7851:
7840:
7836:
7819:
7818:
7814:
7813:
7788:
7784:
7343:
3300:holds. Requirement 4 holds also according to the
1966:#define RotateRight(N) RotateDirRoot(T,N,RIGHT)
16590:
12375:. This can be done in parallel for each element
7000:pass through one additional black node, so that
5738:, where the problem of rebalancing is escalated
2284:// side ( LEFT or RIGHT ) of P where to insert N
1963:#define RotateLeft(N) RotateDirRoot(T,N,LEFT)
952:via a traversal from root to leaf, resulting in
944:, allow quite efficient sequential access (e.g.
16:Self-balancing binary search tree data structure
14638:
14634:
14632:
14630:
14628:
14300:
13679:{\displaystyle \in O(\log |I|+2\cdot \log |T|)}
9959:, first draw a path from the root by inserting
9881:If the black heights are unequal, suppose that
9799:. It returns a tree containing all elements in
8390:{\displaystyle (2^{\lfloor (h-1)/2\rfloor }-1)}
7004:is restored and the total tree is in RB-shape.
4937:
4914:The number of black nodes on the paths through
2552:
1960:#define RotateDir(N,dir) RotateDirRoot(T,N,dir)
1192:has been modified such that instead of using a
14974:SIAM Journal on Algebraic and Discrete Methods
14601:
11473:is used, which misses the second parameter k.
6988:now has one additional black ancestor: either
4635:// side of parent P on which node N is located
4161:is now certain to be an "outer" grandchild of
1568:// Get the child direction (∈ { LEFT, RIGHT })
1097:lie in between AVL trees and red-black trees.
774:All NIL nodes (figure 1) are considered black.
16234:
15710:
15230:
15228:
14696:
14694:
14611:(4th ed.). Addison-Wesley Professional.
11507:) := split(T, I) bulkInsertRec(T
9826:If the two trees have the same black height,
9558:
9516:
9219:
9185:
3215:steps of iteration to repair the tree (where
1523:// null pointer or pointer to sentinel node
760:In addition to the requirements imposed on a
15069:Handbook of Data Structures and Applications
14625:
14277:(2 ed.). Sams Publishing. p. 323.
14153:
14151:
12286:{\displaystyle \in O(k\log |T|+|I|\log |T|)}
11511:, I, ⌈k / 2⌉) || bulkInsertRec(T
11082:
11050:
10987:
10955:
9830:simply creates a new node with left subtree
8737:
8711:
8698:
8684:
8629:
8603:
8545:
8519:
8506:
8492:
8373:
8347:
8139:
8113:
8032:
8002:
7808:
7794:
7779:
7753:
7609:
7595:
7565:
7561:
7515:{\displaystyle 3\cdot 2^{\tfrac {h-1}{2}}-2}
7305:
7291:
7278:
7252:
5767:level higher in the tree in that the parent
4216:the resulting tree satisfies requirement 3.
4208:was violated. After switching the colors of
2206:, is also red then this action introduces a
1003:Red–black trees are similar in structure to
10757:
9925:. At this point a new node with left child
8637:{\displaystyle 2^{\lfloor (h-1)/2\rfloor }}
6232:and after the reassignment a black sibling
5730:The loop is contained in the sections from
4551:// P != NULL, since N is not the root.
2007:denotes the current node, which is labeled
16241:
16227:
15717:
15703:
15679:An intrusive red–black tree written in C++
15668:Binary Search Tree Insertion Visualization
15653:A complete and working implementation in C
15225:
15020:
15018:
14691:
14546:
14353:
13348:is not considered in this analysis. Also,
13096:. Since the length of the subsequences in
11294:Now the algorithm inserts each element of
10188:.blackHeight: /* symmetric */
9555:
8831:
8825:
4662:// sibling of N (has black height >= 1)
819:
15536:
15317:
15302:"Parallel algorithms for red–black trees"
15258:
14759:
14664:
14575:
14510:
14479:
14464:"Red–black trees in a functional setting"
14421:
14407:
14359:
14148:
13980:{\displaystyle \in O(2\cdot |I|\log |T|)}
11125:
11110:
10928:
9984:also returns a boolean value denoting if
8899:
7696:either loses height or some RB property.
7564:
7168:
6735:are affected by this transformation, and
3975:, see diagram) and removes paths through
2515:(red) at the beginning of each iteration.
2272:// -> parent node of N ( may be NULL )
2098:For simplicity, the sample code uses the
990:
15724:
15393:processors on the CRCW PRAM and runs in
15299:
15050:
15048:
14771:. Addison-Wesley Professional. pp.
14597:
14595:
14593:
12968:{\displaystyle s_{n',{\mathit {right}}}}
12678:. This can be done in parallel for each
9971:will be found on the right. By applying
7133:
6021:may still be violated. After relabeling
5664:The color constellation in column group
3944:or the right child of the left child of
3940:is the left child of the right child of
3149:the problem of rebalancing is escalated
1578:
1571:// of the non-root non-NIL RBnode* N:
1104:, where they are one of the most common
1029:Applications and related data structures
994:
15645:Free Software Foundation, Boston 2004,
15485:
15015:
14844:
14842:
14461:
14272:
14197:
14142:
12914:{\displaystyle s_{n',{\mathit {left}}}}
9310:So in both, the even and the odd case,
3959:switches the roles of the current node
933:. For a mathematical proof see section
16591:
15573:An introduction to parallel algorithms
15025:definitively non-NIL later. (See also
14961:
14955:
14296:
14294:
14275:Data Structures and Algorithms in Java
14231:
14218:
13069:is empty. At this point every element
12497:{\displaystyle s_{n,{\mathit {left}}}}
12418:won't be mutated in this process. Now
10655:
10160:.blackHeight: T'=joinRightRB(T
6992:has become black, or it was black and
5993:’s children are black. After painting
3135:The loop is contained in the sections
2979:Insertion: This synopsis shows in its
1041:are based on red–black trees, and the
628:A red–black tree is a special type of
607:Figure 1: ... with explicit NIL leaves
579:code. In 2008, Sedgewick proposed the
16222:
15698:
15244:"Just Join for Parallel Ordered Sets"
15208:{\displaystyle h<2\log _{2}(n+1),}
15045:
14590:
14504:
14237:
12843:{\displaystyle m_{n,{\mathit {dir}}}}
12800:{\displaystyle s_{n,{\mathit {dir}}}}
12757:{\displaystyle m_{n,{\mathit {dir}}}}
12714:{\displaystyle m_{n,{\mathit {dir}}}}
12626:{\displaystyle s_{n,{\mathit {dir}}}}
12583:{\displaystyle m_{n,{\mathit {dir}}}}
12332:of elements to insert must be sorted.
10941:{\displaystyle k\in \mathbb {N} ^{+}}
10890:of elements to insert must be sorted.
7622: (with black root) or for odd
5795:iterations to repair the tree (where
5523:Deletion: This synopsis shows in its
2038:A blue border rings the current node
777:A red node does not have a red child.
764:the following must be satisfied by a
15569:
15067:Dinesh P. Mehta, Sartaj Sahni (Ed.)
14967:"Amortized Computational Complexity"
14899:
14839:
14179:(2nd ed.). MIT Press. pp.
11551:is not considered in this analysis.
10136:): /* symmetric to joinRightRB */
7642:(then with a red root) also
7182:there is a red–black tree of height
6071:// new current node (maybe the root)
4933:) are satisfied throughout the tree.
4575:// Replace N at its parent P by NIL:
2548:) are satisfied throughout the tree.
2155:
934:
16248:
15300:Park, Heejin; Park, Kunsoo (2001).
14410:"Balanced search trees made simple"
14291:
14082:, a variation of the red–black tree
13323:
10435:helper routine that is the same as
10227:The split algorithm is as follows:
8916:The function has been tabulated as
6224:is still short one black node. But
6030:
5857:
5851:
5845:
5839:
5833:
5827:
5735:
5633:
5599:The diagrams show the current node
5475:
5394:
5320:
5158:
5095:
5041:
3711:
3579:
3301:
3267:
3261:
3255:
3249:
3243:
3144:
3140:
3136:
3072:
2931:
2848:
2793:
2753:
2709:
2660:
2440:// N is the new root of the tree T.
929:which is not the case for ordinary
13:
15658:OCW MIT Lecture on Red-black Trees
15601:
15531:. IEEE, Piscataway (NJ): 291–300.
15054:The same partitioning is found in
13803:{\displaystyle \in O(|I|\log |T|)}
12946:
12895:
12827:
12784:
12741:
12698:
12610:
12567:
12478:
12438:must be divided into subsequences
11499:m := ⌊size(I) / 2⌋ (T
10734:
10261:(join(T.left,T.key,L'),b,T.right)
10042:The join algorithm is as follows:
9685:Set operations and bulk operations
8909:{\displaystyle k\in \mathbb {N} .}
7571:{\displaystyle \lfloor \,\rfloor }
7129:
6469:// Otherwise C+D considered black.
6001:, which are precisely those paths
5745:
5564:’s child in the same direction as
3967:. The rotation adds paths through
3789:// Case_I3: N is the root and red.
3156:
3030:The diagrams show the cases where
3011:The diagrams show the parent node
771:Every node is either red or black.
668:" is implied by the condition "is
14:
16625:
15635:
14949:"How does a HashMap work in JAVA"
14822:"The Implementation of epoll (1)"
14468:Journal of Functional Programming
14203:
14173:(2001). "Red–Black Trees".
13318:Stage 3 continues to repair nodes
11526:
11515:, I, ⌊k / 2⌋) T ← join2(T
10893:After that, the algorithm splits
10519:for two red–black trees of sizes
10264:The union of two red–black trees
9988:appears in the tree. The cost of
7615:{\displaystyle \lceil h/2\rceil }
7175:{\displaystyle h\in \mathbb {N} }
6854:
6619:
6542:is red. Exchanging the colors of
6477:
6124:
5919:
5891:
4104:
3863:
3803:
3744:{\displaystyle {\tfrac {h-1}{2}}}
3706:
3497:
3287:
2106:U == NIL || U->color == BLACK
1196:to store different elements with
837:. The result is that the tree is
804:recursive algorithms and proofs.
636:to organize pieces of comparable
399:self-balancing binary search tree
15151:{\displaystyle n=2\cdot 2^{k}-2}
13311:
13299:
13287:
13275:
13263:
13251:
13239:
13227:
13215:
11456:
11444:
11432:
11420:
9933:(set to be red) and right child
6963:
6886:
6877:
6863:
6846:// now: D red && S black
6740:
6651:
6642:
6628:
6569:// P red && S+C+D black:
6509:
6500:
6486:
6328:// now: P red && S black
6247:// S red && P+C+D black:
6156:
6147:
6133:
5961:
5952:
5938:
5648:
5642:
5623:
5603:as the left child of its parent
5509:
5502:
5493:
5468:
5461:
5452:
5435:
5428:
5419:
5387:
5380:
5373:
5366:
5352:
5345:
5338:
5331:
5313:
5306:
5299:
5292:
5275:
5268:
5261:
5254:
5237:
5230:
5223:
5216:
5199:
5192:
5183:
5151:
5144:
5137:
5130:
5088:
5081:
5074:
5067:
4929:All other properties (including
4906:
4608:// start of the (do while)-loop:
4393:Removal of a black non-root leaf
4136:
4127:
4113:
3895:
3886:
3872:
3529:
3520:
3506:
3242:From the body of the loop, case
3015:as the left child of its parent
2963:
2956:
2949:
2921:
2914:
2907:
2887:
2880:
2873:
2838:
2831:
2824:
2804:
2779:
2700:
2693:
2686:
2647:
2544:All other properties (including
2510:
2499:, representing the current node
2476:// start of the (do while)-loop:
2083:
2071:
1995:
1989:
1983:
1759:// pointer to true node required
1177:The original description of the
1057:is another structure supporting
826:, or of requirement 4, called a
614:
600:
15563:
15520:
15479:
15293:
15074:
15061:
15032:
15001:
14992:
14941:
14871:
14828:
14814:
14789:
14753:
14744:
14716:(2022). "13. Red–Black Trees".
14659:. Berlin/Heidelberg: Springer.
14569:
14540:
14455:
14401:
14041:{\displaystyle =O(|I|\log |T|)}
13905:{\displaystyle \in O(\log |T|)}
13565:{\displaystyle \in O(\log |T|)}
13511:{\displaystyle \in O(\log |I|)}
13457:{\displaystyle \in O(\log |T|)}
13199:{\displaystyle \in O(\log |I|)}
12192:{\displaystyle \in O(\log |T|)}
12090:{\displaystyle \in O(\log |T|)}
11757:{\displaystyle \in O(\log |T|)}
11644:{\displaystyle \in O(\log |T|)}
10615:{\displaystyle O(\log m\log n)}
9899:(the other case is symmetric).
9675:{\displaystyle h\in O(\log n).}
5641:By counting the black bullets (
5607:even though it is possible for
4884:// P red && C+S+D black
4378:, simply remove the leaf node.
4334:
3659:// iterate 1 black level higher
3208:{\displaystyle {\tfrac {h}{2}}}
3034:is red also, the red-violation.
3019:even though it is possible for
2033:
15427:{\displaystyle O(\log \log n)}
15421:
15403:
15360:
15354:
15199:
15187:
14581:"Left-leaning Red–Black Trees"
14414:Algorithms and Data Structures
14408:Andersson, Arne (1993-08-11).
14377:
14324:
14266:
14225:Data Structures and Algorithms
14212:
14035:
14031:
14023:
14012:
14004:
14000:
13974:
13970:
13962:
13951:
13943:
13933:
13899:
13895:
13887:
13877:
13845:
13841:
13833:
13829:
13797:
13793:
13785:
13774:
13766:
13762:
13721:
13717:
13709:
13699:
13673:
13669:
13661:
13641:
13633:
13623:
13593:
13585:
13559:
13555:
13547:
13537:
13505:
13501:
13493:
13483:
13451:
13447:
13439:
13429:
13394:
13386:
13378:is assumed to be smaller than
13364:
13356:
13306:Stage 3 begins to repair nodes
13282:Stage 2 begins to repair nodes
13258:Stage 1 begins to repair nodes
13193:
13189:
13181:
13171:
13145:
13141:
13133:
13129:
12280:
12276:
12268:
12257:
12249:
12241:
12233:
12220:
12186:
12182:
12174:
12164:
12132:
12128:
12120:
12116:
12084:
12080:
12072:
12062:
12030:
12024:
11979:
11971:
11954:
11946:
11935:
11927:
11878:
11870:
11853:
11845:
11834:
11826:
11751:
11747:
11739:
11729:
11686:
11678:
11638:
11634:
11626:
11616:
11584:
11572:
11277:
11258:
11247:
11234:
11208:
11189:
11178:
11165:
11121:
10731:
10694:{\displaystyle O(\log \log n)}
10688:
10670:
10609:
10588:
10558:
10549:
10014:
10002:
9666:
9654:
9552:
9540:
9493:
9473:
9445:
9433:
9375:{\displaystyle \log _{2}(n+1)}
9369:
9357:
9244:
9232:
9161:
9149:
8872:
8827:
8810:
8726:
8714:
8618:
8606:
8556:
8534:
8522:
8484:
8384:
8362:
8350:
8339:
8297:
8291:
8249:
8230:
8128:
8116:
8021:
8005:
7768:
7756:
7661:
7649:
7267:
7255:
6962:, namely either red or black (
6756:// C red && S+D black:
6715:’s new sibling. The colors of
5997:red all paths passing through
5816:
4200:is black and its former child
3979:(those in the subtree labeled
3971:(those in the subtree labeled
3236:
1385:
1379:
1329:
1317:
1254:
1242:
1219:
1213:
1138:
1126:
1079:
1067:
974:
962:
920:{\displaystyle h\in O(\log n)}
914:
902:
815:
586:
489:
477:
434:
422:
367:
355:
331:
319:
288:
276:
252:
240:
209:
197:
173:
161:
100:
94:
1:
15467:{\displaystyle n/\log \log n}
15319:10.1016/S0304-3975(00)00287-5
14462:Okasaki, Chris (1999-01-01).
14389:programmers.stackexchange.com
12298:
11590:{\displaystyle \in O(\log k)}
11368:, which can be done by up to
10821:
9890:has larger black height than
9638:nodes (keys) has tree height
6466:// C red && S+D black
6116:// end of the (do while)-loop
5771:becomes the new current node
4845:// C red && S+D black
3812:is red and the root. Because
3701:// end of the (do while)-loop
3182:becomes the new current node
2473:// insert N as dir-child of P
2082:A possibly numbered triangle
1469:// == NIL if root of the tree
1290:
755:
530:. These trees maintained all
15474:processors on the EREW PRAM.
15306:Theoretical Computer Science
15055:
14834:
13727:{\displaystyle =O(\log |T|)}
11151:following constraints hold:
11095:in a way, so that for every
10740:{\displaystyle n\to \infty }
10249:(T.left, true, T.right)
9955:, and those larger than key
9088:{\displaystyle 3>2^{3/2}}
9047:{\displaystyle 9>8=2^{3}}
7588:Its black height is
7351:{\displaystyle ={\Biggl \{}}
7138:Figure 4: Red–black trees RB
7015:// D red && S black:
6077:// (= 1 tree level) higher
4938:Notes to the delete diagrams
4740:// S red ===> P+C+D black
4346:- When the deleted node has
4339:- When the deleted node has
4006:// P red && U black:
3932:is an "inner" grandchild of
3562:becomes red for maintaining
2553:Notes to the insert diagrams
2254:// -> node to be inserted
2169:
7:
16565:Directed acyclic word graph
16331:Double-ended priority queue
15216:
15026:
14908:"Dynamic Optimality—Almost"
14086:Left-leaning red–black tree
14053:
10449:"join-based" implementation
9903:follows the right spine of
9610:being the number of nodes.
9402:{\displaystyle \leq h\leq }
7995:nodes and the black height
7953:{\displaystyle h\!\!-\!\!1}
6538:’s children are black, but
6397:// D red && S black
6038:// Case_D2 (P+C+S+D black):
5927:
5628:(meaning: the current node
4794:// D red && S black
4449:// -> node to be deleted
3492:// P red && U black
3399:// else: P red and G!=NULL.
1484:// == NIL if child is empty
1167:left-leaning red–black tree
1018:left-leaning red-black tree
701:, namely the paths through
694:plus 2 added paths through
673:
594:Example of a red–black tree
581:left-leaning red–black tree
10:
16630:
14719:Introduction to Algorithms
14176:Introduction to Algorithms
13851:{\displaystyle \in O(|I|)}
13151:{\displaystyle \in O(|I|)}
12138:{\displaystyle \in O(|I|)}
10023:{\displaystyle O(\log n),}
9731:is on two red–black trees
6849:// fall through to Case_D6
6472:// fall through to Case_D4
5760:{\displaystyle \Delta h=1}
5522:
4919:
4329:
4096:// fall through to Case_I6
3292:The current node’s parent
3171:{\displaystyle \Delta h=2}
2978:
2534:
2207:
2191:together with a direction
1988:symbolises a red node and
1562:// == NIL if tree is empty
1421:// Basic type definitions:
1409:(v2.0.3 as of June 2019).
1106:persistent data structures
940:Red–black trees, like all
517:
16609:Amortized data structures
16573:
16545:
16439:
16401:
16358:
16277:
16256:
16120:
15999:
15946:
15875:
15732:
15685:3.3 Balanced Search Trees
15608:Mathworld: Red–Black Tree
15496:10.1007/978-3-030-25209-0
15253:, ACM, pp. 253–264,
14927:10.1137/S0097539705447347
14915:SIAM Journal on Computing
14675:10.1007/978-3-540-77978-0
14481:10.1017/S0956796899003494
14432:10.1007/3-540-57155-8_236
13739:
10564:{\displaystyle n(\geq m)}
9916:, which is balanced with
9584:(minimal red–black tree)
8992:Solving the function for
8672:
8591:
8421:
8255:{\displaystyle (m_{h-1})}
7681:{\displaystyle (h-1)/2~.}
7329:
7237:
7001:
6969:
6018:
5875:Rotations occur in cases
5588:before its deletion, but
5173:
5164:
5157:
5150:
5143:
5136:
5129:
4982:
4977:
4972:
4963:
4954:
4949:
4944:
4930:
4482:// -> parent node of N
4397:The complex case is when
4357:
4353:
4224:now go through the black
4217:
4205:
3992:
3831:// P is the root and red:
3563:
3297:
3275:Rotations occur in cases
3004:for its grandparent, and
2597:
2592:
2587:
2578:
2569:
2564:
2559:
2545:
2518:
2305:// -> parent node of P
2178:, at the position in the
2077:
1585:right rotation, animated.
1454:// node of red–black tree
1335:{\displaystyle O(\log n)}
1260:{\displaystyle O(\log m)}
1144:{\displaystyle O(\log n)}
1085:{\displaystyle O(\log n)}
1053:use red–black trees. The
1043:Completely Fair Scheduler
980:{\displaystyle O(\log n)}
796:
749:
495:{\displaystyle O(\log n)}
440:{\displaystyle O(\log n)}
373:{\displaystyle O(\log n)}
337:{\displaystyle O(\log n)}
304:
294:{\displaystyle O(\log n)}
258:{\displaystyle O(\log n)}
225:
215:{\displaystyle O(\log n)}
179:{\displaystyle O(\log n)}
146:
125:
118:
79:
72:
68:
60:
46:
38:
26:
21:
16297:Retrieval Data Structure
16173:Left-child right-sibling
15649:(PDF gzip; 1662 kB)
15619:Pfaff, Ben (June 2004).
15106:{\displaystyle 2\cdot k}
13747:W(find insert positions)
13294:Stage 3 inserts elements
13270:Stage 2 inserts elements
13246:Stage 1 inserts elements
12036:{\displaystyle \in O(k)}
10758:Parallel bulk operations
9566:{\displaystyle {\bigl }}
7006:
6976:(i.o.w. passing through
6747:
6560:
6238:
6074:// iterate 1 black level
6035:
5902:
5775:. So it takes maximally
4407:
4381:- When the deleted node
4370:- When the deleted node
4363:- When the deleted node
4230:
3997:
3822:
3783:
3584:
3351:// From now on P is red.
3306:
3186:. So it takes maximally
2212:
2146:Short-circuit evaluation
1678:// dir ∈ { LEFT, RIGHT }
1588:
1418:
687:, namely a path through
16578:List of data structures
16555:Binary decision diagram
16003:data partitioning trees
15961:C-trie (compressed ADT)
15269:10.1145/2935764.2935768
14605:; Wayne, Kevin (2011).
14336:eternallyconfuzzled.com
14060:List of data structures
13414:T(find insert position)
12001:
11451:insert into the split T
11388:processors in parallel.
10200:.color=black):
10072:.blackHeight):
9980:For some applications,
8969:{\displaystyle h\geq 1}
8054:The other subtree is a
7988:{\displaystyle m_{h-1}}
7892:in figure 4) of height
5905:// Case_D1 (P == NULL):
5689:shows an assignment of
5536:In the diagrams below,
4833:// not considered black
4782:// not considered black
4548:// -> distant nephew
4530:// -> close nephew
4431:// -> red–black tree
3098:shows an assignment of
2236:// -> red–black tree
2136:evaluated in total, if
2125:// not considered black
795:s NIL child, violating
787:(Conclusion) If a node
16560:Directed acyclic graph
15468:
15428:
15387:
15367:
15338:
15209:
15152:
15107:
14556:algs4.cs.princeton.edu
14273:Drozdek, Adam (2001).
14042:
13981:
13906:
13852:
13804:
13728:
13680:
13601:
13566:
13512:
13458:
13402:
13372:
13342:
13200:
13152:
13110:
13086:
13063:
13040:
13015:
12992:
12969:
12915:
12864:
12844:
12801:
12758:
12715:
12672:
12647:
12633:will be inserted into
12627:
12584:
12538:
12518:
12504:is the subsequence of
12498:
12452:
12432:
12412:
12392:
12369:
12349:
12326:
12287:
12193:
12139:
12091:
12037:
11992:
11891:
11783:
11758:
11704:
11645:
11591:
11545:
11409:
11382:
11362:
11342:
11315:
11284:
11215:
11145:
11089:
11037:
11017:
10994:
10942:
10907:
10884:
10860:
10840:
10812:
10792:
10741:
10715:
10695:
10650:directed acyclic graph
10642:
10616:
10565:
10533:
10513:
10290:, is a red–black tree
10241:(nil, false, nil)
10034:operation, such as an
10024:
9676:
9632:
9618:A red–black tree with
9604:
9567:
9500:
9403:
9376:
9324:
9300:
9109:
9089:
9048:
9006:
8970:
8940:
8939:{\displaystyle m_{h}=}
8910:
8879:
8789:
8752:
8665:
8638:
8584:
8563:
8470:
8449:
8391:
8325:
8304:
8277:
8256:
8216:
8195:
8158:
8072:
8048:
7989:
7954:
7912:
7911:{\displaystyle h>1}
7877:
7719:
7699:The RB tree of height
7682:
7636:
7616:
7572:
7540:
7516:
7458:
7433:
7352:
7320:
7230:
7196:
7176:
7151:
6934:becomes the parent of
6783:// S is never the root
5930:Explanation of symbols
5809:
5789:
5761:
4057:// P is never the root
3771:
3745:
3714:has been executed for
3662:// (= 2 tree levels)
3229:
3209:
3172:
2184:in-order predecessor’s
2154:is in accordance with
1954:// new root of subtree
1586:
1392:
1360:
1336:
1281:
1261:
1226:
1145:
1102:functional programming
1086:
1039:computational geometry
1035:real-time applications
1000:
991:Analogy to 2–3–4 trees
981:
921:
879:
855:
724:pointers of value NULL
496:
461:
441:
374:
338:
295:
259:
216:
180:
107:
15570:Jájá, Joseph (1992).
15469:
15429:
15388:
15368:
15339:
15238:; Ferizovic, Daniel;
15210:
15153:
15108:
14648:"7. Sorted Sequences"
14219:Morris, John (1998).
14163:Leiserson, Charles E.
14043:
13982:
13907:
13862:W(insert) + W(repair)
13853:
13814:#insertions, #repairs
13805:
13729:
13681:
13602:
13567:
13522:T(insert) + T(repair)
13513:
13459:
13403:
13373:
13343:
13234:Find insert positions
13201:
13153:
13111:
13087:
13085:{\displaystyle \in I}
13064:
13041:
13016:
13014:{\displaystyle \in S}
12993:
12970:
12916:
12865:
12845:
12802:
12759:
12716:
12673:
12648:
12628:
12590:of every subsequence
12585:
12539:
12519:
12499:
12453:
12433:
12413:
12393:
12391:{\displaystyle \in I}
12370:
12350:
12327:
12288:
12194:
12140:
12092:
12038:
11993:
11892:
11784:
11759:
11705:
11655:insertions per thread
11646:
11592:
11546:
11410:
11383:
11363:
11343:
11341:{\displaystyle T_{j}}
11316:
11314:{\displaystyle I_{j}}
11285:
11216:
11146:
11090:
11038:
11018:
11000:of about equal sizes.
10995:
10943:
10908:
10885:
10861:
10841:
10813:
10793:
10752:join-based algorithms
10742:
10716:
10696:
10643:
10617:
10566:
10534:
10514:
10096:.color⟩,joinRightRB(T
10025:
9874:to be red. Otherwise
9870:have black root, set
9677:
9633:
9605:
9579:(perfect binary tree)
9568:
9501:
9404:
9377:
9325:
9301:
9110:
9090:
9049:
9007:
8971:
8941:
8911:
8880:
8790:
8788:{\displaystyle m_{h}}
8753:
8666:
8639:
8585:
8564:
8471:
8450:
8448:{\displaystyle m_{h}}
8392:
8326:
8305:
8278:
8257:
8217:
8196:
8194:{\displaystyle m_{h}}
8159:
8073:
8049:
7990:
7955:
7913:
7886:A minimal RB tree (RB
7878:
7720:
7683:
7637:
7617:
7573:
7541:
7517:
7459:
7434:
7353:
7321:
7231:
7229:{\displaystyle m_{h}}
7197:
7177:
7137:
6739:may be red or black (
6228:now has a red parent
5810:
5790:
5762:
4926:if other paths exist.
4911:in higher iterations.
4905:is a true black node
4605:// jump into the loop
4512:// -> sibling of N
4311:// insertion complete
3920:is red but the uncle
3858:// insertion complete
3798:// insertion complete
3772:
3746:
3587:// Case_I2 (P+U red):
3345:// insertion complete
3336:// Case_I1 (P black):
3230:
3210:
3173:
2449:// insertion complete
2419:// There is no parent
2140:. Then in both cases
1582:
1402:(two for insertion).
1393:
1361:
1337:
1282:
1262:
1227:
1146:
1087:
1014:1-to-1 correspondence
998:
982:
922:
880:
856:
807:As an example, every
497:
462:
442:
375:
339:
296:
260:
217:
181:
108:
16426:Unrolled linked list
16183:Log-structured merge
15726:Tree data structures
15438:
15397:
15377:
15366:{\displaystyle O(1)}
15348:
15328:
15162:
15117:
15091:
14963:Tarjan, Robert Endre
14143:References and notes
14075:Order statistic tree
13991:
13924:
13868:
13820:
13753:
13690:
13614:
13581:
13528:
13474:
13420:
13382:
13352:
13332:
13162:
13120:
13100:
13073:
13053:
13030:
13002:
12982:
12925:
12874:
12854:
12811:
12768:
12725:
12682:
12657:
12637:
12594:
12551:
12528:
12508:
12462:
12442:
12422:
12402:
12379:
12359:
12339:
12335:For each element in
12316:
12211:
12155:
12107:
12053:
12015:
11906:
11796:
11773:
11720:
11661:
11607:
11563:
11535:
11399:
11372:
11352:
11325:
11298:
11226:
11157:
11099:
11047:
11027:
11007:
10952:
10917:
10897:
10874:
10850:
10830:
10802:
10782:
10725:
10705:
10664:
10626:
10582:
10543:
10523:
10458:
10196:.color=black) and (T
10064:.color=black) and (T
9996:
9642:
9622:
9594:
9511:
9414:
9387:
9341:
9314:
9122:
9099:
9058:
9019:
8996:
8954:
8920:
8889:
8807:
8803:with breakpoints at
8772:
8676:
8655:
8595:
8574:
8481:
8460:
8432:
8336:
8315:
8288:
8267:
8227:
8206:
8178:
8082:
8062:
7999:
7966:
7934:
7896:
7732:
7703:
7646:
7626:
7592:
7558:
7530:
7472:
7448:
7441:
7363:
7335:
7241:
7213:
7186:
7158:
7111:// deletion complete
7042:// P may be the root
6614:// deletion complete
6274:// P may be the root
6193:have to be black. A
5914:// deletion complete
5799:
5779:
5742:
4405:is replaced by NIL.
4266:// G may be the root
3755:
3718:
3219:
3190:
3153:
2182:of a NIL node whose
2144:is not touched (see
1391:{\displaystyle O(1)}
1373:
1350:
1311:
1271:
1236:
1225:{\displaystyle O(m)}
1207:
1120:
1108:, used to construct
1061:
956:
890:
869:
845:
651:of red–black trees (
573:Cormen et al. (2001)
471:
451:
416:
349:
313:
270:
234:
191:
155:
106:{\displaystyle O(n)}
88:
16474:Self-balancing tree
15628:Stanford University
15547:2015arXiv151005433A
14318:10.1109/SFCS.1978.3
14302:Guibas, Leonidas J.
14065:Tree data structure
13600:{\displaystyle |I|}
13577:T(bulkInsert) with
13401:{\displaystyle |T|}
13371:{\displaystyle |I|}
12547:The middle element
11769:T(bulkInsert) with
11495:I: T.insert(e)
11023:must be split into
10656:Parallel algorithms
10641:{\displaystyle m=1}
10116:rotateLeft(T')
9912:until a black node
9773:, i.e. all keys in
9330:is in the interval
8303:{\displaystyle (1)}
8056:perfect binary tree
7718:{\displaystyle h=1}
7117:// end of RBdelete2
6954:are exchanged, and
6220:, the path through
5719:A ✓ sign in column
5548:for the sibling of
4317:// end of RBinsert1
4072:// new current node
3770:{\displaystyle h~.}
3656:// new current node
3550:If both the parent
3480:// considered black
3124:A ✓ sign in column
2323:// -> uncle of N
2108:// considered black
1535:#define right child
1532:#define left child
1520:#define NIL NULL
1297:binary search trees
1049:system call of the
942:binary search trees
931:binary search trees
809:perfect binary tree
542:or even 2–3 trees.
16454:Binary search tree
16319:Double-ended queue
16148:Fractal tree index
15743:associative arrays
15690:Red–black BST Demo
15683:Red–black BSTs in
15615:, by Roger Whitney
15464:
15424:
15383:
15363:
15334:
15205:
15148:
15103:
14951:. coding-geek.com.
14850:"Robert Sedgewick"
14706:Leiserson, Charles
14552:"RedBlackBST.java"
14252:10.1007/BF00289509
14038:
13977:
13902:
13848:
13800:
13724:
13676:
13597:
13562:
13508:
13454:
13398:
13368:
13338:
13196:
13148:
13106:
13082:
13059:
13046:is fully repaired.
13036:
13011:
12988:
12965:
12911:
12860:
12840:
12797:
12754:
12711:
12671:{\displaystyle n'}
12668:
12643:
12623:
12580:
12534:
12514:
12494:
12448:
12428:
12408:
12388:
12365:
12345:
12322:
12283:
12189:
12135:
12087:
12047:W(split) + W(join)
12033:
11988:
11887:
11779:
11754:
11700:
11641:
11601:T(split) + T(join)
11587:
11541:
11405:
11378:
11358:
11338:
11311:
11280:
11211:
11141:
11085:
11033:
11013:
10990:
10938:
10903:
10880:
10856:
10836:
10808:
10788:
10737:
10711:
10691:
10638:
10612:
10561:
10529:
10509:
10282:representing sets
10020:
9843:and right subtree
9786:, and all keys in
9672:
9628:
9600:
9563:
9496:
9399:
9372:
9320:
9296:
9105:
9085:
9044:
9002:
8966:
8936:
8906:
8875:
8785:
8748:
8661:
8634:
8580:
8559:
8466:
8445:
8387:
8321:
8300:
8273:
8252:
8212:
8191:
8154:
8068:
8058:of (black) height
8044:
7985:
7950:
7908:
7873:
7715:
7678:
7632:
7612:
7568:
7536:
7512:
7503:
7454:
7429:
7413:
7386:
7348:
7316:
7226:
7192:
7172:
7152:
6692:is black. After a
5817:amortized constant
5805:
5785:
5757:
5596:may be NIL nodes).
4093:// new parent of N
3767:
3741:
3739:
3237:amortized constant
3225:
3205:
3203:
3168:
2198:P->child == NIL
2180:binary search tree
1587:
1388:
1356:
1332:
1277:
1257:
1222:
1141:
1110:associative arrays
1082:
1001:
977:
946:in-order traversal
917:
875:
851:
762:binary search tree
630:binary search tree
547:Leonidas J. Guibas
512:binary search tree
492:
457:
437:
370:
334:
291:
255:
212:
176:
103:
51:Leonidas J. Guibas
16614:1972 in computing
16586:
16585:
16388:Hashed array tree
16287:Associative array
16216:
16215:
15556:978-1-5090-5411-4
15386:{\displaystyle n}
15337:{\displaystyle n}
15278:978-1-4503-4210-0
14824:. September 2014.
14801:developer.ibm.com
14782:978-0-201-35088-3
14767:Algorithms in C++
14761:Sedgewick, Robert
14684:978-3-540-77977-3
14618:978-0-321-57351-3
14603:Sedgewick, Robert
14577:Sedgewick, Robert
14548:Sedgewick, Robert
14533:978-0-201-06672-2
14512:Sedgewick, Robert
14441:978-3-540-57155-1
14361:Sedgewick, Robert
14332:"Red Black Trees"
14312:. pp. 8–21.
14306:Sedgewick, Robert
14221:"Red–Black Trees"
14206:"Red–Black Trees"
14190:978-0-262-03293-3
14167:Rivest, Ronald L.
14159:Cormen, Thomas H.
14051:
14050:
13737:
13736:
13341:{\displaystyle I}
13109:{\displaystyle S}
13062:{\displaystyle S}
13039:{\displaystyle T}
12991:{\displaystyle T}
12863:{\displaystyle S}
12646:{\displaystyle T}
12537:{\displaystyle n}
12517:{\displaystyle I}
12451:{\displaystyle S}
12431:{\displaystyle I}
12411:{\displaystyle T}
12368:{\displaystyle T}
12348:{\displaystyle I}
12325:{\displaystyle I}
12296:
12295:
11962:
11900:
11899:
11861:
11782:{\displaystyle k}
11694:
11557:#recursion levels
11544:{\displaystyle I}
11408:{\displaystyle I}
11381:{\displaystyle k}
11361:{\displaystyle j}
11256:
11232:
11187:
11163:
11036:{\displaystyle k}
11016:{\displaystyle T}
10906:{\displaystyle I}
10883:{\displaystyle I}
10859:{\displaystyle T}
10839:{\displaystyle I}
10811:{\displaystyle T}
10791:{\displaystyle I}
10714:{\displaystyle n}
10532:{\displaystyle m}
10491:
10381:.left) proc2=
10233:split(T, k):
10184:.blackHeight>T
10156:.blackHeight>T
9795:are greater than
9631:{\displaystyle n}
9603:{\displaystyle n}
9588:
9587:
9323:{\displaystyle h}
9108:{\displaystyle h}
9005:{\displaystyle h}
8762:
8761:
8664:{\displaystyle =}
8583:{\displaystyle +}
8469:{\displaystyle =}
8417:(second subtree)
8324:{\displaystyle +}
8276:{\displaystyle +}
8215:{\displaystyle =}
8071:{\displaystyle s}
7869:
7674:
7635:{\displaystyle h}
7550:
7549:
7539:{\displaystyle h}
7502:
7457:{\displaystyle h}
7412:
7385:
7195:{\displaystyle h}
6942:’s distant child
6915:’s distant child
6895:
6872:
6745:in the diagram).
6688:’s distant child
6660:
6637:
6518:
6495:
6418:// close nephew
6349:// distant nephew
6165:
6142:
6119:// (with return;)
5970:
5947:
5931:
5896:The current node
5808:{\displaystyle h}
5788:{\displaystyle h}
5533:
5532:
5527:columns, that all
4704:// close nephew
4683:// distant nephew
4157:The current node
4145:
4122:
3904:
3881:
3777:The current node
3763:
3738:
3538:
3515:
3396:// P red and root
3228:{\displaystyle h}
3202:
2992:In the diagrams,
2989:
2988:
2983:columns, that all
1615:// red–black tree
1583:Left rotation and
1547:// red–black tree
1359:{\displaystyle n}
1280:{\displaystyle m}
885:of entries, i.e.
878:{\displaystyle n}
854:{\displaystyle h}
460:{\displaystyle n}
387:
386:
383:
382:
16621:
16411:Association list
16243:
16236:
16229:
16220:
16219:
15719:
15712:
15705:
15696:
15695:
15669:
15631:
15625:
15596:
15595:
15567:
15561:
15560:
15540:
15524:
15518:
15517:
15483:
15477:
15476:
15473:
15471:
15470:
15465:
15448:
15433:
15431:
15430:
15425:
15392:
15390:
15389:
15384:
15372:
15370:
15369:
15364:
15343:
15341:
15340:
15335:
15321:
15312:(1–2): 415–435.
15297:
15291:
15289:
15262:
15248:
15236:Blelloch, Guy E.
15232:
15223:
15214:
15212:
15211:
15206:
15183:
15182:
15157:
15155:
15154:
15149:
15141:
15140:
15112:
15110:
15109:
15104:
15078:
15072:
15065:
15059:
15052:
15043:
15036:
15030:
15022:
15013:
15012:
15005:
14999:
14996:
14990:
14989:
14971:
14959:
14953:
14952:
14945:
14939:
14938:
14912:
14903:
14897:
14896:
14894:
14892:
14886:Cs.princeton.edu
14883:
14879:"Balanced Trees"
14875:
14869:
14868:
14866:
14864:
14857:Cs.princeton.edu
14854:
14846:
14837:
14832:
14826:
14825:
14818:
14812:
14811:
14809:
14807:
14793:
14787:
14786:
14770:
14757:
14751:
14748:
14742:
14741:
14722:(4th ed.).
14698:
14689:
14688:
14668:
14652:
14636:
14623:
14622:
14599:
14588:
14587:
14585:
14573:
14567:
14566:
14564:
14562:
14550:; Wayne, Kevin.
14544:
14538:
14537:
14522:(1st ed.).
14521:
14508:
14502:
14501:
14483:
14459:
14453:
14449:
14444:. Archived from
14425:
14405:
14399:
14398:
14396:
14395:
14381:
14375:
14374:
14357:
14351:
14350:
14348:
14347:
14338:. Archived from
14328:
14322:
14321:
14298:
14289:
14288:
14270:
14264:
14263:
14240:Acta Informatica
14235:
14229:
14228:
14216:
14210:
14209:
14201:
14195:
14194:
14155:
14047:
14045:
14044:
14039:
14034:
14026:
14015:
14007:
13986:
13984:
13983:
13978:
13973:
13965:
13954:
13946:
13911:
13909:
13908:
13903:
13898:
13890:
13857:
13855:
13854:
13849:
13844:
13836:
13809:
13807:
13806:
13801:
13796:
13788:
13777:
13769:
13744:
13743:
13733:
13731:
13730:
13725:
13720:
13712:
13685:
13683:
13682:
13677:
13672:
13664:
13644:
13636:
13606:
13604:
13603:
13598:
13596:
13588:
13571:
13569:
13568:
13563:
13558:
13550:
13517:
13515:
13514:
13509:
13504:
13496:
13463:
13461:
13460:
13455:
13450:
13442:
13411:
13410:
13407:
13405:
13404:
13399:
13397:
13389:
13377:
13375:
13374:
13369:
13367:
13359:
13347:
13345:
13344:
13339:
13315:
13303:
13291:
13279:
13267:
13255:
13243:
13231:
13219:
13205:
13203:
13202:
13197:
13192:
13184:
13157:
13155:
13154:
13149:
13144:
13136:
13115:
13113:
13112:
13107:
13091:
13089:
13088:
13083:
13068:
13066:
13065:
13060:
13045:
13043:
13042:
13037:
13020:
13018:
13017:
13012:
12997:
12995:
12994:
12989:
12974:
12972:
12971:
12966:
12964:
12963:
12962:
12961:
12940:
12920:
12918:
12917:
12912:
12910:
12909:
12908:
12907:
12889:
12869:
12867:
12866:
12861:
12849:
12847:
12846:
12841:
12839:
12838:
12837:
12836:
12806:
12804:
12803:
12798:
12796:
12795:
12794:
12793:
12763:
12761:
12760:
12755:
12753:
12752:
12751:
12750:
12720:
12718:
12717:
12712:
12710:
12709:
12708:
12707:
12677:
12675:
12674:
12669:
12667:
12652:
12650:
12649:
12644:
12632:
12630:
12629:
12624:
12622:
12621:
12620:
12619:
12589:
12587:
12586:
12581:
12579:
12578:
12577:
12576:
12543:
12541:
12540:
12535:
12523:
12521:
12520:
12515:
12503:
12501:
12500:
12495:
12493:
12492:
12491:
12490:
12457:
12455:
12454:
12449:
12437:
12435:
12434:
12429:
12417:
12415:
12414:
12409:
12397:
12395:
12394:
12389:
12374:
12372:
12371:
12366:
12354:
12352:
12351:
12346:
12331:
12329:
12328:
12323:
12292:
12290:
12289:
12284:
12279:
12271:
12260:
12252:
12244:
12236:
12198:
12196:
12195:
12190:
12185:
12177:
12144:
12142:
12141:
12136:
12131:
12123:
12096:
12094:
12093:
12088:
12083:
12075:
12042:
12040:
12039:
12034:
12006:
12005:
11997:
11995:
11994:
11989:
11987:
11983:
11982:
11974:
11963:
11958:
11957:
11949:
11943:
11938:
11930:
11896:
11894:
11893:
11888:
11886:
11882:
11881:
11873:
11862:
11857:
11856:
11848:
11842:
11837:
11829:
11788:
11786:
11785:
11780:
11763:
11761:
11760:
11755:
11750:
11742:
11709:
11707:
11706:
11701:
11699:
11695:
11690:
11689:
11681:
11675:
11650:
11648:
11647:
11642:
11637:
11629:
11596:
11594:
11593:
11588:
11554:
11553:
11550:
11548:
11547:
11542:
11460:
11448:
11436:
11424:
11414:
11412:
11411:
11406:
11387:
11385:
11384:
11379:
11367:
11365:
11364:
11359:
11347:
11345:
11344:
11339:
11337:
11336:
11320:
11318:
11317:
11312:
11310:
11309:
11289:
11287:
11286:
11281:
11276:
11275:
11257:
11254:
11246:
11245:
11233:
11230:
11220:
11218:
11217:
11212:
11207:
11206:
11188:
11185:
11177:
11176:
11164:
11161:
11150:
11148:
11147:
11142:
11124:
11119:
11118:
11113:
11094:
11092:
11091:
11086:
11081:
11080:
11062:
11061:
11042:
11040:
11039:
11034:
11022:
11020:
11019:
11014:
10999:
10997:
10996:
10991:
10986:
10985:
10967:
10966:
10947:
10945:
10944:
10939:
10937:
10936:
10931:
10912:
10910:
10909:
10904:
10889:
10887:
10886:
10881:
10865:
10863:
10862:
10857:
10845:
10843:
10842:
10837:
10817:
10815:
10814:
10809:
10797:
10795:
10794:
10789:
10746:
10744:
10743:
10738:
10720:
10718:
10717:
10712:
10700:
10698:
10697:
10692:
10647:
10645:
10644:
10639:
10621:
10619:
10618:
10613:
10570:
10568:
10567:
10562:
10538:
10536:
10535:
10530:
10518:
10516:
10515:
10510:
10508:
10504:
10503:
10499:
10492:
10484:
10401:proc1,proc2
10365:.key) proc1=
10303:
10294:that represents
10293:
10289:
10285:
10281:
10272:
10123:
10029:
10027:
10026:
10021:
9987:
9970:
9966:
9962:
9958:
9954:
9941:
9932:
9928:
9924:
9915:
9911:
9898:
9889:
9877:
9873:
9869:
9860:
9851:
9842:
9838:
9820:
9816:
9807:
9798:
9794:
9785:
9781:
9772:
9752:
9748:
9739:
9692:
9691:red–black trees:
9681:
9679:
9678:
9673:
9637:
9635:
9634:
9629:
9609:
9607:
9606:
9601:
9572:
9570:
9569:
9564:
9562:
9561:
9536:
9535:
9520:
9519:
9505:
9503:
9502:
9497:
9483:
9469:
9468:
9429:
9428:
9408:
9406:
9405:
9400:
9381:
9379:
9378:
9373:
9353:
9352:
9333:
9332:
9329:
9327:
9326:
9321:
9305:
9303:
9302:
9297:
9289:
9288:
9284:
9256:
9255:
9251:
9223:
9222:
9216:
9215:
9211:
9189:
9188:
9173:
9172:
9168:
9134:
9133:
9114:
9112:
9111:
9106:
9095:, which for odd
9094:
9092:
9091:
9086:
9084:
9083:
9079:
9053:
9051:
9050:
9045:
9043:
9042:
9011:
9009:
9008:
9003:
8988:
8982:
8975:
8973:
8972:
8967:
8945:
8943:
8942:
8937:
8932:
8931:
8915:
8913:
8912:
8907:
8902:
8884:
8882:
8881:
8876:
8863:
8862:
8844:
8843:
8830:
8801:piecewise linear
8794:
8792:
8791:
8786:
8784:
8783:
8768:of the function
8757:
8755:
8754:
8749:
8741:
8740:
8733:
8702:
8701:
8694:
8670:
8668:
8667:
8662:
8643:
8641:
8640:
8635:
8633:
8632:
8625:
8589:
8587:
8586:
8581:
8568:
8566:
8565:
8560:
8549:
8548:
8541:
8510:
8509:
8502:
8475:
8473:
8472:
8467:
8454:
8452:
8451:
8446:
8444:
8443:
8407:(higher subtree)
8396:
8394:
8393:
8388:
8377:
8376:
8369:
8330:
8328:
8327:
8322:
8309:
8307:
8306:
8301:
8282:
8280:
8279:
8274:
8261:
8259:
8258:
8253:
8248:
8247:
8221:
8219:
8218:
8213:
8200:
8198:
8197:
8192:
8190:
8189:
8170:
8169:
8163:
8161:
8160:
8155:
8143:
8142:
8135:
8094:
8093:
8077:
8075:
8074:
8069:
8053:
8051:
8050:
8045:
8028:
7994:
7992:
7991:
7986:
7984:
7983:
7961:
7959:
7957:
7956:
7951:
7928:
7917:
7915:
7914:
7909:
7882:
7880:
7879:
7874:
7867:
7850:
7849:
7835:
7834:
7812:
7811:
7804:
7783:
7782:
7775:
7744:
7743:
7724:
7722:
7721:
7716:
7687:
7685:
7684:
7679:
7672:
7668:
7641:
7639:
7638:
7633:
7621:
7619:
7618:
7613:
7605:
7577:
7575:
7574:
7569:
7545:
7543:
7542:
7537:
7521:
7519:
7518:
7513:
7505:
7504:
7498:
7487:
7463:
7461:
7460:
7455:
7438:
7436:
7435:
7430:
7422:
7421:
7414:
7405:
7388:
7387:
7378:
7357:
7355:
7354:
7349:
7347:
7346:
7325:
7323:
7322:
7317:
7309:
7308:
7301:
7282:
7281:
7274:
7235:
7233:
7232:
7227:
7225:
7224:
7207:
7206:
7201:
7199:
7198:
7193:
7181:
7179:
7178:
7173:
7171:
7118:
7115:
7112:
7109:
7106:
7103:
7100:
7097:
7094:
7091:
7088:
7085:
7082:
7079:
7076:
7073:
7070:
7067:
7064:
7061:
7058:
7055:
7052:
7049:
7046:
7043:
7040:
7037:
7034:
7031:
7028:
7025:
7022:
7019:
7016:
7013:
7010:
6967:
6946:. The colors of
6925:
6923:
6919:is red. After a
6894:higher iteration
6893:
6890:
6881:
6870:
6867:
6850:
6847:
6844:
6841:
6838:
6835:
6832:
6829:
6826:
6823:
6820:
6817:
6814:
6811:
6808:
6805:
6802:
6799:
6796:
6793:
6790:
6787:
6784:
6781:
6778:
6775:
6772:
6769:
6766:
6763:
6760:
6757:
6754:
6751:
6744:
6698:
6696:
6659:higher iteration
6658:
6655:
6646:
6635:
6632:
6615:
6612:
6609:
6606:
6603:
6600:
6597:
6594:
6591:
6588:
6585:
6582:
6579:
6576:
6573:
6570:
6567:
6564:
6517:higher iteration
6516:
6513:
6504:
6493:
6490:
6473:
6470:
6467:
6464:
6461:
6458:
6455:
6452:
6449:
6446:
6443:
6440:
6437:
6434:
6431:
6428:
6425:
6422:
6419:
6416:
6413:
6410:
6407:
6404:
6401:
6398:
6395:
6392:
6389:
6386:
6383:
6380:
6377:
6374:
6371:
6368:
6365:
6362:
6359:
6356:
6353:
6350:
6347:
6344:
6341:
6338:
6335:
6332:
6329:
6326:
6323:
6320:
6317:
6314:
6311:
6308:
6305:
6302:
6299:
6296:
6293:
6290:
6287:
6284:
6281:
6278:
6275:
6272:
6269:
6266:
6263:
6260:
6257:
6254:
6251:
6248:
6245:
6242:
6199:
6197:
6185:and the nephews
6164:higher iteration
6163:
6160:
6151:
6140:
6137:
6120:
6117:
6114:
6111:
6108:
6105:
6102:
6099:
6096:
6093:
6090:
6087:
6084:
6081:
6078:
6075:
6072:
6069:
6066:
6063:
6060:
6057:
6054:
6051:
6048:
6045:
6042:
6039:
6005:passing through
5969:higher iteration
5968:
5965:
5956:
5945:
5942:
5929:
5915:
5912:
5909:
5906:
5858:"Delete case D3"
5814:
5812:
5811:
5806:
5794:
5792:
5791:
5786:
5766:
5764:
5763:
5758:
5736:"Delete case D2"
5733:
5652:
5646:
5627:
5614:
5580:’s other child (
5513:
5506:
5497:
5472:
5465:
5456:
5439:
5432:
5423:
5391:
5384:
5377:
5370:
5356:
5349:
5342:
5335:
5317:
5310:
5303:
5296:
5279:
5272:
5265:
5258:
5241:
5234:
5227:
5220:
5203:
5196:
5187:
5155:
5148:
5141:
5134:
5092:
5085:
5078:
5071:
4942:
4941:
4910:
4885:
4882:
4879:
4876:
4873:
4870:
4867:
4864:
4861:
4858:
4855:
4852:
4849:
4846:
4843:
4840:
4837:
4834:
4831:
4828:
4825:
4822:
4819:
4816:
4813:
4810:
4807:
4804:
4801:
4798:
4795:
4792:
4789:
4786:
4783:
4780:
4777:
4774:
4771:
4768:
4765:
4762:
4759:
4756:
4753:
4750:
4747:
4744:
4741:
4738:
4735:
4732:
4729:
4726:
4723:
4720:
4717:
4714:
4711:
4708:
4705:
4702:
4699:
4696:
4693:
4690:
4687:
4684:
4681:
4678:
4675:
4672:
4669:
4666:
4663:
4660:
4657:
4654:
4651:
4648:
4645:
4642:
4639:
4636:
4633:
4630:
4627:
4624:
4621:
4618:
4615:
4612:
4609:
4606:
4603:
4600:
4597:
4594:
4591:
4588:
4585:
4582:
4579:
4576:
4573:
4570:
4567:
4564:
4561:
4558:
4555:
4552:
4549:
4546:
4543:
4540:
4537:
4534:
4531:
4528:
4525:
4522:
4519:
4516:
4513:
4510:
4507:
4504:
4501:
4498:
4495:
4492:
4489:
4486:
4483:
4480:
4477:
4474:
4471:
4468:
4465:
4462:
4459:
4456:
4453:
4450:
4447:
4444:
4441:
4438:
4435:
4432:
4429:
4426:
4423:
4420:
4417:
4414:
4411:
4385:(both NIL), and
4374:(both NIL), and
4318:
4315:
4312:
4309:
4306:
4303:
4300:
4297:
4294:
4291:
4288:
4285:
4282:
4279:
4276:
4273:
4270:
4267:
4264:
4261:
4258:
4255:
4252:
4249:
4246:
4243:
4240:
4237:
4234:
4171:
4169:
4144:higher iteration
4143:
4140:
4131:
4120:
4117:
4100:
4097:
4094:
4091:
4088:
4085:
4082:
4079:
4076:
4073:
4070:
4067:
4064:
4061:
4058:
4055:
4052:
4049:
4046:
4043:
4040:
4037:
4034:
4031:
4028:
4025:
4022:
4019:
4016:
4013:
4010:
4007:
4004:
4001:
3954:
3952:
3903:higher iteration
3902:
3899:
3890:
3879:
3876:
3859:
3856:
3853:
3850:
3847:
3844:
3841:
3838:
3835:
3832:
3829:
3826:
3799:
3796:
3793:
3790:
3787:
3776:
3774:
3773:
3768:
3761:
3750:
3748:
3747:
3742:
3740:
3734:
3723:
3702:
3699:
3696:
3693:
3690:
3687:
3684:
3681:
3678:
3675:
3672:
3669:
3666:
3663:
3660:
3657:
3654:
3651:
3648:
3645:
3642:
3639:
3636:
3633:
3630:
3627:
3624:
3621:
3618:
3615:
3612:
3609:
3606:
3603:
3600:
3597:
3594:
3591:
3588:
3537:higher iteration
3536:
3533:
3524:
3513:
3510:
3493:
3490:
3487:
3484:
3481:
3478:
3475:
3472:
3469:
3466:
3463:
3460:
3457:
3454:
3451:
3448:
3445:
3442:
3439:
3436:
3433:
3430:
3427:
3424:
3421:
3418:
3415:
3412:
3409:
3406:
3403:
3400:
3397:
3394:
3391:
3388:
3385:
3382:
3379:
3376:
3373:
3370:
3367:
3364:
3361:
3358:
3355:
3352:
3349:
3346:
3343:
3340:
3337:
3334:
3331:
3328:
3325:
3322:
3319:
3316:
3313:
3310:
3234:
3232:
3231:
3226:
3214:
3212:
3211:
3206:
3204:
3195:
3177:
3175:
3174:
3169:
3143:, where in case
3141:"Insert case I2"
3137:"Insert case I1"
3026:
2967:
2960:
2953:
2925:
2918:
2911:
2891:
2884:
2877:
2842:
2835:
2828:
2808:
2783:
2704:
2697:
2690:
2651:
2557:
2556:
2514:
2483:
2480:
2477:
2474:
2471:
2468:
2465:
2462:
2459:
2456:
2453:
2450:
2447:
2444:
2441:
2438:
2435:
2432:
2429:
2426:
2423:
2420:
2417:
2414:
2411:
2408:
2405:
2402:
2399:
2396:
2393:
2390:
2387:
2384:
2381:
2378:
2375:
2372:
2369:
2366:
2363:
2360:
2357:
2354:
2351:
2348:
2345:
2342:
2339:
2336:
2333:
2330:
2327:
2324:
2321:
2318:
2315:
2312:
2309:
2306:
2303:
2300:
2297:
2294:
2291:
2288:
2285:
2282:
2279:
2276:
2273:
2270:
2267:
2264:
2261:
2258:
2255:
2252:
2249:
2246:
2243:
2240:
2237:
2234:
2231:
2228:
2225:
2222:
2219:
2216:
2201:
2199:
2194:
2190:
2164:
2153:
2152:considered black
2143:
2139:
2127:
2110:
2087:
2075:
2023:in the diagrams.
2022:
2020:
2014:
2012:
1999:
1993:
1987:
1967:
1964:
1961:
1958:
1955:
1952:
1949:
1946:
1943:
1940:
1937:
1934:
1931:
1928:
1925:
1922:
1919:
1916:
1913:
1910:
1907:
1904:
1901:
1898:
1895:
1892:
1889:
1886:
1883:
1880:
1877:
1874:
1871:
1868:
1865:
1862:
1859:
1856:
1853:
1850:
1847:
1844:
1841:
1838:
1835:
1832:
1829:
1826:
1823:
1820:
1817:
1814:
1811:
1808:
1805:
1802:
1799:
1796:
1793:
1790:
1787:
1784:
1781:
1778:
1775:
1772:
1769:
1766:
1763:
1760:
1757:
1754:
1751:
1748:
1745:
1742:
1739:
1736:
1733:
1730:
1727:
1724:
1721:
1718:
1715:
1712:
1709:
1706:
1703:
1700:
1697:
1694:
1691:
1688:
1685:
1682:
1679:
1676:
1673:
1670:
1667:
1664:
1661:
1658:
1655:
1652:
1649:
1646:
1643:
1640:
1637:
1634:
1631:
1628:
1625:
1622:
1619:
1616:
1613:
1610:
1607:
1604:
1601:
1598:
1595:
1592:
1575:
1572:
1569:
1566:
1563:
1560:
1557:
1554:
1551:
1548:
1545:
1542:
1539:
1536:
1533:
1530:
1527:
1524:
1521:
1518:
1515:
1512:
1509:
1506:
1503:
1500:
1497:
1494:
1491:
1488:
1487:// The index is:
1485:
1482:
1479:
1476:
1473:
1470:
1467:
1464:
1461:
1458:
1455:
1452:
1449:
1446:
1443:
1440:
1437:
1434:
1431:
1428:
1425:
1422:
1397:
1395:
1394:
1389:
1365:
1363:
1362:
1357:
1341:
1339:
1338:
1333:
1307:a small number,
1286:
1284:
1283:
1278:
1266:
1264:
1263:
1258:
1231:
1229:
1228:
1223:
1150:
1148:
1147:
1142:
1091:
1089:
1088:
1083:
986:
984:
983:
978:
928:
926:
924:
923:
918:
884:
882:
881:
876:
860:
858:
857:
852:
767:
736:
671:
667:
663:
658:
656:
642:"internal nodes"
634:computer science
618:
604:
551:Robert Sedgewick
508:memory footprint
501:
499:
498:
493:
466:
464:
463:
458:
446:
444:
443:
438:
391:computer science
379:
377:
376:
371:
343:
341:
340:
335:
300:
298:
297:
292:
264:
262:
261:
256:
221:
219:
218:
213:
185:
183:
182:
177:
112:
110:
109:
104:
74:Space complexity
70:
69:
61:Complexities in
55:Robert Sedgewick
19:
18:
16629:
16628:
16624:
16623:
16622:
16620:
16619:
16618:
16589:
16588:
16587:
16582:
16569:
16541:
16435:
16431:XOR linked list
16397:
16373:Circular buffer
16354:
16273:
16252:
16250:Data structures
16247:
16217:
16212:
16116:
15995:
15942:
15871:
15867:Weight-balanced
15822:Order statistic
15736:
15728:
15723:
15667:
15638:
15623:
15618:
15604:
15602:Further reading
15599:
15584:
15568:
15564:
15557:
15525:
15521:
15506:
15484:
15480:
15444:
15439:
15436:
15435:
15398:
15395:
15394:
15378:
15375:
15374:
15349:
15346:
15345:
15329:
15326:
15325:
15298:
15294:
15279:
15246:
15233:
15226:
15220:
15178:
15174:
15163:
15160:
15159:
15136:
15132:
15118:
15115:
15114:
15092:
15089:
15088:
15087:of even height
15086:
15079:
15075:
15066:
15062:
15053:
15046:
15037:
15033:
15023:
15016:
15007:
15006:
15002:
14997:
14993:
14986:10.1137/0606031
14969:
14960:
14956:
14947:
14946:
14942:
14910:
14904:
14900:
14890:
14888:
14881:
14877:
14876:
14872:
14862:
14860:
14852:
14848:
14847:
14840:
14833:
14829:
14820:
14819:
14815:
14805:
14803:
14797:"IBM Developer"
14795:
14794:
14790:
14783:
14758:
14754:
14749:
14745:
14738:
14714:Stein, Clifford
14699:
14692:
14685:
14666:10.1.1.148.2305
14650:
14637:
14626:
14619:
14600:
14591:
14583:
14574:
14570:
14560:
14558:
14545:
14541:
14534:
14509:
14505:
14460:
14456:
14442:
14423:10.1.1.118.6192
14406:
14402:
14393:
14391:
14383:
14382:
14378:
14358:
14354:
14345:
14343:
14330:
14329:
14325:
14299:
14292:
14285:
14271:
14267:
14236:
14232:
14217:
14213:
14202:
14198:
14191:
14171:Stein, Clifford
14156:
14149:
14145:
14056:
14030:
14022:
14011:
14003:
13992:
13989:
13988:
13987:
13969:
13961:
13950:
13942:
13925:
13922:
13921:
13894:
13886:
13869:
13866:
13865:
13840:
13832:
13821:
13818:
13817:
13792:
13784:
13773:
13765:
13754:
13751:
13750:
13742:
13716:
13708:
13691:
13688:
13687:
13686:
13668:
13660:
13640:
13632:
13615:
13612:
13611:
13592:
13584:
13582:
13579:
13578:
13554:
13546:
13529:
13526:
13525:
13500:
13492:
13475:
13472:
13471:
13446:
13438:
13421:
13418:
13417:
13393:
13385:
13383:
13380:
13379:
13363:
13355:
13353:
13350:
13349:
13333:
13330:
13329:
13326:
13319:
13316:
13307:
13304:
13295:
13292:
13283:
13280:
13271:
13268:
13259:
13256:
13247:
13244:
13235:
13232:
13223:
13220:
13207:
13188:
13180:
13163:
13160:
13159:
13140:
13132:
13121:
13118:
13117:
13101:
13098:
13097:
13074:
13071:
13070:
13054:
13051:
13050:
13031:
13028:
13027:
13025:
13022:
13003:
13000:
12999:
12983:
12980:
12979:
12945:
12944:
12933:
12932:
12928:
12926:
12923:
12922:
12894:
12893:
12882:
12881:
12877:
12875:
12872:
12871:
12855:
12852:
12851:
12826:
12825:
12818:
12814:
12812:
12809:
12808:
12783:
12782:
12775:
12771:
12769:
12766:
12765:
12740:
12739:
12732:
12728:
12726:
12723:
12722:
12697:
12696:
12689:
12685:
12683:
12680:
12679:
12660:
12658:
12655:
12654:
12638:
12635:
12634:
12609:
12608:
12601:
12597:
12595:
12592:
12591:
12566:
12565:
12558:
12554:
12552:
12549:
12548:
12529:
12526:
12525:
12509:
12506:
12505:
12477:
12476:
12469:
12465:
12463:
12460:
12459:
12443:
12440:
12439:
12423:
12420:
12419:
12403:
12400:
12399:
12380:
12377:
12376:
12360:
12357:
12356:
12340:
12337:
12336:
12317:
12314:
12313:
12312:First the bulk
12301:
12275:
12267:
12256:
12248:
12240:
12232:
12212:
12209:
12208:
12181:
12173:
12156:
12153:
12152:
12127:
12119:
12108:
12105:
12104:
12079:
12071:
12054:
12051:
12050:
12016:
12013:
12012:
12009:#splits, #joins
12004:
11978:
11970:
11953:
11945:
11944:
11942:
11934:
11926:
11919:
11915:
11907:
11904:
11903:
11877:
11869:
11852:
11844:
11843:
11841:
11833:
11825:
11809:
11805:
11797:
11794:
11793:
11774:
11771:
11770:
11746:
11738:
11721:
11718:
11717:
11685:
11677:
11676:
11674:
11670:
11662:
11659:
11658:
11633:
11625:
11608:
11605:
11604:
11564:
11561:
11560:
11536:
11533:
11532:
11529:
11524:
11522:
11518:
11514:
11510:
11506:
11502:
11487:k = 1:
11483:(T, I, k):
11464:
11461:
11452:
11449:
11440:
11437:
11428:
11425:
11400:
11397:
11396:
11373:
11370:
11369:
11353:
11350:
11349:
11332:
11328:
11326:
11323:
11322:
11305:
11301:
11299:
11296:
11295:
11265:
11261:
11253:
11241:
11237:
11229:
11227:
11224:
11223:
11196:
11192:
11184:
11172:
11168:
11160:
11158:
11155:
11154:
11120:
11114:
11109:
11108:
11100:
11097:
11096:
11076:
11072:
11057:
11053:
11048:
11045:
11044:
11028:
11025:
11024:
11008:
11005:
11004:
10981:
10977:
10962:
10958:
10953:
10950:
10949:
10932:
10927:
10926:
10918:
10915:
10914:
10898:
10895:
10894:
10875:
10872:
10871:
10870:First the bulk
10851:
10848:
10847:
10831:
10828:
10827:
10824:
10803:
10800:
10799:
10783:
10780:
10779:
10760:
10726:
10723:
10722:
10721:of items where
10706:
10703:
10702:
10665:
10662:
10661:
10658:
10627:
10624:
10623:
10583:
10580:
10579:
10544:
10541:
10540:
10524:
10521:
10520:
10483:
10482:
10478:
10468:
10464:
10459:
10456:
10455:
10426:non-destructive
10418:
10416:
10412:
10408:
10396:
10392:
10388:
10380:
10376:
10372:
10364:
10360:
10356:
10352:
10348:
10340:
10333:
10325:
10317:
10313:
10295:
10291:
10287:
10283:
10280:
10274:
10271:
10265:
10262:
10225:
10223:
10219:
10211:
10207:
10199:
10195:
10187:
10183:
10167:
10163:
10159:
10155:
10147:
10143:
10135:
10131:
10121:
10111:
10103:
10099:
10095:
10091:
10087:
10084:) T'=Node(T
10083:
10079:
10071:
10067:
10063:
10055:
10051:
9997:
9994:
9993:
9985:
9968:
9964:
9960:
9956:
9952:
9940:
9934:
9930:
9926:
9923:
9917:
9913:
9910:
9904:
9897:
9891:
9888:
9882:
9875:
9871:
9868:
9862:
9859:
9853:
9850:
9844:
9840:
9837:
9831:
9818:
9815:
9809:
9806:
9800:
9796:
9793:
9787:
9783:
9780:
9774:
9771:
9760:
9754:
9750:
9747:
9741:
9738:
9732:
9727:: The function
9690:
9687:
9643:
9640:
9639:
9623:
9620:
9619:
9595:
9592:
9591:
9557:
9556:
9531:
9527:
9515:
9514:
9512:
9509:
9508:
9479:
9464:
9460:
9424:
9420:
9415:
9412:
9411:
9388:
9385:
9384:
9348:
9344:
9342:
9339:
9338:
9315:
9312:
9311:
9280:
9276:
9272:
9247:
9231:
9227:
9218:
9217:
9207:
9200:
9196:
9184:
9183:
9164:
9148:
9144:
9129:
9125:
9123:
9120:
9119:
9100:
9097:
9096:
9075:
9071:
9067:
9059:
9056:
9055:
9038:
9034:
9020:
9017:
9016:
9015:The inequality
8997:
8994:
8993:
8978:
8976:
8955:
8952:
8951:
8927:
8923:
8921:
8918:
8917:
8898:
8890:
8887:
8886:
8858:
8854:
8836:
8832:
8826:
8808:
8805:
8804:
8779:
8775:
8773:
8770:
8769:
8729:
8710:
8706:
8690:
8683:
8679:
8677:
8674:
8673:
8656:
8653:
8652:
8621:
8602:
8598:
8596:
8593:
8592:
8575:
8572:
8571:
8537:
8518:
8514:
8498:
8491:
8487:
8482:
8479:
8478:
8461:
8458:
8457:
8439:
8435:
8433:
8430:
8429:
8365:
8346:
8342:
8337:
8334:
8333:
8316:
8313:
8312:
8289:
8286:
8285:
8268:
8265:
8264:
8237:
8233:
8228:
8225:
8224:
8207:
8204:
8203:
8185:
8181:
8179:
8176:
8175:
8131:
8112:
8108:
8089:
8085:
8083:
8080:
8079:
8063:
8060:
8059:
8024:
8000:
7997:
7996:
7973:
7969:
7967:
7964:
7963:
7935:
7932:
7931:
7930:
7926:
7919:
7897:
7894:
7893:
7891:
7845:
7841:
7830:
7826:
7800:
7793:
7789:
7771:
7752:
7748:
7739:
7735:
7733:
7730:
7729:
7704:
7701:
7700:
7664:
7647:
7644:
7643:
7627:
7624:
7623:
7601:
7593:
7590:
7589:
7587:
7559:
7556:
7555:
7531:
7528:
7527:
7488:
7485:
7481:
7473:
7470:
7469:
7449:
7446:
7445:
7403:
7402:
7398:
7376:
7372:
7364:
7361:
7360:
7342:
7341:
7336:
7333:
7332:
7297:
7290:
7286:
7270:
7251:
7247:
7242:
7239:
7238:
7220:
7216:
7214:
7211:
7210:
7187:
7184:
7183:
7167:
7159:
7156:
7155:
7149:
7143:
7132:
7130:Proof of bounds
7120:
7119:
7116:
7113:
7110:
7107:
7104:
7101:
7098:
7095:
7092:
7089:
7086:
7083:
7080:
7077:
7074:
7071:
7068:
7065:
7062:
7059:
7056:
7053:
7050:
7047:
7044:
7041:
7038:
7035:
7032:
7029:
7026:
7023:
7020:
7017:
7014:
7011:
7008:
6921:
6920:
6905:
6904:
6903:
6902:
6898:
6897:
6896:
6891:
6883:
6882:
6874:
6873:
6871:first iteration
6868:
6857:
6852:
6851:
6848:
6845:
6842:
6839:
6836:
6833:
6830:
6827:
6824:
6821:
6818:
6815:
6812:
6809:
6806:
6803:
6800:
6797:
6794:
6791:
6788:
6785:
6782:
6779:
6776:
6773:
6770:
6767:
6764:
6761:
6758:
6755:
6752:
6749:
6731:nor its parent
6694:
6693:
6680:’s close child
6670:
6669:
6668:
6667:
6663:
6662:
6661:
6656:
6648:
6647:
6639:
6638:
6636:first iteration
6633:
6622:
6617:
6616:
6613:
6610:
6607:
6604:
6601:
6598:
6595:
6592:
6589:
6586:
6583:
6580:
6577:
6574:
6571:
6568:
6565:
6562:
6528:
6527:
6526:
6525:
6521:
6520:
6519:
6514:
6506:
6505:
6497:
6496:
6494:first iteration
6491:
6480:
6475:
6474:
6471:
6468:
6465:
6462:
6459:
6456:
6453:
6450:
6447:
6444:
6441:
6438:
6435:
6432:
6429:
6426:
6423:
6420:
6417:
6414:
6411:
6408:
6405:
6402:
6399:
6396:
6393:
6390:
6387:
6384:
6381:
6378:
6375:
6372:
6369:
6366:
6363:
6360:
6357:
6354:
6351:
6348:
6345:
6342:
6339:
6336:
6333:
6330:
6327:
6324:
6321:
6318:
6315:
6312:
6309:
6306:
6303:
6300:
6297:
6294:
6291:
6288:
6285:
6282:
6279:
6276:
6273:
6270:
6267:
6264:
6261:
6258:
6255:
6252:
6249:
6246:
6243:
6240:
6195:
6194:
6175:
6174:
6173:
6172:
6168:
6167:
6166:
6161:
6153:
6152:
6144:
6143:
6141:first iteration
6138:
6127:
6122:
6121:
6118:
6115:
6112:
6109:
6106:
6103:
6100:
6097:
6094:
6091:
6088:
6085:
6082:
6079:
6076:
6073:
6070:
6067:
6064:
6061:
6058:
6055:
6052:
6049:
6046:
6043:
6040:
6037:
5980:
5979:
5978:
5977:
5973:
5972:
5971:
5966:
5958:
5957:
5949:
5948:
5946:first iteration
5943:
5934:
5933:
5922:
5917:
5916:
5913:
5910:
5907:
5904:
5894:
5800:
5797:
5796:
5780:
5777:
5776:
5743:
5740:
5739:
5731:
5612:
5528:
4967:
4958:
4940:
4920:black-violation
4887:
4886:
4883:
4880:
4877:
4874:
4871:
4868:
4865:
4862:
4859:
4856:
4853:
4850:
4847:
4844:
4841:
4838:
4835:
4832:
4829:
4826:
4823:
4820:
4817:
4814:
4811:
4808:
4805:
4802:
4799:
4796:
4793:
4790:
4787:
4784:
4781:
4778:
4775:
4772:
4769:
4766:
4763:
4760:
4757:
4754:
4751:
4748:
4745:
4742:
4739:
4736:
4733:
4730:
4727:
4724:
4721:
4718:
4715:
4712:
4709:
4706:
4703:
4700:
4697:
4694:
4691:
4688:
4685:
4682:
4679:
4676:
4673:
4670:
4667:
4664:
4661:
4658:
4655:
4652:
4649:
4646:
4643:
4640:
4637:
4634:
4631:
4628:
4625:
4622:
4619:
4616:
4613:
4610:
4607:
4604:
4601:
4598:
4595:
4592:
4589:
4586:
4583:
4580:
4577:
4574:
4571:
4568:
4565:
4562:
4559:
4556:
4553:
4550:
4547:
4544:
4541:
4538:
4535:
4532:
4529:
4526:
4523:
4520:
4517:
4514:
4511:
4508:
4505:
4502:
4499:
4496:
4493:
4490:
4487:
4484:
4481:
4478:
4475:
4472:
4469:
4466:
4463:
4460:
4457:
4454:
4451:
4448:
4445:
4442:
4439:
4436:
4433:
4430:
4427:
4424:
4421:
4418:
4415:
4412:
4409:
4395:
4383:has no children
4372:has no children
4365:has no children
4351:
4337:
4332:
4320:
4319:
4316:
4313:
4310:
4307:
4304:
4301:
4298:
4295:
4292:
4289:
4286:
4283:
4280:
4277:
4274:
4271:
4268:
4265:
4262:
4259:
4256:
4253:
4250:
4247:
4244:
4241:
4238:
4235:
4232:
4167:
4166:
4155:
4154:
4153:
4152:
4148:
4147:
4146:
4141:
4133:
4132:
4124:
4123:
4121:first iteration
4118:
4107:
4102:
4101:
4098:
4095:
4092:
4089:
4086:
4083:
4080:
4077:
4074:
4071:
4068:
4065:
4062:
4059:
4056:
4053:
4050:
4047:
4044:
4041:
4038:
4035:
4032:
4029:
4026:
4023:
4020:
4017:
4014:
4011:
4008:
4005:
4002:
3999:
3963:and its parent
3950:
3949:
3914:
3913:
3912:
3911:
3907:
3906:
3905:
3900:
3892:
3891:
3883:
3882:
3880:first iteration
3877:
3866:
3861:
3860:
3857:
3854:
3851:
3848:
3845:
3842:
3839:
3836:
3833:
3830:
3827:
3824:
3806:
3801:
3800:
3797:
3794:
3791:
3788:
3785:
3756:
3753:
3752:
3724:
3721:
3719:
3716:
3715:
3709:
3704:
3703:
3700:
3697:
3694:
3691:
3688:
3685:
3682:
3679:
3676:
3673:
3670:
3667:
3664:
3661:
3658:
3655:
3652:
3649:
3646:
3643:
3640:
3637:
3634:
3631:
3628:
3625:
3622:
3619:
3616:
3613:
3610:
3607:
3604:
3601:
3598:
3595:
3592:
3589:
3586:
3548:
3547:
3546:
3545:
3541:
3540:
3539:
3534:
3526:
3525:
3517:
3516:
3514:first iteration
3511:
3500:
3495:
3494:
3491:
3488:
3485:
3482:
3479:
3476:
3473:
3470:
3467:
3464:
3461:
3458:
3455:
3452:
3449:
3446:
3443:
3440:
3437:
3434:
3431:
3428:
3425:
3422:
3419:
3416:
3413:
3410:
3407:
3404:
3401:
3398:
3395:
3392:
3389:
3386:
3383:
3380:
3377:
3374:
3371:
3368:
3365:
3362:
3359:
3356:
3353:
3350:
3347:
3344:
3341:
3338:
3335:
3332:
3329:
3326:
3323:
3320:
3317:
3314:
3311:
3308:
3290:
3220:
3217:
3216:
3193:
3191:
3188:
3187:
3154:
3151:
3150:
3024:
2984:
2582:
2573:
2555:
2533:is also red (a
2485:
2484:
2481:
2478:
2475:
2472:
2469:
2466:
2463:
2460:
2457:
2454:
2451:
2448:
2445:
2442:
2439:
2436:
2433:
2430:
2427:
2424:
2421:
2418:
2415:
2412:
2409:
2406:
2403:
2400:
2397:
2394:
2391:
2388:
2385:
2382:
2379:
2376:
2373:
2370:
2367:
2364:
2361:
2358:
2355:
2352:
2349:
2346:
2343:
2340:
2337:
2334:
2331:
2328:
2325:
2322:
2319:
2316:
2313:
2310:
2307:
2304:
2301:
2298:
2295:
2292:
2289:
2286:
2283:
2280:
2277:
2274:
2271:
2268:
2265:
2262:
2259:
2256:
2253:
2250:
2247:
2244:
2241:
2238:
2235:
2232:
2229:
2226:
2223:
2220:
2217:
2214:
2197:
2196:
2192:
2188:
2172:
2162:
2151:
2149:
2141:
2137:
2122:
2105:
2081:
2064:
2037:
2018:
2016:
2010:
2008:
1976:
1969:
1968:
1965:
1962:
1959:
1956:
1953:
1950:
1947:
1944:
1941:
1938:
1935:
1932:
1929:
1926:
1923:
1920:
1917:
1914:
1911:
1908:
1905:
1902:
1899:
1896:
1893:
1890:
1887:
1884:
1881:
1878:
1875:
1872:
1869:
1866:
1863:
1860:
1857:
1854:
1851:
1848:
1845:
1842:
1839:
1836:
1833:
1830:
1827:
1824:
1821:
1818:
1815:
1812:
1809:
1806:
1803:
1800:
1797:
1794:
1791:
1788:
1785:
1782:
1779:
1776:
1773:
1770:
1767:
1764:
1761:
1758:
1755:
1752:
1749:
1746:
1743:
1740:
1737:
1734:
1731:
1728:
1725:
1722:
1719:
1716:
1713:
1710:
1707:
1704:
1701:
1698:
1695:
1692:
1689:
1686:
1683:
1680:
1677:
1674:
1671:
1668:
1665:
1662:
1659:
1656:
1653:
1650:
1647:
1644:
1641:
1638:
1635:
1632:
1629:
1626:
1623:
1620:
1617:
1614:
1611:
1608:
1605:
1602:
1599:
1596:
1593:
1590:
1584:
1577:
1576:
1573:
1570:
1567:
1564:
1561:
1558:
1555:
1552:
1549:
1546:
1543:
1540:
1537:
1534:
1531:
1529:#define RIGHT 1
1528:
1526:#define LEFT 0
1525:
1522:
1519:
1516:
1513:
1510:
1507:
1504:
1501:
1498:
1495:
1492:
1489:
1486:
1483:
1480:
1477:
1474:
1471:
1468:
1465:
1462:
1459:
1456:
1453:
1450:
1447:
1444:
1441:
1438:
1435:
1432:
1429:
1426:
1423:
1420:
1374:
1371:
1370:
1351:
1348:
1347:
1312:
1309:
1308:
1293:
1272:
1269:
1268:
1237:
1234:
1233:
1208:
1205:
1204:
1121:
1118:
1117:
1062:
1059:
1058:
1031:
993:
957:
954:
953:
935:Proof of bounds
891:
888:
887:
886:
870:
867:
866:
846:
843:
842:
839:height-balanced
828:black-violation
766:red–black tree:
765:
758:
734:
714:
707:
700:
693:
669:
665:
661:
654:
652:
626:
625:
624:
623:
622:
619:
610:
609:
608:
605:
596:
595:
589:
520:
472:
469:
468:
452:
449:
448:
417:
414:
413:
350:
347:
346:
314:
311:
310:
271:
268:
267:
235:
232:
231:
192:
189:
188:
156:
153:
152:
120:Time complexity
89:
86:
85:
17:
12:
11:
5:
16627:
16617:
16616:
16611:
16606:
16601:
16584:
16583:
16581:
16580:
16574:
16571:
16570:
16568:
16567:
16562:
16557:
16551:
16549:
16543:
16542:
16540:
16539:
16538:
16537:
16527:
16526:
16525:
16523:Hilbert R-tree
16520:
16515:
16505:
16504:
16503:
16501:Fibonacci heap
16498:
16493:
16483:
16482:
16481:
16476:
16471:
16469:Red–black tree
16466:
16461:
16451:
16445:
16443:
16437:
16436:
16434:
16433:
16428:
16423:
16418:
16413:
16407:
16405:
16399:
16398:
16396:
16395:
16390:
16385:
16380:
16375:
16370:
16364:
16362:
16356:
16355:
16353:
16352:
16351:
16350:
16345:
16335:
16334:
16333:
16326:Priority queue
16323:
16322:
16321:
16311:
16306:
16301:
16300:
16299:
16294:
16283:
16281:
16275:
16274:
16272:
16271:
16266:
16260:
16258:
16254:
16253:
16246:
16245:
16238:
16231:
16223:
16214:
16213:
16211:
16210:
16205:
16200:
16195:
16190:
16185:
16180:
16175:
16170:
16165:
16160:
16155:
16150:
16145:
16140:
16135:
16130:
16124:
16122:
16118:
16117:
16115:
16114:
16109:
16104:
16099:
16094:
16089:
16084:
16079:
16074:
16069:
16064:
16059:
16054:
16049:
16032:
16027:
16022:
16017:
16012:
16006:
16004:
15997:
15996:
15994:
15993:
15988:
15983:
15981:Ternary search
15978:
15973:
15968:
15963:
15958:
15952:
15950:
15944:
15943:
15941:
15940:
15935:
15930:
15925:
15920:
15915:
15910:
15905:
15897:
15892:
15887:
15881:
15879:
15873:
15872:
15870:
15869:
15864:
15859:
15854:
15849:
15844:
15839:
15829:
15824:
15819:
15814:
15809:
15804:
15794:
15789:
15784:
15779:
15774:
15769:
15764:
15759:
15754:
15748:
15746:
15730:
15729:
15722:
15721:
15714:
15707:
15699:
15693:
15692:
15687:
15681:
15676:
15664:
15655:
15650:
15637:
15636:External links
15634:
15633:
15632:
15616:
15610:
15603:
15600:
15598:
15597:
15582:
15562:
15555:
15519:
15504:
15478:
15463:
15460:
15457:
15454:
15451:
15447:
15443:
15423:
15420:
15417:
15414:
15411:
15408:
15405:
15402:
15382:
15362:
15359:
15356:
15353:
15344:items runs in
15333:
15292:
15277:
15224:
15204:
15201:
15198:
15195:
15192:
15189:
15186:
15181:
15177:
15173:
15170:
15167:
15147:
15144:
15139:
15135:
15131:
15128:
15125:
15122:
15102:
15099:
15096:
15081:
15073:
15060:
15044:
15031:
15014:
15000:
14991:
14980:(2): 306–318.
14965:(April 1985).
14954:
14940:
14898:
14870:
14838:
14827:
14813:
14788:
14781:
14752:
14743:
14736:
14710:Rivest, Ronald
14702:Cormen, Thomas
14690:
14683:
14644:Sanders, Peter
14640:Mehlhorn, Kurt
14624:
14617:
14589:
14568:
14539:
14532:
14524:Addison-Wesley
14503:
14474:(4): 471–477.
14454:
14448:on 2018-12-08.
14440:
14400:
14376:
14366:Red–Black BSTs
14352:
14323:
14290:
14284:978-0534376680
14283:
14265:
14246:(4): 290–306.
14230:
14211:
14204:Paton, James.
14196:
14189:
14146:
14144:
14141:
14140:
14139:
14134:
14129:
14124:
14122:Scapegoat tree
14119:
14093:
14088:
14083:
14077:
14072:
14067:
14062:
14055:
14052:
14049:
14048:
14037:
14033:
14029:
14025:
14021:
14018:
14014:
14010:
14006:
14002:
13999:
13996:
13976:
13972:
13968:
13964:
13960:
13957:
13953:
13949:
13945:
13941:
13938:
13935:
13932:
13929:
13919:
13913:
13912:
13901:
13897:
13893:
13889:
13885:
13882:
13879:
13876:
13873:
13863:
13859:
13858:
13847:
13843:
13839:
13835:
13831:
13828:
13825:
13815:
13811:
13810:
13799:
13795:
13791:
13787:
13783:
13780:
13776:
13772:
13768:
13764:
13761:
13758:
13748:
13741:
13738:
13735:
13734:
13723:
13719:
13715:
13711:
13707:
13704:
13701:
13698:
13695:
13675:
13671:
13667:
13663:
13659:
13656:
13653:
13650:
13647:
13643:
13639:
13635:
13631:
13628:
13625:
13622:
13619:
13609:
13595:
13591:
13587:
13573:
13572:
13561:
13557:
13553:
13549:
13545:
13542:
13539:
13536:
13533:
13523:
13519:
13518:
13507:
13503:
13499:
13495:
13491:
13488:
13485:
13482:
13479:
13469:
13465:
13464:
13453:
13449:
13445:
13441:
13437:
13434:
13431:
13428:
13425:
13415:
13396:
13392:
13388:
13366:
13362:
13358:
13337:
13325:
13324:Execution time
13322:
13321:
13320:
13317:
13310:
13308:
13305:
13298:
13296:
13293:
13286:
13284:
13281:
13274:
13272:
13269:
13262:
13260:
13257:
13250:
13248:
13245:
13238:
13236:
13233:
13226:
13224:
13221:
13214:
13211:
13210:
13195:
13191:
13187:
13183:
13179:
13176:
13173:
13170:
13167:
13147:
13143:
13139:
13135:
13131:
13128:
13125:
13105:
13081:
13078:
13058:
13047:
13035:
13010:
13007:
12987:
12976:
12960:
12957:
12954:
12951:
12948:
12943:
12939:
12936:
12931:
12906:
12903:
12900:
12897:
12892:
12888:
12885:
12880:
12859:
12835:
12832:
12829:
12824:
12821:
12817:
12792:
12789:
12786:
12781:
12778:
12774:
12764:is unique. If
12749:
12746:
12743:
12738:
12735:
12731:
12706:
12703:
12700:
12695:
12692:
12688:
12666:
12663:
12653:as a new node
12642:
12618:
12615:
12612:
12607:
12604:
12600:
12575:
12572:
12569:
12564:
12561:
12557:
12545:
12533:
12513:
12489:
12486:
12483:
12480:
12475:
12472:
12468:
12447:
12427:
12407:
12387:
12384:
12364:
12344:
12333:
12321:
12300:
12297:
12294:
12293:
12282:
12278:
12274:
12270:
12266:
12263:
12259:
12255:
12251:
12247:
12243:
12239:
12235:
12231:
12228:
12225:
12222:
12219:
12216:
12206:
12200:
12199:
12188:
12184:
12180:
12176:
12172:
12169:
12166:
12163:
12160:
12150:
12146:
12145:
12134:
12130:
12126:
12122:
12118:
12115:
12112:
12102:
12098:
12097:
12086:
12082:
12078:
12074:
12070:
12067:
12064:
12061:
12058:
12048:
12044:
12043:
12032:
12029:
12026:
12023:
12020:
12010:
12003:
12000:
11986:
11981:
11977:
11973:
11969:
11966:
11961:
11956:
11952:
11948:
11941:
11937:
11933:
11929:
11925:
11922:
11918:
11914:
11911:
11898:
11897:
11885:
11880:
11876:
11872:
11868:
11865:
11860:
11855:
11851:
11847:
11840:
11836:
11832:
11828:
11824:
11821:
11818:
11815:
11812:
11808:
11804:
11801:
11791:
11778:
11765:
11764:
11753:
11749:
11745:
11741:
11737:
11734:
11731:
11728:
11725:
11715:
11711:
11710:
11698:
11693:
11688:
11684:
11680:
11673:
11669:
11666:
11656:
11652:
11651:
11640:
11636:
11632:
11628:
11624:
11621:
11618:
11615:
11612:
11602:
11598:
11597:
11586:
11583:
11580:
11577:
11574:
11571:
11568:
11558:
11540:
11528:
11527:Execution time
11525:
11520:
11516:
11512:
11508:
11504:
11500:
11475:
11466:
11465:
11462:
11455:
11453:
11450:
11443:
11441:
11438:
11431:
11429:
11426:
11419:
11404:
11393:
11392:
11389:
11377:
11357:
11335:
11331:
11308:
11304:
11292:
11291:
11290:
11279:
11274:
11271:
11268:
11264:
11260:
11252:
11249:
11244:
11240:
11236:
11221:
11210:
11205:
11202:
11199:
11195:
11191:
11183:
11180:
11175:
11171:
11167:
11140:
11137:
11134:
11131:
11128:
11123:
11117:
11112:
11107:
11104:
11084:
11079:
11075:
11071:
11068:
11065:
11060:
11056:
11052:
11032:
11012:
11003:Next the tree
11001:
10989:
10984:
10980:
10976:
10973:
10970:
10965:
10961:
10957:
10935:
10930:
10925:
10922:
10902:
10891:
10879:
10855:
10835:
10823:
10820:
10807:
10787:
10759:
10756:
10736:
10733:
10730:
10710:
10690:
10687:
10684:
10681:
10678:
10675:
10672:
10669:
10657:
10654:
10637:
10634:
10631:
10611:
10608:
10605:
10602:
10599:
10596:
10593:
10590:
10587:
10577:parallel depth
10560:
10557:
10554:
10551:
10548:
10528:
10507:
10502:
10498:
10495:
10490:
10487:
10481:
10477:
10474:
10471:
10467:
10463:
10414:
10410:
10406:
10394:
10390:
10386:
10378:
10374:
10370:
10362:
10358:
10354:
10350:
10346:
10338:
10331:
10323:
10315:
10311:
10306:
10278:
10269:
10229:
10221:
10217:
10209:
10205:
10197:
10193:
10185:
10181:
10165:
10161:
10157:
10153:
10145:
10141:
10133:
10129:
10109:
10101:
10097:
10093:
10089:
10085:
10081:
10077:
10069:
10068:.blackHeight=T
10065:
10061:
10053:
10049:
10044:
10040:
10039:
10019:
10016:
10013:
10010:
10007:
10004:
10001:
9977:
9976:
9945:
9944:
9938:
9921:
9908:
9895:
9886:
9879:
9866:
9857:
9848:
9835:
9823:
9822:
9813:
9804:
9791:
9782:are less than
9778:
9769:
9758:
9745:
9736:
9702:set difference
9686:
9683:
9671:
9668:
9665:
9662:
9659:
9656:
9653:
9650:
9647:
9627:
9616:
9615:
9599:
9586:
9585:
9582:
9580:
9577:
9574:
9573:
9560:
9554:
9551:
9548:
9545:
9542:
9539:
9534:
9530:
9526:
9523:
9518:
9506:
9495:
9492:
9489:
9486:
9482:
9478:
9475:
9472:
9467:
9463:
9459:
9456:
9453:
9450:
9447:
9444:
9441:
9438:
9435:
9432:
9427:
9423:
9419:
9409:
9398:
9395:
9392:
9382:
9371:
9368:
9365:
9362:
9359:
9356:
9351:
9347:
9336:
9319:
9308:
9307:
9295:
9292:
9287:
9283:
9279:
9275:
9271:
9268:
9265:
9262:
9259:
9254:
9250:
9246:
9243:
9240:
9237:
9234:
9230:
9226:
9221:
9214:
9210:
9206:
9203:
9199:
9195:
9192:
9187:
9182:
9179:
9176:
9171:
9167:
9163:
9160:
9157:
9154:
9151:
9147:
9143:
9140:
9137:
9132:
9128:
9104:
9082:
9078:
9074:
9070:
9066:
9063:
9041:
9037:
9033:
9030:
9027:
9024:
9013:
9012:
9001:
8965:
8962:
8959:
8935:
8930:
8926:
8905:
8901:
8897:
8894:
8874:
8871:
8867:
8861:
8857:
8853:
8850:
8847:
8842:
8839:
8835:
8829:
8824:
8821:
8818:
8815:
8812:
8782:
8778:
8760:
8759:
8758: ■
8747:
8744:
8739:
8736:
8732:
8728:
8725:
8722:
8719:
8716:
8713:
8709:
8705:
8700:
8697:
8693:
8689:
8686:
8682:
8671:
8660:
8650:
8648:
8645:
8644:
8631:
8628:
8624:
8620:
8617:
8614:
8611:
8608:
8605:
8601:
8590:
8579:
8569:
8558:
8555:
8552:
8547:
8544:
8540:
8536:
8533:
8530:
8527:
8524:
8521:
8517:
8513:
8508:
8505:
8501:
8497:
8494:
8490:
8486:
8476:
8465:
8455:
8442:
8438:
8427:
8424:
8423:
8419:
8418:
8415:
8413:
8410:
8408:
8405:
8403:
8401:
8398:
8397:
8386:
8383:
8380:
8375:
8372:
8368:
8364:
8361:
8358:
8355:
8352:
8349:
8345:
8341:
8331:
8320:
8310:
8299:
8296:
8293:
8283:
8272:
8262:
8251:
8246:
8243:
8240:
8236:
8232:
8222:
8211:
8201:
8188:
8184:
8173:
8153:
8148:
8141:
8138:
8134:
8130:
8127:
8124:
8121:
8118:
8115:
8111:
8107:
8104:
8099:
8092:
8088:
8067:
8043:
8040:
8037:
8034:
8031:
8027:
8023:
8020:
8015:
8010:
8007:
8004:
7982:
7979:
7976:
7972:
7949:
7944:
7939:
7921:
7907:
7904:
7901:
7887:
7884:
7883:
7872:
7866:
7863:
7860:
7855:
7848:
7844:
7839:
7833:
7829:
7825:
7822:
7817:
7810:
7807:
7803:
7799:
7796:
7792:
7787:
7781:
7778:
7774:
7770:
7767:
7764:
7761:
7758:
7755:
7751:
7747:
7742:
7738:
7714:
7711:
7708:
7693:
7692:
7677:
7671:
7667:
7663:
7660:
7657:
7654:
7651:
7631:
7611:
7608:
7604:
7600:
7597:
7580:floor function
7567:
7563:
7552:
7551:
7548:
7547:
7535:
7524:
7522:
7511:
7508:
7501:
7497:
7494:
7491:
7484:
7480:
7477:
7466:
7465:
7453:
7442:
7439:
7428:
7425:
7420:
7417:
7411:
7408:
7401:
7397:
7394:
7391:
7384:
7381:
7375:
7371:
7368:
7358:
7345:
7340:
7330:
7327:
7326:
7315:
7312:
7307:
7304:
7300:
7296:
7293:
7289:
7285:
7280:
7277:
7273:
7269:
7266:
7263:
7260:
7257:
7254:
7250:
7246:
7236:
7223:
7219:
7191:
7170:
7166:
7163:
7139:
7131:
7128:
7007:
6901:Delete case D6
6900:
6899:
6892:
6885:
6884:
6876:
6875:
6869:
6862:
6861:
6860:
6859:
6858:
6856:
6855:Delete case D6
6853:
6748:
6711:’s parent and
6666:Delete case D5
6665:
6664:
6657:
6650:
6649:
6641:
6640:
6634:
6627:
6626:
6625:
6624:
6623:
6621:
6620:Delete case D5
6618:
6561:
6524:Delete case D4
6523:
6522:
6515:
6508:
6507:
6499:
6498:
6492:
6485:
6484:
6483:
6482:
6481:
6479:
6478:Delete case D4
6476:
6325:// != NIL
6239:
6171:Delete case D3
6170:
6169:
6162:
6155:
6154:
6146:
6145:
6139:
6132:
6131:
6130:
6129:
6128:
6126:
6125:Delete case D3
6123:
6036:
6031:loop invariant
5976:Delete case D2
5975:
5974:
5967:
5960:
5959:
5951:
5950:
5944:
5937:
5936:
5935:
5926:
5925:
5924:
5923:
5921:
5920:Delete case D2
5918:
5903:
5893:
5892:Delete case D1
5890:
5889:
5888:
5873:
5824:
5804:
5784:
5756:
5753:
5750:
5747:
5728:
5717:
5710:
5683:
5676:
5673:
5662:
5661:—if it exists.
5639:
5616:
5597:
5531:
5530:
5520:
5519:
5517:
5514:
5507:
5500:
5498:
5491:
5489:
5480:
5473:
5466:
5459:
5457:
5449:
5448:
5445:
5440:
5433:
5426:
5424:
5417:
5408:
5399:
5392:
5385:
5378:
5371:
5363:
5362:
5360:
5357:
5350:
5343:
5336:
5329:
5327:
5325:
5318:
5311:
5304:
5297:
5289:
5288:
5285:
5280:
5273:
5266:
5259:
5251:
5250:
5247:
5242:
5235:
5228:
5221:
5213:
5212:
5209:
5204:
5197:
5190:
5188:
5181:
5172:
5163:
5156:
5149:
5142:
5135:
5127:
5126:
5123:
5120:
5118:
5116:
5114:
5111:
5102:
5100:
5093:
5086:
5079:
5072:
5064:
5063:
5061:
5058:
5056:
5054:
5052:
5050:
5048:
5046:
5039:
5037:
5035:
5033:
5029:
5028:
5023:
5018:
5013:
5008:
5003:
4998:
4993:
4987:
4986:
4981:
4976:
4971:
4962:
4953:
4948:
4939:
4936:
4935:
4934:
4927:
4912:
4743:// S is black:
4408:
4394:
4391:
4336:
4333:
4331:
4328:
4231:
4204:is red, since
4188:the parent of
4151:Insert case I6
4150:
4149:
4142:
4135:
4134:
4126:
4125:
4119:
4112:
4111:
4110:
4109:
4108:
4106:
4105:Insert case I6
4103:
3998:
3910:Insert case I5
3909:
3908:
3901:
3894:
3893:
3885:
3884:
3878:
3871:
3870:
3869:
3868:
3867:
3865:
3864:Insert case I5
3862:
3823:
3805:
3804:Insert case I4
3802:
3784:
3766:
3760:
3737:
3733:
3730:
3727:
3712:Insert case I2
3708:
3707:Insert case I3
3705:
3585:
3580:loop invariant
3554:and the uncle
3544:Insert case I2
3543:
3542:
3535:
3528:
3527:
3519:
3518:
3512:
3505:
3504:
3503:
3502:
3501:
3499:
3498:Insert case I2
3496:
3307:
3302:loop invariant
3289:
3288:Insert case I1
3286:
3285:
3284:
3273:
3240:
3224:
3201:
3198:
3167:
3164:
3161:
3158:
3133:
3122:
3115:
3092:
3085:
3082:
3058:
3035:
3028:
3009:
2987:
2986:
2976:
2975:
2973:
2970:
2968:
2961:
2954:
2947:
2945:
2936:
2929:
2926:
2919:
2912:
2904:
2903:
2900:
2895:
2892:
2885:
2878:
2871:
2862:
2853:
2846:
2843:
2836:
2829:
2821:
2820:
2818:
2815:
2813:
2811:
2809:
2802:
2800:
2798:
2791:
2789:
2787:
2784:
2776:
2775:
2773:
2770:
2768:
2766:
2764:
2762:
2760:
2758:
2751:
2749:
2747:
2745:
2741:
2740:
2737:
2734:
2732:
2730:
2728:
2725:
2716:
2714:
2707:
2705:
2698:
2691:
2683:
2682:
2680:
2677:
2675:
2673:
2671:
2669:
2667:
2665:
2658:
2656:
2654:
2652:
2644:
2643:
2638:
2633:
2628:
2623:
2618:
2613:
2608:
2602:
2601:
2596:
2591:
2586:
2577:
2568:
2563:
2554:
2551:
2550:
2549:
2542:
2516:
2504:
2213:
2171:
2168:
2167:
2166:
2159:
2130:
2129:
2128:
2113:
2112:
2111:
2096:
2090:
2089:
2067:
2066:
2057:
2054:
2047:
2029:
2028:
2024:
2001:
1975:
1972:
1589:
1419:
1400:tree rotations
1387:
1384:
1381:
1378:
1355:
1344:Big O notation
1331:
1328:
1325:
1322:
1319:
1316:
1292:
1289:
1276:
1256:
1253:
1250:
1247:
1244:
1241:
1221:
1218:
1215:
1212:
1140:
1137:
1134:
1131:
1128:
1125:
1081:
1078:
1075:
1072:
1069:
1066:
1030:
1027:
992:
989:
976:
973:
970:
967:
964:
961:
916:
913:
910:
907:
904:
901:
898:
895:
874:
865:in the number
850:
801:
800:
785:
778:
775:
772:
757:
754:
732:constant value
712:
705:
698:
691:
620:
613:
612:
611:
606:
599:
598:
597:
593:
592:
591:
590:
588:
585:
519:
516:
491:
488:
485:
482:
479:
476:
456:
436:
433:
430:
427:
424:
421:
402:data structure
395:red–black tree
385:
384:
381:
380:
369:
366:
363:
360:
357:
354:
344:
333:
330:
327:
324:
321:
318:
308:
306:
302:
301:
290:
287:
284:
281:
278:
275:
265:
254:
251:
248:
245:
242:
239:
229:
227:
223:
222:
211:
208:
205:
202:
199:
196:
186:
175:
172:
169:
166:
163:
160:
150:
148:
144:
143:
136:
129:
127:
123:
122:
116:
115:
113:
102:
99:
96:
93:
83:
81:
77:
76:
66:
65:
63:big O notation
58:
57:
48:
44:
43:
40:
36:
35:
30:
24:
23:
22:Red–black tree
15:
9:
6:
4:
3:
2:
16626:
16615:
16612:
16610:
16607:
16605:
16602:
16600:
16597:
16596:
16594:
16579:
16576:
16575:
16572:
16566:
16563:
16561:
16558:
16556:
16553:
16552:
16550:
16548:
16544:
16536:
16533:
16532:
16531:
16528:
16524:
16521:
16519:
16516:
16514:
16511:
16510:
16509:
16506:
16502:
16499:
16497:
16496:Binomial heap
16494:
16492:
16489:
16488:
16487:
16484:
16480:
16477:
16475:
16472:
16470:
16467:
16465:
16462:
16460:
16457:
16456:
16455:
16452:
16450:
16447:
16446:
16444:
16442:
16438:
16432:
16429:
16427:
16424:
16422:
16419:
16417:
16414:
16412:
16409:
16408:
16406:
16404:
16400:
16394:
16393:Sparse matrix
16391:
16389:
16386:
16384:
16381:
16379:
16378:Dynamic array
16376:
16374:
16371:
16369:
16366:
16365:
16363:
16361:
16357:
16349:
16346:
16344:
16341:
16340:
16339:
16336:
16332:
16329:
16328:
16327:
16324:
16320:
16317:
16316:
16315:
16312:
16310:
16307:
16305:
16302:
16298:
16295:
16293:
16290:
16289:
16288:
16285:
16284:
16282:
16280:
16276:
16270:
16267:
16265:
16262:
16261:
16259:
16255:
16251:
16244:
16239:
16237:
16232:
16230:
16225:
16224:
16221:
16209:
16206:
16204:
16201:
16199:
16196:
16194:
16191:
16189:
16186:
16184:
16181:
16179:
16176:
16174:
16171:
16169:
16166:
16164:
16161:
16159:
16158:Hash calendar
16156:
16154:
16151:
16149:
16146:
16144:
16141:
16139:
16136:
16134:
16131:
16129:
16126:
16125:
16123:
16119:
16113:
16110:
16108:
16105:
16103:
16100:
16098:
16095:
16093:
16090:
16088:
16085:
16083:
16080:
16078:
16075:
16073:
16070:
16068:
16065:
16063:
16060:
16058:
16055:
16053:
16050:
16047:
16045:
16039:
16037:
16033:
16031:
16028:
16026:
16023:
16021:
16018:
16016:
16013:
16011:
16008:
16007:
16005:
16002:
15998:
15992:
15989:
15987:
15984:
15982:
15979:
15977:
15974:
15972:
15969:
15967:
15964:
15962:
15959:
15957:
15954:
15953:
15951:
15949:
15945:
15939:
15936:
15934:
15933:van Emde Boas
15931:
15929:
15926:
15924:
15923:Skew binomial
15921:
15919:
15916:
15914:
15911:
15909:
15906:
15904:
15902:
15898:
15896:
15893:
15891:
15888:
15886:
15883:
15882:
15880:
15878:
15874:
15868:
15865:
15863:
15860:
15858:
15855:
15853:
15850:
15848:
15845:
15843:
15840:
15838:
15834:
15830:
15828:
15825:
15823:
15820:
15818:
15815:
15813:
15810:
15808:
15805:
15803:
15802:Binary search
15799:
15795:
15793:
15790:
15788:
15785:
15783:
15780:
15778:
15775:
15773:
15770:
15768:
15765:
15763:
15760:
15758:
15755:
15753:
15750:
15749:
15747:
15744:
15740:
15735:
15731:
15727:
15720:
15715:
15713:
15708:
15706:
15701:
15700:
15697:
15691:
15688:
15686:
15682:
15680:
15677:
15674:
15670:
15665:
15663:
15659:
15656:
15654:
15651:
15648:
15644:
15640:
15639:
15629:
15622:
15617:
15614:
15611:
15609:
15606:
15605:
15593:
15589:
15585:
15579:
15575:
15574:
15566:
15558:
15552:
15548:
15544:
15539:
15534:
15530:
15523:
15515:
15511:
15507:
15505:9783030252090
15501:
15497:
15493:
15489:
15482:
15475:
15461:
15458:
15455:
15452:
15449:
15445:
15441:
15418:
15415:
15412:
15409:
15406:
15400:
15380:
15357:
15351:
15331:
15320:
15315:
15311:
15307:
15303:
15296:
15288:
15284:
15280:
15274:
15270:
15266:
15261:
15256:
15252:
15245:
15241:
15237:
15231:
15229:
15218:
15202:
15196:
15193:
15190:
15184:
15179:
15175:
15171:
15168:
15165:
15145:
15142:
15137:
15133:
15129:
15126:
15123:
15120:
15100:
15097:
15094:
15085:
15077:
15070:
15064:
15057:
15051:
15049:
15041:
15035:
15028:
15021:
15019:
15010:
15004:
14995:
14987:
14983:
14979:
14975:
14968:
14964:
14958:
14950:
14944:
14936:
14932:
14928:
14924:
14920:
14916:
14909:
14902:
14887:
14880:
14874:
14859:. 4 June 2020
14858:
14851:
14845:
14843:
14836:
14831:
14823:
14817:
14802:
14798:
14792:
14784:
14778:
14774:
14769:
14768:
14762:
14756:
14747:
14739:
14737:9780262046305
14733:
14729:
14725:
14721:
14720:
14715:
14711:
14707:
14703:
14697:
14695:
14686:
14680:
14676:
14672:
14667:
14662:
14658:
14657:
14649:
14645:
14641:
14635:
14633:
14631:
14629:
14620:
14614:
14610:
14609:
14604:
14598:
14596:
14594:
14582:
14578:
14572:
14557:
14553:
14549:
14543:
14535:
14529:
14525:
14520:
14519:
14513:
14507:
14499:
14495:
14491:
14487:
14482:
14477:
14473:
14469:
14465:
14458:
14452:
14447:
14443:
14437:
14433:
14429:
14424:
14419:
14415:
14411:
14404:
14390:
14386:
14380:
14373:
14368:
14367:
14362:
14356:
14342:on 2007-09-27
14341:
14337:
14333:
14327:
14319:
14315:
14311:
14307:
14303:
14297:
14295:
14286:
14280:
14276:
14269:
14261:
14257:
14253:
14249:
14245:
14241:
14234:
14226:
14222:
14215:
14207:
14200:
14192:
14186:
14182:
14178:
14177:
14172:
14168:
14164:
14160:
14154:
14152:
14147:
14138:
14135:
14133:
14130:
14128:
14125:
14123:
14120:
14117:
14113:
14109:
14105:
14101:
14097:
14094:
14092:
14089:
14087:
14084:
14081:
14078:
14076:
14073:
14071:
14070:Tree rotation
14068:
14066:
14063:
14061:
14058:
14057:
14027:
14019:
14016:
14008:
13997:
13994:
13966:
13958:
13955:
13947:
13939:
13936:
13930:
13927:
13920:
13918:
13917:W(bulkInsert)
13915:
13914:
13891:
13883:
13880:
13874:
13871:
13864:
13861:
13860:
13837:
13826:
13823:
13816:
13813:
13812:
13789:
13781:
13778:
13770:
13759:
13756:
13749:
13746:
13745:
13713:
13705:
13702:
13696:
13693:
13665:
13657:
13654:
13651:
13648:
13645:
13637:
13629:
13626:
13620:
13617:
13610:
13608:
13607:~ #processors
13589:
13575:
13574:
13551:
13543:
13540:
13534:
13531:
13524:
13521:
13520:
13497:
13489:
13486:
13480:
13477:
13470:
13467:
13466:
13443:
13435:
13432:
13426:
13423:
13416:
13413:
13412:
13409:
13390:
13360:
13335:
13314:
13309:
13302:
13297:
13290:
13285:
13278:
13273:
13266:
13261:
13254:
13249:
13242:
13237:
13230:
13225:
13218:
13213:
13212:
13185:
13177:
13174:
13168:
13165:
13137:
13126:
13123:
13103:
13095:
13079:
13076:
13056:
13048:
13033:
13008:
13005:
12985:
12977:
12941:
12937:
12934:
12929:
12890:
12886:
12883:
12878:
12857:
12822:
12819:
12815:
12779:
12776:
12772:
12736:
12733:
12729:
12693:
12690:
12686:
12664:
12661:
12640:
12605:
12602:
12598:
12562:
12559:
12555:
12546:
12531:
12511:
12473:
12470:
12466:
12445:
12425:
12405:
12385:
12382:
12362:
12342:
12334:
12319:
12311:
12310:
12309:
12306:
12272:
12264:
12261:
12253:
12245:
12237:
12229:
12226:
12223:
12217:
12214:
12207:
12205:
12204:W(bulkInsert)
12202:
12201:
12178:
12170:
12167:
12161:
12158:
12151:
12148:
12147:
12124:
12113:
12110:
12103:
12100:
12099:
12076:
12068:
12065:
12059:
12056:
12049:
12046:
12045:
12027:
12021:
12018:
12011:
12008:
12007:
11999:
11984:
11975:
11967:
11964:
11959:
11950:
11939:
11931:
11923:
11920:
11916:
11912:
11909:
11883:
11874:
11866:
11863:
11858:
11849:
11838:
11830:
11822:
11819:
11816:
11813:
11810:
11806:
11802:
11799:
11792:
11790:
11789:= #processors
11776:
11767:
11766:
11743:
11735:
11732:
11726:
11723:
11716:
11713:
11712:
11696:
11691:
11682:
11671:
11667:
11664:
11657:
11654:
11653:
11630:
11622:
11619:
11613:
11610:
11603:
11600:
11599:
11581:
11578:
11575:
11569:
11566:
11559:
11556:
11555:
11552:
11538:
11498:
11494:
11490:
11486:
11482:
11481:bulkInsertRec
11478:
11474:
11472:
11459:
11454:
11447:
11442:
11439:split I and T
11435:
11430:
11423:
11418:
11417:
11416:
11402:
11390:
11375:
11355:
11333:
11329:
11306:
11302:
11293:
11272:
11269:
11266:
11262:
11250:
11242:
11238:
11222:
11203:
11200:
11197:
11193:
11181:
11173:
11169:
11153:
11152:
11138:
11135:
11132:
11129:
11126:
11115:
11105:
11102:
11077:
11073:
11069:
11066:
11063:
11058:
11054:
11030:
11010:
11002:
10982:
10978:
10974:
10971:
10968:
10963:
10959:
10933:
10923:
10920:
10900:
10892:
10877:
10869:
10868:
10867:
10853:
10833:
10819:
10805:
10785:
10777:
10773:
10769:
10764:
10755:
10753:
10748:
10728:
10708:
10685:
10682:
10679:
10676:
10673:
10667:
10653:
10651:
10635:
10632:
10629:
10606:
10603:
10600:
10597:
10594:
10591:
10585:
10578:
10574:
10555:
10552:
10546:
10526:
10505:
10500:
10496:
10493:
10488:
10485:
10479:
10475:
10472:
10469:
10465:
10461:
10452:
10450:
10446:
10442:
10438:
10434:
10429:
10427:
10423:
10404:
10400:
10384:
10368:
10344:
10336:
10329:
10321:
10309:
10305:
10302:
10298:
10277:
10268:
10260:
10256:
10252:
10248:
10244:
10240:
10236:
10232:
10228:
10215:
10203:
10191:
10179:
10175:
10171:
10151:
10139:
10127:
10119:
10115:
10107:
10075:
10059:
10048:joinRightRB(T
10047:
10043:
10037:
10033:
10017:
10011:
10008:
10005:
9999:
9991:
9983:
9979:
9978:
9974:
9950:
9947:
9946:
9937:
9920:
9907:
9902:
9894:
9885:
9880:
9878:is set black.
9865:
9856:
9847:
9834:
9829:
9825:
9824:
9812:
9803:
9790:
9777:
9768:
9764:
9757:
9744:
9735:
9730:
9726:
9723:
9722:
9721:
9719:
9715:
9711:
9707:
9703:
9699:
9695:
9682:
9669:
9663:
9660:
9657:
9651:
9648:
9645:
9625:
9613:
9612:
9611:
9597:
9583:
9581:
9578:
9576:
9575:
9549:
9546:
9543:
9537:
9532:
9528:
9524:
9521:
9507:
9490:
9487:
9484:
9480:
9476:
9470:
9465:
9461:
9457:
9454:
9451:
9448:
9442:
9439:
9436:
9430:
9425:
9421:
9417:
9410:
9396:
9393:
9390:
9383:
9366:
9363:
9360:
9354:
9349:
9345:
9337:
9335:
9334:
9331:
9317:
9293:
9290:
9285:
9281:
9277:
9273:
9269:
9266:
9263:
9260:
9257:
9252:
9248:
9241:
9238:
9235:
9228:
9224:
9212:
9208:
9204:
9201:
9197:
9193:
9190:
9180:
9177:
9174:
9169:
9165:
9158:
9155:
9152:
9145:
9141:
9138:
9135:
9130:
9126:
9118:
9117:
9116:
9102:
9080:
9076:
9072:
9068:
9064:
9061:
9039:
9035:
9031:
9028:
9025:
9022:
8999:
8991:
8990:
8989:
8986:
8981:
8963:
8960:
8957:
8949:
8933:
8928:
8924:
8903:
8895:
8892:
8869:
8865:
8859:
8855:
8851:
8848:
8845:
8840:
8837:
8833:
8822:
8819:
8816:
8813:
8802:
8798:
8780:
8776:
8767:
8745:
8742:
8734:
8730:
8723:
8720:
8717:
8707:
8703:
8695:
8691:
8687:
8680:
8658:
8651:
8649:
8647:
8646:
8626:
8622:
8615:
8612:
8609:
8599:
8577:
8570:
8553:
8550:
8542:
8538:
8531:
8528:
8525:
8515:
8511:
8503:
8499:
8495:
8488:
8477:
8463:
8456:
8440:
8436:
8428:
8426:
8425:
8422:resulting in
8420:
8416:
8414:
8411:
8409:
8406:
8404:
8402:
8400:
8399:
8381:
8378:
8370:
8366:
8359:
8356:
8353:
8343:
8332:
8318:
8311:
8294:
8284:
8270:
8263:
8244:
8241:
8238:
8234:
8223:
8209:
8202:
8186:
8182:
8174:
8172:
8171:
8168:
8167:
8151:
8146:
8136:
8132:
8125:
8122:
8119:
8109:
8105:
8102:
8097:
8090:
8086:
8065:
8057:
8041:
8038:
8035:
8029:
8025:
8018:
8013:
8008:
7980:
7977:
7974:
7970:
7947:
7942:
7937:
7924:
7905:
7902:
7899:
7890:
7870:
7864:
7861:
7858:
7853:
7846:
7842:
7837:
7831:
7827:
7823:
7820:
7815:
7805:
7801:
7797:
7790:
7785:
7776:
7772:
7765:
7762:
7759:
7749:
7745:
7740:
7736:
7728:
7727:
7726:
7712:
7709:
7706:
7697:
7690:
7689:
7688:
7675:
7669:
7665:
7658:
7655:
7652:
7629:
7606:
7602:
7598:
7585:
7581:
7533:
7525:
7523:
7509:
7506:
7499:
7495:
7492:
7489:
7482:
7478:
7475:
7468:
7467:
7451:
7443:
7440:
7426:
7423:
7418:
7415:
7409:
7406:
7399:
7395:
7392:
7389:
7382:
7379:
7373:
7369:
7366:
7359:
7338:
7328:
7313:
7310:
7302:
7298:
7294:
7287:
7283:
7275:
7271:
7264:
7261:
7258:
7248:
7244:
7221:
7217:
7209:
7208:
7205:
7204:
7203:
7189:
7164:
7161:
7147:
7142:
7136:
7127:
7125:
7018:RotateDirRoot
7005:
7003:
7002:requirement 4
6999:
6995:
6991:
6987:
6983:
6979:
6975:
6971:
6970:requirement 3
6966:
6961:
6957:
6953:
6949:
6945:
6941:
6937:
6933:
6929:
6918:
6914:
6910:
6889:
6880:
6866:
6746:
6743:
6738:
6734:
6730:
6726:
6722:
6718:
6714:
6710:
6706:
6702:
6691:
6687:
6683:
6679:
6675:
6654:
6645:
6631:
6559:
6557:
6553:
6549:
6545:
6541:
6537:
6533:
6512:
6503:
6489:
6250:RotateDirRoot
6237:
6235:
6231:
6227:
6223:
6219:
6215:
6211:
6207:
6203:
6192:
6188:
6184:
6180:
6159:
6150:
6136:
6034:
6032:
6028:
6024:
6020:
6019:requirement 4
6016:
6012:
6008:
6004:
6000:
5996:
5992:
5988:
5984:
5964:
5955:
5941:
5932:
5901:
5899:
5886:
5882:
5878:
5874:
5871:
5867:
5863:
5859:
5855:
5854:
5849:
5848:
5843:
5842:
5837:
5836:
5831:
5830:
5825:
5822:
5818:
5802:
5782:
5774:
5770:
5754:
5751:
5748:
5737:
5729:
5726:
5722:
5718:
5715:
5711:
5708:
5704:
5700:
5696:
5692:
5688:
5684:
5681:
5677:
5674:
5671:
5667:
5663:
5660:
5656:
5651:
5645:
5640:
5637:
5636:
5631:
5626:
5621:
5617:
5610:
5606:
5602:
5598:
5595:
5591:
5587:
5583:
5579:
5575:
5571:
5567:
5563:
5559:
5555:
5551:
5547:
5543:
5539:
5535:
5534:
5526:
5521:
5518:
5515:
5512:
5508:
5505:
5501:
5499:
5496:
5492:
5490:
5488:
5484:
5481:
5479:
5478:
5474:
5471:
5467:
5464:
5460:
5458:
5455:
5451:
5450:
5446:
5444:
5441:
5438:
5434:
5431:
5427:
5425:
5422:
5418:
5416:
5412:
5409:
5407:
5403:
5400:
5398:
5397:
5393:
5390:
5386:
5383:
5379:
5376:
5372:
5369:
5365:
5364:
5361:
5358:
5355:
5351:
5348:
5344:
5341:
5337:
5334:
5330:
5328:
5326:
5324:
5323:
5319:
5316:
5312:
5309:
5305:
5302:
5298:
5295:
5291:
5290:
5286:
5284:
5281:
5278:
5274:
5271:
5267:
5264:
5260:
5257:
5253:
5252:
5248:
5246:
5243:
5240:
5236:
5233:
5229:
5226:
5222:
5219:
5215:
5214:
5210:
5208:
5205:
5202:
5198:
5195:
5191:
5189:
5186:
5182:
5180:
5176:
5171:
5167:
5162:
5161:
5154:
5147:
5140:
5133:
5128:
5124:
5121:
5119:
5117:
5115:
5112:
5110:
5106:
5103:
5101:
5099:
5098:
5094:
5091:
5087:
5084:
5080:
5077:
5073:
5070:
5066:
5065:
5062:
5059:
5057:
5055:
5053:
5051:
5049:
5047:
5045:
5044:
5040:
5038:
5036:
5034:
5031:
5030:
5027:
5024:
5022:
5019:
5017:
5014:
5012:
5009:
5007:
5004:
5002:
4999:
4997:
4994:
4992:
4989:
4988:
4985:
4980:
4975:
4970:
4966:
4961:
4957:
4952:
4947:
4943:
4932:
4931:requirement 3
4928:
4925:
4921:
4917:
4913:
4909:
4904:
4900:
4896:
4895:
4894:
4892:
4406:
4404:
4400:
4390:
4388:
4384:
4379:
4377:
4373:
4368:
4366:
4361:
4359:
4358:requirement 3
4355:
4349:
4344:
4342:
4327:
4325:
4236:RotateDirRoot
4229:
4227:
4223:
4219:
4218:Requirement 4
4215:
4211:
4207:
4206:requirement 3
4203:
4199:
4195:
4191:
4187:
4183:
4179:
4175:
4164:
4160:
4139:
4130:
4116:
3996:
3994:
3993:requirement 4
3990:
3986:
3982:
3978:
3974:
3970:
3966:
3962:
3958:
3947:
3943:
3939:
3935:
3931:
3927:
3923:
3919:
3898:
3889:
3875:
3821:
3819:
3815:
3811:
3782:
3780:
3764:
3758:
3735:
3731:
3728:
3725:
3713:
3583:
3581:
3577:
3573:
3569:
3565:
3564:requirement 4
3561:
3557:
3553:
3532:
3523:
3509:
3305:
3303:
3299:
3298:requirement 3
3296:is black, so
3295:
3282:
3278:
3274:
3271:
3270:
3265:
3264:
3259:
3258:
3253:
3252:
3247:
3246:
3241:
3238:
3222:
3199:
3196:
3185:
3181:
3165:
3162:
3159:
3148:
3147:
3142:
3138:
3134:
3131:
3127:
3123:
3120:
3116:
3113:
3109:
3105:
3101:
3097:
3093:
3090:
3086:
3083:
3080:
3076:
3075:
3070:
3066:
3063:
3059:
3056:
3052:
3048:
3044:
3040:
3036:
3033:
3029:
3022:
3018:
3014:
3010:
3007:
3003:
2999:
2995:
2991:
2990:
2982:
2977:
2974:
2971:
2969:
2966:
2962:
2959:
2955:
2952:
2948:
2946:
2944:
2940:
2937:
2935:
2934:
2930:
2927:
2924:
2920:
2917:
2913:
2910:
2906:
2905:
2901:
2899:
2896:
2893:
2890:
2886:
2883:
2879:
2876:
2872:
2870:
2866:
2863:
2861:
2857:
2854:
2852:
2851:
2847:
2844:
2841:
2837:
2834:
2830:
2827:
2823:
2822:
2819:
2816:
2814:
2812:
2810:
2807:
2803:
2801:
2799:
2797:
2796:
2792:
2790:
2788:
2785:
2782:
2778:
2777:
2774:
2771:
2769:
2767:
2765:
2763:
2761:
2759:
2757:
2756:
2752:
2750:
2748:
2746:
2743:
2742:
2738:
2735:
2733:
2731:
2729:
2726:
2724:
2720:
2717:
2715:
2713:
2712:
2708:
2706:
2703:
2699:
2696:
2692:
2689:
2685:
2684:
2681:
2678:
2676:
2674:
2672:
2670:
2668:
2666:
2664:
2663:
2659:
2657:
2655:
2653:
2650:
2646:
2645:
2642:
2639:
2637:
2634:
2632:
2629:
2627:
2624:
2622:
2619:
2617:
2614:
2612:
2609:
2607:
2604:
2603:
2600:
2595:
2590:
2585:
2581:
2576:
2572:
2567:
2562:
2558:
2547:
2546:requirement 4
2543:
2540:
2536:
2535:red-violation
2532:
2528:
2524:
2520:
2519:Requirement 3
2517:
2513:
2508:
2505:
2502:
2498:
2495:The variable
2494:
2493:
2492:
2490:
2211:
2209:
2208:red-violation
2205:
2185:
2181:
2177:
2160:
2157:
2156:requirement 2
2150:(The comment
2147:
2135:
2131:
2126:
2121:
2120:
2118:
2114:
2109:
2104:
2103:
2101:
2097:
2094:
2093:
2092:
2086:
2079:
2078:requirement 3
2074:
2069:
2068:
2062:
2058:
2055:
2052:
2048:
2045:
2041:
2035:
2031:
2030:
2025:
2006:
2003:The variable
2002:
1998:
1992:
1986:
1982:
1981:
1980:
1971:
1597:RotateDirRoot
1581:
1417:
1415:
1410:
1408:
1403:
1401:
1382:
1376:
1369:
1353:
1345:
1326:
1323:
1320:
1314:
1306:
1302:
1298:
1288:
1274:
1251:
1248:
1245:
1239:
1216:
1210:
1202:
1199:
1195:
1191:
1187:
1182:
1180:
1175:
1173:
1168:
1164:
1159:
1157:
1152:
1135:
1132:
1129:
1123:
1115:
1111:
1107:
1103:
1098:
1096:
1076:
1073:
1070:
1064:
1056:
1052:
1048:
1044:
1040:
1036:
1026:
1022:
1019:
1015:
1010:
1006:
997:
988:
987:search time.
971:
968:
965:
959:
951:
950:direct access
947:
943:
938:
936:
932:
911:
908:
905:
899:
896:
893:
872:
864:
848:
840:
836:
831:
829:
825:
824:red-violation
821:
817:
812:
810:
805:
798:
797:requirement 4
794:
790:
786:
783:
779:
776:
773:
770:
769:
768:
763:
753:
751:
750:requirement 4
747:
743:
738:
733:
727:
725:
721:
720:sentinel node
716:
711:
704:
697:
690:
686:
682:
677:
675:
650:
645:
643:
639:
635:
631:
617:
603:
584:
582:
578:
574:
569:
567:
566:Chris Okasaki
562:
559:
557:
552:
548:
543:
541:
537:
533:
529:
525:
515:
513:
509:
503:
486:
483:
480:
474:
454:
431:
428:
425:
419:
410:
406:
403:
400:
396:
392:
364:
361:
358:
352:
345:
328:
325:
322:
316:
309:
307:
303:
285:
282:
279:
273:
266:
249:
246:
243:
237:
230:
228:
224:
206:
203:
200:
194:
187:
170:
167:
164:
158:
151:
149:
145:
142:
141:
137:
135:
134:
130:
128:
124:
121:
117:
114:
97:
91:
84:
82:
78:
75:
71:
67:
64:
59:
56:
52:
49:
45:
41:
37:
34:
31:
29:
25:
20:
16604:Search trees
16599:Binary trees
16468:
16348:Disjoint-set
16043:
16035:
15900:
15836:
15833:Left-leaning
15739:dynamic sets
15734:Search trees
15662:Erik Demaine
15642:
15572:
15565:
15528:
15522:
15487:
15481:
15323:
15309:
15305:
15295:
15250:
15083:
15076:
15068:
15063:
15034:
15003:
14994:
14977:
14973:
14957:
14943:
14918:
14914:
14901:
14889:. Retrieved
14885:
14873:
14861:. Retrieved
14856:
14830:
14816:
14804:. Retrieved
14800:
14791:
14766:
14755:
14746:
14718:
14655:
14607:
14571:
14559:. Retrieved
14555:
14542:
14517:
14506:
14471:
14467:
14457:
14446:the original
14413:
14403:
14392:. Retrieved
14388:
14379:
14370:
14369:. Coursera.
14365:
14355:
14344:. Retrieved
14340:the original
14335:
14326:
14309:
14274:
14268:
14243:
14239:
14233:
14224:
14214:
14199:
14175:
13916:
13576:
13327:
13222:Initial tree
13093:
12302:
12203:
11901:
11768:
11530:
11496:
11492:
11488:
11484:
11480:
11476:
11467:
11427:initial tree
11394:
10825:
10798:into a tree
10765:
10761:
10749:
10659:
10453:
10444:
10440:
10436:
10432:
10430:
10421:
10419:
10402:
10398:
10397:.right)
10382:
10366:
10342:
10334:
10327:
10319:
10307:
10300:
10296:
10275:
10266:
10263:
10258:
10254:
10250:
10246:
10245:(k = T.key)
10242:
10238:
10234:
10230:
10226:
10220:,⟨k,black⟩,T
10213:
10201:
10189:
10177:
10173:
10169:
10149:
10137:
10128:joinLeftRB(T
10125:
10117:
10113:
10105:
10073:
10057:
10045:
10041:
10031:
9989:
9981:
9972:
9948:
9935:
9918:
9905:
9900:
9892:
9883:
9863:
9854:
9845:
9832:
9827:
9810:
9801:
9788:
9775:
9766:
9762:
9755:
9742:
9733:
9728:
9724:
9718:black height
9717:
9713:
9709:
9705:
9704:. Then fast
9698:intersection
9688:
9617:
9589:
9309:
9014:
8947:
8763:
7922:
7888:
7885:
7698:
7694:
7583:
7553:
7153:
7145:
7140:
7121:
6997:
6993:
6989:
6985:
6981:
6977:
6973:
6959:
6955:
6951:
6947:
6943:
6939:
6935:
6931:
6930:the sibling
6927:
6916:
6912:
6908:
6907:The sibling
6906:
6736:
6732:
6728:
6724:
6720:
6716:
6712:
6708:
6704:
6700:
6689:
6685:
6684:is red, and
6681:
6677:
6673:
6672:The sibling
6671:
6555:
6551:
6547:
6543:
6539:
6535:
6531:
6530:The sibling
6529:
6233:
6229:
6225:
6221:
6217:
6213:
6209:
6205:
6201:
6190:
6186:
6182:
6178:
6177:The sibling
6176:
6026:
6022:
6014:
6010:
6006:
6002:
5998:
5994:
5990:
5986:
5982:
5981:
5897:
5895:
5885:D3 + D5 + D6
5884:
5880:
5876:
5869:
5865:
5861:
5852:
5846:
5840:
5834:
5828:
5820:
5772:
5768:
5724:
5720:
5713:
5706:
5702:
5698:
5694:
5690:
5686:
5679:
5669:
5665:
5658:
5654:
5634:
5629:
5619:
5608:
5604:
5600:
5593:
5589:
5585:
5581:
5577:
5576:nephew) for
5573:
5569:
5565:
5561:
5560:nephew) for
5557:
5553:
5549:
5545:
5541:
5540:is used for
5537:
5524:
5486:
5482:
5476:
5442:
5414:
5410:
5405:
5401:
5395:
5321:
5282:
5244:
5206:
5178:
5174:
5169:
5165:
5159:
5108:
5104:
5096:
5042:
5025:
5020:
5015:
5010:
5005:
5000:
4995:
4990:
4983:
4978:
4973:
4968:
4964:
4959:
4955:
4950:
4945:
4923:
4915:
4902:
4898:
4888:
4402:
4398:
4396:
4386:
4382:
4380:
4375:
4371:
4369:
4364:
4362:
4354:conclusion 5
4348:only 1 child
4347:
4345:
4340:
4338:
4335:Simple cases
4321:
4225:
4221:
4213:
4209:
4201:
4197:
4193:
4189:
4185:
4181:
4180:in place of
4177:
4173:
4162:
4158:
4156:
3991:are red, so
3988:
3984:
3983:). But both
3980:
3976:
3972:
3968:
3964:
3960:
3956:
3945:
3941:
3937:
3933:
3929:
3925:
3921:
3917:
3915:
3817:
3813:
3809:
3807:
3778:
3710:
3575:
3571:
3567:
3559:
3555:
3551:
3549:
3293:
3291:
3280:
3276:
3268:
3262:
3256:
3250:
3244:
3183:
3179:
3145:
3129:
3125:
3118:
3111:
3107:
3103:
3099:
3095:
3088:
3078:
3073:
3068:
3064:
3062:column group
3054:
3050:
3046:
3042:
3038:
3031:
3020:
3016:
3012:
3005:
3001:
2997:
2996:is used for
2993:
2980:
2942:
2938:
2932:
2897:
2868:
2864:
2859:
2855:
2849:
2794:
2754:
2722:
2718:
2710:
2661:
2640:
2635:
2630:
2625:
2620:
2615:
2610:
2605:
2598:
2593:
2588:
2583:
2579:
2574:
2570:
2565:
2560:
2538:
2530:
2526:
2522:
2506:
2500:
2496:
2486:
2203:
2175:
2173:
2161:The related
2133:
2124:
2107:
2091:
2060:
2043:
2039:
2034:requirements
2004:
1977:
1970:
1411:
1404:
1367:
1304:
1300:
1294:
1183:
1176:
1160:
1153:
1099:
1051:Linux kernel
1032:
1023:
1007:, which are
1002:
939:
834:
832:
827:
823:
813:
806:
802:
792:
788:
759:
746:black height
745:
741:
739:
728:
722:(instead of
717:
709:
702:
695:
688:
684:
678:
672:" (see also
646:
627:
570:
563:
560:
544:
535:
524:Rudolf Bayer
521:
504:
447:time, where
411:
407:
394:
388:
139:
132:
16491:Binary heap
16416:Linked list
16133:Exponential
16121:Other trees
15647:ftp.gnu.org
15641:Ben Pfaff:
15027:this remark
14726:. pp.
12101:#insertions
10573:in parallel
10385:: T
10369:: T
7148:=1,2,3,4,5,
7144:of heights
6703:the nephew
6181:is red, so
5685:The column
5678:The column
5544:’s parent,
4184:and making
3916:The parent
3808:The parent
3094:The column
3087:The column
3037:The column
3000:’s parent,
2142:U->color
2117:conjunction
2100:disjunction
1301:rebalancing
1005:2–3–4 trees
863:logarithmic
742:black depth
674:this remark
587:Terminology
540:2–3–4 trees
47:Invented by
16593:Categories
16479:Splay tree
16383:Hash table
16264:Collection
16077:Priority R
15827:Palindrome
15592:0781.68009
15583:0201548569
15538:1510.05433
15434:time with
15373:time with
15260:1602.02120
15240:Sun, Yihan
14921:(1): 240.
14835:Pfaff 2004
14608:Algorithms
14518:Algorithms
14394:2015-09-02
14346:2015-09-02
14127:Splay tree
14104:2–3–4 tree
12305:pipelining
12299:Pipelining
11477:bulkInsert
10822:Join-based
10776:(a,b)-tree
10772:2–3–4 tree
10237:(T = nil)
10208:,⟨k,red⟩,T
10168:)
10100:.right,k,T
10080:,⟨k,red⟩,T
9852:. If both
9749:and a key
9614:Conclusion
8977:(sequence
6911:is black,
6676:is black,
6436:&&
6367:&&
5856:; section
5687:assignment
4812:&&
4761:&&
4341:2 children
4176:, putting
3936:(i.e., if
3096:assignment
1407:GNU libavl
1305:worst case
1291:Operations
1194:LinkedList
1179:tango tree
1156:2–3–4 tree
1154:For every
1095:WAVL trees
756:Properties
649:leaf nodes
632:, used in
556:Xerox PARC
140:Worst Case
16535:Hash tree
16421:Skip list
16368:Bit array
16269:Container
16163:iDistance
16042:implicit
16030:Hilbert R
16025:Cartesian
15908:Fibonacci
15842:Scapegoat
15837:Red–black
15514:201692657
15459:
15453:
15416:
15410:
15185:
15143:−
15130:⋅
15098:⋅
15056:Ben Pfaff
14724:MIT Press
14661:CiteSeerX
14490:1469-7653
14418:CiteSeerX
14137:WAVL tree
14020:
13959:
13940:⋅
13928:∈
13884:
13872:∈
13824:∈
13782:
13757:∈
13706:
13658:
13652:⋅
13630:
13618:∈
13544:
13532:∈
13490:
13478:∈
13436:
13424:∈
13178:
13166:∈
13124:∈
13077:∈
13006:∈
12383:∈
12265:
12230:
12215:∈
12171:
12159:∈
12149:W(insert)
12111:∈
12069:
12057:∈
12019:∈
11968:
11924:
11910:∈
11867:
11823:
11814:
11800:∈
11736:
11724:∈
11714:T(insert)
11665:∈
11623:
11611:∈
11579:
11567:∈
11130:≤
11106:∈
11083:⟩
11067:⋯
11051:⟨
10988:⟩
10972:⋯
10956:⟨
10924:∈
10735:∞
10732:→
10683:
10677:
10604:
10595:
10553:≥
10476:
10357:)=split(t
10009:
9661:
9649:∈
9538:
9471:
9449:−
9431:
9397:≤
9391:≤
9355:
9291:−
9270:⋅
9258:−
9225:⋅
9202:−
9194:⋅
9175:−
9156:−
9142:⋅
9115:leads to
9054:leads to
8961:≥
8896:∈
8866:−
8852:⋅
8743:−
8738:⌋
8712:⌊
8699:⌋
8685:⌊
8630:⌋
8613:−
8604:⌊
8551:−
8546:⌋
8529:−
8520:⌊
8507:⌋
8493:⌊
8379:−
8374:⌋
8357:−
8348:⌊
8242:−
8166:induction
8147:−
8140:⌋
8123:−
8114:⌊
8098:−
8033:⌋
8014:−
8003:⌊
7978:−
7943:−
7854:−
7816:−
7809:⌋
7795:⌊
7780:⌋
7754:⌊
7656:−
7610:⌉
7596:⌈
7566:⌋
7562:⌊
7507:−
7493:−
7479:⋅
7424:−
7390:−
7370:⋅
7311:−
7306:⌋
7292:⌊
7279:⌋
7253:⌊
7165:∈
6980:and node
6924:-rotation
6759:RotateDir
6697:-rotation
6198:-rotation
5746:Δ
5572:(meaning
5556:(meaning
4891:invariant
4413:RBdelete2
4039:RotateDir
3953:-rotation
3729:−
3157:Δ
2489:invariant
2218:RBinsert1
2170:Insertion
1368:amortized
1324:
1249:
1201:hashcodes
1198:colliding
1172:2–3 trees
1163:Sedgewick
1161:In 2008,
1133:
1074:
969:
909:
897:∈
564:In 1999,
522:In 1972,
484:
429:
362:
326:
283:
247:
204:
168:
133:Amortized
16464:AVL tree
16343:Multiset
16292:Multimap
16279:Abstract
16178:Link/cut
15890:Binomial
15817:Interval
15242:(2016),
15215:e.g. in
14891:26 March
14863:26 March
14763:(1998).
14646:(2008).
14579:(2008).
14514:(1983).
14498:20298262
14363:(2012).
14260:28836825
14100:2–3 tree
14091:AVL tree
14054:See also
13328:Sorting
12938:′
12887:′
12665:′
11531:Sorting
10768:2–3 tree
10399:wait all
10389:=union(R
10373:=union(L
10308:function
10231:function
10138:function
10126:function
10088:.left,⟨T
10046:function
10036:AVL tree
9817:also as
9753:, where
8950:–1) for
8946:A027383(
7124:in-place
6707:becomes
5734:through
5680:rotation
4623:childDir
4560:childDir
4387:is black
4324:in-place
4000:Case_I56
3486:Case_I56
3441:// uncle
3408:childDir
3089:rotation
2138:U == NIL
2115:and the
2051:rotation
2027:actions.
1346:, where
1055:AVL tree
126:Function
39:Invented
16518:R+ tree
16513:R* tree
16459:AA tree
16138:Fenwick
16102:Segment
16001:Spatial
15918:Pairing
15913:Leftist
15835:)
15807:Dancing
15800:)
15798:Optimal
15673:YouTube
15543:Bibcode
15287:2897793
15222:black.)
15219:p. 264.
14935:1480961
14561:7 April
14451:Alt URL
14116:UB-tree
14112:B*-tree
14108:B+ tree
14080:AA tree
13468:#stages
10622:. When
10575:with a
10413:.key, T
10318:):
10310:union(t
10176:T'
10148:):
10120:T' /* T
10104:))
10056:):
9929:, root
9839:, root
8983:in the
8980:A027383
8078:having
7962:it has
7584:minimal
7578:is the
7554:nodes (
7009:Case_D6
6750:Case_D5
6695:(1-dir)
6563:Case_D4
6460:Case_D5
6391:Case_D6
6241:Case_D3
5881:D5 + D6
5841:D5 + D6
5732:Start_D
5574:distant
4984:Δh
4878:Case_D4
4839:Case_D5
4788:Case_D6
4734:Case_D3
4638:Start_D
4599:Start_D
4330:Removal
4170:-rotate
4168:(1-dir)
3825:Case_I4
3390:Case_I4
3281:I5 + I6
3263:I5 + I6
2599:Δh
2021:
2017:
2013:
2009:
1639:subtree
1499:color_t
1427:color_t
1190:HashMap
1188:8, the
1009:B-trees
657:
653:
518:History
16547:Graphs
16508:R-tree
16449:B-tree
16403:Linked
16360:Arrays
16188:Merkle
16153:Fusion
16143:Finger
16067:Octree
16057:Metric
15991:Y-fast
15986:X-fast
15976:Suffix
15895:Brodal
15885:Binary
15590:
15580:
15553:
15512:
15502:
15285:
15275:
15217:Cormen
15071:10.4.2
14933:
14806:25 May
14779:
14775:–575.
14734:
14730:–332.
14681:
14663:
14615:
14530:
14496:
14488:
14438:
14420:
14281:
14258:
14187:
14183:–301.
14132:T-tree
14096:B-tree
13209:level.
13024:steps.
12398:since
11503:, _, T
11489:forall
11463:join T
11043:parts
10948:parts
10443:calls
10420:Here,
10405:join(T
10403:return
10343:return
10341:= nil
10328:return
10326:= nil
10259:return
10255:return
10247:return
10239:return
10216:Node(T
10214:return
10212:)
10204:Node(T
10202:return
10174:return
10144:, k, T
10140:join(T
10132:, k, T
10118:return
10114:return
10092:.key,T
10076:Node(T
10074:return
10052:, k, T
8885:where
8797:convex
8412:(root)
7868:
7673:
7105:return
6608:return
6204:turns
6101:parent
5989:, and
5908:return
5850:, and
5666:before
5568:, and
5525:before
4965:assig-
4946:before
4536:RBnode
4533:struct
4518:RBnode
4515:struct
4500:RBnode
4497:struct
4476:parent
4458:RBnode
4455:struct
4437:RBnode
4434:struct
4419:RBtree
4376:is red
4305:return
3852:return
3792:return
3762:
3686:parent
3372:parent
3339:return
3266:, and
3065:before
3053:’s to
2981:before
2580:assig-
2561:before
2443:return
2386:parent
2311:RBnode
2308:struct
2293:RBnode
2290:struct
2260:RBnode
2257:struct
2242:RBnode
2239:struct
2224:RBtree
2095:Remark
1945:return
1876:parent
1858:parent
1822:parent
1741:assert
1729:RBnode
1705:RBnode
1699:parent
1681:RBnode
1618:RBnode
1603:RBtree
1591:RBnode
1550:RBnode
1541:RBtree
1538:struct
1472:RBnode
1463:parent
1457:RBnode
1448:RBnode
1445:struct
1267:where
1184:As of
820:delete
816:insert
780:Every
536:binary
528:B-tree
502:time.
305:Delete
226:Insert
147:Search
16441:Trees
16314:Queue
16309:Stack
16257:Types
16198:Range
16168:K-ary
16128:Cover
15971:Radix
15956:Ctrie
15948:Tries
15877:Heaps
15857:Treap
15847:Splay
15812:HTree
15767:(a,b)
15757:2–3–4
15624:(PDF)
15533:arXiv
15510:S2CID
15283:S2CID
15255:arXiv
15247:(PDF)
15113:with
14970:(PDF)
14931:S2CID
14911:(PDF)
14882:(PDF)
14853:(PDF)
14651:(PDF)
14584:(PDF)
14494:S2CID
14256:S2CID
13094:stage
11471:join2
11321:into
11255:first
11186:first
10913:into
10441:Split
10433:Join2
10422:split
10383:start
10367:start
10124:' */
9990:Split
9982:Split
9949:Split
9765:<
9761:<
9710:Split
9694:union
9590:with
8766:graph
7691:Proof
7464:even
7202:with
7099:BLACK
7093:color
7090:->
7081:BLACK
7075:color
7072:->
7063:color
7060:->
7051:color
7048:->
6816:BLACK
6810:color
6807:->
6792:color
6789:->
6602:BLACK
6596:color
6593:->
6578:color
6575:->
6445:color
6442:->
6412:child
6409:->
6376:color
6373:->
6343:child
6340:->
6307:BLACK
6301:color
6298:->
6283:color
6280:->
6208:into
6098:->
6083:while
6047:color
6044:->
6017:, so
5725:after
5714:after
5709:also.
5558:close
4974:after
4969:nment
4956:rota-
4863:color
4860:->
4821:color
4818:->
4770:color
4767:->
4719:color
4716:->
4698:child
4695:->
4677:child
4674:->
4656:child
4653:->
4584:child
4581:->
4473:->
4293:color
4290:->
4281:BLACK
4275:color
4272:->
4087:child
4084:->
4027:child
4024:->
3948:). A
3846:BLACK
3840:color
3837:->
3683:->
3668:while
3632:color
3629:->
3620:BLACK
3614:color
3611:->
3602:BLACK
3596:color
3593:->
3474:BLACK
3468:color
3465:->
3435:child
3432:->
3369:->
3327:BLACK
3321:color
3318:->
3130:after
3119:after
3114:also.
2589:after
2584:nment
2571:rota-
2529:when
2461:child
2458:->
2425:->
2383:->
2368:right
2365:->
2347:->
2332:color
2329:->
2195:with
2049:If a
1930:->
1912:child
1909:->
1873:->
1855:->
1840:child
1837:->
1819:->
1786:child
1783:->
1774:child
1771:->
1723:child
1720:->
1696:->
1502:color
1478:child
1433:BLACK
1047:epoll
713:right
699:right
666:BLACK
532:paths
397:is a
80:Space
16530:Trie
16486:Heap
16304:List
16203:SPQR
16082:Quad
16010:Ball
15966:Hash
15938:Weak
15928:Skew
15903:-ary
15578:ISBN
15551:ISBN
15500:ISBN
15273:ISBN
15169:<
15040:tail
14893:2022
14865:2022
14808:2024
14777:ISBN
14732:ISBN
14679:ISBN
14613:ISBN
14563:2018
14528:ISBN
14486:ISSN
14436:ISBN
14279:ISBN
14185:ISBN
13740:Work
12978:Now
12002:Work
11497:else
11251:<
11231:last
11182:<
11162:last
11136:<
10846:and
10774:and
10750:The
10539:and
10445:Join
10437:Join
10353:,b,R
10286:and
10273:and
10164:,k,T
10032:join
9973:Join
9901:Join
9861:and
9828:Join
9740:and
9729:Join
9725:Join
9714:Join
9712:and
9706:bulk
9700:and
9522:<
9264:>
9065:>
9026:>
8985:OEIS
8799:and
8764:The
7903:>
7546:odd
7154:For
6950:and
6938:and
6719:and
6546:and
6534:and
6457:goto
6388:goto
6216:and
6189:and
6110:NULL
6029:the
5883:and
5879:and
5868:and
5721:next
5670:case
5647:and
5592:and
4979:next
4960:tion
4951:case
4875:goto
4836:goto
4785:goto
4731:goto
4596:goto
4485:byte
4410:void
4212:and
4192:and
3987:and
3695:NULL
3578:the
3483:goto
3387:goto
3381:NULL
3279:and
3139:and
3126:next
3069:case
3060:The
3045:and
2594:next
2575:tion
2566:case
2428:root
2410:NULL
2350:left
2215:void
1933:root
1924:else
1900:NULL
1654:root
1633:root
1556:root
1496:enum
1424:enum
1186:Java
1114:sets
1112:and
1045:and
818:and
782:path
740:The
708:and
706:left
692:left
681:path
647:The
638:data
577:Java
549:and
506:its
393:, a
53:and
42:1978
33:Tree
28:Type
16338:Set
16208:Top
16062:MVP
16020:BSP
15772:AVL
15752:2–3
15671:on
15660:by
15588:Zbl
15492:doi
15456:log
15450:log
15413:log
15407:log
15314:doi
15310:262
15265:doi
15176:log
14982:doi
14923:doi
14773:565
14728:331
14671:doi
14476:doi
14428:doi
14314:doi
14248:doi
14181:273
14017:log
13956:log
13881:log
13779:log
13703:log
13655:log
13627:log
13541:log
13487:log
13433:log
13175:log
13116:is
12921:or
12870:as
12262:log
12227:log
12168:log
12066:log
11965:log
11921:log
11864:log
11820:log
11811:log
11733:log
11620:log
11576:log
11519:, T
10680:log
10674:log
10601:log
10592:log
10473:log
10409:, t
10314:, t
10006:log
9992:is
9658:log
9529:log
9462:log
9422:log
9346:log
8795:is
7526:if
7444:if
7036:dir
6926:at
6922:dir
6798:RED
6777:dir
6699:at
6584:RED
6451:RED
6433:NIL
6382:RED
6364:NIL
6289:RED
6268:dir
6200:at
6196:dir
6053:RED
6025:to
6003:not
5821:not
5613:dir
4922:at
4869:RED
4827:RED
4809:NIL
4776:RED
4758:NIL
4725:RED
4617:dir
4590:NIL
4554:dir
4488:dir
4299:RED
4260:dir
4172:at
4051:dir
3955:at
3951:dir
3638:RED
3574:to
3456:NIL
3402:dir
3057:’s.
3025:dir
2537:at
2509:is
2374:NIL
2356:NIL
2338:RED
2278:dir
2275:int
2193:dir
2134:not
2015:or
1810:NIL
1753:NIL
1669:dir
1666:int
1651:the
1645:may
1511:key
1508:int
1439:RED
1414:C++
1342:in
1321:log
1246:log
1232:to
1130:log
1071:log
966:log
906:log
735:NIL
726:).
676:).
670:NIL
664:or
662:NIL
655:NIL
481:log
426:log
389:In
359:log
323:log
280:log
244:log
201:log
165:log
16595::
16193:PQ
16107:VP
16097:R*
16092:R+
16072:PH
16046:-d
16038:-d
16015:BK
15862:UB
15787:B*
15782:B+
15762:AA
15626:.
15586:.
15549:.
15541:.
15508:.
15498:.
15322:.
15308:.
15304:.
15281:,
15271:,
15263:,
15249:,
15227:^
15047:^
15029:.)
15017:^
14976:.
14972:.
14929:.
14919:37
14917:.
14913:.
14884:.
14855:.
14841:^
14799:.
14712:;
14708:;
14704:;
14693:^
14677:.
14669:.
14653:.
14642:;
14627:^
14592:^
14554:.
14526:.
14492:.
14484:.
14470:.
14466:.
14434:.
14426:.
14387:.
14334:.
14304:;
14293:^
14254:.
14242:.
14223:.
14169:;
14165:;
14161:;
14150:^
14114:,
14110:,
14106:,
14102:,
11998:.
11523:)
11493:in
11491:e
11485:if
10818:.
10770:,
10451:.
10417:)
10393:,t
10377:,t
10361:,t
10349:(L
10335:if
10320:if
10299:∪
10251:if
10243:if
10235:if
10224:)
10192:(T
10190:if
10178:if
10170:if
10150:if
10108:(T
10106:if
10060:(T
10058:if
9808:,
9720:.
9696:,
8987:).
8036:=:
7925:–1
7920:RB
7126:.
7039:);
6780:);
6448:==
6430:!=
6421:if
6379:==
6361:!=
6352:if
6271:);
6113:);
6107:!=
6086:((
5985:,
5928:→
5877:D6
5870:D4
5866:D5
5864:,
5862:D6
5853:D1
5847:D4
5844:,
5838:,
5835:D6
5832:,
5829:D3
5705:,
5701:,
5697:,
5638:).
5635:D2
5552:,
5477:D6
5447:0
5443:D6
5413::=
5396:D5
5322:D4
5287:0
5283:D4
5249:0
5245:D5
5211:0
5207:D6
5177::=
5160:D3
5125:1
5107::=
5097:D2
5043:D1
4893::
4866:==
4851:if
4824:==
4806:!=
4797:if
4773:==
4755:!=
4746:if
4722:==
4707:if
4632:);
4611:do
4569:);
4360:.
4326:.
4263:);
4228:.
4196:.
4054:);
4018:==
4009:if
3698:);
3692:!=
3671:((
3471:==
3459:||
3453:==
3444:if
3417:);
3378:==
3357:((
3354:if
3324:==
3309:if
3304:.
3277:I6
3269:I3
3260:,
3257:I6
3254:,
3251:I4
3245:I1
3146:I2
3110:,
3106:,
3074:I2
2933:I6
2902:0
2898:I6
2867::=
2850:I5
2795:I4
2755:I3
2739:2
2721::=
2711:I2
2662:I1
2541:).
2491::
2479:do
2407:==
2398:if
2210:.
2200:.)
2163:if
2158:.)
2148:).
2119::
2102::
1897:!=
1888:if
1807:!=
1798:if
1756:);
1750:!=
1657:of
1648:be
1636:of
1630://
1565:};
1517:};
1442:};
937:.
830:.
793:N'
737:.
16242:e
16235:t
16228:v
16112:X
16087:R
16052:M
16048:)
16044:k
16040:(
16036:k
15901:d
15852:T
15831:(
15796:(
15792:B
15777:B
15745:)
15741:/
15737:(
15718:e
15711:t
15704:v
15630:.
15594:.
15559:.
15545::
15535::
15516:.
15494::
15462:n
15446:/
15442:n
15422:)
15419:n
15404:(
15401:O
15381:n
15361:)
15358:1
15355:(
15352:O
15332:n
15316::
15290:.
15267::
15257::
15203:,
15200:)
15197:1
15194:+
15191:n
15188:(
15180:2
15172:2
15166:h
15146:2
15138:k
15134:2
15127:2
15124:=
15121:n
15101:k
15095:2
15084:k
15082:2
15058:.
15042:.
15011:.
14988:.
14984::
14978:6
14937:.
14925::
14895:.
14867:.
14810:.
14785:.
14740:.
14687:.
14673::
14621:.
14586:.
14565:.
14536:.
14500:.
14478::
14472:9
14430::
14397:.
14349:.
14320:.
14316::
14287:.
14262:.
14250::
14244:1
14227:.
14208:.
14193:.
14118:)
14098:(
14036:)
14032:|
14028:T
14024:|
14013:|
14009:I
14005:|
14001:(
13998:O
13995:=
13975:)
13971:|
13967:T
13963:|
13952:|
13948:I
13944:|
13937:2
13934:(
13931:O
13900:)
13896:|
13892:T
13888:|
13878:(
13875:O
13846:)
13842:|
13838:I
13834:|
13830:(
13827:O
13798:)
13794:|
13790:T
13786:|
13775:|
13771:I
13767:|
13763:(
13760:O
13722:)
13718:|
13714:T
13710:|
13700:(
13697:O
13694:=
13674:)
13670:|
13666:T
13662:|
13649:2
13646:+
13642:|
13638:I
13634:|
13624:(
13621:O
13594:|
13590:I
13586:|
13560:)
13556:|
13552:T
13548:|
13538:(
13535:O
13506:)
13502:|
13498:I
13494:|
13484:(
13481:O
13452:)
13448:|
13444:T
13440:|
13430:(
13427:O
13395:|
13391:T
13387:|
13365:|
13361:I
13357:|
13336:I
13206:.
13194:)
13190:|
13186:I
13182:|
13172:(
13169:O
13146:)
13142:|
13138:I
13134:|
13130:(
13127:O
13104:S
13080:I
13057:S
13034:T
13009:S
12986:T
12975:.
12959:t
12956:h
12953:g
12950:i
12947:r
12942:,
12935:n
12930:s
12905:t
12902:f
12899:e
12896:l
12891:,
12884:n
12879:s
12858:S
12834:r
12831:i
12828:d
12823:,
12820:n
12816:m
12791:r
12788:i
12785:d
12780:,
12777:n
12773:s
12748:r
12745:i
12742:d
12737:,
12734:n
12730:m
12705:r
12702:i
12699:d
12694:,
12691:n
12687:m
12662:n
12641:T
12617:r
12614:i
12611:d
12606:,
12603:n
12599:s
12574:r
12571:i
12568:d
12563:,
12560:n
12556:m
12544:.
12532:n
12512:I
12488:t
12485:f
12482:e
12479:l
12474:,
12471:n
12467:s
12446:S
12426:I
12406:T
12386:I
12363:T
12343:I
12320:I
12281:)
12277:|
12273:T
12269:|
12258:|
12254:I
12250:|
12246:+
12242:|
12238:T
12234:|
12224:k
12221:(
12218:O
12187:)
12183:|
12179:T
12175:|
12165:(
12162:O
12133:)
12129:|
12125:I
12121:|
12117:(
12114:O
12085:)
12081:|
12077:T
12073:|
12063:(
12060:O
12031:)
12028:k
12025:(
12022:O
11985:)
11980:|
11976:T
11972:|
11960:k
11955:|
11951:I
11947:|
11940:+
11936:|
11932:T
11928:|
11917:(
11913:O
11884:)
11879:|
11875:T
11871:|
11859:k
11854:|
11850:I
11846:|
11839:+
11835:|
11831:T
11827:|
11817:k
11807:(
11803:O
11777:k
11752:)
11748:|
11744:T
11740:|
11730:(
11727:O
11697:)
11692:k
11687:|
11683:I
11679:|
11672:(
11668:O
11639:)
11635:|
11631:T
11627:|
11617:(
11614:O
11585:)
11582:k
11573:(
11570:O
11539:I
11521:2
11517:1
11513:2
11509:1
11505:2
11501:1
11403:I
11376:k
11356:j
11334:j
11330:T
11307:j
11303:I
11278:)
11273:1
11270:+
11267:j
11263:I
11259:(
11248:)
11243:j
11239:T
11235:(
11209:)
11204:1
11201:+
11198:j
11194:T
11190:(
11179:)
11174:j
11170:I
11166:(
11139:k
11133:j
11127:1
11122:|
11116:+
11111:N
11103:j
11078:k
11074:T
11070:,
11064:,
11059:1
11055:T
11031:k
11011:T
10983:k
10979:I
10975:,
10969:,
10964:1
10960:I
10934:+
10929:N
10921:k
10901:I
10878:I
10854:T
10834:I
10806:T
10786:I
10729:n
10709:n
10689:)
10686:n
10671:(
10668:O
10636:1
10633:=
10630:m
10610:)
10607:n
10598:m
10589:(
10586:O
10559:)
10556:m
10550:(
10547:n
10527:m
10506:)
10501:)
10497:1
10494:+
10489:m
10486:n
10480:(
10470:m
10466:(
10462:O
10415:R
10411:2
10407:L
10395:2
10391:1
10387:R
10379:2
10375:1
10371:L
10363:2
10359:1
10355:1
10351:1
10347:1
10345:t
10339:2
10337:t
10332:2
10330:t
10324:1
10322:t
10316:2
10312:1
10301:B
10297:A
10292:t
10288:B
10284:A
10279:2
10276:t
10270:1
10267:t
10222:R
10218:L
10210:R
10206:L
10198:R
10194:L
10186:L
10182:R
10180:T
10166:R
10162:L
10158:R
10154:L
10152:T
10146:R
10142:L
10134:R
10130:L
10122:'
10110:L
10102:R
10098:L
10094:L
10090:L
10086:L
10082:R
10078:L
10070:R
10066:L
10062:L
10054:R
10050:L
10038:.
10018:,
10015:)
10012:n
10003:(
10000:O
9986:x
9969:x
9965:x
9961:x
9957:x
9953:x
9939:2
9936:t
9931:k
9927:c
9922:2
9919:t
9914:c
9909:1
9906:t
9896:2
9893:t
9887:1
9884:t
9876:k
9872:k
9867:2
9864:t
9858:1
9855:t
9849:2
9846:t
9841:k
9836:1
9833:t
9821:.
9819:k
9814:2
9811:t
9805:1
9802:t
9797:k
9792:2
9789:t
9784:k
9779:1
9776:t
9770:2
9767:t
9763:k
9759:1
9756:t
9751:k
9746:2
9743:t
9737:1
9734:t
9670:.
9667:)
9664:n
9655:(
9652:O
9646:h
9626:n
9598:n
9559:]
9553:)
9550:1
9547:+
9544:n
9541:(
9533:2
9525:2
9517:[
9494:)
9491:1
9488:+
9485:2
9481:/
9477:n
9474:(
9466:2
9458:2
9455:=
9452:2
9446:)
9443:2
9440:+
9437:n
9434:(
9426:2
9418:2
9394:h
9370:)
9367:1
9364:+
9361:n
9358:(
9350:2
9318:h
9306:.
9294:2
9286:2
9282:/
9278:h
9274:2
9267:2
9261:2
9253:2
9249:/
9245:)
9242:2
9239:+
9236:h
9233:(
9229:2
9220:)
9213:2
9209:/
9205:3
9198:2
9191:3
9186:(
9181:=
9178:2
9170:2
9166:/
9162:)
9159:1
9153:h
9150:(
9146:2
9139:3
9136:=
9131:h
9127:m
9103:h
9081:2
9077:/
9073:3
9069:2
9062:3
9040:3
9036:2
9032:=
9029:8
9023:9
9000:h
8964:1
8958:h
8948:h
8934:=
8929:h
8925:m
8904:.
8900:N
8893:k
8873:)
8870:2
8860:k
8856:2
8849:2
8846:=
8841:k
8838:2
8834:m
8828:|
8823:k
8820:2
8817:=
8814:h
8811:(
8781:h
8777:m
8746:2
8735:2
8731:/
8727:)
8724:1
8721:+
8718:h
8715:(
8708:2
8704:+
8696:2
8692:/
8688:h
8681:2
8659:=
8627:2
8623:/
8619:)
8616:1
8610:h
8607:(
8600:2
8578:+
8557:)
8554:2
8543:2
8539:/
8535:)
8532:1
8526:h
8523:(
8516:2
8512:+
8504:2
8500:/
8496:h
8489:2
8485:(
8464:=
8441:h
8437:m
8385:)
8382:1
8371:2
8367:/
8363:)
8360:1
8354:h
8351:(
8344:2
8340:(
8319:+
8298:)
8295:1
8292:(
8271:+
8250:)
8245:1
8239:h
8235:m
8231:(
8210:=
8187:h
8183:m
8152:1
8137:2
8133:/
8129:)
8126:1
8120:h
8117:(
8110:2
8106:=
8103:1
8091:s
8087:2
8066:s
8042:.
8039:s
8030:2
8026:/
8022:)
8019:1
8009:h
8006:(
7981:1
7975:h
7971:m
7960:;
7948:1
7938:h
7927:,
7923:h
7906:1
7900:h
7889:h
7871:.
7865:1
7862:=
7859:2
7847:0
7843:2
7838:+
7832:1
7828:2
7824:=
7821:2
7806:2
7802:/
7798:1
7791:2
7786:+
7777:2
7773:/
7769:)
7766:1
7763:+
7760:1
7757:(
7750:2
7746:=
7741:1
7737:m
7713:1
7710:=
7707:h
7676:.
7670:2
7666:/
7662:)
7659:1
7653:h
7650:(
7630:h
7607:2
7603:/
7599:h
7586:.
7534:h
7510:2
7500:2
7496:1
7490:h
7483:2
7476:3
7452:h
7427:2
7419:1
7416:+
7410:2
7407:h
7400:2
7396:=
7393:2
7383:2
7380:h
7374:2
7367:2
7344:{
7339:=
7314:2
7303:2
7299:/
7295:h
7288:2
7284:+
7276:2
7272:/
7268:)
7265:1
7262:+
7259:h
7256:(
7249:2
7245:=
7222:h
7218:m
7190:h
7169:N
7162:h
7146:h
7141:h
7114:}
7108:;
7102:;
7096:=
7087:D
7084:;
7078:=
7069:P
7066:;
7057:P
7054:=
7045:S
7033:,
7030:P
7027:,
7024:T
7021:(
7012::
6998:N
6994:S
6990:P
6986:N
6982:3
6978:D
6974:N
6960:S
6956:D
6952:S
6948:P
6944:D
6940:S
6936:P
6932:S
6928:P
6917:D
6913:S
6909:S
6843:;
6840:C
6837:=
6834:S
6831:;
6828:S
6825:=
6822:D
6819:;
6813:=
6804:C
6801:;
6795:=
6786:S
6774:-
6771:1
6768:,
6765:S
6762:(
6753::
6737:P
6733:P
6729:N
6725:N
6721:C
6717:S
6713:N
6709:S
6705:C
6701:S
6690:D
6686:S
6682:C
6678:S
6674:S
6611:;
6605:;
6599:=
6590:P
6587:;
6581:=
6572:S
6566::
6556:N
6552:S
6548:P
6544:S
6540:P
6536:S
6532:S
6463:;
6454:)
6439:C
6427:C
6424:(
6415:;
6406:S
6403:=
6400:C
6394:;
6385:)
6370:D
6358:D
6355:(
6346:;
6337:S
6334:=
6331:D
6322:;
6319:C
6316:=
6313:S
6310:;
6304:=
6295:S
6292:;
6286:=
6277:P
6265:,
6262:P
6259:,
6256:T
6253:(
6244::
6234:S
6230:P
6226:N
6222:N
6218:S
6214:P
6210:N
6206:S
6202:P
6191:D
6187:C
6183:P
6179:S
6104:)
6095:N
6092:=
6089:P
6080:}
6068:;
6065:P
6062:=
6059:N
6056:;
6050:=
6041:S
6027:N
6023:P
6015:P
6011:P
6007:N
5999:S
5995:S
5991:S
5987:S
5983:P
5911:;
5898:N
5872:.
5803:h
5783:h
5773:N
5769:P
5755:1
5752:=
5749:h
5716:.
5707:D
5703:S
5699:C
5695:P
5691:N
5659:P
5655:N
5630:N
5620:N
5615:.
5609:N
5605:P
5601:N
5594:D
5590:C
5586:N
5582:S
5578:S
5570:D
5566:N
5562:S
5554:C
5550:N
5546:S
5542:N
5538:P
5516:✓
5487:S
5485:↶
5483:P
5415:N
5411:N
5406:S
5404:↷
5402:C
5359:✓
5179:N
5175:N
5170:S
5168:↶
5166:P
5122:?
5113:?
5109:P
5105:N
5060:✓
5032:—
5026:D
5021:S
5016:C
5011:P
5006:D
5001:S
4996:C
4991:P
4924:P
4916:N
4903:N
4899:N
4881:;
4872:)
4857:P
4854:(
4842:;
4830:)
4815:C
4803:C
4800:(
4791:;
4779:)
4764:D
4752:D
4749:(
4737:;
4728:)
4713:S
4710:(
4701:;
4692:S
4689:=
4686:C
4680:;
4671:S
4668:=
4665:D
4659:;
4650:P
4647:=
4644:S
4641::
4629:N
4626:(
4620:=
4614:{
4602:;
4593:;
4587:=
4578:P
4566:N
4563:(
4557:=
4545:;
4542:D
4539:*
4527:;
4524:C
4521:*
4509:;
4506:S
4503:*
4491:;
4479:;
4470:N
4467:=
4464:P
4461:*
4452:{
4446:)
4443:N
4440:*
4428:,
4425:T
4422:*
4416:(
4403:N
4399:N
4314:}
4308:;
4302:;
4296:=
4287:G
4284:;
4278:=
4269:P
4257:-
4254:1
4251:,
4248:G
4245:,
4242:T
4239:(
4226:P
4222:G
4214:G
4210:P
4202:P
4198:G
4194:G
4190:N
4186:P
4182:G
4178:P
4174:G
4163:G
4159:N
4099:}
4090:;
4081:G
4078:=
4075:P
4069:;
4066:P
4063:=
4060:N
4048:,
4045:P
4042:(
4033:{
4030:)
4021:P
4015:N
4012:(
4003::
3989:N
3985:P
3981:4
3977:P
3973:2
3969:N
3965:P
3961:N
3957:P
3946:G
3942:G
3938:N
3934:G
3930:N
3926:P
3922:U
3918:P
3855:;
3849:;
3843:=
3834:P
3828::
3818:P
3814:N
3810:P
3795:;
3779:N
3765:.
3759:h
3736:2
3732:1
3726:h
3689:)
3680:N
3677:=
3674:P
3665:}
3653:;
3650:G
3647:=
3644:N
3641:;
3635:=
3626:G
3623:;
3617:=
3608:U
3605:;
3599:=
3590:P
3576:N
3572:G
3568:G
3560:G
3556:U
3552:P
3489:;
3477:)
3462:U
3450:U
3447:(
3438:;
3429:G
3426:=
3423:U
3414:P
3411:(
3405:=
3393:;
3384:)
3375:)
3366:P
3363:=
3360:G
3348:}
3342:;
3333:{
3330:)
3315:P
3312:(
3294:P
3272:.
3239:.
3223:h
3200:2
3197:h
3184:N
3180:G
3166:2
3163:=
3160:h
3121:.
3112:U
3108:G
3104:P
3100:N
3079:N
3055:N
3051:P
3047:N
3043:P
3039:x
3032:P
3027:.
3021:P
3017:G
3013:P
3006:U
3002:G
2998:N
2994:P
2972:✓
2943:G
2941:↷
2939:P
2928:o
2894:o
2869:P
2865:N
2860:N
2858:↶
2856:P
2845:i
2817:✓
2786:—
2772:✓
2744:—
2736:?
2727:?
2723:G
2719:N
2679:✓
2641:x
2636:U
2631:G
2626:P
2621:x
2616:U
2611:G
2606:P
2539:N
2531:P
2527:P
2525:←
2523:N
2507:N
2501:N
2497:N
2482:{
2470:;
2467:N
2464:=
2455:P
2452:}
2446:;
2437:;
2434:N
2431:=
2422:T
2416:{
2413:)
2404:P
2401:(
2395:;
2392:P
2389:=
2380:N
2377:;
2371:=
2362:N
2359:;
2353:=
2344:N
2341:;
2335:=
2326:N
2320:;
2317:U
2314:*
2302:;
2299:G
2296:*
2287:{
2281:)
2269:,
2266:P
2263:*
2251:,
2248:N
2245:*
2233:,
2230:T
2227:*
2221:(
2204:P
2189:P
2176:N
2061:N
2046:.
2044:N
2040:N
2036:.
2019:N
2011:N
2005:N
1957:}
1951:;
1948:S
1942:;
1939:S
1936:=
1927:T
1921:;
1918:S
1915:=
1906:G
1903:)
1894:G
1891:(
1885:;
1882:G
1879:=
1870:S
1867:;
1864:S
1861:=
1852:P
1849:;
1846:P
1843:=
1834:S
1831:;
1828:P
1825:=
1816:C
1813:)
1804:C
1801:(
1795:;
1792:C
1789:=
1780:P
1777:;
1768:S
1765:=
1762:C
1747:S
1744:(
1738:;
1735:C
1732:*
1726:;
1717:P
1714:=
1711:S
1708:*
1702:;
1693:P
1690:=
1687:G
1684:*
1675:{
1672:)
1663:)
1660:T
1642:(
1627:,
1624:P
1621:*
1612:,
1609:T
1606:*
1600:(
1594:*
1559:;
1553:*
1544:{
1514:;
1505:;
1481:;
1475:*
1466:;
1460:*
1451:{
1436:,
1430:{
1386:)
1383:1
1380:(
1377:O
1354:n
1330:)
1327:n
1318:(
1315:O
1275:m
1255:)
1252:m
1243:(
1240:O
1220:)
1217:m
1214:(
1211:O
1139:)
1136:n
1127:(
1124:O
1080:)
1077:n
1068:(
1065:O
975:)
972:n
963:(
960:O
927:,
915:)
912:n
903:(
900:O
894:h
873:n
849:h
799:.
789:N
710:6
703:6
696:1
689:1
685:1
490:)
487:n
478:(
475:O
455:n
435:)
432:n
423:(
420:O
368:)
365:n
356:(
353:O
332:)
329:n
320:(
317:O
289:)
286:n
277:(
274:O
253:)
250:n
241:(
238:O
210:)
207:n
198:(
195:O
174:)
171:n
162:(
159:O
101:)
98:n
95:(
92:O
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
