Week 93 of 125
TAOCP 6.2.2 Binary Tree Searching
Sign up or sign in to tick these off and give this week a due date.
-
Binary search trees: insertion, deletion, the average cost of random BSTs, and optimal BSTs built with dynamic programming when access frequencies are known.
Time About 8 hours this week
Why it matters
BSTs are the basis of ordered maps. The optimal BST algorithm is a classic dynamic programming example.
Before you start
- 2.3 Trees
- 6.2.1 Searching an Ordered Table
How to approach it
Implement BST insert, search and delete with tests. Then implement the optimal BST dynamic program and check it on a small set of words with frequencies.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Deletion of a node with two children is the classic bug spot.