Red-black tree

A red-black tree is a BST augmented with one bit per node (often drawn as red or black) such that simple coloring rules hold along every path. Together they guarantee height O(log n) without requiring AVL’s strict height difference—updates tend to need fewer structural fixes than AVL in many workloads.

Contrast with AVL trees for a stricter balance criterion. Prerequisites: BST ordering from Binary search tree.

1) Common invariants

Definitions vary slightly by textbook (sentinel leaf vs NULL), but the usual picture is:

• Every node is either red or black.
• The root is black.
• Every leaf (NIL) is black.
• If a node is red, both children are black (no consecutive reds on a simple path).
• For each node, every path down to leaves has the same number of black nodes—the black height.

2) Insert and delete

Insert starts like a BST insert; the new node is typically colored red to avoid instantly breaking black-height. If a red-red conflict appears with the parent, apply recolorings and at most a couple of rotations walking up—classic case analysis (parent and uncle colors).

Delete is harder: removing a black node can break black-height symmetry; fixup walks up while maintaining invariants using rotations and recolorings. Interview courses often drill insert fixup first.

3) Complexity

Height is at most about 2 log₂(n+1) in standard formulations—still O(log n). Search is straightforward BST search; insert/delete include fixup overhead but remain O(log n).

4) Practical use

Many language runtimes and libraries use red-black or similar BSTs for ordered maps (guaranteed worst-case logarithmic ops vs hash tables’ expected case). Kernel schedulers and file-system metadata sometimes use comparable balanced-tree ideas; on-disk structures usually switch to B-trees or B+ trees—see B-tree.