Trees in computing
Many core data structures and algorithms are trees in disguise. Recognising them explains their speed and their limits.
Heaps and priority queues
A binary heap is a complete binary tree where each parent is no larger (in a min-heap) than its children. The smallest item sits at the root. Inserting and removing the minimum take \(O(\log n)\) time. Priority queues built on heaps schedule tasks and power Dijkstra's and Prim's algorithms.
Heapsort
Build a heap from the data, then repeatedly remove the root to produce sorted output. Heapsort runs in \(O(n\log n)\) time in the worst case and sorts in place, without extra memory.
Tries
A trie stores strings by their characters along paths from the root, so words with a shared prefix share a branch. Autocomplete and spell checkers use tries: finding all words starting with 'pre' means walking three edges and listing the subtree.
Decision trees and lower bounds
Any comparison-based sorting algorithm can be modelled as a binary decision tree whose leaves are the possible orderings. With \(n!\) leaves, the tree's height is at least \(\log_2(n!) \approx n\log_2 n\). So no comparison sort can beat \(O(n\log n)\) in the worst case: a beautiful lower-bound argument from trees.
\log_2(n!) \approx n \log_2 nExpression and syntax trees
Compilers parse code into syntax trees that capture its structure: in \(3 + 4 \times 5\), multiplication sits lower in the tree, so it is evaluated first. Evaluating the tree from the leaves up computes the expression, respecting precedence automatically.
B-trees in databases
Databases store indexes in B-trees: wide, shallow trees where each node holds many keys and has many children. Because each node fits a disk block, even billions of records can be searched with just a few disk reads. This is why indexed database lookups are fast.
Game trees
Games like chess can be modelled as trees of possible moves. The minimax algorithm assumes both players play optimally, scoring positions from the leaves upward. Pruning techniques skip branches that cannot affect the result, letting programs search far deeper.
Common mistakes
Assuming any binary search tree is balanced; inserting sorted data into a plain BST creates a tall chain with \(O(n)\) search. Confusing heaps (partial order) with search trees (full order). Forgetting that the \(n\log n\) lower bound applies only to comparison-based sorts.
Key takeaways
Heaps give fast priority queues and heapsort. Tries store strings by prefix. Decision trees prove that comparison sorting needs \(\Omega(n\log n)\) comparisons. Syntax trees, B-trees, and game trees show how central trees are to compilers, databases, and AI.
Flashcard
Complete binary tree with heap order
Check your understanding
Why can no comparison-based sorting algorithm be faster than about n log n comparisons in the worst case?