Red-Black Trees

Self-Balancing Binary Search Trees

Overview

A Red-Black Tree is a type of self-balancing binary search tree that ensures the tree remains approximately balanced during insertions and deletions. This guarantees O(log n) time complexity for search, insert, and delete operations.

Key Properties

Every node is either red or black.
The root node is always black.
All leave nodes (null/NIL nodes) are black.
If a node is red, both its children are black and there should be no red-red violations.
Every path from a node to its descendant leave nodes must have the same number of black nodes (black height must be conserved).

Diagram of a Red-Black Tree — Example of an invalid and a valid Red-Black Tree showing red and black nodes.

Learn more at Red–Black Tree — geeksforgeeks .