Under Construction: Consider this content a preview of the real thing which is coming soon (hopefully).
Prerequisites (click to view)
graph LR
ALG(["fas:fatrophy Red Black Tree fas:fatrophy #160;"])
ASY_ANA(["fas:facheck Asymptotic Analysis #160;"])
click ASY_ANA "./mathasymptoticanalysis"
BT(["fas:facheck Binary Tree #160;"])
click BT "./listdatastructbinarytree"
SBT(["fas:facheck Self Balancing Binary Tree #160;"])
click SBT "./listdatastructselfbaltree"
ASY_ANA>ALG
BT>SBT>ALG
Redblack trees are one of the many strains of Self Balancing Binary Trees. It’s not practical to cover all variations owing to the breadth of topic. However, redblack balancing techniques are representative of the whole. A conception of this data structure will equip one with the mental tools necessary to pursue other alternatives.
History
The Xerox PARC company is famous for many groundbreaking inventions^{1}, the most notable of which is the Graphical User Interface (GUI). It’s not surprising that many algorithms also find their origins there. Two Xerox employees, Robert Sedgewick and Leonidas J. Guibas, published a paper in 1978 entitled A Dichromatic Framework for Balanced Trees^{2} which introduced redblack trees to the world. To borrow an aphorism from Issac Newton, Sedgewick an Guibas were “standing on the shoulders of giants”. They attribute much of their work to Rudolf Bayer’s 1972 paper entitled Symmetric binary BTrees: Data structure and maintenance algorithms^{3}.
A redblack tree is an enhanced binary search tree. The changes required to transform a binary search tree into a redblack tree are strictly additive. That is to say, a redblack tree is a standard binary search tree that maintains additional invariants designed to approximately minimize the height of the tree.
 Every node is designated as either red or black
 The root node is always black
 Red nodes must have black children and parents. Otherwise stated, consecutive red nodes are prohibited
 Every path starting at the root node and ending in a NULL pointer must pass through the same number of black nodes (the path that traverse operations take through the tree when searching for an item that doesn’t exist)
An interesting aside is that the only reasoning behind the choice of the colors red and black is that they made the most ascetically pleasing prints using seventiesera printers. The use of color serves no computational purpose. Any binary state is equally adequate for producing balanced trees.
Although it’s not entirely intuitive from reading these invariants, maintaining them ensures that the height of the tree is $\leq 2\log_{2}(n + 1)$. Consider the simplest possible case: a tree with three nodes. It’s not possible to arrange the nodes in such a way that it is both unbalanced and also a valid redblack tree. See the image below (The image does not provide an exhaustive account of every invalid variation, the reader is invited to extrapolate).
Balance and RedBlack Tree Properties
If maintaining redblack tree properties ensures balance, the question becomes how is it possible to maintain these properties when inserting or deleting items. The answer is by two primary mechanisms: recoloring and rotation. The concept of recoloring is fairly self intuitive: changing the color of a node from red to black or black to red. Rotations are a more complex topic. Conceptually, a rotation is rotating a node to change the number of nodes on either side. The image below depicts the most simple rotation operations possible.
Simple Tree Rotations
Of course, things get more complicated when there are child nodes. Consider the rotation depicted in the image below. The red arrows represent pointers that will be deleted and the blue arrows represent pointers that will be added.
Left Rotation
In order to rotate the root node (50) to the left, three things must happen:
 The parent of the rotation node (50) becomes the parent of the right node (75). In this case, NULL.
 The rotation node’s (50) right pointer is updated to the right node’s left pointer
 The right node’s (75) left pointer changes to the rotation node (50)
A similar process occurs when rotating right. In this example, a branch node (75) is rotated. Consult the image below.
Right Rotation
Much like a left rotation, three things happen in a right rotation.
 The parent (50) of the rotation node (75) becomes the parent of the left node (61).
 The rotation node’s (75) left pointer is updated to the left node’s right pointer (NULL)
 The left node’s (61) right pointer changes to the rotation node (75)
