AVL Tree
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 50, 25, 75, 10, 30, 60, 80, 5, 27, 55 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 19, with their answers.
50 has balance 1 after inserting 25. What happens here?
Answer: Stays as it is. A balance of 1 is allowed. Only 2 or -2 triggers a rotation.
50 has balance 0 after inserting 75. What happens here?
Answer: Stays as it is. A balance of 0 is allowed. Only 2 or -2 triggers a rotation.
25 has balance 1 after inserting 10. What happens here?
Answer: Stays as it is. A balance of 1 is allowed. Only 2 or -2 triggers a rotation.
50 has balance 1 after inserting 10. What happens here?
Answer: Stays as it is. A balance of 1 is allowed. Only 2 or -2 triggers a rotation.
25 has balance 0 after inserting 30. What happens here?
Answer: Stays as it is. A balance of 0 is allowed. Only 2 or -2 triggers a rotation.
50 has balance 1 after inserting 30. What happens here?
Answer: Stays as it is. A balance of 1 is allowed. Only 2 or -2 triggers a rotation.
75 has balance 1 after inserting 60. What happens here?
Answer: Stays as it is. A balance of 1 is allowed. Only 2 or -2 triggers a rotation.
50 has balance 0 after inserting 60. What happens here?
Answer: Stays as it is. A balance of 0 is allowed. Only 2 or -2 triggers a rotation.
75 has balance 0 after inserting 80. What happens here?
Answer: Stays as it is. A balance of 0 is allowed. Only 2 or -2 triggers a rotation.
50 has balance 0 after inserting 80. What happens here?
Answer: Stays as it is. A balance of 0 is allowed. Only 2 or -2 triggers a rotation.
10 has balance 1 after inserting 5. What happens here?
Answer: Stays as it is. A balance of 1 is allowed. Only 2 or -2 triggers a rotation.
25 has balance 1 after inserting 5. What happens here?
Answer: Stays as it is. A balance of 1 is allowed. Only 2 or -2 triggers a rotation.
50 has balance 1 after inserting 5. What happens here?
Answer: Stays as it is. A balance of 1 is allowed. Only 2 or -2 triggers a rotation.
30 has balance 1 after inserting 27. What happens here?
Answer: Stays as it is. A balance of 1 is allowed. Only 2 or -2 triggers a rotation.
25 has balance 0 after inserting 27. What happens here?
Answer: Stays as it is. A balance of 0 is allowed. Only 2 or -2 triggers a rotation.
50 has balance 1 after inserting 27. What happens here?
Answer: Stays as it is. A balance of 1 is allowed. Only 2 or -2 triggers a rotation.
60 has balance 1 after inserting 55. What happens here?
Answer: Stays as it is. A balance of 1 is allowed. Only 2 or -2 triggers a rotation.
75 has balance 1 after inserting 55. What happens here?
Answer: Stays as it is. A balance of 1 is allowed. Only 2 or -2 triggers a rotation.
50 has balance 0 after inserting 55. What happens here?
Answer: Stays as it is. A balance of 0 is allowed. Only 2 or -2 triggers a rotation.
How it runs, step by step
Insert 50, 25, 75, 10, 30, 60, 80, 5, 27, 55 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 10 values with rebalancing.
Insert 50. First as an ordinary BST insert: descend and attach a leaf.
Inserting 50.
50 is the first value, so it is the root.
50 is added as a leaf.
Insert 25. First as an ordinary BST insert: descend and attach a leaf.
Inserting 25.
25 attaches as the left child of 50.
25 is added as a leaf.
At 50: left height 1, right height 0, balance 1. Within one, so it stays.
Node 50 has balance 1. It is fine.
Insert 75. First as an ordinary BST insert: descend and attach a leaf.
Inserting 75.
75 attaches as the right child of 50.
75 is added as a leaf.
At 50: left height 1, right height 1, balance 0. Within one, so it stays.
Node 50 has balance 0. It is fine.
Insert 10. First as an ordinary BST insert: descend and attach a leaf.
Inserting 10.
10 attaches as the left child of 25.
10 is added as a leaf.
At 25: left height 1, right height 0, balance 1. Within one, so it stays.
Node 25 has balance 1. It is fine.
At 50: left height 2, right height 1, balance 1. Within one, so it stays.
Node 50 has balance 1. It is fine.
Insert 30. First as an ordinary BST insert: descend and attach a leaf.
Inserting 30.
30 attaches as the right child of 25.
30 is added as a leaf.
At 25: left height 1, right height 1, balance 0. Within one, so it stays.
Node 25 has balance 0. It is fine.
At 50: left height 2, right height 1, balance 1. Within one, so it stays.
Node 50 has balance 1. It is fine.
Insert 60. First as an ordinary BST insert: descend and attach a leaf.
Inserting 60.
60 attaches as the left child of 75.
60 is added as a leaf.
At 75: left height 1, right height 0, balance 1. Within one, so it stays.
Node 75 has balance 1. It is fine.
At 50: left height 2, right height 2, balance 0. Within one, so it stays.
Node 50 has balance 0. It is fine.
Insert 80. First as an ordinary BST insert: descend and attach a leaf.
Inserting 80.
80 attaches as the right child of 75.
80 is added as a leaf.
At 75: left height 1, right height 1, balance 0. Within one, so it stays.
Node 75 has balance 0. It is fine.
At 50: left height 2, right height 2, balance 0. Within one, so it stays.
Node 50 has balance 0. It is fine.
Insert 5. First as an ordinary BST insert: descend and attach a leaf.
Inserting 5.
5 attaches as the left child of 10.
5 is added as a leaf.
At 10: left height 1, right height 0, balance 1. Within one, so it stays.
Node 10 has balance 1. It is fine.
At 25: left height 2, right height 1, balance 1. Within one, so it stays.
Node 25 has balance 1. It is fine.
At 50: left height 3, right height 2, balance 1. Within one, so it stays.
Node 50 has balance 1. It is fine.
Insert 27. First as an ordinary BST insert: descend and attach a leaf.
Inserting 27.
27 attaches as the left child of 30.
27 is added as a leaf.
At 30: left height 1, right height 0, balance 1. Within one, so it stays.
Node 30 has balance 1. It is fine.
At 25: left height 2, right height 2, balance 0. Within one, so it stays.
Node 25 has balance 0. It is fine.
At 50: left height 3, right height 2, balance 1. Within one, so it stays.
Node 50 has balance 1. It is fine.
Insert 55. First as an ordinary BST insert: descend and attach a leaf.
Inserting 55.
55 attaches as the left child of 60.
55 is added as a leaf.
At 60: left height 1, right height 0, balance 1. Within one, so it stays.
Node 60 has balance 1. It is fine.
At 75: left height 2, right height 1, balance 1. Within one, so it stays.
Node 75 has balance 1. It is fine.
At 50: left height 3, right height 3, balance 0. Within one, so it stays.
Node 50 has balance 0. It is fine.
All 10 values in, 0 rotations. Height 4: an unbalanced BST with these values could be up to 10 tall.
The AVL tree is complete with height 4 after 0 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
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
- AVL treeWikipedia
- Tree rotationWikipedia
- AVL tree visualisedUSF
- avl.c, the AVL tree embedded throughout OpenZFSOpenZFS · github.com
- RtlInitializeGenericTableAvl: AVL generic tables for file system driversMicrosoft Learn · learn.microsoft.com