Red-Black Trees

What is a Red-Black Tree?

A Red-Black Tree is a self-balancing binary search tree where each node stores an extra bit representing its color (red or black). These color properties are used to keep the tree approximately balanced during insertions and deletions, guaranteeing O(log n) time for search, insert, and delete operations.

Key Properties

1. Every node is either red or black.
2. The root is always black.
3. Every null leaf (NIL) is considered black.
4. If a node is red, both of its children must be black (no two consecutive red nodes).
5. Every path from a node to its descendant NIL leaves contains the same number of black nodes.

Balancing Operations

When an insertion or deletion violates the red-black properties, the tree is fixed using rotations and recoloring. The three main cases during insertion involve the uncle node's color and the relative position of the new node to its grandparent.

Rotation Types

• Left Rotation: moves a node down to the left and its right child up.
• Right Rotation: moves a node down to the right and its left child up.
• Recoloring: flips the colors of a node and its children to restore balance.

Learn More

For a deeper dive into Red-Black Trees, check out the Wikipedia article on Red-Black Trees.