What is a self-balancing tree
A self-balancing binary search tree is a BST that reshapes itself after every insert and delete so its height stays proportional to log n. Nothing about the ordering rule changes; what changes is that the tree refuses to get tall.
The mechanism is one local operation, applied a handful of times per write. It does not rebuild the tree, it does not sort anything, and it never moves more than three pointers. It is called a rotation, and it is the entire subject of this article.
Imagine a shelf where you always add new books to the right end. Reach for a book and you walk the shelf from the left — fine at first, tedious once the shelf is long.
Now imagine the shelf reorganises itself: every time it notices one side has grown taller than the other, it shifts one book to become the new middle, and hangs the two halves off it. Nothing is sorted, nothing is rebuilt — one book changes position and the whole shelf gets shallower. That is a rotation.
The problem a Binary Search Tree couldn't solve
The previous article ended on a structure with excellent average behaviour and no floor under its worst case. Insert values in ascending order and every one goes right, producing a tree of height n − 1 — a linked list with an unused pointer per node.
The uncomfortable part was not that a bad case exists. It is that the bad case is the ordinary one: data comes from an ORDER BY, from an auto-incrementing id, from a timestamp, from a sorted file. A structure whose performance collapses on the most common input shape is not a structure you can put behind a production query.
So the goal is narrow and specific: keep every guarantee the BST already offers — ordered iteration, range queries, O(h) operations — while making h provably O(log n) no matter what order the data arrives in.
Rotations
A rotation takes a parent and one of its children and swaps which of them is on top, reattaching the subtrees so the ordering rule still holds. That is all it is.
A right rotation
The left child rises, the parent sinks to become its right child.
balance factor of 30 is +2, which is one past the limit
the same three values, one level shorter
Three pointer writes, and the height dropped. No comparison of values was needed to decide the reshape — only the observation that one side was too tall.
A left rotation is the exact mirror: the right child rises and the parent becomes its left child. Everything below applies to both, with left and right swapped, which is why implementations write one and derive the other.
Why the invariant survives
The reason a rotation is safe is worth spelling out, because it is the only thing that makes the operation legal rather than merely convenient.
When the parent has a subtree hanging off the child that rises, that subtree has to move. Watch where it lands:
25 sits between 20 and 30, which is what makes the next step legal
the same five values in the same order — a reshuffle, not an edit
The value 25 was in 20's right subtree, so by the invariant it is greater than 20. And it was in 30's left subtree, so it is less than 30. Those are exactly the two conditions for being a legal member of 30's left subtree after the rotation. The subtree does not need checking; its position already proved it.
That is the general argument. A rotation only ever moves the middle subtree, and the middle subtree is by definition bounded by the two nodes swapping places — so it is legal on both sides of the operation. Read the values left to right before and after and you get the same sequence, which is the strongest way to see that nothing was broken.
AVL trees
An AVL tree — named for Adelson-Velsky and Landis, 1962, the first self-balancing BST — enforces the strictest useful condition: for every node, its two subtrees differ in height by at most one.
The balance factor
Each node carries, or can compute, a balance factor: the height of its left subtree minus the height of its right. Legal values are -1, 0 and +1. Anything else means that node needs work.
50 leans left by one and 30 leans left by one — both legal, so no rotation
After an insert, only the nodes on the path from the new leaf back to the root can have changed height, so only those need checking. That is O(log n) nodes, and the fix at each is O(1) — which is what keeps the whole insert logarithmic.
The four cases
When a node's factor reaches ±2, which way to rotate depends on where the excess height actually is. There are four configurations, and they are two shapes plus their mirrors.
Left-left. The node leans left, and its left child also leans left. One right rotation fixes it — this is the figure from earlier in the article.
30 leans left, 20 leans left · one right rotation
Left-right. The node leans left, but its left child leans right. A single right rotation here does not help — it just moves the problem to the other side. First rotate the child left, which turns this into the left-left case, then rotate the node right.
30 leans left, 10 leans right · rotate 10 left first, then 30 right
Right-right and right-left are the mirrors of those two. So the whole decision table is: look at the node's lean, look at its child's lean, and if they disagree do an extra rotation first to make them agree.
Deletion
Delete works the same way — perform the BST delete from the previous article, then walk back up rebalancing. There is one difference worth knowing: an insert needs at most one rotation to restore the whole tree, while a delete can need one at every level on the way up, so O(log n) of them.
That asymmetry is the seed of the next section.
Red-black trees
AVL is not what your standard library uses. std::map, TreeMap, and the Linux kernel's scheduler all use red-black trees, which enforce a looser condition through a different mechanism: every node is painted red or black, and the colours obey rules that bound the height indirectly.
The five rules
- Every node is red or black.
- The root is black.
- All leaves — the null children — count as black.
- A red node's children are both black. So no two reds in a row.
- Every path from a node down to any of its null descendants passes through the same number of black nodes.
no red node has a red child, and every root-to-null path crosses two blacks
Rule 5 is the one doing the work. It says the tree is perfectly balanced if you only count black nodes. Rule 4 then caps how many reds can pad a path — at most one red between blacks — so the longest path is at most twice the shortest. Height is bounded by 2 · log₂(n+1), which is O(log n) with a worse constant than AVL.
Why the libraries chose red-black
AVL trees are shorter, so their lookups are marginally faster. Red-black trees won anyway, and the reason is the asymmetry mentioned above.
Red-black repairs use recolouring first and only rotate when recolouring is not enough. Flipping a colour is free — it moves no pointers — so many insertions and deletions resolve with no structural change at all. A red-black delete needs at most three rotations, ever; an AVL delete can need O(log n).
So the trade is: AVL is faster to read, red-black is faster to write and has a tighter bound on the work a single operation can do. For a general-purpose container in a standard library, where writes are common and predictable latency matters, that is the better default.
Try it yourself
The same playground as the previous article, with balancing switched on. Press Insert in ascending order — the input that produced height 6 last time — and watch it stay logarithmic. The status line names the rotation each time one fires, and every node shows its balance factor.
insert, search or delete — the path lights up as it walks
Worth trying: insert values one at a time and watch the balance factors climb toward ±2 before a rotation resets them. That moment, where the tree notices and reacts, is the whole idea.
Common operations and their costs
The point of the table is the column that no longer exists. The previous article needed a "degenerate" column showing O(n); here there is no bad case to show.
| Operation | AVL | Red-black |
|---|---|---|
| Search | ||
| Insert | ||
| Delete | ||
| Rotations per write | ||
| Height bound |
Every cell is O(log n). The differences are constant factors, and they point in opposite directions — which is exactly why both structures still exist.
Balanced trees in the real world
Ordered containers in standard libraries
std::map and std::set in C++, TreeMap and TreeSet in Java, BTreeMap in Rust. When a language offers a sorted map alongside a hash map, the sorted one is a balanced tree, and usually red-black.
The Linux kernel
The completely fair scheduler keeps runnable tasks in a red-black tree keyed by how much CPU time they have had, so "who runs next" is the leftmost node. epoll uses one to track watched file descriptors, and the virtual memory system uses one for address ranges. Predictable worst case is why — a scheduler cannot afford an occasional O(n).
Database indexes, and where B-trees come in
The CREATE INDEX in your migration is almost certainly a B-tree, not a binary one. Same idea, different constant: instead of one value and two children per node, a B-tree node holds hundreds of values and hundreds of children, sized so one node fills one disk page.
The reason is that the cost model changes. In memory, the cost is comparisons; on disk, the cost is page reads, and a page read costs the same whether you use one value from it or five hundred. Making nodes enormous makes the tree shallow — a few levels covers millions of rows — so a lookup is a handful of page reads instead of twenty.
This is what the hash tables article was pointing at when it noted that PostgreSQL defaults to B-tree indexes and offers hash indexes only as a specialisation. The B-tree default buys you ORDER BY without a sort and BETWEEN without a scan, both from the ordering property, and a hash index can offer neither.
When balanced trees fall short
You pay on every write. Maintaining the invariant is work that a plain BST does not do. If your workload is write-heavy and lookups are rare, or if you know your insertion order is already random, the rebalancing is overhead buying a guarantee you were not going to need.
A hash table is still faster for exact lookups. Average O(1) beats guaranteed O(log n), and the gap is wider than the notation suggests. Balancing does not change the decision from the previous article: choose a tree for ordering, a hash table for pure key-value access.
Still pointer chasing. A balanced tree guarantees you touch only log n nodes, not that those nodes are anywhere near each other in memory. Twenty guaranteed cache misses is better than a million, and worse than the sequential read an array gives you. This is precisely why the disk-oriented case became B-trees rather than balanced binary trees.
Bulk-loading sorted data deserves better. If you already have n sorted values, inserting them one at a time costs O(n log n) and a pile of rotations, when you could build a perfectly balanced tree directly in O(n) by taking the middle value as the root and recursing. Libraries expose this as a range constructor; use it when you have it.
Correctness is genuinely hard. Delete is where hand-written balanced trees break, and the failures are silent — the tree stays a valid BST while losing its height guarantee, so it works and slowly gets slower. This is a use-the-library structure.
Summary
Balanced trees keep everything a BST offers and add a floor under the worst case:
- A rotation swaps a parent with a child — three pointer writes, and it can only move the middle subtree, which the invariant already proved legal on both sides
- In-order sequence is preserved exactly — so sorted iteration, range queries, minimum and maximum all survive; only the shape changes
- AVL keeps every balance factor within one — four rotation cases, which are two shapes and their mirrors, and the double cases exist only to turn an inside lean into an outside one
- Red-black bounds height with colours — no two reds in a row, equal black counts on every path, giving
2 log n - Libraries chose red-black — recolouring is free, so writes rarely rotate, and a delete needs at most three rotations against AVL's
O(log n) - B-trees are the same idea for disk — hundreds of values per node, because the unit of cost is a page read, not a comparison
The key insight is that balancing converts an average-case guarantee into a worst-case one, and pays a constant factor on writes to do it. A plain BST is already O(log n) on random input; what it cannot survive is the input you are most likely to have. Rotations are cheap insurance against your data arriving in order — which it will.
That closes the search story. The next article changes the question. Instead of "where is this value", it asks "what is the smallest value right now" — and it turns out a much weaker invariant answers that one, weak enough to fit the whole tree in a flat array with no pointers at all.