26.5 Exercises
Factual
Suppose we use the following trie to represent a map. What would
get("sea")
return? What aboutget("sell")
?
Consider the Trie-based set below. What does
keysWithPrefix("sp")
return? What nodes does it visit during this call?
What is the worst-case runtime when searching for a single word in a trie? Let be the size of the alphabet, and be the number of items in the trie, and be the length of the word being operated on.
Metacognitive
Compare the worst-case number of character comparisons required to insert a word into an LLRB, hash table, and R-way trie. Let be the size of the alphabet, and be the number of items in the trie, and be the maximum length of any word.
Last updated