With the preliminary concepts out of the way, it’s finally time to consider an actual a redblack tree insert operation. There are four primary steps:
RedBlack Insert at a High Level
 Insert using the Binary Tree insert algorithm
 Color the new node red
 If the new node’s parent is black, no invariants are broken so terminate
 Restore redblack tree invariants
The first three steps are selfexplanatory while the fourth is fairly complex; therefore, it is the focus for the remainder of this section. Restoring the redblack invariants is a recursive process starting at the inserted node. Below is an outline for the algorithm.
 Parent is black
 terminate
 if root is red, recolor to black
 Uncle is red
 recolor parent black
 recolor uncle black
 recolor grandparent red
 recurse on grandparent
 Uncle is black or NULL
 parent is a left branch
 node is a right branch
 rotate parent left
 recurse on parent
 node is a left branch
 change parent color to black
 change grandparent color to red
 rotate grandparent right
 recurse on node
 node is a right branch
 parent is a right branch or NULL
 node is a left branch
 rotate parent right
 recurse on parent
 node is a right branch
 change parent color it black
 change grandparent color to red
 rotate grandparent left
 recurse on node
 node is a left branch
 parent is a left branch
Don’t worry if this seems a bit overwhelming. It’s normal to review redblack tree insertions several times before comprehension sets in. It’s also difficult to fathom without a concrete example. The image below steps through the process graphically.
In order to keep these concepts as accessible as possible, a few abstruse details were omitted. However, the pseudo code as well as accompanying source code are rigorously complete and should be studied assiduously. With a firm understanding of the redblack trees from a conceptual level, understanding the code should be trivial. Additionally, there are no details of deletions are provided. The reader is encouraged to implement delete on their own.
Asymptotic Complexity
 Insert\Delete: $O(\log_{2}n)$
 Search: $O(\log_{2}n)$
 Enumerate: $O(n + \log_{2}n)$
 Min: $O(\log_{2}n)$
 Max: $O(\log_{2}n)$
 Predecessor: $O(\log_{2}n)$
 Successor: $O(\log_{2}n)$
 Select: $O(\log_{2}n)$
 Rank: $O(\log_{2}n)$
Pseudo Code
global variables:
NULL_NODE = black tree node  replaces all NULL parents and leafs. This
simplifies the algorithm
insert:
T = binary tree
new_node = node to insert into the tree
binary tree insert (see binary tree pseudo code)
new_node>left = NULL_NODE
new_node>right = NULL_NODE
new_node>color = red
node = new_node
while new>node>parent == red:
if node>parent == node>grandparent>left:
uncle = node>grandparent>right
if uncle>color == red:
uncle>color = black
node>parent>color = black
node>grandparent>color = red
node = node>grandparent
else if node = node>parent>right
node = node>parent
left_rotate(node)
else
node>parent>color = black
node>grandparent>color = red
right_rotate(node>grandparent)
else
uncle = node>parent>parent>left
if uncle>color == red:
uncle>color = black
node>parent>color = black
node>grandparent>color = red
node = node>grandparent
else if node = node>parent>left
node = node>parent
left_rotate(node)
else
node>parent>color = black
node>grandparent>color = red
left_rotate(node>grandparent)
T>root>color = black
Source Code
Relevant Files:
Click here for build and run instructions
Advantages
 Binary Tree: Because a redblack tree is essentially an enhanced binary tree, it has the same advantages.
 Search: Optimized for quick search operations. Guaranteed to remain balanced regardless of insertion order.
Disadvantages
 Binary Tree: Because a redblack tree is essentially an enhanced binary tree, it has the same disadvantages.
 Complexity: Added complexity beyond Binary Trees.
Applications
 The Linux Completely Fair Scheduler (CFS)

…or discoveries depending on your philosophical predilection. Do scientific concept exist before they are documented? If you believe they spring into existence in the human mind, then they are inventions. If you believe they are transcendent truths, they are discoveries. In practice, the distinction isn’t significant. ↩

Available online at https://ieeexplore.ieee.org/document/4567957 ↩

Available online at https://link.springer.com/article/10.1007%2FBF00289509 ↩