Red-Black Tree Implementation in C++

A Red-Black Tree is a self-balancing binary search tree where each node stores an extra bit for denoting the color of the node, either red or black. The tree ensures that the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf, which guarantees the tree remains balanced.

Key Properties of Red-Black Tree

• Each node is either red or black.
• The root is always black.
• All leaves (NIL nodes) are black.
• If a node is red, both its children must be black.
• Every path from a node to its descendant NIL nodes must have the same number of black nodes.

Program Structure

The C++ implementation of a Red-Black Tree will include:

1. Red-Black Tree Node Structure: Defining the structure of a node in the Red-Black Tree.
2. Insertion Operation: Implementing the insertion function with necessary rebalancing and recoloring to maintain Red-Black Tree properties.
3. Rotation Operations: Implementing left and right rotations for balancing the tree.
4. Traversal Operation: Implementing an in-order traversal to display the keys in sorted order.

Code Implementation

#include <iostream>
#include <memory>

enum Color {RED, BLACK};

struct Node {
    int data;
    Color color;
    Node *left, *right, *parent;

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

class RedBlackTree {
private:
    Node *root;

protected:
    void rotateLeft(Node *&root, Node *&pt);
    void rotateRight(Node *&root, Node *&pt);
    void fixViolation(Node *&root, Node *&pt);

public:
    RedBlackTree() { root = nullptr; }
    void insert(const int &data);
    void inorder();
    void inorderHelper(Node *root);
    Node* getRoot() { return root; }
};

void RedBlackTree::rotateLeft(Node *&root, Node *&pt) {
    Node *pt_right = pt->right;

    pt->right = pt_right->left;

    if (pt->right != nullptr)
        pt->right->parent = pt;

    pt_right->parent = pt->parent;

    if (pt->parent == nullptr)
        root = pt_right;
    else if (pt == pt->parent->left)
        pt->parent->left = pt_right;
    else
        pt->parent->right = pt_right;

    pt_right->left = pt;
    pt->parent = pt_right;
}

void RedBlackTree::rotateRight(Node *&root, Node *&pt) {
    Node *pt_left = pt->left;

    pt->left = pt_left->right;

    if (pt->left != nullptr)
        pt->left->parent = pt;

    pt_left->parent = pt->parent;

    if (pt->parent == nullptr)
        root = pt_left;
    else if (pt == pt->parent->left)
        pt->parent->left = pt_left;
    else
        pt->parent->right = pt_left;

    pt_left->right = pt;
    pt->parent = pt_left;
}

void RedBlackTree::fixViolation(Node *&root, Node *&pt) {
    Node *parent_pt = nullptr;
    Node *grand_parent_pt = nullptr;

    while ((pt != root) && (pt->color != BLACK) && (pt->parent->color == RED)) {

        parent_pt = pt->parent;
        grand_parent_pt = pt->parent->parent;

        if (parent_pt == grand_parent_pt->left) {
            Node *uncle_pt = grand_parent_pt->right;

            if (uncle_pt != nullptr && uncle_pt->color == RED) {
                grand_parent_pt->color = RED;
                parent_pt->color = BLACK;
                uncle_pt->color = BLACK;
                pt = grand_parent_pt;
            } else {
                if (pt == parent_pt->right) {
                    rotateLeft(root, parent_pt);
                    pt = parent_pt;
                    parent_pt = pt->parent;
                }

                rotateRight(root, grand_parent_pt);
                std::swap(parent_pt->color, grand_parent_pt->color);
                pt = parent_pt;
            }
        } else {
            Node *uncle_pt = grand_parent_pt->left;

            if (uncle_pt != nullptr && uncle_pt->color == RED) {
                grand_parent_pt->color = RED;
                parent_pt->color = BLACK;
                uncle_pt->color = BLACK;
                pt = grand_parent_pt;
            } else {
                if (pt == parent_pt->left) {
                    rotateRight(root, parent_pt);
                    pt = parent_pt;
                    parent_pt = pt->parent;
                }

                rotateLeft(root, grand_parent_pt);
                std::swap(parent_pt->color, grand_parent_pt->color);
                pt = parent_pt;
            }
        }
    }

    root->color = BLACK;
}

void RedBlackTree::insert(const int &data) {
    Node *pt = new Node(data);

    root = bstInsert(root, pt);

    fixViolation(root, pt);
}

void RedBlackTree::inorder() {
    inorderHelper(root);
}

void RedBlackTree::inorderHelper(Node *root) {
    if (root == nullptr)
        return;

    inorderHelper(root->left);
    std::cout << root->data << " "; inorderHelper(root->right);
}

Node* bstInsert(Node* root, Node *pt) {
    if (root == nullptr)
        return pt;

    if (pt->data < root->data) {
        root->left = bstInsert(root->left, pt);
        root->left->parent = root;
    } else if (pt->data > root->data) {
        root->right = bstInsert(root->right, pt);
        root->right->parent = root;
    }

    return root;
}

int main() {
    RedBlackTree tree;

    tree.insert(10);
    tree.insert(20);
    tree.insert(30);
    tree.insert(15);
    tree.insert(25);
    tree.insert(5);
    tree.insert(2);

    std::cout << "Inorder Traversal of Created Tree: ";
    tree.inorder();

    return 0;
}

Explanation

Red-Black Tree Node Structure

The Node structure represents a node in the Red-Black Tree. It contains:

• data: The value stored in the node.
• color: The color of the node (red or black).
• left, right, parent: Pointers to the left child, right child, and parent nodes, respectively.

Rotation Operations

The Red-Black Tree uses rotations to maintain balance. The rotateLeft() and rotateRight() functions perform left and right rotations, respectively, which are essential for fixing any violations of the Red-Black Tree properties after insertion.

Insertion Operation

The insert() function adds a new node to the Red-Black Tree. If necessary, it calls fixViolation() to ensure that the Red-Black Tree properties are maintained. This function handles rebalancing by performing rotations and recoloring nodes.

Traversal Operation

The inorder() function performs an in-order traversal of the Red-Black Tree, printing the nodes’ values in sorted order. The inorderHelper() function is a recursive helper that traverses the left subtree, prints the current node, and then traverses the right subtree.

Conclusion

The Red-Black Tree is an efficient self-balancing binary search tree that ensures balanced height, enabling operations like insertion, deletion, and search in logarithmic time. This C++ implementation covers the essential aspects of the Red-Black Tree, including rotations, insertion, and traversal, making it suitable for various applications where balanced trees are required.