View source for Red–black tree

{{Short description|Self-balancing binary search tree data structure}}

{{Infobox data structure-amortized
| name = Red–black tree
| type = [[Tree (data structure)|Tree]]
| invented_by = [[Leonidas J. Guibas]] and [[Robert Sedgewick (computer scientist)|Robert Sedgewick]]
| invented_year = 1978
| space_avg = <math>O(n)</math>
| search_avg = <math>O(\log n)</math>
| search_worst = <math>O(\log n)</math>
| insert_avg = <math>O(\log n)</math>
| insert_worst = <math>O(\log n)</math>
| delete_avg = <math>O(\log n)</math>
| delete_worst = <math>O(\log n)</math>
}}
[[File:Red-black tree example with sockets.svg|thumb|right|275px|Example of a red-black tree]]

In [[computer science]], a '''red–black tree''' is a [[self-balancing binary search tree]] [[data structure]] 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.<ref name="Cormen2001">{{Anchor|Cormen}}{{Cite book |last1=Cormen |first1=Thomas H. |author1-link=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |author2-link=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |author3-link=Ronald L. Rivest |last4=Stein |first4=Clifford |author4-link=Clifford Stein |year=2001 |title=Introduction to Algorithms |edition=2nd |isbn=978-0-262-03293-3 |chapter=Red&ndash;Black Trees |pages=[https://archive.org/details/introductiontoal00corm_691/page/n735 273]–301 |title-link=Introduction to Algorithms |publisher=MIT Press}}</ref>

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.

The (re-)balancing is not perfect, but guarantees searching in <math>O(\log n)</math> time, where <math>n</math> is the number of entries in the tree. The insert and delete operations, along with tree rearrangement and recoloring, also execute in <math>O(\log n)</math> time.<ref name="wiscurl2">{{cite web |last=Paton |first=James |title=Red–Black Trees |url=http://pages.cs.wisc.edu/~paton/readings/Red-Black-Trees/}}</ref><ref>{{cite web |url=https://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html |title=Red–Black Trees |first=John |last=Morris |date=1998 |work=Data Structures and Algorithms}}</ref>

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 its [[memory footprint]] is almost identical to that of a classic (uncolored) [[binary search tree]]. In some cases, the added bit of information can be stored at no added memory cost.

{{TOC limit|4}}

== History ==
In 1972, [[Rudolf Bayer]]<ref name="Bayer72">{{cite journal
|last=Bayer |first=Rudolf
|year=1972
|title=Symmetric binary B-Trees: Data structure and maintenance algorithms
|journal=Acta Informatica
|volume=1
|issue=4
|pages=290–306
|doi=10.1007/BF00289509
|s2cid=28836825
}}</ref> invented a data structure that was a special order-4 case of a [[B-tree]]. These trees maintained all [[path (graph theory)|paths]] from root to leaf with the same number of nodes, creating perfectly balanced trees. However, they were not ''binary'' search trees. Bayer called them a "symmetric binary B-tree" in his paper and later they became popular as [[2–3–4 tree]]s or even 2–3 trees.<ref>{{Cite book |last=Drozdek |first=Adam |title=Data Structures and Algorithms in Java |publisher=Sams Publishing |year=2001 |isbn=978-0534376680 |pages=323 |edition=2}}</ref>

In a 1978 paper, "A Dichromatic Framework for Balanced Trees",<ref name="GS78">{{cite conference
 |last1=Guibas |first1=Leonidas J. |author1-link=Leonidas J. Guibas |last2=Sedgewick |first2=Robert |author2-link=Robert Sedgewick (computer scientist)
 |title=A Dichromatic Framework for Balanced Trees
 |book-title=Proceedings of the 19th Annual Symposium on Foundations of Computer Science
 |year=1978
 |pages=8–21
 |doi=10.1109/SFCS.1978.3}}</ref> [[Leonidas J. Guibas]] and [[Robert Sedgewick (computer scientist)|Robert Sedgewick]] derived the red–black tree from the symmetric binary B-tree.<ref>{{Cite web|title=Red Black Trees|url=http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx|website=eternallyconfuzzled.com|access-date=2015-09-02|archive-url=https://web.archive.org/web/20070927222509/http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx|archive-date=2007-09-27|url-status=dead}}</ref> 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 [[Xerox PARC]].<ref name="Sedgewick12">{{cite AV media
 |last=Sedgewick |first=Robert |author-link=Robert Sedgewick (computer scientist)
 |year=2012
 |title=Red–Black BSTs
 |url=https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/8acpe/red-black-trees
 |publisher=Coursera
 |quote=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[sic] graphic user interfaces, Ethernet and object-oriented programmings[sic] 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.
}}
</ref> Another response from Guibas states that it was because of the red and black pens available to them to draw the trees.<ref>{{Cite web|title=Where does the term "Red/Black Tree" come from?|url=http://programmers.stackexchange.com/a/116621/40127|website=programmers.stackexchange.com|access-date=2015-09-02}}</ref>

In 1993, Arne Andersson introduced the idea of a right leaning tree to simplify insert and delete operations.<ref>{{Cite book
|chapter=Balanced search trees made simple
|series=Lecture Notes in Computer Science
|type=Proceedings
|publisher=Springer-Verlag Berlin Heidelberg
|date=1993-08-11
|isbn=978-3-540-57155-1
|doi=10.1007/3-540-57155-8_236
|pages=60–71 |volume=709
|first=Arne |last=Andersson
|editor-first=Frank |editor-last=Dehne
|editor-first2=Jörg-Rüdiger
|editor-last2=Sack
|editor-first3=Nicola
|editor-last3=Santoro
|editor-first4=Sue
|editor-last4=Whitesides
|chapter-url=https://www.springer.com/la/book/9783540571551
|title=Algorithms and Data Structures
|archive-url=https://web.archive.org/web/20181208183054/https://www.springer.com/la/book/9783540571551
|archive-date=2018-12-08
|citeseerx=10.1.1.118.6192
}} [http://user.it.uu.se/~arnea/ps/simp.pdf Alt URL]</ref>

In 1999, [[Chris Okasaki]] 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.<ref>{{cite journal |title=Red–black trees in a functional setting |journal=Journal of Functional Programming |date=1999-01-01 |doi=10.1017/S0956796899003494 |issn=1469-7653 |pages=471–477 |volume=9 |issue=4 |first=Chris |last=Okasaki |s2cid=20298262 |doi-access=free }}</ref>

The original algorithm used 8 unbalanced cases, but {{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}} reduced that to 6 unbalanced cases.<ref name="Cormen2001"/> Sedgewick showed that the insert operation can be implemented in just 46 lines of [[Java (programming language)|Java]].<ref name="Algs1">{{cite book
|last=Sedgewick
|first=Robert |author-link=Robert Sedgewick (computer scientist)
|title=Algorithms
|publisher=[[Addison-Wesley]]
|edition=1st
|year=1983
|isbn=978-0-201-06672-2
|url-access=registration
|url=https://archive.org/details/algorithms00sedg
}}</ref><ref>{{cite web
|url=http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/RedBlackBST.java.html
|title=RedBlackBST.java
|last1=Sedgewick
|first1=Robert
|author1-link=Robert Sedgewick (computer scientist)
|last2=Wayne
|first2=Kevin
|website=algs4.cs.princeton.edu
|access-date=7 April 2018}}</ref>
In 2008, Sedgewick proposed the [[left-leaning red–black tree]], 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.<ref>{{cite web
|title=Left-leaning Red–Black Trees
|last=Sedgewick
|first=Robert
|author1-link=Robert Sedgewick (computer scientist)
|date=2008
|url=https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf}}</ref><ref name="Algs4">{{Cite book
|last1=Sedgewick
|first1=Robert
|author1-link=Robert Sedgewick (computer scientist)
|last2=Wayne
|first2=Kevin
|title=Algorithms
|edition=4th
|isbn=978-0-321-57351-3
|year=2011
|publisher=Addison-Wesley Professional
|url=http://algs4.cs.princeton.edu}}</ref>

== Terminology ==

The '''black depth''' 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 '''black height''' of a red–black tree is the number of black nodes in any path from the root to the leaves, which, by [[#req4|requirement 4]], is constant (alternatively, it could be defined as the black depth of any leaf node).<ref name="Mehlhorn2008">{{cite book
|chapter=7. Sorted Sequences
|chapter-url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/SortedSequences.pdf
|title=Algorithms and Data Structures: The Basic Toolbox
|url=http://people.mpi-inf.mpg.de/~mehlhorn/Toolbox.html
|last1=Mehlhorn |first1=Kurt |author-link1=Kurt Mehlhorn
|last2=Sanders|first2=Peter |author-link2=Peter Sanders (computer scientist)
|publisher=Springer |location= Berlin/Heidelberg
|year=2008
|isbn=978-3-540-77977-3
|doi=10.1007/978-3-540-77978-0 |citeseerx=10.1.1.148.2305
}}</ref>{{rp|154–165}}
The black height of a node is the black height of the subtree rooted by it. In this article, the black height of a null node shall be set to 0, because its subtree is empty as suggested by the example figure, and its tree height is also 0.

== Properties ==
In addition to the requirements imposed on a [[binary search tree]] the following must be satisfied by a {{nowrap|red–black tree:<ref name="Cormen2009">{{cite book
|last1=Cormen |first1=Thomas |author-link1=Thomas H. Cormen
|last2=Leiserson |first2=Charles |author-link2=Charles E. Leiserson
|first3=Ronald |last3=Rivest |author-link3=Ron Rivest
|first4=Clifford |last4=Stein |author-link4=Clifford Stein
|chapter=13. Red–Black Trees
|title=Introduction to Algorithms |title-link=Introduction to Algorithms
|edition=4th |year=2022 |publisher=[[MIT Press]] |isbn=9780262046305
|pages=[https://archive.org/details/introductiontoal00corm_805/page/n328 331]–332
}}</ref>}}

# Every node is either red or black.
# {{Anchor|consideredBlack}}All null nodes are considered black.
# {{anchor|req3}}A red node does not have a red child.
# {{anchor|req4}}Every [[path (graph theory)|path]] from a given node to any of its leaf nodes (that is, to any descendant null node) goes through the same number of black nodes.
#{{anchor|con5}}(Conclusion) If a node '''N''' has exactly one child, the child must be red. If the child were black, its leaves would sit at a different black depth than '''N''''s null node (which is considered black by rule 2), violating [[#req4|requirement 4]].

Some authors, e.g. Cormen & al.,<ref name="Cormen2009"/> claim "the root is black" as fifth requirement; but not Mehlhorn & Sanders<ref name="Mehlhorn2008"/> or Sedgewick & Wayne.<ref name="Algs4"/>{{rp|432–447}} 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 recursive algorithms and proofs.

As an example, every [[Binary tree#Types of binary trees|perfect binary tree]] that consists only of black nodes is a red–black tree.

The read-only operations, such as search or tree traversal, do not affect any of the requirements. In contrast, the modifying operations [[#Insertion|insert]] and [[#Removal: simple cases|delete]] 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 {{anchor|ViolR}}'''red-violation''', or of requirement 4, called a {{anchor|ViolB}}'''black-violation'''.

The requirements enforce a critical property of red–black trees: ''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''. The result is that the tree is [[Height-balanced binary search tree|height-balanced]]. Since operations such as inserting, deleting, and finding values require worst-case time proportional to the height <math>h</math> of the tree, this upper bound on the height allows red–black trees to be efficient in the worst case, namely [[Logarithmic growth|logarithmic]] in the number <math>n</math> of entries, i.e. {{nowrap|<math>h \in O(\log n)</math>}} (a property which is shared by all self-balancing trees, e.g., [[AVL tree]] or [[B-tree]], but not the ordinary [[binary search tree]]s). For a mathematical proof see section [[#Proof of bounds|Proof of bounds]].

Red–black trees, like all [[binary search tree]]s, allow quite efficient sequential access (e.g. [[in-order traversal]], that is: in the order Left–Root–Right) of their elements. But they support also asymptotically optimal [[Random access|direct access]] via a traversal from root to leaf, resulting in <math>O(\log n)</math> search time.

== Analogy to 2–3–4 trees ==
[[File:Red-black trees and 2–3–4 trees.svg|alt=A 2-node maps to a single black node. A 3-node maps to a black node with a red child. A 4-node maps to a black node with two red children.|thumb|Figure 1: Similarities between 2–3–4 trees and red-black trees]]

Red–black trees are similar in structure to [[2–3–4 trees]], which are [[B-trees]] of order 4.<ref>Using Knuth’s definition of order: the maximum number of children</ref> 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 1. It is not a [[1-to-1 correspondence]], because 3-nodes have two equivalent representations: the red child may lie either to the left or right. The [[left-leaning red-black tree]] 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.

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.<ref>{{Cite book |last=Sedgewick |first=Robert |author-link=Robert Sedgewick (computer scientist) |url=https://archive.org/details/algorithmscparts00sedg |title=Algorithms in C++ |publisher=Addison-Wesley Professional |year=1998 |isbn=978-0-201-35088-3 |pages=[https://archive.org/details/algorithmscparts00sedg/page/n569 565]–575 |url-access=limited}}</ref>

== Applications and related data structures ==
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 [[real-time computing|real-time application]]s, but it makes them valuable building blocks in other data structures that provide worst-case guarantees. For example, many data structures used in [[computational geometry]] are based on red–black trees, and the [[Completely Fair Scheduler]] and [[epoll]] system call of the [[Linux kernel]] use red–black trees.<ref>{{cite web |title=IBM Developer |url=https://developer.ibm.com/tutorials/l-completely-fair-scheduler/ |website=developer.ibm.com |access-date=25 May 2024}}</ref><ref>{{Cite web
|url=https://idndx.com/2014/09/01/the-implementation-of-epoll-1/
|title=The Implementation of epoll (1)
|work=Datong's Random Thoughts
|date=September 2014
|access-date=2018-06-25
|archive-date=2020-10-11
|archive-url=https://web.archive.org/web/20201011122015/https://idndx.com/2014/09/01/the-implementation-of-epoll-1/
|url-status=dead
}}</ref>
The [[AVL tree]] is another structure supporting <math>O(\log n)</math> 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 cases in 79 runs find AVL to RB ratios between 0.677 and 1.077, median at 0.947, and geometric mean 0.910.<ref>[[#Pfaff b|Pfaff 2004]]</ref> The performance of [[WAVL tree]]s lie in between AVL trees and red-black trees.{{cn|date=April 2024}}

Red–black trees are also particularly valuable in [[functional programming]], where they are one of the most common [[persistent data structure]]s, used to construct [[associative array]]s and [[set (computer science)|set]]s that can retain previous versions after mutations. The persistent version of red–black trees requires <math>O(\log n)</math> space for each insertion or deletion, in addition to time.

For every [[2–3–4 tree]], 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.

In 2008, [[Robert Sedgewick (computer scientist)|Sedgewick]] introduced a simpler version of the red–black tree called the [[left-leaning red–black tree]]<ref name="LLRB">{{cite web|url=http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf|title=Robert Sedgewick|website=Cs.princeton.edu|date=4 June 2020 |access-date=26 March 2022}}</ref> 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 [[2–3 tree]]s,<ref>{{cite web|url=http://www.cs.princeton.edu/courses/archive/fall08/cos226/lectures/10BalancedTrees-2x2.pdf|title=Balanced Trees|website=Cs.princeton.edu|access-date=26 March 2022}}</ref> or 2–3–4 trees,<ref name="LLRB"/> for any sequence of operations. The 2–3–4 tree isometry was described in 1978 by Sedgewick.<ref name="GS78"/> 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.

The original description of the [[tango tree]], a type of tree optimised for fast searches, specifically uses red–black trees as part of its data structure.<ref name="DHIP">{{cite journal 
|doi=10.1137/S0097539705447347
|url=http://erikdemaine.org/papers/Tango_SICOMP/paper.pdf 
|title=Dynamic Optimality—Almost
|journal=SIAM Journal on Computing
|volume=37
|issue=1 
|pages=240|year=2007
|last1=Demaine 
|first1=E. D. 
|last2=Harmon |first2=D. 
|last3=Iacono |first3=J. 
|last4=Pătraşcu 
|first4=M. 
|s2cid=1480961}}</ref>

As of [[Java (programming language)|Java]] 8, the [[Hashtable|HashMap]] has been modified such that instead of using a [[LinkedList]] to store different elements with [[Hash function#Uniformity|colliding]] [[hashcode]]s, a red–black tree is used. This results in the improvement of time complexity of searching such an element from <math>O(m)</math> to <math>O(\log m)</math> where <math>m</math> is the number of elements with colliding hashes.<ref>{{cite web |url=http://coding-geek.com/how-does-a-hashmap-work-in-java/#JAVA_8_improvements |title= How does a HashMap work in JAVA |publisher=coding-geek.com}}</ref>

== Implementation ==
The read-only operations, such as search or tree traversal, on a red–black tree require no modification from those used for [[binary search tree]]s, 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 ''rebalancing'' so that red–black trees become self-balancing.
{{anchor|amortized}}Rebalancing (i.e. color changes) has a worst-case time complexity of <math>O(\log n)</math> and average of <math>O(1)</math>,<ref name="tarjan">{{cite journal|last=Tarjan|first=Robert Endre|author-link=Robert Tarjan|title=Amortized Computational Complexity|journal=SIAM Journal on Algebraic and Discrete Methods|date=April 1985|volume=6|issue=2|pages=306–318|doi=10.1137/0606031|url=http://www.cs.duke.edu/courses/fall11/cps234/reading/Tarjan85_AmortizedComplexity.pdf}}</ref>{{rp|310}}<ref name="Mehlhorn2008"/>{{rp|158}} though these are very quick in practice. Additionally, rebalancing takes no more than three [[tree rotation]]s<ref>The important thing about these tree rotations is that they preserve the in-order sequence of the tree’s nodes.</ref> (two for insertion).

This is an example implementation of insert and remove in [[C (programming language)|C]]. Below are the data structures and the <code>rotate_subtree</code> helper function used in the insert and remove examples.

<syntaxhighlight lang="c" line="1">
typedef enum Color: char { 
    BLACK, 
    RED 
} Color;

typedef enum Direction: char { 
    LEFT, 
    RIGHT 
} Direction;

// red-black tree node
typedef struct Node {
	struct Node* parent; // null for the root node
	union {
		// Union so we can use ->left/->right or ->child[0]/->child[1]
		struct {
			struct Node* left;
			struct Node* right;
		};
		struct Node* child[2];
	};
	Color color;
	int key;
} Node;

typedef struct {
	struct Node* root;
} Tree;

static Direction direction(const Node* N) {
    return N == N->parent->right ? RIGHT : LEFT;
}

Node* rotate_subtree(Tree* tree, Node* sub, Direction dir) {
	Node* sub_parent = sub->parent;
	Node* new_root = sub->child[1 - dir]; // 1 - dir is the opposite direction
	Node* new_child = new_root->child[dir];

	sub->child[1 - dir] = new_child;

	if (new_child) {
        new_child->parent = sub;
    }

	new_root->child[dir] = sub;

	new_root->parent = sub_parent;
	sub->parent = new_root;
	if (sub_parent) {
		sub_parent->child[sub == sub_parent->right] = new_root;
	} else {
		tree->root = new_root;
    }

	return new_root;
}</syntaxhighlight>

[[File:Binary Tree Rotation (animated).gif|160px|thumb|right|Left rotation and<br/>right rotation, animated.]]{{Anchor|explan}}

=== Notes to the sample code and diagrams of insertion and removal ===
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, the other five cases rebalance the tree of their own. The more complicated cases are pictured in a diagram.

* [[File:RedNode.svg|baseline]] symbolises a red node and [[File:BlackNode.svg|13px|baseline]] a (non-NULL) black node (of black height &ge; 1), [[File:RedOrBlackNode.svg|baseline]] symbolises the color red or black of a non-NULL node, but the same color throughout the same diagram. NULL nodes are not represented in the diagrams.
* The variable '''N''' denotes the current node, which is labeled <span style="background:black">&thinsp;<span style="color:white">N</span>&thinsp;</span> or <span style="background:red">&thinsp;<span style="color:white">N</span>&thinsp;</span> in the diagrams.
* 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 actions.<ref name="pullout">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 definitively non-NIL later. (See also [[#C-eval|this remark]].)</ref>
# The action "entry" shows the constellation of nodes with their colors which defines a case and mostly violates some of the [[#Properties|requirements]].<br/>A blue border rings the current node '''N''' and the other nodes are labeled according to their relation to '''N'''.
# If a [[tree rotation|rotation]] is considered useful, this is pictured in the next action, which is labeled "rotation".
# If some recoloring is considered useful, this is pictured in the next action, which is labeled "color".<ref>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 [[Tail call|tail]].</ref>
# 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 '''N''', which then again carries a blue ring and relative to which other nodes may have to be reassigned also. This action is labeled "reassign".<br/>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.
* A possibly numbered triangle with a black circle atop [[File:TriangleTop.svg|baseline]] represents a red–black subtree (connected to its parent according to [[#req3|requirement 3]]) 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.<br/>A possibly numbered triangle [[File:TriangleSubtree.svg|baseline]] represents a red–black subtree with a black height one less, i.e. its parent has black height zero in the second iteration.

{{anchor|C-eval}}
; Remark
: For simplicity, the sample code uses the [[Logical disjunction|disjunction]]:
:: <code>U == NULL || U->color == BLACK ''// considered black''</code>
: and the [[Logical conjunction|conjunction]]:
:: <code>U != NULL && U->color == RED &nbsp; ''// not considered black''</code>
: Thereby, it must be kept in mind that both statements are ''not'' evaluated in total, if <code>U == NULL</code>. Then in both cases <code>U->color</code> is not touched (see [[Short-circuit evaluation]]).<br/>(The comment <code>considered black</code> is in accordance with [[#consideredBlack|requirement 2]].)
: The related <code>if</code>-statements have to occur far less frequently if the proposal<ref name="pullout"/> is realised.

=== Insertion ===
Insertion begins by placing the new (non-NULL) node, say '''N''', at the position in the [[binary search tree]] of a NULL node whose [[in-order traversal|in-order predecessor’s]] 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 <code>P</code> together with a direction <code>dir</code> with {{nowrap|1=<code>P->child[dir] == NULL</code>.)}}
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 '''P''', is also red then this action introduces a [[#ViolR|red-violation]].

<syntaxhighlight lang="c" line="1" linelinks="insert" copy>
// parent is optional
void insert(Tree* tree, Node* node, Node* parent, Direction dir) {
	node->color = RED;
	node->parent = parent;

	if (!parent) {
		tree->root = node;
		return;
	}

	parent->child[dir] = node;

	// rebalance the tree 
	do {
		// Case #1
		if (parent->color == BLACK) {
            return; 
        }

	    Node* grandparent = parent->parent;

		if (!grandparent) {
			// Case #4
			parent->color = BLACK;
			return;
		}

		dir = direction(parent);
		Node* uncle = grandparent->child[1 - dir];
		if (!uncle || uncle->color == BLACK) {
			if (node == parent->child[1 - dir]) {
				// Case #5
				rotate_subtree(tree, parent, dir);
				node = parent;
				parent = grandparent->child[dir];
			}

			// Case #6
			rotate_subtree(tree, grandparent, 1 - dir);
			parent->color = BLACK;
			grandparent->color = RED;
			return;
		}
	
		// Case #2
		parent->color = BLACK;
		uncle->color = BLACK;
		grandparent->color = RED;
		node = grandparent;

	} while ((parent = node->parent));

	// Case #3
	return;

}
</syntaxhighlight>

{{Anchor|loopInvariantI}}The rebalancing loop of the insert operation has the following [[Loop invariant|invariants]]:
* '''Node''' is the current node, initially the insertion node.
* '''Node''' is red at the beginning of each iteration.
* [[#req3|Requirement 3]] is satisfied for all pairs node←parent with the possible exception '''node'''←'''parent''' when '''parent''' is also red (a [[#ViolR|red-violation]] at '''node''').
* All other properties (including [[#req4|requirement 4]]) are satisfied throughout the tree.

==== Notes to the insert diagrams ====
{| class="wikitable floatright" style="text-align:center;"
|- style="background:#E8E8E8;font-size:smaller;"
|colspan="4"| ''before'' ||rowspan="2"|''case''||rowspan="2" {{verth|''rotation''}} ||rowspan="2" {{verth|''assign&shy;ment''}} ||colspan="4"| ''after'' ||rowspan="2"|''next''||rowspan="2"| &Delta;''h''
|- style="background:#E8E8E8"
| '''P''' || '''G''' || '''U''' ||style="width:.8em;"| ''x'' || '''P''' || '''G''' || '''U''' ||style="width:.8em;"| ''x''
|-
| [[File:BlackNode.svg|13px]] || || || || [[#Insert case 1|'''I1''']] || || || || || || || {{ya}} ||
|-
| [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || || [[#Insert case 2|'''I2''']] || || '''N''':='''G''' || {{dunno}} || || || || {{dunno}} || 2
|-
| — || || || || [[#Insert case 3|'''I3''']] || || || || || || || {{ya}} ||
|-
| [[File:RedNode.svg]] || — || || || [[#Insert case 4|'''I4''']] || || || [[File:BlackNode.svg|13px]] || || || || {{ya}} ||
|-
| [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || i || [[#Insert case 5|'''I5''']] || '''P'''↶'''N''' || '''N''':='''P''' || [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || o || '''I6''' || 0
|-
| [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || o || [[#Insert case 6|'''I6''']] || '''P'''↷'''G''' || || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || || {{ya}} ||
|-
|colspan="13" style="text-align:left;font-size:smaller;"| 
;Insertion: This synopsis shows in its ''before'' columns, that all<br/>possible cases<ref name="cases">The same partitioning is found in [[#Pfaff a|Ben Pfaff]].</ref> of constellations are covered.
|}
* In the diagrams, '''P''' is used for '''N'''’s parent, '''G''' for its grandparent, and '''U''' for its uncle. In the table, "—" indicates the root.
* The diagrams show the parent node '''P''' as the left child of its parent '''G''' even though it is possible for '''P''' to be on either side. The sample code covers both possibilities by means of the side variable <code>dir</code>.
* The diagrams show the cases where '''P''' is red also, the red-violation.
* The column ''x'' indicates the change in child direction, i.e. o (for "outer") means that '''P''' and '''N''' are both left or both right children, whereas i (for "inner") means that the child direction changes from '''P'''’s to '''N'''’s.
* The [[column group]] ''before'' defines the case, whose name is given in the column ''case''. Thereby possible values in cells left empty are ignored. So in case '''[[#Insert case 2|I2]]''' the sample code covers both possibilities of child directions of '''N''', although the corresponding diagram shows only one.
* The rows in the synopsis are ordered such that the coverage of all possible RB cases is easily comprehensible.
* The column ''rotation'' indicates whether a rotation contributes to the rebalancing.
* The column ''assignment'' shows an assignment of '''N''' before entering a subsequent step. This possibly induces a reassignment of the other nodes '''P''', '''G''', '''U''' also.
* If something has been changed by the case, this is shown in the column group ''after''.
* A [[File:Check-green.svg|13px]] sign in column ''next'' signifies that the rebalancing is complete with this step. If the column ''after'' determines exactly one case, this case is given as the subsequent one, otherwise there are question marks.
* In case '''[[#Insert case 2|2]]''' the problem of rebalancing is escalated <math>\Delta h=2</math> tree levels or 1 black level higher in the tree, in that the grandfather '''G''' becomes the new current node '''N'''. So it takes maximally <math>\tfrac{h}2</math> steps of iteration to repair the tree (where {{mvar|h}} 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 [[#amortized|amortized constant]].
* Rotations occur in cases '''I6''' and '''I5 + I6''' – outside the loop. Therefore, at most two rotations occur in total.

==== Insert case 1 ====
The current node’s parent '''P''' is black, so [[#req3|requirement 3]] holds. Requirement 4 holds also according to the [[#loopInvariantI|loop invariant]].
==== Insert case 2 ====
<!--actions: [e=entry,][r=rotation,][c=color,][a=reassign]-->
<!--actions: eca-->
{{Multiple image
| align             = right
| state             = expanded
| image1            = Red-black_tree_insert_case_B0t.svg
| width1            = 85
| caption1          = <small>first iteration</small>
| image2            = Red-black_tree_perpendic_579_switch.svg
| width2            = 9
| image3            = Red-black_tree_insert_case_B1t.svg
| width3            = 97
| caption3          = <small>higher iteration</small>
| footer            = Insert Case 2
}}

If both the parent '''P''' and the uncle '''U''' are red, then both of them can be repainted black and the grandparent '''G''' becomes red for maintaining [[#req4|requirement 4]]. 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 '''G''' may now violate requirement 3, if it has a red parent. After relabeling '''G''' to '''N''' the [[#loopInvariantI|loop invariant]] is fulfilled so that the rebalancing can be iterated on one black level (= 2 tree levels) higher.
==== Insert case 3 ====
[[#Insert case 2|Insert case 2]] has been executed for <math>\tfrac{h-1}2</math> times and the total height of the tree has increased by 1, now being {{mvar|h}}&thinsp;.
The current node '''N''' is the (red) root of the tree, and all RB-properties are satisfied.
==== Insert case 4 ====
The parent '''P''' is red and the root.
Because '''N''' is also red, requirement 3 is violated. But after switching '''P'''’s color the tree is in RB-shape.
The black height of the tree increases by 1.
==== Insert case 5 ====
<!--actions: era-->
{{Multiple image
| align             = left
| state             = expanded
| image1            = Red-black_tree_insert_case_C0.svg
| width1            = 64
| caption1          = <small>first iteration</small>
| image2            = Red-black_tree_perpendic_639era_switch.svg
| width2            = 9
| image3            = Red-black_tree_insert_case_C1.svg
| width3            = 97
| caption3          = <small>higher iteration</small>
| footer            = Insert Case 5
}}

The parent '''P''' is red but the uncle '''U''' is black. The ultimate goal is to rotate the parent node '''P''' to the grandparent position, but this will not work if '''N''' is an "inner" grandchild of '''G''' (i.e., if '''N''' is the left child of the right child of '''G''' or the right child of the left child of '''G'''). A {{nowrap|<code>dir</code>-rotation}} at '''P''' switches the roles of the current node '''N''' and its parent '''P'''. The rotation adds paths through '''N''' (those in the subtree labeled '''2''', see diagram) and removes paths through '''P''' (those in the subtree labeled '''4'''). But both '''P''' and '''N''' are red, so [[#req4|requirement 4]] is preserved. Requirement 3 is restored in case 6.

{{Multiple image
| align             = right
| state             = expanded
| image1            = Red-black_tree_insert_case_D0rot.svg
| width1            = 64
| caption1          = <small>first iteration</small>
| image2            = Red-black_tree_perpendic_639erc_switch.svg
| width2            = 9
| image3            = Red-black_tree_insert_case_D1rot.svg
| width3            = 97
| caption3          = <small>higher iteration</small>
| footer            = Insert Case 6
}}

==== Insert case 6 ====
<!--actions: erc-->The current node '''N''' is now certain to be an "outer" grandchild of '''G''' (left of left child or right of right child). Now {{nowrap|<code>(1-dir)</code>-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 [[#req3|requirement 3]] was violated. After switching the colors of '''P''' and '''G''' the resulting tree satisfies requirement 3. [[#req4|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 algorithm|in-place]].

=== Removal ===
==== Simple cases ====
* When the deleted node has '''2 children''' (non-NULL), 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-NULL) or no child at all.
* When the deleted node has '''only 1 child''' (non-NULL). In this case, just replace the node with its child, and color it black.
** The single child (non-NULL) must be red according to [[#con5|conclusion 5]], and the deleted node must be black according to [[#req3|requirement 3]].
* When the deleted node '''has no children''' (both NULL) and is the root, replace it with NULL. The tree is empty.
* When the deleted node '''has no children''' (both NULL), and '''is red''', simply remove the leaf node.
* When the deleted node '''has no children''' (both NULL), and '''is black''', deleting it will create an imbalance, and requires a rebalance, as covered in the next section.

==== Removal of a black non-root leaf ====
The complex case is when '''N''' is not the root, colored black and has no proper child (⇔ only NULL children).
In the first iteration, '''N''' is replaced by NULL.

<syntaxhighlight lang="c" line="1" linelinks="remove" copy>
void remove(Tree* tree, Node* node) {
	Node* parent = node->parent;

	Node* sibling;
	Node* close_nephew;
	Node* distant_nephew;

	Direction dir = direction(node);

	parent->child[dir] = NULL;
	goto start_balance;

	do {
		dir = direction(node);
start_balance:
		sibling = parent->child[1 - dir];
		distant_nephew = sibling->child[1 - dir];
		close_nephew = sibling->child[dir];
		if (sibling->color == RED) {
			// Case #3
			rotate_subtree(tree, parent, dir);
			parent->color = RED;
			sibling->color = BLACK;
			sibling = close_nephew;

			distant_nephew = sibling->child[1 - dir];
			if (distant_nephew && distant_nephew->color == RED) {
				goto case_6;
            }
			close_nephew = sibling->child[dir];
			if (close_nephew && close_nephew->color == RED) {
				goto case_5;
            }

			// Case #4
			sibling->color = RED;
			parent->color = BLACK;
			return;
		}

		if (distant_nephew && distant_nephew->color == RED) {
			goto case_6;
        }

		if (close_nephew && close_nephew->color == RED) {
			goto case_5;
        }

		if (!parent) {
		    // Case #1
            return;
        }

		if (parent->color == RED) {
			// Case #4
			sibling->color = RED;
			parent->color = BLACK;
			return;
		}

		// Case #2
		sibling->color = RED;
		node = parent;

	} while (parent = node->parent);

case_5:

	rotate_subtree(tree, sibling, 1 - dir);
	sibling->color = RED;
	close_nephew->color = BLACK;
	distant_nephew = sibling;
	sibling = close_nephew;

case_6:

	rotate_subtree(tree, parent, dir);
	sibling->color = parent->color;
	parent->color = BLACK;
	distant_nephew->color = BLACK;
	return;
}</syntaxhighlight>

{{Anchor|loopInvariantD}}The rebalancing loop of the delete operation has the following [[Loop invariant|invariant]]:
* At the beginning of each iteration the black height of '''N''' equals the iteration number minus one, which means that in the first iteration it is zero and that '''N''' is a true black node [[File:BlackNode.svg|13px]] in higher iterations.
* The number of black nodes on the paths through '''N''' is one less than before the deletion, whereas it is unchanged on all other paths, so that there is a [[#ViolB|black-violation]] at '''P''' if other paths exist.
* All other properties (including [[#req3|requirement 3]]) are satisfied throughout the tree.

==== Notes to the delete diagrams ====
{| class="wikitable floatright" style="text-align:center;"
|- style="background:#E8E8E8;font-size:smaller;"
|colspan="4"| ''before'' ||rowspan="2"|''case''||rowspan="2" {{verth|''rotation''}} ||rowspan="2" {{verth|''assignment''}} ||colspan="4"|''after'' ||rowspan="2"|''next''||rowspan="2"| &Delta;''h''
|- style="background:#E8E8E8"
| '''P''' || '''C''' || '''S''' || '''D''' || '''P''' || '''C''' || '''S''' || '''D'''
|-
| — || || || || [[#Delete case 1|'''D1''']] || || || || || ||  ||  {{ya}}  ||
|-
| [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[#Delete case 2|'''D2''']] || || '''N''':='''P''' || {{dunno}} || || || || {{dunno}} || 1
|-
|rowspan="3"| [[File:BlackNode.svg|13px]] ||rowspan="3"| [[File:BlackNode.svg|13px]] ||rowspan="3"| [[File:RedNode.svg]] ||rowspan="3"| [[File:BlackNode.svg|13px]] ||rowspan="3"| [[#Delete case 3|'''D3''']] ||rowspan="3"| '''P'''↶'''S''' ||rowspan="3"| '''N''':='''N''' || [[File:RedNode.svg]] || || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || '''D6''' || 0
|-
|  [[File:RedNode.svg]] || [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || '''D5''' || 0
|-
| [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || '''D4''' || 0
|-
| [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[#Delete case 4|'''D4''']] || || || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] ||  {{ya}}  ||
|-
| [[File:RedOrBlackNode.svg|13px]] || [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[#Delete case 5|'''D5''']] || '''C'''↷'''S''' || '''N''':='''N''' || [[File:RedOrBlackNode.svg]] || || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || '''D6''' || 0
|-
| [[File:RedOrBlackNode.svg|13px]] || || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || [[#Delete case 6|'''D6''']] || '''P'''↶'''S''' || || [[File:BlackNode.svg|13px]] || || [[File:RedOrBlackNode.svg]] || [[File:BlackNode.svg|13px]] ||  {{ya}}  ||
|-
|colspan="13" style="text-align:left; font-size:smaller;"| 
;Deletion: This synopsis shows in its ''before'' columns, that all<br/>possible cases<ref name="cases"/> of color constellations are covered.
|}
* In the diagrams below, '''P''' is used for '''N'''’s parent, '''S''' for the sibling of '''N''', '''C''' (meaning ''close'' nephew) for '''S'''’s child in the same direction as '''N''', and '''D''' (meaning ''distant'' nephew) for '''S'''’s other child ('''S''' cannot be a NULL node in the first iteration, because it must have black height one, which was the black height of '''N''' before its deletion, but '''C''' and '''D''' may be NULL nodes).
* The diagrams show the current node '''N''' as the left child of its parent '''P''' even though it is possible for '''N''' to be on either side. The code samples cover both possibilities by means of the side variable <code>dir</code>.
* At the beginning (in the first iteration) of removal, '''N''' is the NULL node replacing the node to be deleted. Because its location in parent’s node is the only thing of importance, it is symbolised by [[File:NilBlue.svg|8px]] (meaning: the current node '''N''' is a NULL node and left child) in the left column of the delete diagrams. As the operation proceeds also proper nodes (of black height &ge; 1) may become current (see e.g. case '''[[#Delete case 2|2]]''').
* By counting the black bullets ([[File:BlackNode.svg|13px]] and [[File:TriangleTop.svg]]) in a delete diagram it can be observed that the paths through '''N''' have one bullet less than the other paths. This means a black-violation at '''P'''—if it exists.
* The color constellation in column group ''before'' defines the case, whose name is given in the column ''case''. Thereby possible values in cells left empty are ignored.
* The rows in the synopsis are ordered such that the coverage of all possible RB cases is easily comprehensible.
* The column ''rotation'' indicates whether a rotation contributes to the rebalancing.
* The column ''assignment'' shows an assignment of '''N''' before entering a subsequent iteration step. This possibly induces a reassignment of the other nodes '''P''', '''C''', '''S''', '''D''' also.
* If something has been changed by the case, this is shown in the column group ''after''.
* A [[File:Check-green.svg|13px]] sign in column ''next'' signifies that the rebalancing is complete with this step. If the column ''after'' determines exactly one case, this case is given as the subsequent one, otherwise there are question marks.
* The loop is where the problem of rebalancing is escalated <math>\Delta h=1</math> level higher in the tree in that the parent '''P''' becomes the new current node '''N'''. So it takes maximally {{mvar|h}} iterations to repair the tree (where {{mvar|h}} 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 [[#amortized|amortized constant]]. (Just as an aside: Mehlhorn & Sanders point out: "AVL trees do ''not'' support constant amortized update costs."<ref name="Mehlhorn2008"/>{{rp|165,158}} This is true for the rebalancing after a deletion, but not AVL insertion.<ref>Dinesh P. Mehta, Sartaj Sahni (Ed.) ''Handbook of Data Structures and Applications'' 10.4.2</ref>)
* Out of the body of the loop there are exiting branches to the cases '''[[#Delete case 3|3]]''', '''[[#Delete case 6|6]]''', '''[[#Delete case 5|5]]''', '''[[#Delete case 4|4]]''', and '''[[#Delete case 1|1]]'''; section [[#Delete case 3|"Delete case 3"]] of its own has three different exiting branches to the cases '''6''', '''5''' and '''4'''.
* Rotations occur in cases '''6''' and '''5 + 6''' and '''3 + 5 + 6''' – all outside the loop. Therefore, at most three rotations occur in total.

==== Delete case 1 ====
The current node '''N''' 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.
==== Delete case 2 ====
<!--actions: eca-->
{{Multiple image
| align             = right
| state             = expanded
| header_align      = center
| header            = [[#explan|→ <small>Explanation of symbols</small>]]
| image1            = Red-black_tree_delete_case_B0t.svg
| width1            = 71
| caption1          = <small>first iteration</small>
| image2            = Red-black_tree_perpendic_579_switch.svg
| width2            = 9
| image3            = Red-black_tree_delete_case_B1t.svg
| width3            = 117
| caption3          = <small>higher iteration</small>
| footer            = Delete case D2
}}

'''P''', '''S''', and '''S'''’s children are black. After painting '''S''' red all paths passing through '''S''', which are precisely those paths ''not'' passing through '''N''', have one less black node. Now all paths in the subtree rooted by '''P''' have the same number of black nodes, but one fewer than the paths that do not pass through '''P''', so [[#req4|requirement 4]] may still be violated. After relabeling '''P''' to '''N''' the [[#loopInvariantD|loop invariant]] is fulfilled so that the rebalancing can be iterated on one black level (= 1 tree level) higher.
==== Delete case 3 ====
<!--actions: rca-->
{{Multiple image
|align=left
|state=expanded
|image1=Red-black_tree_delete_case_A0rot3.svg
|width1=91
|caption1=<small>first iteration</small>
|image2=Red-black_tree_perpendic_865_switch.svg
|width2=9
|image3=Red-black_tree_delete_case_A1rot3.svg
|width3=117
|caption3=<small>higher iteration</small>
|footer=Delete case D3
}}

The sibling '''S''' is red, so '''P''' and the nephews '''C''' and '''D''' have to be black. A {{nowrap|<code>dir</code>-rotation}} at '''P''' turns '''S''' into '''N'''’s grandparent.
Then after reversing the colors of '''P''' and '''S''', the path through '''N''' is still short one black node. But '''N''' now has a red parent '''P''' and after the reassignment a black sibling '''S''', so the transformations in cases 4, 5, or 6 are able to restore the RB-shape.
==== Delete case 4 ====
<!--actions: ec-->
{{Multiple image
|align=right
|state=expanded
|image1=Red-black_tree_delete_case_C0.svg
|width1=71
|caption1=<small>first iteration</small>
|image2=Red-black_tree_perpendic_419_switch.svg
|width2=9
|image3=Red-black_tree_delete_case_C1.svg
|width3=117
|caption3=<small>higher iteration</small>
|footer=Delete case D4
}}

The sibling '''S''' and '''S'''’s children are black, but '''P''' is red. Exchanging the colors of '''S''' and '''P''' does not affect the number of black nodes on paths going through '''S''', but it does add one to the number of black nodes on paths going through '''N''', making up for the deleted black node on those paths.

==== Delete case 5 ====
<!--actions: rca-->
{{Multiple image
|align=left
|state=expanded
|image1=Red-black_tree_delete_case_D0rot.svg
|width1=71
|caption1=<small>first iteration</small>
|image2=Red-black_tree_perpendic_919_switch.svg
|width2=9
|image3=Red-black_tree_delete_case_D1rot.svg
|width3=117
|caption3=<small>higher iteration</small>
|footer=Delete case D5
}}

The sibling '''S''' is black, '''S'''’s close child '''C''' is red, and '''S'''’s distant child '''D''' is black. After a {{nowrap|<code>(1-dir)</code>-rotation}} at '''S''' the nephew '''C''' becomes '''S'''’s parent and '''N'''’s new sibling. The colors of '''S''' and '''C''' are exchanged.
All paths still have the same number of black nodes, but now '''N''' has a black sibling whose distant child is red, so the constellation is fit for case D6. Neither '''N''' nor its parent '''P''' are affected by this transformation, and '''P''' may be red or black ([[File:RedOrBlackNode.svg]] in the diagram).
==== Delete case 6 ====
<!--actions: erc-->
{{Multiple image
|align=right
|state=expanded
|image1=Red-black_tree_delete_case_E0rot.svg
|width1=71
|caption1=<small>first iteration</small>
|image2=Red-black_tree_perpendic_639erc_switch.svg
|width2=9
|image3=Red-black_tree_delete_case_E1rot.svg
|width3=96
|caption3=<small>higher iteration</small>
|footer=Delete case D6
}}

The sibling '''S''' is black, '''S'''’s distant child '''D''' is red. After a {{nowrap|<code>dir</code>-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. The whole subtree still has the same color at its root '''S''', namely either red or black ([[File:RedOrBlackNode.svg]] in the diagram), which refers to the same color both before and after the transformation. This way [[#req3|requirement 3]] is preserved. The paths in the subtree not passing through '''N''' (i.o.w. passing through '''D''' and node '''3''' in the diagram) pass through the same number of black nodes as before, but '''N''' now has one additional black ancestor: either '''P''' has become black, or it was black and '''S''' was added as a black grandparent. Thus, the paths passing through '''N''' pass through one additional black node, so that [[#req4|requirement 4]] is restored and the total tree is in RB-shape.

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 algorithm|in-place]].

== Proof of bounds ==
[[File:5 minimal red-black trees nN.svg|thumb|right|320px|Figure 2: Red–black trees RB<sub>''h''</sub> of heights ''h''=1,2,3,4,5,<br/>each with minimal number 1,2,4,6 resp. 10 of nodes.]]
For <math>h\in\N</math> there is a red–black tree of height <math>h</math> with
:{|
|-
|<math>m_h</math> ||colspan=2| <math>= 2^{\lfloor(h+1)/2\rfloor} + 2^{\lfloor h/2 \rfloor} - 2</math>
|-
|rowspan=2| ||rowspan=2;style="vertical-align:bot"| <math>= \Biggl\{</math> ||style="vertical-align:top"| <math>2 \cdot 2^{\tfrac{h}2}-2 = 2^{\tfrac{h}2+1}-2</math> || &nbsp; &nbsp; &nbsp; ||style="vertical-align:bot"| if <math>h</math> even
|-
|style="vertical-align:top"| <math>3 \cdot 2^{\tfrac{h-1}2}-2</math> || ||style="vertical-align:bot"| if <math>h</math> odd
|}
nodes (<math>\lfloor \, \rfloor</math> is the [[Floor and ceiling functions|floor function]]) and there is no red–black tree of this tree height with fewer nodes—therefore it is '''minimal'''.<br/>Its black height is &thinsp; <math>\lceil h/2\rceil</math> &thinsp; (with black root) or for odd <math>h</math> (then with a red root) also &thinsp; <math>(h-1)/2~.</math>

;Proof
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.<ref name="Algs4"/>{{rp|444 Proof sketch}} If a node is taken off this tree it either loses height or some RB property.

The RB tree of height <math>h=1</math> with red root is minimal. This is in agreement with
: <math>m_1 = 2^{\lfloor (1+1)/2\rfloor} \!+\!2^{\lfloor 1/2 \rfloor} \!\!-\!\!2 = 2^1\!+\!2^0\!\!-\!\!2 = 1~.</math>

A minimal RB tree (RB<sub>''h''</sub> in figure 2) of height <math>h>1</math> has a root whose two child subtrees are of different height. The higher child subtree is also a minimal RB tree, {{nowrap|RB<sub>''h''–1</sub>,}} containing also a longest path that defines its height {{nowrap|<math>h\!\!-\!\!1 </math>;}} it has <math>m_{h-1}</math> nodes and the black height <math>\lfloor(h\!\!-\!\!1)/2\rfloor =: s .</math> The other subtree is a [[Binary tree#Types of binary trees|perfect binary tree]] of (black) height <math>s</math> having <math>2^s\!\!-\!\!1=2^{\lfloor(h-1)/2\rfloor}\!\!-\!\!1</math> black nodes—and no red node. Then the number of nodes is by [[Mathematical induction|induction]]
{|
|-
|style="width:1.0em;"| || <math>m_h</math> || <math>=</math> || <math>(m_{h-1})</math> ||style="width:4em;text-align:center;"| <math>+</math> || <math>(1)</math> ||style="width:4em;text-align:center;"| <math>+</math> || <math>(2^{\lfloor(h-1)/2\rfloor}-1)</math>
|-
| || || || (higher subtree) || || (root) || || (second subtree)
|-
|colspan="8"| resulting in
|-
| || <math>m_h</math> || <math>=</math> || <math>(2^{\lfloor h/2 \rfloor} + 2^{\lfloor(h-1)/2\rfloor} - 2)</math> ||style="text-align:center;"| <math>+</math> ||colspan="2" style="text-align:right;"| <math>2^{\lfloor(h-1)/2\rfloor}</math>
|-
| || || <math>=</math> ||colspan="8"| <math>2^{\lfloor h/2 \rfloor} + 2^{\lfloor(h+1)/2\rfloor} - 2</math>&nbsp;&nbsp;■
|}

The [[Graph of a function|graph]] of the function <math>m_h</math> is [[Convex function|convex]] and [[Piecewise linear function|piecewise linear]] with breakpoints at <math>(h=2k\;|\;m_{2k}=2 \cdot 2^k\!-\!2)</math> where <math>k \in \N .</math> The function has been tabulated as <math>m_h=</math> A027383(''h''–1) for <math>h\geq 1</math> {{nowrap|{{OEIS|A027383}}.}}

;Solving the function for <math>h</math>
The inequality <math>9>8=2^3</math> leads to <math>3 > 2^{3/2}</math>, which for odd <math>h</math> leads to
: <math>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</math>.
So in both, the even and the odd case, <math>h</math> is in the interval
{|
|-
|style="width:1.0em;"| ||style="text-align:right;"| <math>\log_2(n+1) </math> ||style="width:8em;text-align:center"| <math>\leq h \leq </math> || <math>2 \log_2(n+2)-2 = 2 \log_2 (n/2 +1) </math> ||style="width:12em;text-align:right"| <math>\bigl[ < 2 \log_2(n+1) \; \bigr]</math>
|-
| || (perfect binary tree) || ||style="text-align:left;"| (minimal red–black tree)
|}
with <math>n </math> being the number of nodes.<ref>Equality at the upper bound holds for the minimal RB trees RB<sub>2''k''</sub> of even height <math>2 \cdot k </math> with <math>n = 2 \cdot 2^k-2 </math> nodes and only for those. So the inequality is marginally more precise than the widespread <math>h < 2 \log_2(n+1) ,</math> e.g. in [[#Cormen|Cormen]] p. 264.<br/>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 black.)</ref>

;Conclusion
A red–black tree with <math>n</math> nodes (keys) has tree height <math>h \in O(\log n) .</math>

== Set operations and bulk operations ==
In addition to the single-element insert, delete and lookup operations, several set operations have been defined on {{nowrap|red–black trees:}} [[Union (set theory)|union]], [[Intersection (set theory)|intersection]] and [[set difference]]. Then fast ''bulk'' operations on insertions or deletions can be implemented based on these set functions. These set operations rely on two helper operations, ''Split'' and ''Join''. With the new operations, the implementation of red–black trees can be more efficient and highly-parallelizable.<ref name="join-based">{{cite book
 | last1=Blelloch | first1=Guy E. | author-link1=Guy Blelloch
 | last2=Ferizovic | first2=Daniel
 | last3=Sun | first3=Yihan | author-link3=Yihan Sun
 | doi=10.1145/2935764.2935768
 | isbn=978-1-4503-4210-0
 | pages=253–264
 | publisher=ACM
 | title=Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
 | chapter=Just Join for Parallel Ordered Sets | year=2016 | arxiv=1602.02120
 | s2cid=2897793 | contribution-url=http://www.cs.cmu.edu/~yihans/papers/join.pdf
 }}.</ref> 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 '''black height'''.

* ''Join'': The function ''Join'' is on two red–black trees {{math|''t''<sub>1</sub>}} and {{math|''t''<sub>2</sub>}} and a key {{mvar|k}}, where {{math|''t''<sub>1</sub> < ''k'' < ''t''<sub>2</sub>}}, i.e. all keys in {{math|''t''<sub>1</sub>}} are less than {{mvar|k}}, and all keys in {{math|''t''<sub>2</sub>}} are greater than {{mvar|k}}. It returns a tree containing all elements in {{math|''t''<sub>1</sub>}}, {{math|''t''<sub>2</sub>}} also as {{mvar|k}}.
: If the two trees have the same black height, ''Join'' simply creates a new node with left subtree {{math|''t''<sub>1</sub>}}, root {{mvar|k}} and right subtree {{math|''t''<sub>2</sub>}}. If both {{math|''t''<sub>1</sub>}} and {{math|''t''<sub>2</sub>}} have black root, set {{mvar|k}} to be red. Otherwise {{mvar|k}} is set black. 
: If the black heights are unequal, suppose that {{math|''t''<sub>1</sub>}} has larger black height than {{math|''t''<sub>2</sub>}} (the other case is symmetric). ''Join'' follows the right spine of {{math|''t''<sub>1</sub>}} until a black node {{mvar|c}}, which is balanced with {{math|''t''<sub>2</sub>}}. At this point a new node with left child {{mvar|c}}, root {{mvar|k}} (set to be red) and right child {{math|''t''<sub>2</sub>}} 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 is the difference of the black heights between the two input trees.

* ''Split'': To split a red–black tree into two smaller trees, those smaller than key {{mvar|x}}, and those larger than key {{mvar|x}}, first draw a path from the root by inserting {{mvar|x}} into the red–black tree. After this insertion, all values less than {{mvar|x}} will be found on the left of the path, and all values greater than {{mvar|x}} will be found on the right. By applying ''Join'', 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.
: For some applications, ''Split'' also returns a Boolean value denoting if {{mvar|x}} appears in the tree. The cost of ''Split'' is <math>O(\log n) ,</math> 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 ''join'' operation, such as an [[AVL tree]].

The join algorithm is as follows:

 '''function''' joinRightRB(T<sub>L</sub>, k, T<sub>R</sub>):
     '''if''' (T<sub>L</sub>.color=black) and (T<sub>L</sub>.blackHeight=T<sub>R</sub>.blackHeight):
         '''return''' Node(T<sub>L</sub>,⟨k,red⟩,T<sub>R</sub>)
     T'=Node(T<sub>L</sub>.left,⟨T<sub>L</sub>.key,T<sub>L</sub>.color⟩,joinRightRB(T<sub>L</sub>.right,k,T<sub>R</sub>))
     '''if''' (T<sub>L</sub>.color=black) and (T'.right.color=T'.right.right.color=red):
         T'.right.right.color=black;
         '''return''' rotateLeft(T')
     '''return''' T' /* T{{single+single}}[recte T'] */
 
 '''function''' joinLeftRB(T<sub>L</sub>, k, T<sub>R</sub>):
   /* symmetric to joinRightRB */
 
 '''function''' join(T<sub>L</sub>, k, T<sub>R</sub>):
     '''if''' T<sub>L</sub>.blackHeight>T<sub>R</sub>.blackHeight:
         T'=joinRightRB(T<sub>L</sub>,k,T<sub>R</sub>)
         '''if''' (T'.color=red) and (T'.right.color=red):
             T'.color=black
         '''return''' T'
     '''if''' T<sub>R</sub>.blackHeight>T<sub>L</sub>.blackHeight:
         /* symmetric */
     '''if''' (T<sub>L</sub>.color=black) and (T<sub>R</sub>.color=black):
         '''return''' Node(T<sub>L</sub>,⟨k,red⟩,T<sub>R</sub>)
     '''return''' Node(T<sub>L</sub>,⟨k,black⟩,T<sub>R</sub>)

The split algorithm is as follows:

 '''function''' split(T, k):
     '''if''' (T = NULL) '''return''' (NULL, false, NULL)
     '''if''' (k = T.key) '''return''' (T.left, true, T.right)
     '''if''' (k < T.key):
         (L',b,R') = split(T.left, k)
         '''return''' (L',b,join(R',T.key,T.right))
     (L',b,R') = split(T.right, k)
     '''return''' (join(T.left,T.key,L'),b,T.right)

The union of two red–black trees {{math|''t''<sub>1</sub>}} and {{math|''t''<sub>2</sub>}} representing sets {{mvar|A}} and {{mvar|B}}, is a red–black tree {{mvar|t}} that represents {{math|''A'' ∪ ''B''}}. The following recursive function computes this union:

 '''function''' union(t<sub>1</sub>, t<sub>2</sub>):
     '''if''' t<sub>1</sub> = NULL '''return''' t<sub>2</sub>
     '''if''' t<sub>2</sub> = NULL '''return''' t<sub>1</sub>
     (L<sub>1</sub>,b,R<sub>1</sub>)=split(t<sub>1</sub>,t<sub>2</sub>.key)
     proc1='''start''':
         T<sub>L</sub>=union(L<sub>1</sub>,t<sub>2</sub>.left)
     proc2='''start''':
         T<sub>R</sub>=union(R<sub>1</sub>,t<sub>2</sub>.right)
     '''wait all''' proc1,proc2
     '''return''' join(T<sub>L</sub>, t<sub>2</sub>.key, T<sub>R</sub>)

Here, ''split'' is presumed to return two trees: one holding the keys less its input key, one holding the greater keys. (The algorithm is [[persistent data structure|non-destructive]], but an in-place destructive version exists also.)

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. 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 ''Split'' calls ''Join'' but does not deal with the balancing criteria of red–black trees directly, such an implementation is usually called the [[Join-based tree algorithms|"join-based" implementation]].

The complexity of each of union, intersection and difference is <math>O\left(m \log \left({n\over m}+1\right)\right)</math> for two red–black trees of sizes <math>m</math> and <math>n(\ge m)</math>. 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 [[parallel programming|in parallel]] with a [[Analysis of parallel algorithms|parallel depth]] <math>O(\log m \log n)</math>.<ref name="join-based"/> When <math>m=1</math>, the join-based implementation has the same computational [[directed acyclic graph]] (DAG) as single-element insertion and deletion if the root of the larger tree is used to split the smaller tree.

== Parallel algorithms ==
Parallel algorithms for constructing red–black trees from sorted lists of items can run in constant time or <math>O(\log \log n)</math> time, depending on the computer model, if the number of processors available is asymptotically proportional to the number <math>n</math> of items where <math>n\to\infty</math>. Fast search, insertion, and deletion parallel algorithms are also known.<ref>
{{cite journal
 | journal=Theoretical Computer Science
 | title=Parallel algorithms for red–black trees
 | first1=Heejin |last1=Park |first2=Kunsoo |last2=Park
 | volume=262
 | issue=1–2
 | pages=415–435
 | year=2001
 | doi=10.1016/S0304-3975(00)00287-5
 |quote=Our parallel algorithm for constructing a red–black tree from a sorted list of <math>n</math> items runs in <math>O(1)</math> time with <math>n</math> processors on the CRCW PRAM and runs in <math>O(\log \log n)</math> time with <math>n / \log \log n</math> processors on the EREW PRAM.
 | doi-access=free
 }}</ref>

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

=== Parallel bulk operations ===
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.

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 [[2–3 tree]], [[2–3–4 tree]] and [[(a,b)-tree]]. 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 <math>I</math> into a tree <math>T</math>.

==== Join-based ====
This approach can be applied to every sorted sequence data structure that supports efficient join- and split-operations.<ref>{{cite book
 | last=Sanders
 | first=Peter
 | editor1-last=Mehlhorn
 | editor1-first=Kurt
 | editor2-last=Dietzfelbinger
 | editor2-first=Martin
 | editor3-last=Dementiev
 | editor3-first=Roman
 | year=2019
 | title=Sequential and Parallel Algorithms and Data Structures : The Basic Toolbox
 | series=Springer eBooks
 | location=Cham
 | publisher=Springer
 | pages=252–253
 | isbn=9783030252090
| doi=10.1007/978-3-030-25209-0
 | s2cid=201692657
 }}</ref>
The general idea is to split {{mvar|I}} and {{mvar|T}} in multiple parts and perform the insertions on these parts in parallel.

# First the bulk {{mvar|I}} of elements to insert must be sorted.
# After that, the algorithm splits {{mvar|I}} into <math>k \in \mathbb{N}^+</math> parts <math>\langle I_1, \cdots, I_k \rangle</math> of about equal sizes.
# Next the tree {{mvar|T}} must be split into {{mvar|k}} parts <math>\langle T_1, \cdots, T_k \rangle</math> in a way, so that the ranges of <math>I_m</math> and <math>T_n</math> overlap for corresponding parts only (<math>m=n</math>); in other words, thanks to the ordering, for every <math>j \in \mathbb{N}^+ | \, 1 \leq j < k</math> following constraints hold:
##<math>\text{last}(I_j) < \text{first}(T_{j + 1})</math>
## <math>\text{last}(T_j) < \text{first}(I_{j + 1})</math>
# Now the algorithm inserts each element of <math>I_j</math> into <math>T_j</math> sequentially. This step must be performed for every {{mvar|j}}, which can be done by up to {{mvar|k}} processors in parallel.
# Finally, the resulting trees will be joined to form the final result of the entire operation.

Note that in Step 3 the constraints for splitting {{mvar|I}} assure that in Step 5 the trees can be joined again and the resulting sequence is sorted.
<gallery widths="400px" heights="250px" perrow="2">
BulkInsert JoinBased InitialTree.svg|initial tree
BulkInsert JoinBased SplitTree.svg|split I and T
BulkInsert JoinBased SplitTreeInserted.svg|insert into the split T
BulkInsert JoinBased JoinedTree.svg|join T
</gallery>

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 [[Join-based tree algorithms#Join2|join2]] is used, which misses the second parameter k.

 '''bulkInsert'''(T, I, k):
     I.sort()
     bulklInsertRec(T, I, k)
 
 '''bulkInsertRec'''(T, I, k):
     '''if''' k = 1:
         '''forall''' e '''in''' I: T.insert(e)
     '''else'''
         m := ⌊size(I) / 2⌋
         (T<sub>1</sub>, _, T<sub>2</sub>) := split(T, I[m])
         bulkInsertRec(T<sub>1</sub>, I[0 .. m], ⌈k / 2⌉)
             || bulkInsertRec(T<sub>2</sub>, I[m + 1 .. size(I) - 1], ⌊k / 2⌋)
         T ← join2(T<sub>1</sub>, T<sub>2</sub>)

===== Execution time =====
Sorting {{mvar|I}} is not considered in this analysis.
:{| 
|-
| #recursion levels || <math>\in O(\log k)</math>
|-
| T(split) + T(join) || <math>\in O(\log |T|)</math>
|-
| insertions per thread || <math>\in O\left(\frac{|I|}{k}\right)</math>
|-
| T(insert) || <math>\in O(\log |T|)</math>
|-
| {{nowrap|1='''T(bulkInsert) with {{mvar|k}} = #processors'''}} || <math>\in O\left(\log k \log |T| + \frac{|I|}{k} \log |T|\right)</math>
|}
This can be improved by using parallel algorithms for splitting and joining.
In this case the execution time is <math>\in O\left(\log |T| + \frac{|I|}{k} \log |T|\right)</math>.<ref>{{cite book
 | last1=Akhremtsev | first1=Yaroslav
 | last2=Sanders | first2=Peter
 | title=2016 IEEE 23rd International Conference on High Performance Computing (HiPC)
 | chapter=Fast Parallel Operations on Search Trees
 | pages=291–300
 | year=2016
 | isbn=978-1-5090-5411-4
 | arxiv=1510.05433
 | doi=10.1109/HiPC.2016.042
 }}</ref>

===== Work =====
:{| 
|-
| #splits, #joins || <math>\in O(k)</math>
|-
| W(split) + W(join) || <math>\in O(\log |T|)</math>
|-
| #insertions || <math>\in O(|I|)</math>
|-
| W(insert) || <math>\in O(\log |T|)</math>
|-
| '''W(bulkInsert)''' || <math>\in O(k \log |T| + |I| \log |T|)</math>
|}

==== Pipelining ====
Another method of parallelizing bulk operations is to use a [[Pipeline (computing)|pipelining]] approach.<ref>{{cite book
 | title=An introduction to parallel algorithms
 | last=Jájá
 | first=Joseph
 | location=Reading, Mass. [u.a.]
 | publisher=Addison-Wesley
 | year=1992
 | isbn=0201548569
 | url=http://zbmath.org/?q=an:0781.68009
 | pages=65–70
| zbl=0781.68009
 }}</ref>
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.

# First the bulk {{mvar|I}} of elements to insert must be sorted.
# For each element in {{mvar|I}} the algorithm locates the according insertion position in {{mvar|T}}. This can be done in parallel for each element <math>\in I</math> since {{mvar|T}} won't be mutated in this process. Now {{mvar|I}} must be divided into subsequences {{mvar|S}} according to the insertion position of each element. For example <math>s_{n, \mathit{left}}</math> is the subsequence of {{mvar|I}} that contains the elements whose insertion position would be to the left of node {{mvar|n}}.
# The middle element <math>m_{n, \mathit{dir}}</math> of every subsequence <math>s_{n, \mathit{dir}}</math> will be inserted into {{mvar|T}} as a new node <math>n'</math>. This can be done in parallel for each <math>m_{n, \mathit{dir}}</math> since by definition the insertion position of each <math>m_{n, \mathit{dir}}</math> is unique. If <math>s_{n, \mathit{dir}}</math> contains elements to the left or to the right of <math>m_{n, \mathit{dir}}</math>, those will be contained in a new set of subsequences {{mvar|S}} as <math>s_{n', \mathit{left}}</math> or <math>s_{n', \mathit{right}}</math>.
# Now {{mvar|T}} 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 <math>\in S</math> have to be updated, if the corresponding nodes are affected by rotations.
#* 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 steps.
#* This step will be applied successively to the black levels above until {{mvar|T}} is fully repaired.
# The steps 3 to 5 will be repeated on the new subsequences until {{mvar|S}} is empty. At this point every element <math>\in I</math> has been inserted. Each application of these steps is called a ''stage''. Since the length of the subsequences in {{mvar|S}} is <math>\in O(|I|)</math> and in every stage the subsequences are being cut in half, the number of stages is <math>\in O(\log |I|)</math>.
#* 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 level.
<gallery perrow="3" widths="250px" heights="180px">
BulkInsert Pipelining InitialTree.svg|Initial tree
BulkInsert Pipelining InsertPositions.svg|Find insert positions
BulkInsert Pipelining Stage1Insert.svg|Stage 1 inserts elements
BulkInsert Pipelining Stage1Repair.svg|Stage 1 begins to repair nodes
BulkInsert Pipelining Stage2Insert.svg|Stage 2 inserts elements
BulkInsert Pipelining Stage2Repair.svg|Stage 2 begins to repair nodes
BulkInsert Pipelining Stage3Insert.svg|Stage 3 inserts elements
BulkInsert Pipelining Stage3Repair1.svg|Stage 3 begins to repair nodes
BulkInsert Pipelining Stage3Repair2.svg|Stage 3 continues to repair nodes
</gallery>

===== Execution time =====
Sorting {{mvar|I}} is not considered in this analysis.
Also, <math>|I|</math> is assumed to be smaller than <math>|T|</math>, otherwise it would be more efficient to construct the resulting tree from scratch.
:{|
|-
| T(find insert position) || <math>\in O(\log |T|)</math>
|-
| #stages || <math>\in O(\log |I|)</math>
|-
| T(insert) + T(repair) || <math>\in O(\log |T|)</math>
|- style="vertical-align:top"
| '''T(bulkInsert) with <math>|I|</math> ~ #processors''' || <math>\in O(\log |I| + 2 \cdot \log |T|)</math><br/><math> = O(\log |T|)</math>
|}

===== Work =====
:{|
|-
| W(find insert positions) || <math>\in O(|I| \log |T|)</math>
|-
| #insertions, #repairs || <math>\in O(|I|)</math>
|-
| W(insert) + W(repair) || <math>\in O(\log |T|)</math>
|- style="vertical-align:top"
| '''W(bulkInsert)''' || <math>\in O(2 \cdot |I| \log |T|)</math><br/><math>= O(|I| \log |T|)</math>
|}

== See also ==
*[[List of data structures]]
*[[Tree data structure]]
*[[Tree rotation]]
*[[Order statistic tree]]
*[[AA tree]], a variation of the red–black tree
*[[Left-leaning red–black tree]]
*[[AVL tree]]
*[[B-tree]] ([[2–3 tree]], [[2–3–4 tree]], [[B+ tree]], [[B*-tree]], [[UB-tree]])
*[[Scapegoat tree]]
*[[Splay tree]]
*[[T-tree]]
*[[WAVL tree]]
*[http://adtinfo.org/ GNU libavl]

== References and notes ==
{{reflist|37em}}

== Further reading ==
*[http://mathworld.wolfram.com/Red-BlackTree.html Mathworld: Red–Black Tree]
*[http://www.eli.sdsu.edu/courses/fall95/cs660/notes/RedBlackTree/RedBlack.html#RTFToC2 San Diego State University: CS 660: Red–Black tree notes], by Roger Whitney
*{{anchor|Pfaff b}} {{cite web |last=Pfaff |first=Ben |title=Performance Analysis of BSTs in System Software |publisher=[[Stanford University]] |date=June 2004 |url=http://www.stanford.edu/~blp/papers/libavl.pdf |ref=none}}

== External links ==
*{{anchor|Pfaff a}}Ben Pfaff: ''An Introduction to Binary Search Trees and Balanced Trees.'' Free Software Foundation, Boston 2004, [https://ftp.gnu.org/gnu/avl/avl-2.0.3.pdf.gz ftp.gnu.org] (PDF gzip; 1662&nbsp;kB)
*[https://web.archive.org/web/20140328232325/http://en.literateprograms.org/Red-black_tree_(C) A complete and working implementation in C]
*[http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-10-red-black-trees-rotations-insertions-deletions/ OCW MIT Lecture on Red-black Trees] by [[Erik Demaine]] 
*{{YouTube|id=_VbTnLV8plU|title=Binary Search Tree Insertion Visualization}} – Visualization of random and pre-sorted data insertions, in elementary binary search trees, and left-leaning red–black trees
*[https://gist.github.com/pallas/10697727 An intrusive red–black tree written in C++]
*Red–black BSTs in [https://algs4.cs.princeton.edu/33balanced/ 3.3 Balanced Search Trees]
*[https://web.archive.org/web/20160722175219/http://algs4.cs.princeton.edu/lectures/33DemoRedBlackBST.mov Red–black BST Demo]

{{CS-Trees}}
{{Data structures}}

{{DEFAULTSORT:Red-Black Tree}}
[[Category:Binary trees]]
[[Category:Search trees]]
[[Category:Amortized data structures]]
[[Category:1972 in computing]]
[[Category:Articles containing proofs]]
[[Category:Articles with example C code]]