Red-Black Tree

A Binary Search Tree (BST) is a data structure used to implement associative containers, such as set and map. However, a BST is not perfect because the order of insertion can cause the tree to become unbalanced. If you insert elements in either ascending or descending order, the binary tree can degrade into a normal doubly-linked list, where insertion and search take $O(n)$ time instead of $O(\log(n))$. To maintain balance in a BST, certain rules are enforced regarding how elements are treated, which led to the creation of the Red-Black Tree (RBT).

• A node is either red or black
• The root node and the leaf nodes are black
• If a node is red, its children are black
• All paths from a node to the leaf nodes contain same number of black nodes

The above rules ensure that a Red-Black Tree remains balanced. (The leaf nodes here are null nodes, which are assumed to be black.) Due to the introduction of the color property, represented by 0 and 1, extra information needs to be stored. However, these rules guarantee that the longest path is no more than twice the length of the shortest path, leading to a relatively balanced BST. Below is how we can define a node in an RBT.

// Enum to represent the color of the nodes in the Red-Black Tree
enum Color {RED, BLACK};
 
template <typename T>
class Node {
public:
    T data;
    Color color;
    Node<T>* left;
    Node<T>* right;
    Node<T>* parent;
 
    Node(T data) : data(data), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

Rotation

Out of the three main operations—searching, insertion, and deletion—the latter two can violate the Red-Black Tree properties. To prevent such violations, we use the rotation operation, which rearranges the tree after these operations to follow the rules.

• Left rotation on a node makes the node the left child of its right child and makes the left child of the right child the right child of the original node.
• Right rotation on a node makes the node the right child of its left child and makes the right child of the left child the left child of the original node.

void leftRotate(Node<T>* x) {
    Node<T>* y = x->right;
    // make left child of the right child be the right child of x
    x->right = y->left;
    if (y->left != nullptr) {
        y->left->parent = x; 
    }
 
    // Take care of parent pointer of right child
    y->parent = x->parent;
 
    // Take care of x's parent
    if (x->parent == nullptr) {
        root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y; 
    } else {
        x->parent->right = y;
    }
 
    // make x the left child of the right child
    y->left = x;
    x->parent = y;
};

The left rotation is illustrated in the code below. It only requires a few changes to the pointers, implying a time complexity of $O(1)$. The rotation operation ensures that the BST property is preserved while rearranging the nodes, which is essential when fixing violations.

Insertion

When inserting a node into an RBT, we initially color the node red. Fixing violations of the second and third rules is relatively straightforward, as they can be resolved by recoloring and rotations. To fix violations, we need to consider different scenarios that might occur during insertion. There are four scenarios, which are illustrated in the diagram below.

• Case 1: If the inserted node is the root, we simply recolor it to black.
• Case 2: If the inserted node has a red parent, we recolor the parent, grandparent, and the uncle to the opposite color. This ensures that red and black nodes alternate, following the third rule.
• Case 3: If the inserted node is a left/right child of a parent, who is a left/right child of the grandparent, forming a line, we rotate the grandparent in the opposite direction of the inserted node and then recolor the parent and the grandparent.
• Case 4: If the inserted node is a left/right child of a parent, who is a right/left child of the grandparent, forming a triangle, we rotate the parent in the opposite direction of the inserted node to convert the situation to Case 3, and then we apply the fix for Case 3.

The implementation of RBT insertion is shown below.

int insert(T data) {
    Node<T>* node = new Node<T>(data);
    Node<T>* y = nullptr;  // Variable to keep track of the parent
    Node<T>* x = root;
    // BST insertion
    while (x != nullptr) {
        y = x;  // Keep track of the parent
        if (node->data < x->data) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    node->parent = y;
 
    if (y == nullptr) {
        root = node; // Case 1
        return 1;
    } else if (node->data < y->data) {
        y->left = node;
    } else {
        y->right = node;
    }
 
    // Step 3: Fix violations
    fixInsert(node);
    return 1;
};
 
void fixInsert(Node<T>* k) {
    while (k->parent != nullptr && k->parent->color == RED) {
        Node<T>* grandparent = k->parent->parent;
        if (k->parent == grandparent->left) {
            Node<T>* uncle = grandparent->right;
 
            // Case 2: Uncle is red (Recoloring)
            if (uncle != nullptr && uncle->color == RED) {
                k->parent->color = BLACK;      // Recolor parent
                uncle->color = BLACK;          // Recolor uncle
                grandparent->color = RED;      // Recolor grandparent
                k = grandparent;               // Move up to grandparent
            } else {
                // Case 4
                if (k == k->parent->right) {
                    k = k->parent;
                    leftRotate(k);
                }
                // Case 3
                k->parent->color = BLACK;
                grandparent->color = RED;
                rightRotate(grandparent);
            }
        } else {
            // Symmetric to the above, k's parent is the right child
            Node<T>* uncle = grandparent->left;
 
            // Case 2: Uncle is red (Recoloring)
            if (uncle != nullptr && uncle->color == RED) {
                k->parent->color = BLACK;      // Recolor parent
                uncle->color = BLACK;          // Recolor uncle
                grandparent->color = RED;      // Recolor grandparent
                k = grandparent;               // Move up to grandparent
            } else {
                // Case 4
                if (k == k->parent->left) {
                    k = k->parent;
                    rightRotate(k);
                }
                // Case 3
                k->parent->color = BLACK;
                grandparent->color = RED;
                leftRotate(grandparent);
            }
        }
    }
    root->color = BLACK;
};

When inserting an element into the tree, we need to fix any violations until the entire tree is a valid RBT. Inserting a node at the bottom requires tree traversal, which takes $O(\log (n))$. Afterward, we set the color to red, which takes $O(1)$. We then continue fixing violations with $O(1)$ recoloring and rotations, working from the bottom to the top of the tree ($O(log(n))$). As a result, the total time complexity of insertion is $O(\log (n))$, which matches the average time complexity of a BST.

Deletion

The deletion process is quite complex, involving multiple steps and scenarios. To understand the process, we break it down into three steps: replace, delete, and delete fixup.

Step 1. Replace

When we delete a node from an RBT, we first need to decide which node will replace the deleted node. There are three possible scenarios to consider. The first case is when the deleted node has two NIL child nodes, which can be replaced by either of the NIL nodes (defaulting to the right NIL child). The second case is when the deleted node has one NIL child and one non-NIL child, which can be replaced by the non-NIL child. The third case is when the deleted node has two non-NIL child nodes, in which case it is replaced by the left-most node of the right subtree, as it is likely that it has the closest value to the deleted node.

In the first two cases, we know by the rules of RBT that the replacement node has NIL children. Therefore, when we replace the node, we don't need to worry about the replacement node’s children. However, in the third case, the replacement node might have a non-NIL right child (but not a left one because we pick the left-most node), which we need to keep track of to attach to the appropriate place later after the replacement. Therefore, we assign pointer $x$ to the replacement node for the first two cases but to the replacement node's right child for the third case, and attach it in the appropriate place.

Step 2. Delete

Now that we have determined the replacement node and its potential non-NIL child, we can proceed to delete the node. The deletion simply changes the pointer of the deleted node's child to point to the replacement node and changes the replacement node's parent pointer to point to the deleted node's parent, while freeing the memory occupied by the deleted node. In the third case from step 1, we might need to adjust the pointers of $x$ to attach it to where the replacement node was. At this point, several scenarios may arise: some will pose no problem in maintaining the RBT properties, while others may require significant fixing.

If the deleted node is red and the replacement node is red or NIL, the deletion is complete. If the deleted node is red and the replacement node is black and non-NIL, the replacement node needs to be recolored to red to avoid violating the third rule, although there might still be a violation of the fourth rule. In this second case, we proceed to step 3.

If the deleted node is black and the replacement node is red, we can complete the deletion by recoloring the replacement node to black. If both the deleted node and replacement node are black, and $x$ becomes the root of the tree after the replacement, it means the tree originally only had one root node. In this fourth case, the deletion is complete. If both the deleted node and replacement node are black and $x$ does not become the root, we might violate the rules and need to proceed to step 3.

Step 3. Delete Fixup

After step 2, we perform step 3 when the deleted node is red and the replacement node is black and non-NIL, or when both the deleted node and replacement node are black, and $x$ does not become the root. In both cases, we are concerned with violations of the fourth rule, as both situations move a black node up the tree. In such cases, there are five scenarios to consider when fixing the violation.

The first case is when $x$ is red, and the number of black nodes in the paths involving $x$ is one less than in other paths. This can be fixed simply by recoloring $x$ to black. From the second case onward, the operation is more complex and involves $x$'s sibling, labeled $w$. Fixing the violation may not happen immediately, so the process of identifying the correct case and performing the corresponding operation must be repeated until no further cases apply.

• Second case: $x$ is black and $w$ is red. This can be fixed by recoloring $w$ to black, $x$'s parent to red, rotating the parent in the same direction as $x$, and then setting $w$ to be $x$'s sibling again.
• Third case: $x$, $w$, and $w$'s children are all black. This can be resolved by recoloring $w$ to red and setting $x$ to be its parent. After setting $x$ to its parent, we need to check if the new $x$ is red or black and the root of the tree. If $x$ is red, it only needs to be recolored to black, and if $x$ is the root, no further operations are needed.
• Fourth case: Both $x$ and $w$ are black, $w$'s child on the same side as $x$ is red, and $w$'s other child is black. In this case, recolor $w$'s child on the same side as $x$ to black, recolor $w$ to red, rotate $w$ in the opposite direction of $x$, and then set $w$ to be $x$'s sibling again.
• Fifth case: Both $x$ and $w$ are black, and $w$'s child on the opposite side of $x$ is red. Recolor $x$ to have the same color as $x$'s parent, recolor $x$'s parent to black, recolor $w$'s child on the opposite side of $x$ to black, and rotate $x$'s parent in the same direction as $x$. This should result in a valid RBT.

From the above steps, we see that step 1 involves tree traversal to find the replacement node, taking $O(\log (n))$, step 2 simply checks conditions and performs recoloring as needed in $O(1)$, and step 3 can repeat the process of recoloring and rotation at most $\log (n)$ times, also $O(\log (n))$. The overall time complexity is therefore $O(\log (n))$, which is the same as the average time complexity of a BST.

NOTE: There are many scenarios to consider in the deletion steps, and some operations are complex, making it difficult to understand how the steps resolve the violations. I'm still unsure about some parts of the algorithm, but after reading the content multiple times and visualizing deletions on example RBTs, I’ve gained a reasonable understanding. I recommend you do the same—read the process multiple times and work through it with examples. Additionally, I challenge you to implement deletion in your own RBT class!

Conclusion

As we can observe, by introducing some rules and modifying operations accordingly, RBT guarantees a balanced BST and achieves worst-case time complexities for insertion and deletion equal to the average time complexities of a regular BST. While RBT requires more space due to additional pointers and an integer for each node, and involves complex operations for insertion and deletion, this is a good trade-off considering the abundant space available in modern systems. In the next article, we will explore alternative tree data structures for implementing associative containers, which may also be useful for other purposes.

Exercises

From this article, there will be an exercise section where you can test your understanding of the material introduced in the article. I highly recommend solving these questions by yourself after reading the main part of the article. You can click on each question to see its answer.

Resources

• Chang, A. 2022. Red-black tree deletion: steps + 10 examples. YouTube.
• Sambol, M. n.d. Red-Black Trees // Michael Sambol. YouTube.