Comment on page
- 1.Suppose we use the following trie to represent a map. What would
get("sea")return? What about
- 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? Letbe the size of the alphabet, andbe the number of items in the trie, andbe 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. Letbe the size of the alphabet, andbe the number of items in the trie, andbe the maximum length of any word.
LLRB: We always insert at the bottom of the LLRB, so there are
comparisons to figure out where the new node goes. Each word comparison takes up to
character comparisons. Thus, there are
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
items, this takes
R-way trie: In the worst case, we follow or create
nodes to the end of the word. Thus, there are at most