Lesson 26 of 48
Trees and heaps
Structures that are fast because of their shape.
A balanced tree is fast for a geometric reason: each step halves what is left. Lose the balance and you lose the speed, which is the most instructive failure in data structures.
Do this
Implement a binary search tree with insert, search and in-order traversal. Then insert already-sorted data and watch the tree degenerate into a list.
The question that unlocks the next lesson
Why does inserting already-sorted data into a plain binary search tree destroy its performance?
- ASorted data hashes badly
- BEvery insert goes to the same side, so the tree becomes a linked list and search drops to O(n)
- CThe traversal no longer produces sorted output
- DSorted data cannot be stored in a tree