The Red-Black Tree

Node Color: Every node is either red or black.
Root Property: The root is always black.
Red Rule: Red nodes cannot have red children (no two reds in a row).
Black Depth: Every path from a node to its descendant NULL nodes must contain the same number of black nodes.

A specialized version of a Binary Search Tree that stays balanced through color-coding.

Why Use Red-Black Trees?

Unlike a standard BST, which can become "leggy" and inefficient (O(n)), Red-Black Trees ensure a height of O(log n), keeping operations fast even with large datasets.

        Core Properties
        Node Color: Every node is either red or black.
Root Property: The root is always black.
Red Rule: Red nodes cannot have red children (no two reds in a row).
Black Depth: Every path from a node to its descendant NULL nodes must contain the same number of black nodes.

    

Common Operations

Search (O(log n))
Insertion (with rotations and recoloring)
Deletion (the most complex balancing act)