Red-Black Trees

What is a Red-Black Tree?

A Red-Black Tree is a type of self-balancing binary search tree. It ensures that the tree remains approximately balanced, which keeps operations like insertion, deletion, and search efficient — all in O(log n) time.

Rules of a RBT

• Every node is either red or black
• The root is always black
• All leaves (NIL) are black
• If a node is red, then both its children must be black
• Every path from a node to its descendant NIL nodes must have the same number of black nodes

For more information on Red-Black Trees, click on this line