Red-Black Trees

What is a Red-Black Tree?

A Red-Black Tree is a self-balancing binary search tree where each node has an extra bit for denoting the color of the node, either red or black. This ensures the tree remains approximately balanced during insertions and deletions.

Key Properties

• Every node is either red or black
• The root is always black
• All leaves (NIL) are black
• Red nodes cannot have red children (no two red nodes in a row)
• Every path from root to leaf has the same number of black nodes

Why Use Red-Black Trees?

Red-Black Trees guarantee O(log n) time complexity for search, insert, and delete operations. They are used in many real-world applications including Java's TreeMap and C++'s std::map.

Common Operations

1. Insert a new node (always starts red)
2. Fix red property violations through rotations and recoloring
3. Ensure the root remains black

Visual Example

Example of a balanced Red-Black Tree structure

Learn More

For more information about Red-Black Trees, visit the Wikipedia article on Red-Black Trees .