[8] Another response from Guibas states that it was because of the red and black pens available to them to draw the trees.

[9] In 1993, Arne Andersson introduced the idea of a right leaning tree to simplify insert and delete operations.

[1] Sedgewick showed that the insert operation can be implemented in just 46 lines of Java code.

[12][13] In 2008, Sedgewick proposed the left-leaning red–black tree, leveraging Andersson’s idea that simplified the insert and delete operations.

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.

Since operations such as inserting, deleting, and finding values require worst-case time proportional to the height

But they support also asymptotically optimal direct access via a traversal from root to leaf, resulting in

The left-leaning red-black tree variant makes this relationship exactly 1-to-1, by only allowing the left child representation.

The performance measurements of Ben Pfaff with realistic test cases in 79 runs find AVL to RB ratios between 0.677 and 1.077, median at 0.947, and geometric mean 0.910.

[citation needed] Red–black trees are also particularly valuable in functional programming, where they are one of the most common persistent data structures, used to construct associative arrays and sets that can retain previous versions after mutations.

The LLRB maintains an additional invariant that all red links must lean left except during inserts and deletes.

[25] As of Java 8, the HashMap has been modified such that instead of using a LinkedList to store different elements with colliding hashcodes, a red–black tree is used.

, a constant number,[27]: 310  [16]: 158  of color changes (which are very quick in practice); and no more than three tree rotations[28] (two for insertion).

The details of the insert and removal operations will be demonstrated with example C++ code, which uses the type definitions, macros below, and the helper function for rotations:

The rebalancing loop of the insert operation has the following invariant: The current node’s parent P is black, so requirement 3 holds.

Now (1-dir)-rotate at G, putting P in place of G and making P the parent of N and G. G is black and its former child P is red, since requirement 3 was violated.

Requirement 4 also remains satisfied, since all paths that went through the black G now go through the black P. 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 in-place.

The single child (non-NIL) must be red according to conclusion 5, and the deleted node must be black according to requirement 3.

The complex case is when N is not the root, colored black and has no proper child (⇔ only NIL children).

But N now has a red parent P and after the reassignment a black sibling S, so the transformations in cases D4, D5, or D6 are able to restore the RB-shape.

After a dir-rotation at P the sibling S becomes the parent of P and S’s distant child D. The colors of P and S are exchanged, and D is made black.

[15]: 444 Proof sketch  If a node is taken off this tree it either loses height or some RB property.

The higher child subtree is also a minimal RB tree, RBh–1, containing also a longest path that defines its height

Then fast bulk operations on insertions or deletions can be implemented based on these set functions.

The algorithm for intersection or difference is similar, but requires the Join2 helper routine that is the same as Join but without the middle key.

Parallel algorithms for constructing red–black trees from sorted lists of items can run in constant time or

[36] The join-based algorithms for red–black trees are parallel for bulk operations, including union, intersection, construction, filter, map-reduce, and so on.

This approach can be applied to every sorted sequence data structure that supports efficient join- and split-operations.

The pseudo code shows a simple divide-and-conquer implementation of the join-based algorithm for bulk-insert.

The join operation used here differs from the version explained in this article, instead join2 is used, which misses the second parameter k. Sorting