Self-Balancing Trees (AVL / Red-Black)

BSTs that rotate on write to keep height O(log n) no matter the insertion order. The fix for the sorted-input worst case.

What to know

AVL balances harder (height diff ≤ 1): faster reads, more rotation work on writes.
Red-black relaxes balance for cheaper writes — the standard library default.
Full mechanics live in the Red-Black Trees deep dive.

In the wild: C++ std::map, Java TreeMap, Linux CFS scheduler, epoll timers.

Rotations (LL/RR/LR/RL)

O(1) each

Local O(1) rebalancing after insert/delete

Guaranteed O(log n) ops

O(log n)

Ordered map/set without degeneration

Each problem has its own page: progressive hints, how to approach it, and the full solution.

Balanced Binary Tree

Hints → approach → solution

Convert Sorted Array to Binary Search Tree

Hints → approach → solution

Balance a Binary Search Tree

Hints → approach → solution