Concept

A Red-Black Tree is a self-balancing binary search tree where each node contains an extra bit for color (red or black). The tree balances itself after insertions and deletions to ensure that the longest path from the root to a leaf is no more than twice as long as the shortest path, guaranteeing O(log n) time for search, insert, and delete operations.

Characteristics

Each node is either red or black.
The root is always black.
No two red nodes can be adjacent (parent-child).
Every path from a node to its descendant NULL nodes has the same number of black nodes.
Ensures O(log n) height for n nodes.

Visualization (Dynamic)

Insert values to see the Red-Black Tree grow

Red nodes are red, black nodes are black.
Insert numbers and watch balancing and coloring in action.

Code Example (C++)

#include <iostream>
using namespace std;

enum Color { RED, BLACK };

struct Node {
    int data;
    Color color;
    Node *left, *right;
    Node(int data, Color color) : data(data), color(color), left(nullptr), right(nullptr) {}
};

void inorder(Node* node) {
    if (node) {
        inorder(node->left);
        cout << node->data << (node->color == RED ? "(R) " : "(B) ");
        inorder(node->right);
    }
}

int main() {
    Node* root = new Node(10, BLACK);
    root->left = new Node(5, RED);
    root->right = new Node(20, RED);
    root->left->left = new Node(2, BLACK);
    root->left->right = new Node(8, BLACK);
    inorder(root); // Output: 2(B) 5(R) 8(B) 10(B) 20(R)
    return 0;
}

Code Example (Python)

# Simple Red-Black Tree Node and Insert Example (no balancing for brevity)
class Node:
    def __init__(self, data, color="R"):
        self.data = data
        self.color = color  # "R" or "B"
        self.left = None
        self.right = None

def inorder(node):
    if node:
        inorder(node.left)
        print(f"{node.data}({node.color})", end=" ")
        inorder(node.right)

# Example usage:
root = Node(10, "B")
root.left = Node(5, "R")
root.right = Node(20, "R")
root.left.left = Node(2, "B")
root.left.right = Node(8, "B")
inorder(root)  # Output: 2(B) 5(R) 8(B) 10(B) 20(R)

Key Points

Self-balancing BST with O(log n) insert, delete, and search.
Used in many standard libraries (C++ STL map/set, Java TreeMap, etc).
Guarantees that the longest path is no more than twice the shortest.
Red-Black properties ensure balance with minimal overhead.