Red Black Trees

A red-black tree is an enhanced binary search tree. All of the constraints, operations, and pseudo code defined in Binary Tree also apply here. In short, the changes required to make a binary tree a red-black tree are additive. Valid red-black trees maintain all Binary Tree properties in addition to the following.

Red-Black Tree Properties (aka invariants)

  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)

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.