An AVL tree is a binary search tree that rebalances itself using a single number tracked at every node: the balance factor, the height of the left subtree minus the height of the right subtree. Named for inventors Georgy Adelson-Velsky and Evgenii Landis, who published it in 1962, it was the first self-balancing binary search tree, and it remains the tightest-balanced one in common use today.
What changed in 2026
- AVL trees remain more common in academic and read-heavy database contexts than in general-purpose standard libraries, which mostly default to red-black trees for their cheaper writes.
- The comparison against red-black trees is still the standard way this structure gets taught, since the two make an unusually clean tradeoff to reason about side by side.
- Interactive rotation visualizers have made the four rebalancing cases far easier to internalize than memorizing them from a textbook diagram.
The balance factor: the whole idea in one number
For every node, height(left) - height(right) must stay in {-1, 0, 1}. The moment an insert or delete pushes any node balance factor to -2 or +2, a rotation restores it before the operation is considered done.
The four rotation cases
- Left-Left: a single right rotation.
- Right-Right: a single left rotation.
- Left-Right: rotate the child left, then rotate the node right.
- Right-Left: rotate the child right, then rotate the node left.
def rotate_right(y):
x = y.left
t2 = x.right
x.right = y
y.left = t2
y.height = 1 + max(height(y.left), height(y.right))
x.height = 1 + max(height(x.left), height(x.right))
return x # x is the new subtree root
Each insert or delete can trigger a cascade of these fixes back up to the root, unlike a red-black tree, where the fix-up work is bounded by a small constant per operation.
AVL tree vs red-black tree vs an unbalanced BST
| Property |
AVL tree |
Red-black tree |
Unbalanced BST |
| Height bound |
~1.44 log2(n) |
~2 log2(n) |
O(n) worst case |
| Lookup speed |
Fastest of the three |
Slightly slower |
Can degrade to a linked list |
| Insert/delete cost |
More rotations |
Fewer rotations |
Cheap but no guarantee |
| Best for |
Lookup-heavy workloads |
Write-heavy workloads |
Never, in production |
When an AVL tree is the right call
Reach for one when lookups vastly outnumber inserts and deletes — an in-memory index built once and queried constantly, for example — or when the tightest possible worst-case lookup depth matters. See red-black trees explained for the write-heavy side of this same tradeoff.
Common pitfalls
Mixing up the Left-Right and Right-Left rotation order. Rotate the child first, then the node — reversing the order does not fix the imbalance.
Forgetting to update stored heights after a rotation. Every rotation changes the height of the nodes involved; stale heights silently break future rebalancing decisions.
Choosing AVL for a write-heavy workload. The extra rotation cost on every insert and delete usually outweighs the faster lookups; a red-black tree or B-tree typically wins there instead.
FAQ
Who invented the AVL tree?
Georgy Adelson-Velsky and Evgenii Landis, who published it in 1962 as the first self-balancing binary search tree.
Is AVL always better than a red-black tree?
No. AVL gives faster lookups because it is more tightly balanced, but it rebalances more often, so a red-black tree tends to win when writes are frequent.
What is the maximum height of an AVL tree?
Roughly 1.44 × log2(n + 2), tighter than the roughly 2 × log2(n + 1) bound of a red-black tree.
Do modern standard libraries use AVL trees?
Rarely as the default ordered container — most favor red-black trees or B-trees — but AVL trees still appear in read-dominated databases and filesystems.
Where to go next