Introduction to Red-Black Tree

Binary search trees are a fundamental data structure, but their performance can suffer if the tree becomes unbalanced. Red Black Trees are a type of balanced binary search tree that use a set of rules to maintain balance, ensuring logarithmic time complexity for operations like insertion, deletion, and searching, regardless of the initial shape of the tree. Red Black Trees are self-balancing, using a simple color-coding scheme to adjust the tree after each modification.

Red-Black Tree

What is a Red-Black Tree?

A Red-Black Tree is a self-balancing binary search tree where each node has an additional attribute: a color, which can be either red or black. The primary objective of these trees is to maintain balance during insertions and deletions, ensuring efficient data retrieval and manipulation.

Properties of Red-Black Trees

A Red-Black Tree have the following properties:

1. Node Color: Each node is either red or black.
2. Root Property: The root of the tree is always black.
3. Red Property: Red nodes cannot have red children (no two consecutive red nodes on any path).
4. Black Property: Every path from a node to its descendant null nodes (leaves) has the same number of black nodes.
5. Leaf Property: All leaves (NIL nodes) are black.

These properties ensure that the longest path from the root to any leaf is no more than twice as long as the shortest path, maintaining the tree’s balance and efficient performance.

Example of Red-Black Tree

The Correct Red-Black Tree in above image ensures that every path from the root to a leaf node has the same number of black nodes. In this case,​ there is one (excluding the root node).

The Incorrect Red Black Tree does not follow the red-black properties as two red nodes are adjacent to each other. Another problem is that one of the paths to a leaf node has zero black nodes, whereas the other two contain a black node.

Why Red-Black Trees?

Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that the height of the tree remains O(log n) after every insertion and deletion, then we can guarantee an upper bound of O(log n) for all these operations. The height of a Red-Black tree is always O(log n) where n is the number of nodes in the tree. 

Comparison with AVL Tree:

The AVL trees are more balanced compared to Red-Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves frequent insertions and deletions, then Red-Black trees should be preferred. And if the insertions and deletions are less frequent and search is a more frequent operation, then AVL tree should be preferred over the Red-Black Tree.

How does a Red-Black Tree ensure balance?

A simple example to understand balancing is, that a chain of 3 nodes is not possible in the Red-Black tree. We can try any combination of colors and see if all of them violate the Red-Black tree property. 

Proper structure of three noded Red-black tree

Interesting points about Red-Black Tree:

• The black height of the red-black tree is the number of black nodes on a path from the root node to a leaf node. Leaf nodes are also counted as black nodes. So, a red-black tree of height h has black height >= h/2.
• Height of a red-black tree with n nodes is h<= 2 log₂(n + 1).
• All leaves (NIL) are black.
• The black depth of a node is defined as the number of black nodes from the root to that node i.e the number of black ancestors.

Basic Operations on Red-Black Tree:

The basic operations on a Red-Black Tree include:

1. Insertion
2. Search
3. Deletion
4. Rotation

1. Insertion

Inserting a new node in a Red-Black Tree involves a two-step process: performing a standard binary search tree (BST) insertion, followed by fixing any violations of Red-Black properties.

Insertion Steps

1. BST Insert: Insert the new node like in a standard BST.
2. Fix Violations:
   • If the parent of the new node is black, no properties are violated.
   • If the parent is red, the tree might violate the Red Property, requiring fixes.

Fixing Violations During Insertion

After inserting the new node as a red node, we might encounter several cases depending on the colors of the node’s parent and uncle (the sibling of the parent):

• Case 1: Uncle is Red: Recolor the parent and uncle to black, and the grandparent to red. Then move up the tree to check for further violations.
• Case 2: Uncle is Black:
  • Sub-case 2.1: Node is a right child: Perform a left rotation on the parent.
  • Sub-case 2.2: Node is a left child: Perform a right rotation on the grandparent and recolor appropriately.

2. Searching

Searching for a node in a Red-Black Tree is similar to searching in a standard Binary Search Tree (BST). The search operation follows a straightforward path from the root to a leaf, comparing the target value with the current node’s value and moving left or right accordingly.

Search Steps

1. Start at the Root: Begin the search at the root node.
2. Traverse the Tree:
   • If the target value is equal to the current node’s value, the node is found.
   • If the target value is less than the current node’s value, move to the left child.
   • If the target value is greater than the current node’s value, move to the right child.
