Study B-trees for disk optimization, persistent trees for version control, and van Emde Boas trees for integer keys
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.
With 10 keys and order 4:
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.
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.
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.
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.
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!
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.
You now understand specialized tree structures for different use cases:
Next: Head to the Algorithms Playground to experiment freely with all structures, then test your knowledge with a comprehensive quiz!