26.5 Exercises
Last updated
Last updated
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.
. 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.
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.
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 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 items, this takes comparisons.
R-way trie: In the worst case, we follow or create nodes to the end of the word. Thus, there are at most comparisons.