AVL trees: insertion

Why AVL trees?

A binary search tree is fast only while it stays bushy. Insert keys in sorted order and it degrades into a linked list, and every operation becomes O(n). An AVL tree, named after its inventors Adelson-Velsky and Landis (1962), was the first self-balancing binary search tree. It checks every node's balance after each change and repairs it with rotations, keeping the height below about 1.44·log₂(n + 2). So search, insert and delete are all O(log n).

Height and balance factor

• The height of a subtree is the number of nodes on its longest path down. An empty subtree has height 0, a leaf has height 1, and any other node has 1 + the larger of its children's heights.
• A node's balance factor is height(left) − height(right). Positive means left-heavy, negative means right-heavy.

The AVL rule: every node's balance factor is −1, 0 or +1.

Inserting a key

First insert it like any binary search tree: walk down from the root, going left when smaller and right when larger, and attach it at the empty spot you reach. The new leaf has height 1.

Only the nodes on the path you just walked can have changed height. So walk back up that path, and at each node update its height and work out its balance factor:

Balance factor	What it means	What to do
0	The shorter side caught up; this node's height didn't change.	Stop. Nothing above can have changed.
+1 or −1	Still balanced, but this node grew taller.	Move up to the parent and check again.
+2 or −2	Out of balance.	Rotate (below), then stop.

The four rotation cases

When a node is out of balance, name the three nodes involved:

A

the unbalanced node (the first one you meet walking up)

B

A's taller child

C

B's taller child

The case is named after the two steps from A down to C. These are also the two turns the new key took on its way down.

Case	Shape	Fix
Left-Left	B is A's left child, C is B's left child: a straight line.	Right-rotate at A.
Right-Right	The mirror image: a straight line to the right.	Left-rotate at A.
Left-Right	B is A's left child, C is B's right child: a zig-zag.	Left-rotate at B (now it's Left-Left), then right-rotate at A.
Right-Left	The mirror image zig-zag.	Right-rotate at B (now it's Right-Right), then left-rotate at A.

A left rotation lifts the right child; a right rotation lifts the left child. Either way, the left-to-right order of keys doesn't change. After the rotation, the middle key of A, B, C sits on top with the other two as its children. The subtree is back to exactly the height it had before the insertion, so the walk stops. That means at most one rebalancing per insertion.

AVL or red-black?

Both guarantee O(log n). AVL trees are more strictly balanced, so lookups are a little faster. Red-black trees do less rotating on insert and delete, so many standard libraries use them. The ideas carry over: walk the search path, spot the broken rule, and fix it locally with rotations.

Start the walkthrough →