Self-Balancing BSTs Overview (AVL, Red-Black, Treap)

A self-balancing binary search tree is a BST that automatically restructures itself after inserts and deletes so its height stays O(log n). A plain BST can degenerate into a straight line (height O(n)) if you insert sorted data — turning its “fast” operations into O(n) scans. Self-balancing variants guarantee logarithmic search, insert, delete, and ordered traversal no matter the input order. This page is a conceptual map of the main variants and, crucially, the built-in ordered containers you’ll actually reach for in real code.

The balance problem

Insert 1, 2, 3, 4, 5 into a naive BST and you get a degenerate chain — every node has only a right child. Balanced trees detect this imbalance and fix it with rotations, local O(1) pointer rearrangements that preserve the BST ordering while reducing height.

The main flavors

• AVL trees keep every node’s two subtree heights within 1 of each other. They are the most rigidly balanced, so lookups are very fast, at the cost of more rotations on updates. Best when reads vastly outnumber writes. See Balanced Trees & AVL for the rotation mechanics.
• Red-black trees allow looser balance (the longest path is at most twice the shortest) using node colors and recoloring. Fewer rotations on updates than AVL, so they’re the default in most standard libraries.
• Treaps combine a BST key with a random heap priority. Randomness keeps the expected height O(log n) with very little code — popular in competitive programming.

All guarantee O(log n) search, insert, and delete, and O(n) sorted in-order traversal.

Use the built-in — don’t reimplement

In an interview or production you rarely hand-roll a red-black tree. C++ and Java ship a balanced-BST-backed ordered map/set that keeps keys sorted and supports range/neighbor queries like “smallest key ≥ x”. Here’s the same task — insert keys, then find the smallest key ≥ a target — in each language:

#include <map>
// std::map / std::set are red-black trees (ordered, O(log n))
std::map<int, std::string> m;
m[5] = "five"; m[1] = "one"; m[8] = "eight";
auto it = m.lower_bound(6);          // smallest key >= 6  -> 8
if (it != m.end()) /* it->first == 8 */;
for (auto& [k, v] : m) { /* visited in sorted key order */ }

import java.util.TreeMap;
// TreeMap / TreeSet are red-black trees (ordered, O(log n))
TreeMap<Integer, String> m = new TreeMap<>();
m.put(5, "five"); m.put(1, "one"); m.put(8, "eight");
Integer k = m.ceilingKey(6);         // smallest key >= 6  -> 8
for (var e : m.entrySet()) { /* visited in sorted key order */ }

// JavaScript has NO built-in balanced BST / ordered map.
// Map preserves INSERTION order, not sorted order.
// Workaround: keep a sorted array and binary-search it,
// or use a third-party library (e.g. a red-black tree package).
const keys = [5, 1, 8].sort((a, b) => a - b); // [1, 5, 8]
function ceil(arr, target) {          // smallest value >= target
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] < target) lo = mid + 1; else hi = mid;
  }
  return lo < arr.length ? arr[lo] : null; // -> 8 for target 6
}

# Python has NO built-in balanced BST / ordered map.
# dict preserves INSERTION order, not sorted order.
# Use the bisect module on a sorted list, or sortedcontainers.SortedDict.
import bisect
keys = sorted([5, 1, 8])              # [1, 5, 8]
i = bisect.bisect_left(keys, 6)       # smallest value >= 6
ceil = keys[i] if i < len(keys) else None  # -> 8

Important: JavaScript and Python have no built-in balanced BST. Their Map/dict are hash-based and ordered only by insertion, not by key. When you need sorted-key operations in those languages, use a sorted array with the binary-search bisect pattern, or a library (sortedcontainers.SortedDict/SortedList in Python). C++‘s std::map/std::set and Java’s TreeMap/TreeSet are balanced (red-black) trees.

What you get from an ordered map

Beyond plain key lookup, a balanced BST gives you, all in O(log n):

• Ordered iteration — visit keys in sorted order.
• Range queries — lower_bound / ceilingKey / floorKey: the nearest key above or below a target.
• Min / max — first and last keys.

If you only need lookup by key and don’t care about order, a hash map is faster (O(1) average). Choose an ordered map specifically when order or nearest-key queries matter.

Common pitfalls

• Assuming dict/Map is sorted. It is insertion-ordered, not key-ordered.
• Reimplementing a red-black tree under interview pressure. Prefer the built-in unless explicitly asked to implement balancing.
• Using a hash map when you need range queries. Hash maps can’t answer “smallest key ≥ x”.

When to use it

Choose a self-balancing BST (via the built-in ordered map/set) when you need sorted order plus fast updates: leaderboards, interval scheduling, “next greater key” lookups, or maintaining a running sorted multiset. For pure key→value lookup, use a hash map; for static sorted data, a sorted array with binary search.

Ready to practice? Head to the advanced exercises.