Search tools and guides ⌘K
II · Trees, with shape

AVL tree

Always height-balanced, to within one.

1962 · Adelson-Velsky & Landis · USSR
The story

Two Soviet computer scientists (the V in AVL is for Velsky) published the first self-balancing BST. The constraint: at every node, the heights of the two subtrees differ by at most one. The result: log-base-φ depth, the tightest balance bound of any common tree.

How it works

After every insert/delete, rotate to restore the height-difference invariant. There are four rotation cases (LL, LR, RL, RR); all are local, touching at most three nodes.

Where it lives

Less common than red-black trees in production. AVL is read-optimal but write-heavy. Used in Windows NT's VirtualAlloc, some database engines, in-memory geometric searches.

The key insight

AVL trees are "more balanced" than red-black trees: better for read-heavy workloads. Red-black wins when writes dominate, because rebalances are cheaper.

More in Trees, with shape
Binary search tree Sorted, but with shortcuts. Red-black tree Almost balanced, much faster to maintain. B-tree / B+ tree The shape of a database index. Heap (binary heap) A priority queue you can grep. Skip list Probabilistic balance, beautifully. Trie (prefix tree) A tree you walk one character at a time. Segment tree Range queries in logarithmic time. Fenwick tree (BIT) Prefix sums, with constant tweaks. Treap BST and heap, secretly the same tree. Splay tree No metadata — and surprising amortised guarantees.
Across the cabinet
III Cuckoo hashing Two slots, no chains. III Robin Hood hashing Steal from the rich, give to the poor. III Consistent hashing Hashing that survives node changes. III Perfect hashing Zero collisions, by design. IV Bloom filter A set, in a thousandth of the space. IV HyperLogLog Count distinct, in 12 KB. IV Count-Min sketch Approximate frequencies, in tiny memory. IV MinHash Set similarity, in a few hashes.
← All data structures