Red Black Trees

Under Construction: Consider this content a preview of the real thing which is coming soon (hopefully).

Red-black 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, red-black 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 inventions1, 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 Trees2 which introduced red-black 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 B-Trees: Data structure and maintenance algorithms3.

A red-black tree is an enhanced binary search tree. The changes required to transform a binary search tree into a red-black tree are strictly additive. That is to say, a red-black tree is a standard binary search tree that maintains additional invariants designed to approximately minimize the height of the tree.

1. Every node is designated as either red or black
2. The root node is always black
3. Red nodes must have black children and parents. Otherwise stated, consecutive red nodes are prohibited
4. 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 seventies-era 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 red-black 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 Red-Black Tree Properties

If maintaining red-black 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:

1. The parent of the rotation node (50) becomes the parent of the right node (75). In this case, NULL.
2. The rotation node’s (50) right pointer is updated to the right node’s left pointer
3. 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.

1. The parent (50) of the rotation node (75) becomes the parent of the left node (61).
2. The rotation node’s (75) left pointer is updated to the left node’s right pointer (NULL)
3. 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 red-black tree insert operation. There are four primary steps:

Red-Black Insert at a High Level

1. Insert using the Binary Tree insert algorithm
2. Color the new node red
3. If the new node’s parent is black, no invariants are broken so terminate
4. Restore red-black tree invariants

The first three steps are self-explanatory while the fourth is fairly complex; therefore, it is the focus for the remainder of this section. Restoring the red-black invariants is a recursive process starting at the inserted node. Below is an outline for the algorithm.

1. Parent is black
• terminate
• if root is red, recolor to black
2. Uncle is red
• recolor parent black
• recolor uncle black
• recolor grandparent red
• recurse on grandparent
3. 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
• 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

Don’t worry if this seems a bit overwhelming. It’s normal to review red-black 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 red-black 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

Full Repo

Relevant Files:

Click here for build and run instructions

• Binary Tree: Because a red-black 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.