An AVL tree is a self-balancing binary search tree named after its
inventors Adelson-Velsky and Landis. Every node tracks a balance factor —
the height of its left subtree minus the height of its right subtree. Whenever an
insertion or deletion pushes that balance factor to +2 or -2,
the tree performs a rotation to restore balance, guaranteeing
O(log n) search, insert and delete time no matter what order keys arrive in.
AVL trees (1962) were the first self-balancing binary search tree structure ever published — predating red-black trees by over a decade — and they keep tighter balance than red-black trees, which makes lookups slightly faster at the cost of more rotations during insertion.
A self-balancing binary search tree rendered in 3D: every node's color reflects its live balance factor, and inserting or deleting a key triggers left, right or left-right/right-left rotations that visibly re-arrange the tree to keep it balanced.
Each node tracks the height difference between its left and right subtrees (its balance factor). When an insert or delete pushes that value past ±1, the tree rotates nodes around the offending pivot, and the rotation log records exactly which rotation ran and where.
Click "Insert random" or "Delete random" to modify the tree one key at a time, or switch on Auto-build to watch a continuous stream of insertions and deletions rebalance the tree on its own. Drag to orbit, scroll to zoom.
AVL trees, published in 1962 by Adelson-Velsky and Landis, were the first self-balancing binary search tree — guaranteeing O(log n) operations regardless of insertion order, decades before red-black trees became the default in most standard libraries.