Balanced Trees & set / map

Feed a plain BST sorted data and it quietly turns into a linked list. Balanced trees guarantee O(log n) whatever the input, and you use one every time you write std::set or std::map.

intermediate⏱ 10 min read

←Builds on

5Binary Search TreeA BST decays to O(n) when it grows into a chain; balancing keeps h = O(log n).1Hash Tables: Sets & Mapsstd::set and std::map are the ordered counterparts of unordered_set and unordered_map.

Leads to→

101-D DP: Coins & LISO(n log n) LIS keeps the best tails sorted and finds each spot with lower_bound, as in std::set.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01The shape decides the cost

Every BST operation costs O(h), and h depends only on the order of the insertions. Insert 1, 2, 3, 4, 5, 6, 7 and each key hangs to the right of the previous one: a chain of height 6, and search(7) checks all seven keys. Insert the same keys as 4, 2, 6, 1, 3, 5, 7 and you get a perfect tree of height 2: three comparisons.

Real data is often sorted or nearly sorted: timestamps, auto-increment ids, names read from a sorted file. On such input a plain BST is exactly as slow as a list.

We want a tree that keeps itself short whatever the insertion order, with h = O(log n) for n keys. Balancing does not change what a BST is; it only adds a little repair work after each insert and delete.

02Rotations: the repair tool

Every balanced tree repairs itself with rotations. A right rotation at y takes its left child x and lifts it: x becomes the root of this subtree, y becomes x’s right child, and x’s old right subtree B moves over to become y’s left subtree. A left rotation is the mirror image.

Only three pointers change, so a rotation costs O(1). And it never breaks the BST rule: before and after, the inorder sequence is A, x, B, y, C. What changes is the shape: one side gets a level shorter, the other a level taller.

After an insert or delete, a balanced tree walks back up toward the root, checks at each vertex whether its subtree has become too lopsided, and fixes it with one or two rotations.

Only the parents of x, y and the subtree B change.

03AVL and red-black trees

Two recipes dominate:

AVL tree: every node stores its height, and the heights of its two subtrees may differ by at most 1. After an insert or delete, walk back up; wherever the difference reaches 2, rotate. The height stays below about 1.44·log₂ n.
Red-black tree: every node is red or black; a red node never has a red child, and every path from the root down to a NULL link passes the same number of black nodes. The rules are looser, so it rotates less often; the height stays below 2·log₂(n + 1).

You rarely write either by hand. What matters is the guarantee: search, insert and delete in O(log n) even in the worst case, plus everything a plain BST offers: sorted iteration, minimum, maximum, predecessor and successor. Treaps and splay trees reach similar bounds using randomness or amortized analysis.

04std::set and std::map in practice

In C++ the balanced tree comes ready to use: std::set, std::map, std::multiset and std::multimap are red-black trees. Use them when you need a sorted collection that keeps changing:

s.insert(x), s.erase(x), s.count(x): O(log n);
s.lower_bound(x): the first key ≥ x, also O(log n), the walk in the figure;
*s.begin() and *s.rbegin() are the minimum and maximum; a range-for visits the keys in sorted order.

std::map<K, V> is the same tree with a value attached to each key. If you only ask “is x present?” and never need order, std::unordered_set (a hash table) is usually faster on average. Choose the tree when order matters: the nearest key, everything in a range, the smallest free slot. Java’s TreeSet and TreeMap play the same role; Python has nothing like it built in, so people use bisect on a sorted list or the sortedcontainers package.

lower_bound(15) is one walk from root to leaf in the balanced tree.

Cost at a glance

Search / insert / delete (balanced)O(log n)

lower_bound / upper_boundO(log n)

One rotationO(1)

Iterate in sorted orderO(n)

Remember

A plain BST’s height depends on the insertion order; sorted input turns it into a chain with O(n) operations.
Rotations reshape a subtree in O(1) without breaking the BST order, and balanced trees use them to keep h = O(log n).
In practice, reach for std::set / std::map (red-black trees) whenever you need a sorted collection that changes.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Compare the two builds: the same seven keys, a chain of height 6 versus a tree of height 2. Count the comparisons for search(7).

Interactive visualizerfocus here, then space ← →

Degenerate BST (ascending inserts) · height: 1 · search(7) comparisons: 0

Insert 1. Since keys arrive in increasing order, each one attaches to the right of the last, and the tree grows into a straight chain.

Pseudocode

 1 insert keys one by one into a BST 2   each key walks down to a leaf slot 3 search cost = number of nodes on the path = O(height) 4 balanced trees (AVL, red-black) rotate to keep height O(log n)

1 / 1

Check

Three questions. Pick an answer to see why.

A right rotation at y (left child x; subtrees A, B under x, C under y). Which subtree gets a new parent?

You must add numbers, remove numbers, and answer “smallest number ≥ q” many times. The best tool?

Which rule does an AVL tree maintain?

Practice

Real problems to lock it in, easiest first.

LeetCodeBalanced Binary Tree beginner↗LeetCodeConvert Sorted Array to Binary Search Tree beginner↗CSESConcert Tickets intermediate↗LeetCodeMy Calendar I intermediate↗CSESTraffic Lights intermediate↗