AVL Tree

An AVL tree is a binary search tree that stores each node's height and rotates whenever a local balance factor reaches +2 or -2. That rule keeps search and insertion at O(log n). Insert the sorted keys 10..70: AVL stops at edge-height 2, while a plain BST reaches 6, cutting the worst search path from seven nodes to three.

Picture a hanging mobile with numbered weights. Add one weight and a branch may sag two levels to one side. You do not rebuild the mobile; you swing two or three nearby joints until the middle weight sits on top again. The keys keep their left-to-right order. Only the local parent-child links change.

How AVL trees work

Every node still obeys the BST rule: smaller keys live on the left, larger keys on the right. AVL adds one stored number:

height(node) = 1 + max(height(node.left), height(node.right))

This lesson counts edges, so a null child has height -1 and a leaf has height 0. The balance factor is:

BF(node) = height(node.left) - height(node.right)

A node is balanced when its balance factor is -1, 0, or +1. After inserting a leaf, the recursive calls unwind toward the root. At each ancestor, the algorithm first updates the stored height, then computes the balance factor. A result of +2 means the left side is too tall; -2 means the right side is too tall.

Insertion repairs the first unbalanced ancestor it reaches on that return walk. One repair site may require one primitive rotation or a pair of rotations. Afterward, the repaired subtree has the same height it had before the insertion, so higher ancestors do not need another rotation. That last fact is why an AVL insertion has at most one rebalancing event, not why it has "at most one rotation."

The four rotation cases (LL, RR, LR, RL)

The heavy side gives the first letter. The inserted key's direction from the heavy child gives the second.

LR and RL are where memorized recipes tend to fall apart. An inward zig-zag must first become an outward line. The second rotation then promotes the middle key.

Every rotation also transfers a middle subtree, called T2 here. Suppose a left rotation promotes the right child. That child's left subtree must become the demoted node's right subtree: its keys lie between the two rotating keys, so no other position preserves BST order. Rewire first, update the demoted node's height, then update the promoted node's height.

This lesson implements insertion and search. Deletion is a separate lesson-sized problem: removing a node can shrink a subtree, so several ancestors may need repairs on the way back to the root.

AVL tree step by step

The default run performs insert 30, insert 20, insert 10, insert 25, insert 28, insert 29, search 29.

1. Insert 30. The root is null, so 30 becomes a leaf with height 0. The no-rotation BST starts with the same root.

2. Insert 20. Since 20 is smaller than 30, it becomes the left child. Node 30 updates to height 1, with BF(30) = 0 - (-1) = +1. No repair is needed.

3. Insert 10. The path is 30, then 20, then the empty left slot. On the return walk, node 20 gets height 1 and balance factor +1. Node 30 gets height 2 and balance factor +2. The key arrived left-left, so this is LL. A right rotation promotes 20, leaving 10 on its left and 30 on its right.

4. Insert 25. Search goes right from 20 to 30, then left. Node 30 becomes left-heavy by one level; root 20 becomes right-heavy by one. Both remain legal.

5. Insert 28. The path is 20 -> 30 -> 25 -> right. Node 30 reaches balance factor +2, but its left child 25 leans right. This is LR. A left rotation promotes 28 above 25; a right rotation then promotes 28 above 30. The repaired local subtree is 28 with children 25 and 30.

6. Insert 29. The path is 20 -> 28 -> 30 -> left. Root 20 reaches balance factor -2, and the new key lies to the right of its right child 28, so this is RR. A left rotation promotes 28. The existing subtree rooted at 25 is T2: it moves from 28.left to 20.right, between keys 20 and 28 where it belongs. The final AVL tree has edge-height 2. The same inserts without rotations form a plain BST of edge-height 4.

7. Search 29. AVL visits 28 -> 30 -> 29, three probes. The plain BST visits 30 -> 20 -> 25 -> 28 -> 29, five probes. Both trees contain the same sorted sequence; their shapes determine how much searching you pay for.

The algorithm always unwinds one ancestor at a time: update its stored height, compute its balance factor, classify the local shape if needed, and repair the first illegal ancestor. Small traces can expose those stored heights beside the active path. Dense trees move the arithmetic into the workbench so labels do not bury the structure.

AVL tree time and space complexity

The logarithmic height is a theorem, not a hopeful reading of a tidy diagram. Let N(h) be the fewest nodes an AVL tree of edge-height h can have. The sparsest legal tree puts heights h - 1 and h - 2 under its root:

N(-1) = 0, N(0) = 1, N(h) = 1 + N(h - 1) + N(h - 2)

That recurrence gives N(h) = F(h + 3) - 1. Fibonacci numbers grow exponentially, so height grows logarithmically; a convenient bound is about h <= 1.44 log2(n + 2). Search follows one root-to-leaf path. Insertion follows that path down and back up, then performs one constant-size rebalancing event. There is no hidden "rotation tax" multiplying the logarithm.

When to reach for an AVL tree

Choose AVL when lookups dominate and a tight height bound matters enough to pay for exact height maintenance after writes. A red-black tree allows a looser shape, so update-heavy general-purpose libraries often prefer it; it trades some lookup tightness for less aggressive balancing work. A plain BST is simpler still, but its height depends entirely on insertion order. If an adversary or sorted input can choose that order, "simpler" may mean "linear search with pointers."

Edge cases

• Empty tree: search reaches null with zero probes. The first insertion creates a height-0 root.
• Duplicate key: insertion stops at the existing node. Node count, both tree shapes, and all stored heights remain unchanged.
• Inner-heavy insertion: LR and RL need two rotations. Applying only the outer rotation leaves the local subtree unbalanced.
• Null T2: a rotation still works when the middle subtree is empty; there is simply no child link to transfer.
• Visualization limit: the drawing caps the tree at 15 nodes. AVL trees have no fixed capacity; this is a canvas limit.

Common mistakes

• Reversing the balance-factor sign. This lesson uses left height - right height. The opposite convention is valid only if every case test reverses with it.
• Calling a leaf height 1 in an edge-height implementation. Here, null is -1 and a leaf is 0. Mixing conventions can corrupt stored heights and, through them, the balance factors and case tests.
• Updating heights before rewiring. The old child links produce old heights. Rewire first, update the demoted node, then the promoted node.
• Dropping T2. The middle subtree belongs between the promoted and demoted keys. Losing it deletes data; attaching it on the wrong side breaks BST order.
• Treating every left-heavy node as LL. The heavy child may lean inward. Check the second direction before choosing a single rotation.
• Rotating at every ancestor after insertion. Repair the lowest unbalanced ancestor once. Continuing to rotate higher nodes changes a tree that is already valid.