3. Repeat: Continue this process until the target value is found or a NIL node is reached (indicating the value is not present in the tree).

3. Deletion

Deleting a node from a Red-Black Tree also involves a two-step process: performing the BST deletion, followed by fixing any violations that arise.

Deletion Steps

1. BST Deletion: Remove the node using standard BST rules.
2. Fix Double Black:
   • If a black node is deleted, a “double black” condition might arise, which requires specific fixes.

Fixing Violations During Deletion

When a black node is deleted, we handle the double black issue based on the sibling’s color and the colors of its children:

• Case 1: Sibling is Red: Rotate the parent and recolor the sibling and parent.
• Case 2: Sibling is Black:
  • Sub-case 2.1: Sibling’s children are black: Recolor the sibling and propagate the double black upwards.
  • Sub-case 2.2: At least one of the sibling’s children is red:
    • If the sibling’s far child is red: Perform a rotation on the parent and sibling, and recolor appropriately.
    • If the sibling’s near child is red: Rotate the sibling and its child, then handle as above.

4. Rotation

Rotations are fundamental operations in maintaining the balanced structure of a Red-Black Tree (RBT). They help to preserve the properties of the tree, ensuring that the longest path from the root to any leaf is no more than twice the length of the shortest path. Rotations come in two types: left rotations and right rotations.

1. Left Rotation

A left rotation at node 𝑥x moves 𝑥x down to the left and its right child 𝑦y up to take 𝑥x’s place.

Before Rotation:

    x                                              
     \                                             
      y                                                         
     / \                                                     
    a   b                                                     

After Left Rotation:

      y
     / \
    x   b
   /
  a

Left Rotation Steps:

1. Set y to be the right child of x.
2. Move y’s left subtree to x’s right subtree.
3. Update the parent of x and y.
4. Update x’s parent to point to y instead of x.
5. Set y’s left child to x.
6. Update x’s parent to y.

Pseudocode of Left Rotation:

