Trees keep data ordered while it changes. A binary search tree makes insert, lookup and delete logarithmic, as long as it stays balanced.
Ten pages show the trade-offs: plain BST and its traversals, self-balancing AVL and red-black trees, B-trees for disks, heaps and tries for special shapes of data.
All algorithms
10Each card runs its own algorithmLeft smaller, right larger. Degrades when unbalanced.
In, pre, post and level order over the same tree.
Rotates whenever heights differ by more than one.
Colour rules keep the tree roughly balanced with fewer rotations.
Wide nodes for disk pages. Databases live here.
Complete tree in an array; parent beats children.
One node per character; prefixes are shared.
Range queries and updates over an array.
Prefix sums with bit tricks.
BST by key, heap by random priority.