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

Balance and Red-Black 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

Rotate

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

Complex 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

Complex 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.

Red-Black Insert

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

Advantages

  • 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.

Disadvantages

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

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

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