Unit 5 · Heavy
Ordering that supports fast search, but only while the shape stays balanced. The caveat is the unit, and self-balancing structures exist entirely to enforce it.
Know
In-order yields sorted output on a search tree; pre-order suits copying; post-order suits deletion; level-order needs a queue.
Apply
Pick the traversal from the task rather than by habit.
Watch out
Deleting pre-order, which frees a parent whose children are still reachable only through it.
Know
The ordering property constrains entire subtrees, not just immediate children, which is what allows discarding half the tree per step.
Apply
Validate the property recursively, carrying bounds down the tree.
Watch out
Checking only parent against children, which accepts invalid trees.
Know
Inserting sorted keys degenerates a plain BST into a chain, turning logarithmic search linear. AVL and red-black trees restore balance by rotation.
Apply
Quote logarithmic search only alongside the balance assumption.
Watch out
Assuming a BST is balanced. Nothing enforces it unless the structure is self-balancing.
Know
A trie indexes by prefix, making prefix queries proportional to key length rather than to the number of keys. Segment trees answer range queries on changing data.
Apply
Use a trie for prefix work and a segment tree when ranges must be queried and updated.
Watch out
Using a prefix array on data that changes, where a segment tree is the right structure.
Connections and techniques that receive extra attention in this unit.
Related topics some schools attach to this unit and others leave out. Covered on request rather than assumed.
Modeling drill
Write a validator for a binary search tree that carries bounds downward, and explain why local comparison is insufficient.
Work through questions with a tutor and get help with the steps you find difficult.
Get help with this topic