Trees & Heaps
9 min readTrees & Heaps
TL;DR
Trees buy you ordering at O(log n) — but only while they stay balanced, and an unbalanced binary search tree is a linked list wearing a costume. That single fact explains red-black trees, AVL trees, and B-trees, and it explains why database indexes are B-trees rather than binary trees. Heaps are a different bet entirely: they give you the minimum or maximum in O(1) and give up all other ordering, which is exactly the right trade for schedulers, top-k, and Dijkstra.
How it works
Binary search tree and the balance problem
A BST keeps every left descendant less than the node and every right descendant greater, so search, insert, and delete are O(height). With a balanced tree, height is O(log n). Insert already-sorted data into a naive BST, however, and every insertion goes right — height becomes n and every operation is O(n):
Insert 1,2,3,4,5 into an unbalanced BST:
1
\
2
\
3
\
4
\
5 <- height 5, not log(5). This is a linked list.Sorted insertion order is not an exotic case — it is the normal case for timestamps, sequential IDs, and imported data. That is why production code uses self-balancing trees.
Red-black trees rebalance via colour rules and rotations, guaranteeing height ≤ 2·log(n+1). They are what SortedDictionary<K,V> and SortedSet<T> use. AVL trees balance more strictly (heights differ by at most one), giving faster lookups and slower writes — the classic read-heavy versus write-heavy trade.
B-trees — why databases do not use binary trees
A B-tree node holds many keys and has many children, so the tree is wide and shallow. This matters because a database index lives on disk (or in pages that must be fetched), and the cost is dominated by the number of page reads, not comparisons. A binary tree over a million rows is about 20 levels — 20 random reads. A B-tree with a few hundred keys per 8 KB page is 3 levels — 3 reads. Same O(log n), utterly different constant, because the log base is the branching factor rather than 2.
This is the answer to "why is your index a B-tree" and the reason the same reasoning applies to filesystems.
Heaps and priority queues
A binary heap is a complete binary tree stored in a flat array — no node objects, no pointers, excellent locality. The heap property is only that a parent is ≤ (min-heap) or ≥ (max-heap) both children. Siblings are unordered, which is precisely why it is cheaper than a fully sorted structure.
// Array-backed: children of i are at 2i+1 and 2i+2, parent at (i-1)/2.
// PriorityQueue<TElement, TPriority> ships in .NET 6+.
var scheduled = new PriorityQueue<Job, DateTime>();
scheduled.Enqueue(job, job.RunAt);
while (scheduled.TryPeek(out _, out DateTime next) && next <= DateTime.UtcNow)
{
scheduled.Dequeue().Run();
}| Operation | Cost |
|---|---|
| Peek min/max | O(1) |
| Insert | O(log n) |
| Extract min/max | O(log n) |
| Build from n items | O(n), not O(n log n) |
| Find arbitrary element | O(n) |
| Sorted iteration | not supported |
Heapify being O(n) rather than O(n log n) is a favourite question: most nodes are near the leaves and sift down only a level or two, and the sum over all levels converges to a constant multiple of n.
Note that .NET's PriorityQueue<TElement,TPriority> is a min-heap, is not stable for equal priorities, and has no O(log n) "decrease key" — for Dijkstra you either push duplicates and skip stale pops, or use an indexed heap.
Tries — prefix structures
A trie stores strings by character along tree edges, giving O(m) lookup for a length-m key regardless of how many keys are stored. That is what makes autocomplete, routing tables, and prefix matching fast. The cost is memory: a naive trie allocates a child map per node. Compressed variants (radix trees) collapse single-child chains and are what routers and some databases actually use.
A: Because BST operations cost O(height), not O(log n) — the logarithm only appears when the tree is balanced. Inserting keys in sorted or reverse-sorted order makes every insertion go the same direction, producing a chain of height n that is functionally a linked list with extra pointers. This is not a rare pathological case: timestamps, auto-incrementing IDs, and bulk imports of already-ordered data are all sorted insertion, so the degenerate case is closer to the default than the exception. That is exactly why production structures use self-balancing trees rather than plain BSTs.
A: It colours nodes red or black and enforces invariants — the root and leaves are black, a red node cannot have a red child, and every path from a node to its descendant leaves contains the same number of black nodes. Together these bound the longest path at no more than twice the shortest, so height is at most 2·log(n+1) and all operations are O(log n) worst case. Insertions and deletions restore the invariants with a constant number of recolourings and rotations, so rebalancing does not change the asymptotic cost. SortedDictionary and SortedSet in .NET are red-black trees.
A: Because the dominant cost is page reads from storage, not in-memory comparisons, and a binary tree makes one dependent read per level. A B-tree node is sized to a storage page and holds hundreds of keys, so the branching factor is hundreds rather than two and the log base changes accordingly: a million-row index is about twenty levels as a binary tree but three levels as a B-tree, meaning three reads instead of twenty. The same asymptotic O(log n) hides a constant-factor difference of nearly an order of magnitude. B+ trees go further by keeping all values in the leaves and linking them, which makes range scans a sequential leaf walk.
A: A heap only guarantees the relationship between a parent and its children — the parent is smaller than both, for a min-heap — and says nothing about the order between siblings or across subtrees, so it can answer "what is the minimum" in O(1) but cannot search for an arbitrary key in better than O(n). A BST maintains a total ordering, so it supports search, ordered iteration, ranges, and predecessor or successor queries at O(log n). The heap's weaker invariant is precisely why it is cheaper to maintain and can live in a flat array with no pointers, which is the right trade when you only ever need the extreme.
A: Because the work is dominated by nodes near the leaves, which barely move. Building bottom-up by sifting down each node, half the nodes are leaves needing zero work, a quarter sift down at most one level, an eighth at most two, and so on — the total is n times the sum of k over 2^k, which converges to a constant, giving O(n). Inserting the elements one at a time instead is O(n log n), because each insertion sifts up through the full current height. It is a nice demonstration that the same final structure has different construction costs depending on the order you build it in.
A: A trie stores strings along the edges of a tree so that shared prefixes share a path, giving O(m) lookup for a key of length m independent of how many keys are stored — where a hash table is O(m) to hash plus a comparison, but cannot answer prefix questions at all. It is worth the memory when you need prefix operations: autocomplete, typeahead, longest-prefix-match in IP routing, dictionary and spell-check lookups, or listing everything under a namespace. It is not worth it for plain exact-match lookup, where a hash table is faster and far smaller, because a naive trie allocates a child map per node and that overhead is substantial.
A: SortedDictionary<K,V> and SortedSet<T> are red-black trees, and SortedList<K,V> is a sorted array pair rather than a tree but offers the same ordered semantics. Over a Dictionary they give you ordered enumeration, minimum and maximum, range queries via GetViewBetween on SortedSet, and predecessor or successor lookups — none of which a hash table can do without sorting everything first. They also give a hard O(log n) worst case rather than an average-case O(1) that can degrade. You pay with slower typical operations and, for the tree types, a node allocation per element.
A: With a min-heap keyed by scheduled time, which is exactly PriorityQueue<Job, DateTime> in .NET 6 and later. Peeking the next due time is O(1), so the loop sleeps until that instant rather than polling, and enqueuing or dequeuing is O(log n), which stays fast with a large backlog. Two caveats matter in practice: .NET's priority queue is not stable, so equal timestamps do not preserve insertion order unless you make the priority a composite of time and a monotonic sequence number, and there is no efficient decrease-key or remove-arbitrary operation, so cancelling a scheduled job is usually handled by marking it cancelled and discarding it when it pops.
Key takeaways
- BST operations are O(height), not O(log n) — sorted insertion (timestamps, sequential IDs) produces a linked list.
- Red-black trees guarantee height ≤ 2·log(n+1); AVL balances harder — faster reads, slower writes.
- B-trees exist because the cost is page reads: branching factor changes the log base, 20 levels becomes 3.
- A heap only orders parent versus child — that weaker invariant is what makes O(1) peek and array storage possible.
- Heapify is O(n); inserting one at a time is O(n log n) for the same result.
- Tries give O(m) prefix lookup independent of key count, at real memory cost — use them for prefix work, not exact match.
- .NET's
PriorityQueueis a min-heap, unstable, with no decrease-key.