Trees

Trees? We've got all the trees you need! I'm thinking about writing a pop computer science book, one chapter on each of these.

• red-black
• AVL (Adelson-Velsky + Landis)
• pq
• maple
• top
• fat
• b / b+ / 2-3
• vEB (van Emde Boas)
• radix
• dancing
• splay
• trie
• up-sweep (Blelloch 1990)
• kd
• (minimal) spanning
• Gomory-Hu
• decision
• Hilbert R
• Fenwick
• game
• aa
• finger
• Trémaux
• Steiner
• Order statistic
• LSM (log-structured merge)
• Cartesian
• segment
• interval

Compiling

• abstract syntax
• doubly logarithmic
• dominator

...

Theory

• Finite/Pushdown Tree Automata
• Algebraic tree systems