// Utility function to perform left rotation
void leftRotate(Node* x)
{
    Node* y = x->right;
    x->right = y->left;
    if (y->left != NIL) {
        y->left->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == nullptr) {
        root = y;
    }
    else if (x == x->parent->left) {
        x->parent->left = y;
    }
    else {
        x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
}

2. Right Rotation

A right rotation at node 𝑥x moves 𝑥x down to the right and its left child 𝑦y up to take 𝑥x’s place.

Befor Right Rotation:    

      x
     /
    y
   / \
  a   b

After Right Rotation:

    y
   / \
  a   x
     /
    b

Right Rotation Steps:

1. Set y to be the left child of x.
2. Move y’s right subtree to x’s left subtree.
3. Update the parent of x and y.
4. Update x’s parent to point to y instead of x.
5. Set y’s right child to x.
6. Update x’s parent to y.

Pseudocode of Right Rotation:

// Utility function to perform right rotation
void rightRotate(Node* x)
{
    Node* y = x->left;
    x->left = y->right;
    if (y->right != NIL) {
        y->right->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == nullptr) {
        root = y;
    }
    else if (x == x->parent->right) {
        x->parent->right = y;
    }
    else {
        x->parent->left = y;
    }
    y->right = x;
    x->parent = y;
}

When to Perform Rotations?

Rotations in Red-Black Trees are typically performed during insertions and deletions to maintain the properties of the tree. Below are the scenarios for rotations:

1. Fixing Violations after Insertion

When a new node is inserted, it is always colored red. This can create violations of Red-Black Tree properties, specifically:

• The root must be black.
• Red nodes cannot have red children.

Case Analysis for Fixing Insertions:

• Case 1: Recoloring and Propagating Upwards
  • If the parent and uncle of the new node are both red, recolor the parent and uncle to black, and the grandparent to red. Then, recursively apply the fix-up to the grandparent.
• Case 2: Rotation and Recoloring
  • If the new node’s uncle is black and the new node is the right child of a left child (or vice versa), perform a rotation to move the new node up and align it.
  • If the new node’s uncle is black and the new node is the left child of a left child (or right of a right), perform a rotation and recolor the parent and grandparent to fix the violation.

2. Fixing Violations after Deletion

After deletion, the tree might need fixing to restore properties:

• When a black node is removed, or a red node is replaced by a black node, a double-black situation can arise.

Case Analysis for Fixing Deletions:

• Case 1: Sibling is Red
  • Recolor the sibling and the parent, and perform a rotation.
• Case 2: Sibling is Black with Black Children
  • Recolor the sibling to red and move the problem up to the parent.
• Case 3: Sibling is Black with at least one Red Child
  • Rotate and recolor to fix the double-black issue.

Implementation of Red-Black Tree:

Here’s a detailed implementation of a Red-Black Tree including insertion, search, and rotation functions:

#include <iostream>
using namespace std;

// Node structure for the Red-Black Tree
struct Node {
    int data;
    string color;
    Node *left, *right, *parent;

    Node(int data)
        : data(data)
        , color("RED")
        , left(nullptr)
        , right(nullptr)
        , parent(nullptr)
    {
    }
};

// Red-Black Tree class
class RedBlackTree {
private:
    Node* root;
    Node* NIL;

    // Utility function to perform left rotation
    void leftRotate(Node* x)
    {
        Node* y = x->right;
        x->right = y->left;
        if (y->left != NIL) {
            y->left->parent = x;
        }
        y->parent = x->parent;
        if (x->parent == nullptr) {
            root = y;
        }
        else if (x == x->parent->left) {
            x->parent->left = y;
        }
        else {
            x->parent->right = y;
        }
        y->left = x;
        x->parent = y;
    }

    // Utility function to perform right rotation
    void rightRotate(Node* x)
    {
        Node* y = x->left;
        x->left = y->right;
        if (y->right != NIL) {
            y->right->parent = x;
        }
        y->parent = x->parent;
        if (x->parent == nullptr) {
            root = y;
        }
        else if (x == x->parent->right) {
            x->parent->right = y;
        }
        else {
            x->parent->left = y;
        }
        y->right = x;
        x->parent = y;
    }

    // Function to fix Red-Black Tree properties after
    // insertion
    void fixInsert(Node* k)
    {
        while (k != root && k->parent->color == "RED") {
            if (k->parent == k->parent->parent->left) {
                Node* u = k->parent->parent->right; // uncle
                if (u->color == "RED") {
                    k->parent->color = "BLACK";
                    u->color = "BLACK";
                    k->parent->parent->color = "RED";
                    k = k->parent->parent;
                }
                else {
                    if (k == k->parent->right) {
                        k = k->parent;
                        leftRotate(k);
                    }
                    k->parent->color = "BLACK";
                    k->parent->parent->color = "RED";
                    rightRotate(k->parent->parent);
                }
            }
            else {
                Node* u = k->parent->parent->left; // uncle
                if (u->color == "RED") {
                    k->parent->color = "BLACK";
                    u->color = "BLACK";
                    k->parent->parent->color = "RED";
                    k = k->parent->parent;
                }
                else {
                    if (k == k->parent->left) {
                        k = k->parent;
                        rightRotate(k);
                    }
                    k->parent->color = "BLACK";
                    k->parent->parent->color = "RED";
                    leftRotate(k->parent->parent);
                }
            }
        }
        root->color = "BLACK";
    }

    // Inorder traversal helper function
    void inorderHelper(Node* node)
    {
        if (node != NIL) {
            inorderHelper(node->left);
            cout << node->data << " ";
            inorderHelper(node->right);
        }
    }

    // Search helper function
    Node* searchHelper(Node* node, int data)
    {
        if (node == NIL || data == node->data) {
            return node;
        }
        if (data < node->data) {
            return searchHelper(node->left, data);
        }
        return searchHelper(node->right, data);
    }

public:
    // Constructor
    RedBlackTree()
    {
        NIL = new Node(0);
        NIL->color = "BLACK";
        NIL->left = NIL->right = NIL;
        root = NIL;
    }

    // Insert function
    void insert(int data)
    {
        Node* new_node = new Node(data);
        new_node->left = NIL;
        new_node->right = NIL;

        Node* parent = nullptr;
        Node* current = root;

        // BST insert
        while (current != NIL) {
            parent = current;
            if (new_node->data < current->data) {
                current = current->left;
            }
            else {
                current = current->right;
            }
        }

        new_node->parent = parent;

        if (parent == nullptr) {
            root = new_node;
        }
        else if (new_node->data < parent->data) {
            parent->left = new_node;
        }
        else {
            parent->right = new_node;
        }

        if (new_node->parent == nullptr) {
            new_node->color = "BLACK";
            return;
        }

        if (new_node->parent->parent == nullptr) {
            return;
        }

        fixInsert(new_node);
    }

    // Inorder traversal
    void inorder() { inorderHelper(root); }

    // Search function
    Node* search(int data)
    {
        return searchHelper(root, data);
    }
};

int main()
{
    RedBlackTree rbt;

    // Inserting elements
    rbt.insert(10);
    rbt.insert(20);
    rbt.insert(30);
    rbt.insert(15);

    // Inorder traversal
    cout << "Inorder traversal:" << endl;
    rbt.inorder(); // Output: 10 15 20 30

    // Search for a node
    cout << "\nSearch for 15: "
         << (rbt.search(15) != rbt.search(0))
         << endl; // Output: 1 (true)
    cout << "Search for 25: "
         << (rbt.search(25) != rbt.search(0))
         << endl; // Output: 0 (false)

    return 0;
}

Advantages of Red-Black Trees:

• Balanced: Red-Black Trees are self-balancing, meaning they automatically maintain a balance between the heights of the left and right subtrees. This ensures that search, insertion, and deletion operations take O(log n) time in the worst case.
• Efficient search, insertion, and deletion: Due to their balanced structure, Red-Black Trees offer efficient operations. Search, insertion, and deletion all take O(log n) time in the worst case.
• Simple to implement: The rules for maintaining the Red-Black Tree properties are relatively simple and straightforward to implement.
• Widely used: Red-Black Trees are a popular choice for implementing various data structures, such as maps, sets, and priority queues.

Disadvantages of Red-Black Trees:

• More complex than other balanced trees: Compared to simpler balanced trees like AVL trees, Red-Black Trees have more complex insertion and deletion rules.
• Constant overhead: Maintaining the Red-Black Tree properties adds a small overhead to every insertion and deletion operation.
• Not optimal for all use cases: While efficient for most operations, Red-Black Trees might not be the best choice for applications where frequent insertions and deletions are required, as the constant overhead can become significant.

Applications of Red-Black Trees:

• Implementing maps and sets: Red-Black Trees are often used to implement maps and sets, where efficient search, insertion, and deletion are crucial.
• Priority queues: Red-Black Trees can be used to implement priority queues, where elements are ordered based on their priority.
• File systems: Red-Black Trees are used in some file systems to manage file and directory structures.
• In-memory databases: Red-Black Trees are sometimes used in in-memory databases to store and retrieve data efficiently.
• Graphics and game development: Red-Black Trees can be used in graphics and game development for tasks like collision detection and pathfinding.

Frequently Asked Questions (FAQs) on Red-Black Tree:

1. What is a Red-Black Tree?

A Red-Black Tree is a self-balancing binary search tree that maintains a balance between the heights of its left and right subtrees. This ensures that search, insertion, and deletion operations take O(log n) time in the worst case. Red-Black Trees are widely used in various applications where efficient data structures are required.

2. How does a Red-Black Tree maintain its balance?

Red-Black Trees maintain their balance by enforcing specific rules on the colors of nodes (RED or BLACK) and the relationships between them. These rules ensure that the tree remains balanced and that the height difference between the left and right subtrees is at most 1.

3. What are the advantages of using a Red-Black Tree?

• Balanced: Red-Black Trees are self-balancing, ensuring efficient search, insertion, and deletion operations.
• Efficient: They offer O(log n) time complexity for most operations.
• Simple to implement: The rules for maintaining Red-Black Tree properties are relatively straightforward.
• Widely used: They are a popular choice for implementing various data structures and algorithms.

4. What are the disadvantages of using a Red-Black Tree?

• Compared to simpler balanced trees like AVL trees, Red-Black Trees have more complex insertion and deletion rules.
• Maintaining the Red-Black Tree properties adds a small overhead to every insertion and deletion operation.
• For applications with frequent insertions and deletions, other balanced tree structures might be more suitable.

5. What are some common applications of Red-Black Trees?

• Implementing maps and sets
• Priority queues
• File systems
• In-memory databases
• Graphics and game development (collision detection, pathfinding)

Related Articles:

• Red-Black Tree definition & meaning in DSA
• Self-Balancing Binary Search Trees
• Red Black Tree vs AVL Tree
• What is the difference between Heap and Red-Black Tree?
• Insertion in Red-Black Tree
• Deletion in Red-Black Tree
• Red-Black Trees | Top-Down Insertion

GeeksforGeeks

Improve