AntInLoop

Red-Black Tree Code Implementations

Production-ready Red-Black Tree data structure implementations in C++, Python, Java, and JavaScript on AntInLoop.

Study Red-Black Tree Guide ยท Launch Visualizer

CPP Implementation

#include<bits/stdc++.h>
using namespace std;

// A Node of the doubly linked list
struct Node
{
    int data; // data part
    Node *left, *right; // left and right pointers
    int color; // color of the node, 0 for black, 1 for red
};

// Function to create a new node
Node* newNode(int data)
{
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    node->color = 1; // new nodes are initially red
    return node;
}

// Function to perform left-rotation
void rotateLeft(Node *&root, Node *&pt)
{
    Node *pt_right = pt->right;
    pt->right = pt_right->left;
    if (pt->right != NULL)
        pt->right->parent = pt;
    pt_right->parent = pt->parent;
    if (pt->parent == NULL)
        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;
}

// Function to perform right-rotation
void rotateRight(Node *&root, Node *&pt)
{
    Node *pt_left = pt->left;
    pt->left = pt_left->right;
    if (pt->left != NULL)
        pt->left->parent = pt;
    pt_left->parent = pt->parent;
    if (pt->parent == NULL)
        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;
}

// Function to fix violations caused during insertion
void fixViolation(Node *&root, Node *&pt)
{
    Node *parent_pt = NULL;
    Node *grand_parent_pt = NULL;
    while ((pt != root) && (pt->color != 0) && (pt->parent->color == 1))
    {
        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 != NULL && uncle_pt->color == 1)
            {
                grand_parent_pt->color = 1;
                parent_pt->color = 0;
                uncle_pt->color = 0;
                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);
                swap(parent_pt->color, grand_parent_pt->color);
                pt = parent_pt;
            }
        }
        else
        {
            Node *uncle_pt = grand_parent_pt->left;
            if ((uncle_pt != NULL) && (uncle_pt->color == 1))
            {
                grand_parent_pt->color = 1;
                parent_pt->color = 0;
                uncle_pt->color = 0;
                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);
                swap(parent_pt->color, grand_parent_pt->color);
                pt = parent_pt;
            }
        }
    }
    root->color = 0;
}

// Function to insert a new node with given data
void insert(Node *&root, int data)
{
    Node *pt = newNode(data);
    root = insertBST(root, pt);
    fixViolation(root, pt);
}

// Function to do inorder and level order traversals
void inorder(Node *trav)
{
    if (trav == NULL)
        return;
    inorder(trav->left);
    cout << trav->data << "  ";
    inorder(trav->right);
}

// Driver Code
int main()
{
    Node *root = NULL;
    insert(root, 7);
    insert(root, 6);
    insert(root, 5);
    insert(root, 4);
    insert(root, 3);
    insert(root, 2);
    insert(root, 1);
    cout << "Inorder Traversal of Created Tree\n";
    inorder(root);
    cout << "\n";
    return 0;
}

JAVA Implementation

// Red-Black Tree Implementation in Java
class RedBlackTree {

    // Define node colors
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    // Node structure
    static class Node {
        int data;
        Node left, right, parent;
        boolean color;

        Node(int data) {
            this.data = data;
            this.color = RED; // new node is always RED initially
        }
    }

    private Node root;

    // Left rotate
    private void leftRotate(Node x) {
        Node y = x.right;
        x.right = y.left;
        if (y.left != null) y.left.parent = x;
        y.parent = x.parent;
        if (x.parent == null) {
            root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }

    // Right rotate
    private void rightRotate(Node y) {
        Node x = y.left;
        y.left = x.right;
        if (x.right != null) x.right.parent = y;
        x.parent = y.parent;
        if (y.parent == null) {
            root = x;
        } else if (y == y.parent.left) {
            y.parent.left = x;
        } else {
            y.parent.right = x;
        }
        x.right = y;
        y.parent = x;
    }

    // Fix violations after insertion
    private void fixInsert(Node z) {
        while (z.parent != null && z.parent.color == RED) {
            if (z.parent == z.parent.parent.left) {
                Node y = z.parent.parent.right;
                if (y != null && y.color == RED) {
                    // Case 1: Uncle is RED
                    z.parent.color = BLACK;
                    y.color = BLACK;
                    z.parent.parent.color = RED;
                    z = z.parent.parent;
                } else {
                    // Case 2 & 3: Uncle is BLACK
                    if (z == z.parent.right) {
                        z = z.parent;
                        leftRotate(z);
                    }
                    z.parent.color = BLACK;
                    z.parent.parent.color = RED;
                    rightRotate(z.parent.parent);
                }
            } else {
                Node y = z.parent.parent.left;
                if (y != null && y.color == RED) {
                    // Case 1: Uncle is RED
                    z.parent.color = BLACK;
                    y.color = BLACK;
                    z.parent.parent.color = RED;
                    z = z.parent.parent;
                } else {
                    // Case 2 & 3: Uncle is BLACK
                    if (z == z.parent.left) {
                        z = z.parent;
                        rightRotate(z);
                    }
                    z.parent.color = BLACK;
                    z.parent.parent.color = RED;
                    leftRotate(z.parent.parent);
                }
            }
        }
        root.color = BLACK; // Root must always be BLACK
    }

    // Insert a new node
    public void insert(int data) {
        Node z = new Node(data);
        Node y = null;
        Node x = root;

        while (x != null) {
            y = x;
            if (z.data < x.data) {
                x = x.left;
            } else {
                x = x.right;
            }
        }

        z.parent = y;
        if (y == null) {
            root = z;
        } else if (z.data < y.data) {
            y.left = z;
        } else {
            y.right = z;
        }

        fixInsert(z);
    }

    // Search a value
    public boolean search(int data) {
        Node node = root;
        while (node != null) {
            if (data == node.data) return true;
            if (data < node.data) node = node.left;
            else node = node.right;
        }
        return false;
    }

    // Inorder Traversal
    public void inorder(Node node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.data + (node.color == RED ? "(R) " : "(B) "));
        inorder(node.right);
    }

    public void inorder() {
        inorder(root);
        System.out.println();
    }

    // Main method
    public static void main(String[] args) {
        RedBlackTree rbt = new RedBlackTree();

        int[] values = {10, 20, 30, 15, 25, 5, 1};
        for (int val : values) {
            rbt.insert(val);
            System.out.print("Inorder after inserting " + val + ": ");
            rbt.inorder();
        }

        System.out.println("Search 15: " + (rbt.search(15) ? "Found" : "Not Found"));
        System.out.println("Search 50: " + (rbt.search(50) ? "Found" : "Not Found"));
    }
}