Red-Black Trees: The self balancing BST

A Red-Black tree is a type of Binary Search Tree that keeps its height as small as possible using red and black nodes.

The Rules:

To maintain the tree's balance, every node in a Red-Black tree is assigned Red or Black. These colors must obey rules known as the Red-Black properties.

• The root of the tree must be black.
• Each node must be red or black.
• The parent of a red node must be black.
• The number of black nodes traversed through every path to a null node must be the same.

Insertion and Deletion

When you insert or delete a node, the tree's structure might violate one of the Red-Black properties. To restore balance, the tree performs repair operations:

Restoring Balance

1. Recoloring: Changing the color of one or more nodes, sometimes flipping colors of nodes with others.
2. Rotating: Rotating nodes left and/or right to reduce the height of the tree and restore properties.
3. (Bonus) Repair Cases: Each type of violation in insertion and deletion have different cases that the tree must account for to restore balance.

Further Reading

For a more in-depth explanation of Red-Black Trees, check out the Wikipedia page: Red–black tree - Wikipedia