AVL trees
Self-balancing binary search trees where subtree heights differ by at most 1. AVL trees guarantee O(log n) operations through automatic rebalancing. Rotations restore balance after insertions and deletions.
Formula
Balance factor = height(left subtree) − height(right subtree); must be −1, 0, or +1
Real World
The Oxford English Dictionary's digital search engine uses AVL-style balanced indexing — when new words like 'deepfake' are added, the tree automatically rebalances so lookups among 600,000+ entries stay fast.
Exam Focus
In rotation questions, draw the tree before and after — examiners expect you to show which node becomes the new root after rebalancing.
How well did you know this?