AVL Tree
A self-balancing BST that checks the balance factor (left height − right height) after every insert and rotates when it exceeds ±1 — guaranteeing O(log n) height no matter the insertion order.
An AVL tree is a plain BST with one extra rule enforced after every insert: at every node, the heights of the left and right subtrees may differ by at most 1. Walking back up from the newly inserted node, each ancestor recomputes its height and checks this balance factor.
Four rotation cases fix a violation: LL and RR (a single rotation) when the imbalance is all on one side, and LR/RL (a rotation of the child, then the node) when it zigzags. Each fixup is O(1), and at most O(log n) ancestors need checking, so insert stays O(log n) overall.
The payoff over a plain BST is a hard guarantee: height never exceeds ~1.44·log₂(n), so lookup is always fast — unlike a BST, which degrades to O(n) on sorted input. The cost is more bookkeeping and rotation overhead per insert than a looser structure like a red-black tree.
Operations
| Operation | Complexity |
|---|---|
| search | O(log n) |
| insert (+ rebalance) | O(log n) |
| delete (+ rebalance) | O(log n) |
| height | always O(log n) |
Where it's used
Anywhere a BST is wanted but worst-case height must be bounded: database indexes, in-memory ordered sets with heavy lookups relative to inserts.