AVL tree

On 29 July 2025 a magnitude 8.8 earthquake struck, the strongest in the USGS catalogue in eleven years, and over the next week the catalogue recorded hundreds of shocks of magnitude 5 and above. Suppose a service keeps all shocks of the last seven days at hand in a search tree ordered by time: a new one is always later than all others, and one older than a week leaves. For an ordinary search tree this is the worst case: every new key lands to the right of all others, and the tree grows as a stick; by 4 August it would have 277 storeys. An AVL tree on the same events never rose above nine storeys, as many as a perfect tree of 277 nodes. The scene starts a few hours before the main shock.

Look at the right edge. A new shock takes its place as a leaf at the bottom right, and almost at once some node above it turns out lopsided: its right branch is two storeys higher than its left. The tree rotates; nodes change storeys, but the left-to-right order stays the same. In 2025, 946 insertions out of a thousand ended with a rotation. Old shocks leave on the left, and there are half as many rebalancings there: 481 per thousand deletions. Switch the tree to “no balancing” and the same week turns into a diagonal, and every search for the latest shock walks all of it. In the chart at the bottom the orange line is how many shocks are in the window, that is, the height of the stick; the teal line is the height of the AVL tree, and it stays at the dashed line of perfect height for all eleven years.

The idea

Every node stores the height of its subtree, and there is one rule: at any node the heights of the left and right branches differ by at most one. Insertion and deletion are done as in an ordinary search tree, and then the tree is walked from the place of the change up to the root, recomputing heights, and wherever the difference has become two, it rotates. A rotation moves nodes from storey to storey without touching the order of keys and gives the lopsided bush an allowed shape again. This rule is enough to keep the height below about 1.44·log₂ n whatever order the keys come in.

What a rotation is, how to write it in three assignments and how the tree itself was invented is told in the course chapter on search trees; there is also a garden there where you can rotate by hand. Here: how many rotations each operation costs, why the height cannot grow, and what happens on deletion, which textbooks often describe in one line.

The balance of a node is the difference between the heights of its left and right branches. In an AVL tree it is −1, 0 or +1, and it can be stored instead of the height, two bits per node. Storing the height is simpler, and in a node with two links it takes almost no room anyway; the listing below does that.

Four kinds of lean

Suppose that after an insertion or deletion the left branch of a node x has become two storeys higher than the right one. Call the left child y. What to do depends on which branch of y is higher.

The letters read as the path from the lopsided node down to the highest branch: LL is left and left again. When the high branch grows outwards, one rotation lifts it a storey and the bush levels out. When it grows inwards, a zigzag, one rotation only moves the lean to the other side: the high middle branch moves over to x and stays just as high. So the zigzag is first straightened by a rotation about the child, and the usual case LL or RR results.

The proviso “or both equally” is needed only on deletion. After an insertion the child of the lopsided node always has branches of different heights: the new branch grew and became higher. On deletion the child can turn out level, and then a single rotation is needed. A double one in that case can leave a two-storey lean at the former child, and the tree stops being an AVL tree; this mistake is common in home-made implementations, and one of the article's problems catches it.

In the earthquake scene only one case ever occurs on insertion: RR. The new key is larger than all others, and the high branch is always the right branch of the right child. The listing below inserts 19,073 keys in order, as many as there are events in the catalogue, and all of its 19,058 rebalancings are RR.

One rotation is enough for an insertion

An insertion increases heights on the way up from the new leaf, and several nodes on this path may become lopsided at once. Only one, however, has to be repaired.

A rotation does not change the height of the tree, so it can grow only on insertions without a rotation. On increasing keys this shows in pure form: the listing inserts the numbers 1 to 19,073 and counts 19,058 rotations. Exactly fifteen insertions did without one, the 1st, 2nd, 4th, 8th and so on by powers of two up to the 16 384th, and each of them raised the tree by a storey: to height 15, as for a perfect tree. Why exactly powers of two is worked out in the article's second problem: a tree grown from keys in order turns out to be the binary notation of the number n, and each insertion an increment.

If the keys come in random order, there are half as many rotations. The same year 2025, shuffled, is inserted with 477 rebalancings per thousand insertions, and a little over half of them, 563 of 1015, are double.

Why the height is a logarithm

The rule speaks only of the two branches of one node, yet it holds the height of the whole tree. To see this, ask the other way round: what is the smallest number of nodes an AVL tree of height h can have?

For a million keys that is at most 28 storeys, for a billion at most 42. In the course chapter the same idea is proved with a simpler bound, $h \le \log_\varphi(n + 1)$; here Binet's formula adds precision, and the bound becomes almost attainable: the thinnest trees, called Fibonacci trees, come right up to it. Here they are.

Real AVL trees are far below the limit. For 277 nodes the theorem allows 11 storeys, and the scene's tree had height 9, like a perfect one. The 2128 shocks of 2025, shuffled, grew into a tree of height 13 against a perfect 12 and an allowed 15. Fibonacci trees are a rare breed: to grow one by insertions, the keys have to be chosen on purpose.

Deletion: the lean climbs to the root

Deletion is done as in an ordinary search tree: a leaf is cut off, a node with one branch is replaced by that branch, and a node with two branches gets its key replaced by its successor, the leftmost key of the right branch, and the successor's old node is cut off. Then, as on insertion, the tree is walked upwards recomputing heights. The difference is that a rotation after a deletion often makes the subtree a storey lower. Then the parent's branch gets shorter, and it may become lopsided too, and then a node higher still. In the scene above choose height 8 and press “Delete the smallest”: the lean climbs to the root, and there are three rebalancings.

