Red-Black Tree

Introduction

The Red-Black Tree (RBT) is a self-balancing binary search tree that guarantees O(log n) operations for insertion, deletion, and search. It uses node colors (red or black) to enforce balance while maintaining BST ordering.

Balancing Rules

1. Every node is either red or black.
2. The root is always black.
3. All leaves (null nodes) are black.
4. No two red nodes are adjacent.
5. Every path from a node to its descendant leaves contains the same number of black nodes.

Further Reading

Explore more about the Red-Black Tree and its operations on Wikipedia .