Red-Black Tree

Overview

A Red-Black Tree (RBT) is a type of self-balancing binary search tree that guarantees log time for search, insert, and delete by maintaining simple color-based rules.

Key Properties

Tree invariants

• Every node is either red or black.
• The root is always black; all leaves (NILs) are black.
• No red node has a red child (no two reds in a row).
• Every path from a node to descendant NILs has the same number of black nodes (black-height).

Visual