Fibonacci trees reach this bound. The listing builds them for heights 1 to 12, deletes each key in turn from a fresh tree and finds the worst. Deleting the smallest key is always among the worst: exactly ⌊(h − 1)/2⌋ rebalancings. This is exactly what happens on the left in the first scene: the smallest key, the oldest event, leaves the window.

h  nodes  delete the smallest  the worst key
8     54                    3              3
9     88                    4              4
10   143                    4              4
11   232                    5              5
12   376                    5              5

On average, though, cascades are rare. In 2025 the seven-day window made 0.481 rebalancings per deletion, and shuffled order 0.248. The worst case is logarithmic, but you almost never have to pay it.

Code

A node stores a key, two links and the height of its subtree. Insertion and deletion are recursive: on the way back out of the recursion each node calls _rebalance, and the climb to the root comes by itself; the height of the tree is at most a few dozen, so the stack will not overflow. The check method walks the tree and checks the order of keys, the stored heights and the balance rule; in problems such a check catches mistakes that would otherwise show up a thousand operations later. In Go the tree is generic, for any ordered key type (cmp.Ordered), and the window's key, “time and line number”, is packed into one number.

window      most nodes  max height  perfect  rebalancings per insert  per delete
1 day              166           8        8                    0.691       0.385
7 days             277           9        9                    0.946       0.481
30 days            471          10        9                    0.984       0.496
no window         2128          12       12                    0.994       0.000
shuffled          2128          13       12                    0.477       0.248

The wider the window, the closer the share of rotating insertions is to one, to what a solid increasing sequence gives, where only the insertions that raise the height do without a rotation. In the 30-day window the tree once rose a storey above perfect, 10 against a perfect 9: an AVL tree need not be perfect, the rule is enough for it.

What it costs

Memory is O(n): a height or balance is added to the key and two links. A rotation costs O(1): three links and two heights. The climb to the root after an operation costs O(log n) even without rotations: the heights must be recomputed along the whole path. It can be cut short, since once a node's height has not changed nothing above will change, but that does not change the asymptotics.

What all this is for shows in a measurement. Inserting n keys: an AVL tree on increasing and on random keys, and an ordinary search tree on the same.

On increasing keys the ordinary tree pays for each insertion with a walk along the whole stick: at ten thousand keys in Go that is almost fifty times longer than the AVL tree, and the gap grows in proportion to n. A million increasing keys go into the AVL tree in Go in under a third of a second. On random keys balancing wins nothing, since the ordinary tree is low anyway, and only costs. In Go the difference is small, while in Python the AVL tree is 2.5–3.7 times slower: every level of recursion, every height update and balance comparison is work for the interpreter. Curiously, the AVL tree on increasing keys in Go is faster than on random ones, although there are twice as many rebalancings: the new keys always go down the same right branch, and its nodes never leave the processor cache.

Where it is used

Kernels and system libraries. OpenZFS, the file system that came from Solaris, has a shared AVL tree for kernel code, the file module/avl/avl.c. Its comment explains two decisions: the node is embedded right in the user's structure, with no separate memory allocation, and instead of recursion the node stores a link to its parent, because the kernel stack is small. In musl, a compact C standard library, the functions tsearch and tdelete, which POSIX describes as operations on a search tree, are built on an AVL tree: the node stores a height, and the lean is checked the same way as in the listing. In the Windows kernel drivers have ready-made “generic tables”; by default they are built on a splay tree, and the documentation warns that such a tree can become deep and narrow, even a straight line, and recommends the AVL variant, RtlInitializeGenericTableAvl, for a more balanced tree.

Against the red-black tree. Standard ordered dictionaries are usually built on a red-black tree: it allows a bigger lean and so rotates less often, at most two rotations on insertion and at most three on deletion. The AVL tree is lower and closer to perfect, so a search in it makes slightly fewer comparisons, but it pays for that with rotations. The two trees are compared on the same data in the article on the red-black tree.

Where neither fits. If the data lie on disk, you need a B-tree: a binary tree would read a page per storey. If simplicity matters more and randomness is acceptable, there are the treap and the skip list. And Python and Go have no ready balanced tree in their standard libraries at all; for ordered data they keep a sorted array, as told in the article on the search tree.

History

The AVL tree is the first search tree that guarantees logarithmic height for any order of keys. Georgy Adelson-Velsky and Evgenii Landis described it in 1962 in the paper “An algorithm for the organization of information”: four pages about a tree that checks its shape after every insertion and repairs it with rotations, so that search and insertion take on the order of log n steps for any order of keys. An English translation came out the same year, and the name from the initials of the surnames, AVL, took root in every language. Who the authors were and what they worked on is told in the course chapter. B-trees appeared in 1970, and in 1972 Rudolf Bayer invented symmetric binary B-trees, later called red-black trees: they learned to keep their balance with fewer rotations.

Problems

In the first problem you implement an AVL tree with deletion honestly and count the rotations on a stream of events, by the very rules of the article, including the proviso “or both equally”. The second is about why on increasing keys only powers of two do without a rotation: the tree of the keys 1, 2, …, n has to be described without building it, for n up to 10¹⁸.