Wing

Tree Algorithms

1960s

AVL Tree

Georgy Adelson-Velsky & Evgenii Landis, 1962

A self-balancing binary search tree where the heights of two child subtrees differ by at most one, using rotations to maintain balance.

1970s

Red-Black Tree

Rudolf Bayer, 1972

A self-balancing BST with colored nodes ensuring no path from root to leaf is more than twice as long as any other.

B-Tree

Rudolf Bayer & Edward M. McCreight, 1972

A balanced search tree for external memory: nodes hold many keys and children; insertion splits full nodes so all leaves stay at the same depth.

B+ Tree

Rudolf Bayer & Edward M. McCreight, 1973

All keys live in leaves; internal nodes only route; leaves are linked for range scans.

Segment Tree

Jon Bentley, 1977

Canonical decomposition for range max on [1…5], then refresh ancestors after a point update at leaf 2.

1980s

Splay Tree

Daniel Sleator & Robert Tarjan, 1985

A self-adjusting BST that moves recently accessed elements to the root through a sequence of rotations called splaying.

1990s

Skip List

William Pugh, 1990

Probabilistic multi-level linked lists that support search, insert, and delete in expected logarithmic time.

Fenwick Tree

Peter Fenwick, 1994

Walk a binary indexed tree for a prefix sum, then propagate a point update along ancestor links i + (i & −i).