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.

Insert 10, 20, 30 one at a time. After each, walk back up checking balance, and rotate the first node whose sides differ in height by two.

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. 10 has balance -1 after inserting 20. What happens here?

    • Stays as it is
    • One rotation
    • Two rotations

    Answer: Stays as it is. A balance of -1 is allowed. Only 2 or -2 triggers a rotation.

  2. 20 has balance -1 after inserting 30. What happens here?

    • Stays as it is
    • One rotation
    • Two rotations

    Answer: Stays as it is. A balance of -1 is allowed. Only 2 or -2 triggers a rotation.

  3. 10 has balance -2 after inserting 30. What happens here?

    • Stays as it is
    • One rotation
    • Two rotations

    Answer: One rotation. Right-right: the imbalance is a straight line, so one rotation fixes it.

How it runs, step by step

  1. Insert 10, 20, 30 one at a time. After each, walk back up checking balance, and rotate the first node whose sides differ in height by two.

    Building an AVL tree by inserting 3 values with rebalancing.

  2. Insert 10. First as an ordinary BST insert: descend and attach a leaf.

    Inserting 10.

  3. 10 is the first value, so it is the root.

    10 is added as a leaf.

  4. Insert 20. First as an ordinary BST insert: descend and attach a leaf.

    Inserting 20.

  5. 20 attaches as the right child of 10.

    20 is added as a leaf.

  6. At 10: left height 0, right height 1, balance -1. Within one, so it stays.

    Node 10 has balance -1. It is fine.

  7. Insert 30. First as an ordinary BST insert: descend and attach a leaf.

    Inserting 30.

  8. 30 attaches as the right child of 20.

    30 is added as a leaf.

  9. At 20: left height 0, right height 1, balance -1. Within one, so it stays.

    Node 20 has balance -1. It is fine.

  10. At 10: left height 0, right height 2, balance -2. Too heavy on the right, and the new value went right of the right child. One left rotation.

    Node 10 has balance -2. It needs a rotation.

  11. 20 is now the root of this subtree, with 10 beneath it. Heights differ by at most one again, and nothing above needs checking: the subtree is exactly as tall as before the insert.

    After the rotation 20 heads the subtree and it is balanced.

  12. All 3 values in, 1 rotation. Height 2: an unbalanced BST with these values could be up to 3 tall.

    The AVL tree is complete with height 2 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