Red-Black Trees

A Red-Black Tree is a type of self-balancing Binary Search Tree (BST) that maintains height balance through color properties, ensuring efficient insertions, deletions, and lookups.

Properties of Red-Black Trees

• Every node is either red or black.
• The root is always black.
• All leaves (NIL nodes) are black.
• Red nodes cannot have red children.
• Every path from a node to its descendant NIL nodes has the same number of black nodes.

Visualization

Why Red-Black Trees?

1. Guaranteed O(log n) height for fast operations.
2. Used in C++ STL maps/sets and Java TreeMap/TreeSet.
3. Ensures balance without frequent rotations.

Learn more at the following link: Wikipedia article on Red-Black Trees.

Note: Red-Black Trees are a specific type of self-balancing BST discovered by Rudolf Bayer in 1972.