THE AVL TREE two Soviets, 1962 - the first that balances itself
A binary search tree stays fast only while it stays bushy; feed it sorted data and it degenerates into a list. The AVL tree was the first to keep itself balanced: after every insert it checks each node’s two subtree heights and, if they differ by more than one, rotates to fix it — guaranteeing O(log n) forever.
THE TECHNIQUE balance factor, then rotate
Each node tracks its balance factor — the height of its right subtree minus the left. Insert as in any BST; then walk back up, and at the first node whose balance goes to ±2, apply a rotation (single or double) to restore ±1. Insert values and watch it stay bushy instead of listing. live demo
HISTORY & CREDIT an acronym miscounted for 60 years
“AVL” looks like three initials for three people — it is two, and the first name is one hyphenated surname. cited
1962 · Georgy Adelson-Velsky and Evgenii Landis, Soviet mathematicians, publish “An algorithm for the organization of information” — the first self-balancing binary search tree. A-V + L = AVL. the guarantee · the balance rule keeps the height under ~1.44 log₂n — the tightest of the classic balanced trees, so lookups are fastest, at the cost of more rotations on update. the family · the red-black tree (dart 073) balances more loosely — taller but cheaper to update — which is why libraries usually pick red-black for general maps and AVL for lookup-heavy work. Adelson-Velsky also led the team behind one of the first chess programs to beat a rival machine — the Soviet ITEP program that won the 1966–67 Stanford–ITEP telegraph match 3–1 in 1967.
The idea that a structure should repair its own shape after every change starts here. first to self-balance
RECOMMEND FOR I-13 the pointer wall, honestly
A complete binary tree needs no pointers — the heap (dart 062) proved that on the array. But a search tree grows and rotates arbitrarily, so its nodes are dynamically linked:
// each node: {key, left, right, height} with left/right as references
// rotations relink those references -- heap-allocated, pointered nodes
Recommend: the aggregate/pointer wall, stated plainly. I-13’s array embeds a complete tree (heap-062) with index arithmetic, but an AVL tree is not complete — it needs genuine node references that rotations relink, which the bounded f64 array cannot express. It can be faked with parallel arrays (key[], left[], right[] as integer indices into a node pool), which runs — the classic pointerless encoding — but that is a node arena, the honest shape of the want. Note: the balance logic (compare heights, rotate) is scalar and runs; only the linked structure is the wall — the same aggregate frontier the trie (074) and red-black tree (073) hit.