Comment on page

# 26.5 Exercises

- 1.Suppose we use the following trie to represent a map. What would
`get("sea")`

return? What about`get("sell")`

?

- 2.Consider the Trie-based set below. What does
`keysWithPrefix("sp")`

return? What nodes does it visit during this call?

- 3.What is the worst-case runtime when searching for a single word in a trie? Let$R$be the size of the alphabet, and$N$be the number of items in the trie, and$L$be the length of the word being operated on.

- 1.Compare the worst-case number of character comparisons required to insert a word into an LLRB, hash table, and R-way trie. Let$R$be the size of the alphabet, and$N$be the number of items in the trie, and$L$be the maximum length of any word.

**LLRB**: We always insert at the bottom of the LLRB, so there are

$\Theta(\log N)$

comparisons to figure out where the new node goes. Each word comparison takes up to $L$

character comparisons. Thus, there are $\Theta(L \log N)$

comparisons.**Hash table**: In the worst case, all items hash to the same bucket. On an insertion, we must compare a word to all other words in the bucket for equality. Assuming this bucket has

$N$

items, this takes $\Theta(LN)$

comparisons.**R-way trie**: In the worst case, we follow or create

$L$

nodes to the end of the word. Thus, there are at most $\Theta(L)$

comparisons.Last modified 8mo ago