C
C
CS61B Textbook
Search
⌃K
Comment on page

26.5 Exercises

Factual

  1. 1.
    Suppose we use the following trie to represent a map. What would get("sea") return? What about get("sell")?
  1. 2.
    Consider the Trie-based set below. What does keysWithPrefix("sp") return? What nodes does it visit during this call?
​
​
  1. 3.
    What is the worst-case runtime when searching for a single word in a trie? Let
    RR
     be the size of the alphabet, and
    NN
     be the number of items in the trie, and
    LL
     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
​
Θ(L)\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. 1.
    Compare the worst-case number of character comparisons required to insert a word into an LLRB, hash table, and R-way trie. Let
    RR
     be the size of the alphabet, and
    NN
     be the number of items in the trie, and
    LL
     be the maximum length of any word.
Problem 1
LLRB: We always insert at the bottom of the LLRB, so there are
Θ(log⁡N)\Theta(\log N)
comparisons to figure out where the new node goes. Each word comparison takes up to
LL
 character comparisons. Thus, there are
Θ(Llog⁡N)\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
NN
 items, this takes
Θ(LN)\Theta(LN)
 comparisons.
R-way trie: In the worst case, we follow or create
LL
 nodes to the end of the word. Thus, there are at most
Θ(L)\Theta(L)
 comparisons.
Previous
26.4 Summary
Next
27. Software Engineering I
Last modified 8mo ago