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

1. Insert a node like in a normal BST and color it red.
2. Check the tree for violations of Red-Black rules.
3. If there’s a violation, apply rotations (left or right) and recoloring to restore properties.
4. Repeat until all rules are satisfied from the modified node to the root.