Red Black Trees

Red Black Trees are a kind of Binary Search Tree that enforce an additional property onto nodes: color. This additional variable allows insertion and deletion algorithms to rebalance the tree in ways that maintain the BST logarithmic search.

Properties of Red Black Trees

Because they introduce a new color property, Red Black Trees also introduce a rule-set regarding a node's color related to its position. These rules are:

  1. Every node is either Red or Black
  2. The Root node is always Black
  3. Red Nodes cannot have Red children
  4. Every path from node to NULL must contain the same number of black nodes
  5. All NULL nodes are considered to be Black
  6. All newly inserted nodes begin as Red nodes

Visual example of a Red Black Tree

Updated Insertion Algorithm

A visual guide to Red Black Tree insertion repair algorithms

Back

Red Black Trees feature an updated insertion algorithm that balances the tree height by performing repair operations whenever a rule is broken. Usually, the broken rule will be an incorrectly colored root node, or a red parent having a red child, often called a "Double Red violation". Repair operations consist of subtree rotations and color swaps in a specific algorithmically optimal manner.

Step 1: Insertion

The first part of a Red Black Tree insertion is the insertion itself. Because RBTs are themselves Binary Search Trees, they inherit and use the same BST insertion operation. Starting from the root node, the algorithm recursively finds the new node's correct position by comparing the new value to the current value. If the new value is less than the current value, the algorithm checks for children in the left subtree, and if its greater, the algorithm checks the right subtree.

Step 2: Balancing

The 6th listed rule of Red Black Trees creates problems with the 1st and 3rd: If all nodes begin as red, then the first node will be red, thus yielding a tree with a red root. Additionally, if a black root has a right child, and then another right child, there will be a Double Red violation. To combat this, the insertion algorithm contains dedicated code that repairs the tree according to broken rules. To decide which repairs to use, we must look at the newly inserted node's "Aunt" node (it's parent's sibling).

Case A: The Aunt is Red

This case requires a series of color swaps to make the repair. If there is a violation and the Aunt is red, then we know:

A simple solution here is to swap the colors of the parent and aunt to black, and the grandparent to red. This ensures that neither of the grandparent's subtrees will have a rule #4 violation.

However, we aren't finished. We just colored the grandparent red, which could create further Double Red violations. To fix this, we check for property violations, treating the grandparent node as the new "child node". We recursively move back up the tree until there are no further violations.

Case B: The Aunt is Black

As a reminder, NULL nodes are considered black. If there is a violation and the Aunt is black, then we know:

Before changing any node's colors, we must determine the orientation of the child and parent. If they are "jagged" with respect to the grandparent, we must perform a rotation to create a straight descendant line from grandparent to child. Now we can perform the repair.

First we rotate about the grandparent. This could be a right or left rotation, depending on the parent-child relation between the parent and the grandparent. After rotating, we swap the colors of what was the grandparent node and what was the parent node. Every time this case occurs, the repair operation completely repairs the tree -- no further recursion needed.

Updated Deletion Algorithm

A visual guide to Red Black Tree deletion repair alglorithms

Back

Red Black Tree deletion is more complex than insertion because removing a node can create a rule #4 violation. While the initial removal still follows Binary Search Tree deletion rules, additional repair operations are often required to restore Red Black properties. These repairs primarily address violations of the black-height rule and situations involving "Double Black" nodes.

Step 1: Deletion

As with insertion, Red Black Trees begin deletion using standard Binary Search Tree logic. The algorithm searches for the node to be removed. There are three cases:

If the removed node or the node replacing it is red, the operation is simple: we recolor the replacement node black, and no further violations occur. However, if a black node is removed, we introduce a "Double Black" violation that must be repaired.

Step 2: Balancing

A Double Black violation occurs when a black node is removed and replaced by another black node (or NULL). This causes an imbalance in the number of black nodes along paths in the tree. To fix this, we analyze the removed node’s sibling and apply one of several repair cases.

Case A: The Sibling is Red

If the sibling of the Double Black node is red, then we know:

To fix this, we perform a rotation about the parent in the direction of the Double Black node. Then, we swap the colors of the parent and sibling. This transforms the tree into a configuration where the sibling is now black, allowing us to proceed to another case.

Case B: The Sibling is Black with Black Children

If the sibling is black and both of its children are black (or NULL), then:

We recolor the sibling to red. This effectively "moves" the extra black up the tree to the parent. If the parent was red, we recolor it black and finish. Otherwise, the parent becomes the new Double Black node, and we recursively repeat the repair process up the tree.

Case C: The Sibling is Black with at Least One Red Child

If the sibling is black and has at least one red child, we can resolve the violation with rotations and recoloring. First, we determine the orientation of the sibling’s red child:

After performing the appropriate rotation, we swap colors between the parent and sibling, and recolor the sibling’s red child to black. This fully restores all Red Black properties, and no further repairs are needed.

Back