Study B-trees for disk optimization, persistent trees for version control, and van Emde Boas trees for integer keys
Binary search trees are all-rounders. Each tree here beats them at one job: fewer disk reads, keeping every old version, fast access at both ends, or O(log log U) integer lookups.
Pick an order (max children per node) and search for a value. Raise the order and watch the tree get shorter, cutting the disk reads a search needs.
With 10 keys and order 4:
Binary search trees are fundamental, but specialized applications demand specialized structures. B-trees minimize disk accesses, persistent trees preserve history efficiently, finger trees provide fast access to both ends, and van Emde Boas trees achieve O(log log U) for integers.
Each structure optimizes for a specific access pattern: disk I/O, immutability, double-ended queues, or integer predecessor queries. Understanding when to use each is the mark of an advanced algorithm designer.
B-trees store many keys per node, minimizing the height and thus disk accesses. A B-tree of order m has at most m children per node. With m=100 and millions of keys, we need only 2-3 disk reads for any search. This powers databases like PostgreSQL and file systems like NTFS.
Insert and delete keys, then click back through the version history or compare two versions. Each update copies only the path to the change; the rest is shared.
Path copying shares unchanged subtrees between versions.
When modifying a node, we create a new path from the root to that node. All nodes not on this path are shared with the previous version. This gives O(log n) space per update instead of O(n) for a full copy.
Persistent (immutable) data structures preserve all previous versions. Using path copying, we create new nodes only along the path to the modified node, sharing unchanged subtrees. This gives O(log n) space per update instead of O(n) for full copies.
Push and pop at either end and watch the prefix and suffix fingers change. Both ends of the sequence stay within immediate reach.
Finger trees maintain fingers (direct pointers) to both ends. The prefix and suffix hold 1-4 elements each. When full, we push a group to the recursive middle structure. The amortized cost spreads out the rare expensive operations across many cheap ones.
Finger trees provide O(1) amortized access to both ends, O(log n) concatenation and splitting. They achieve this by maintaining "fingers" (direct pointers) to the ends, with a recursive middle structure. Perfect for implementing sequences and priority queues.
Pick a universe size, insert some integers, then search or ask for a successor or predecessor. The recursion trace shows how few levels each query visits.
vEB trees recursively split the universe into √U clusters of size √U. Each recursion halves the exponent, giving depth log log U.
| Structure | Insert | Search | Successor |
|---|---|---|---|
| Sorted Array | O(n) | O(log n) | O(log n) |
| BST / AVL / RB | O(log n) | O(log n) | O(log n) |
| Hash Table | O(1) | O(1) | O(n) |
| Bit Vector | O(1) | O(1) | O(U) = O(16) |
| van Emde Boas | O(log log U) = O(2) | O(log log U) = O(2) | O(log log U) = O(2) |
vEB trees excel when you need fast successor/predecessor queries on integers from a bounded universe. They're used in network routers (IP lookup), scheduling algorithms, and computational geometry. The trade-off is O(U) space.
vEB trees achieve O(log log U) for insert, delete, search, successor, and predecessor on integers in [0, U-1]. They work by recursively splitting the universe into √U clusters of size √U. For U = 232, this means at most 5 recursions!
Spot a mistake or have an idea?