Week 94 of 125
TAOCP 6.2.3 Balanced Trees
Sign up or sign in to tick these off and give this week a due date.
-
AVL trees: keeping a BST balanced with rotations so height stays logarithmic, plus discussion of other balancing schemes and list operations on balanced trees.
Time About 9 hours this week
Why it matters
Self-balancing trees power ordered maps in most standard libraries and many databases. Rotations are a core skill.
Before you start
- 6.2.2 Binary Tree Searching
How to approach it
Implement AVL insertion with single and double rotations. Write a checker that verifies balance factors after every insert, and run it on a million random inserts. Deletion is a stretch goal.
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
- Updating balance factors incorrectly after a double rotation.