Red-Black Tree

A Red-Black Tree is a self-balancing binary search tree where each node has a color – either red or black. These colors enforce rules that keep the tree roughly balanced, ensuring that the longest path from root to a leaf is no more than twice the shortest path. This guarantees predictable performance for searches, insertions, and deletions.

How it Works

When a node is inserted or deleted, the tree may temporarily violate its color rules. To restore balance, the tree uses a combination of recoloring and rotations. It maintains balance through four key properties: the root is always black, all leaves (null nodes) are black, red nodes cannot have red children, and every path from a node to its descendant leaves contains the same number of black nodes.

Step by Step