Chapter 5 of 10All chapters
Chapter 5 of 10
Trees
Order with fast lookup.
Binary search trees
Smaller values go left, larger right, so lookup halves the search each step. That gives logarithmic time as long as the tree stays balanced.
- Inserting sorted data into a naive tree produces a linked list.
- Self-balancing variants such as red-black trees keep the guarantee.
Other trees
Heaps order only parent against child. Tries store strings by prefix and power autocomplete. B-trees keep databases fast on disk by matching the block size.