Lesson 5.1
From if-ladder to radix tree
Why the if-ladder examines routes one by one, how a trie makes lookup O(path-length), and how edge compression turns the trie into a radix tree. Then you lay down the RadixNode and the Router shell.
What you will build
- State the worst-case cost of the if-ladder router and why it grows with route count.
- Explain why a trie's lookup is O(path-length) and why one node per character uses unnecessary memory.
- Define edge compression and the radix tree, and say why children keyed by first byte give O(1) child selection.