AVL trees

A binary search tree that rebalances itself. Height stays O(log n) — for any input.

Balance factor + rotation

• Each node: balance factor = height(left) − height(right), kept in {−1,0,+1}
• Insertion breaks it → repair with an O(1) rotation
• Rotation: 3 pointers move, BST order preserved
• Four cases: two single rotations, two double (zig-zag)

Watch sorted input stay balanced

Insert 1..7 sorted — the case that killed the plain BST. AVL rotates → height 3, not 7.

Balance guarantees O(log n)

At 100000 sorted inserts: AVL height 17 vs plain BST 100000. 104× faster at n=8000.

AVL vs red-black

• AVL: tighter balance → shorter, faster lookups, more rotations
• Red-black: looser → fewer rotations, better for updates
• Both O(log n); spend the balancing budget differently

Takeaway

A small O(1) repair, applied consistently, converts a catastrophic worst case into an ironclad guarantee. Next: red-black trees.