AlgoScope

AVL Tree

structureadvancedTime O(log n)Space O(1)

A search tree that refuses to lean. After every insert it walks back up, and the first node whose two sides differ in height by two gets rotated until they do not.

510152527305055607590

Delete 90 from this AVL tree. First an ordinary BST delete: a leaf is unlinked, a node with one child is replaced by it, and a node with two children is replaced by its successor, the smallest key on its right. Then every ancestor of the spot that changed is checked, and unlike insert, more than one of them may need a rotation.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.

  1. 90 has 0 children. How is it removed?

    • A leaf: unlink it
    • One child: the child takes its place
    • Two children: the successor takes its place

    Answer: A leaf: unlink it. The number of children decides: nothing, the child, or the successor moves into the gap.

  2. 75 has balance 2, and its taller child has balance 1. What happens here?

    • Stays as it is
    • One rotation
    • Two rotations

    Answer: One rotation. The taller child leans the same way or is even, so one rotation fixes it.

  3. 50 has balance 1. What happens here?

    • Stays as it is
    • One rotation
    • Two rotations

    Answer: Stays as it is. A balance of 1 is allowed, but unlike insert the walk continues upward.

How it runs, step by step

  1. Delete 90 from this AVL tree. First an ordinary BST delete: a leaf is unlinked, a node with one child is replaced by it, and a node with two children is replaced by its successor, the smallest key on its right. Then every ancestor of the spot that changed is checked, and unlike insert, more than one of them may need a rotation.

    Deleting 90 from an AVL tree of 11 nodes.

  2. Found 90 as the right child of 75. It is a leaf, so it is simply unlinked.

    Found 90.

  3. 90 is unlinked. Now walk back up: 75, 50 may have lost height.

    90 is unlinked.

  4. At 75: left height 2, right height 0, balance 2. Too heavy on the left and the left child leans left or is even: one right rotation.

    Node 75 has balance 2.

  5. 60 now heads this subtree with 75 beneath it. The subtree may be shorter than before the delete, so the ancestors above still have to be checked.

    After the rotation 60 heads the subtree.

  6. At 50: left height 3, right height 2, balance 1. Within one, so it stays. Keep climbing, since a delete can shorten the whole path.

    Node 50 has balance 1.

  7. 90 deleted, 1 rotation on the way up. Height 4. A delete can need a rotation at every level, O(log n) of them, where an insert never needs more than one.

    Deleted 90; the tree has height 4 after 1 rotations.

Remember

  • Balance factor is left height minus right height, and every node must stay within -1 to 1.
  • A straight-line imbalance takes one rotation. A zig-zag takes two, the child first.
  • One rotation restores the subtree's old height, so an insert never needs more than one fix.

Topics covered

Related

Where this is used

FilesystemsOpenZFS in-memory indexes

OpenZFS embeds an AVL tree in most of the sorted structures it keeps in memory: the vdev I/O scheduler's offset-ordered read and write queues, the set of open dbufs hanging off each dnode, the pool's error lists. The tree links are fields inside the structures being indexed, so avl_insert and avl_remove allocate nothing and take no lock of their own, which matters on a kernel path that churns thousands of entries per transaction group. The tight height bound is what keeps a lookup short while that churn is going on.

Operating systemsWindows file system drivers

The Windows kernel ships two versions of its generic table API: the default is built on splay trees, and the Rtl...GenericTableAvl family is built on AVL. Microsoft's own driver documentation tells you to switch to the AVL version because an unlucky insert order can stretch a splay tree into something close to a straight line, and file systems use these tables for things like name-lookup data on every open file. Paying a rotation or two per write buys a height that cannot degrade.

Language runtimesErlang ETS ordered_set tables

An ETS table declared as ordered_set is an AVL tree in the BEAM's C source. Ordered tables have to answer ets:next/2 and range selects in key order, which rules out a hash table, and any process may insert any key at any moment, so the runtime needs a shape that the arrival order of keys cannot degrade. Worst-case depth matters more than average depth when one slow table is shared by every process touching it.

Standard librariestsearch in musl libc

POSIX's tsearch and tfind build a binary search tree out of nodes the library owns, and musl implements them as an AVL tree. Each node carries one small height field, no parent pointer and no colour, and the rotation code is a few dozen lines, which suits a libc trying to stay small. The balance guarantee is what stops the classic failure of a caller inserting already-sorted keys into a plain BST.

Why it works this way

Why allow a height difference of one, and not demand zero?

A tree where every node's two sides are exactly equal in height only exists when the node count is 2^k - 1, so almost every insert would force a rebuild. One level of slack is the loosest rule that still pins the height down: the smallest AVL tree of height h has N(h) = N(h-1) + N(h-2) + 1 nodes, which grows like the Fibonacci numbers, so the height stays under about 1.44 log2(n). A worst-case AVL tree is roughly 44 percent taller than a perfect one, and that is what buys you cheap inserts.

Why an insert stops after one rotation but a delete can rotate at every level

A delete makes a subtree one level shorter, and the rotation that rebalances it can take off one more level, which unbalances the parent, and so on all the way to the root. An insert has no such chain. That is why the delete code calls rebalance on every frame as the recursion unwinds while insert returns the moment it has rotated, and why a single delete can cost O(log n) rotations against an insert's one.

Choosing the case by the inserted key only works for insert

The insert code tests key < n.left.key to tell a left-left imbalance from a left-right one, which is sound because the key just added is certainly inside the heavy subtree. After a delete the key is gone and may have been on the light side, so the same test picks the wrong case and the tree comes out still unbalanced. The general rule, the one rebalance uses, is to read the taller child's own balance factor: the same sign as the parent means a single rotation, the opposite sign means the double. A balance factor of zero on that child only ever happens during a delete, and there the single rotation is the one that works, because the double would move a whole subtree off that child and leave it leaning by two. That is why the test is >= 0 and not > 0.

AVL or red-black?

Both hold the height to O(log n), but AVL's bound is about 1.44 log2(n) against red-black's 2 log2(n), so AVL lookups touch fewer nodes. The cost is on the write path: a red-black delete needs at most three rotations, an AVL delete may rotate all the way up. AVL also stores a height or balance factor per node where red-black stores a single colour bit. Read-heavy in-memory indexes lean AVL, while general-purpose ordered containers tend to take the bounded rebalancing work instead, which is what std::map, Java's TreeMap and the Linux scheduler's run queue all do with red-black trees.

Read more

Next up