Red-Black Trees

What is a Red-Black Tree?

A Red-Black Tree is a self-balancing binary search tree. Each node is either red or black, and the tree follows rules that help keep its heigh balanced.

Properties of Red-Black Trees

• Every node is either red or black.
• The root node is always black.
• Red nodes cannot have red children.
• Must maintain the same number of black nodes from a node to its null leaves.
\

Example Red-Black Tree

Why Are They Useful

Red-Black Trees support searching, insertion, and deletion in O(log n) time. This makes them useful for implementing efficient sorted collections.

Learn more about Red-Black Trees on Wikipedia