27.5 Exercises

Factual

1. Suppose we use the following trie to represent a map. What would get("sea") return? What about get("sell")?

1. Consider the Trie-based set below. What does keysWithPrefix("sp") return? What nodes does it visit during this call?

1. 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.

Problem 1

sea terminates at the node with value 6. sell does not exist in the trie (since it does not terminate at the node with l, so the get operation returns null.

Problem 2

keysWithPrefix follows the prefix to the final letter of the prefix, then performs DFS from that node to get all children.

During this procedure, it traverses the nodes s, p, i, t, e, y. The final return value is spit, spite, spy.

Problem 3

$\Theta(L)$. In the worst case, the word is a prefix of some other word in the trie, but is not present in the trie itself. In this case, we go through all the letters of the word.

Metacognitive

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.

Problem 1

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.