Create only the missing nodes along the required trie path, and mark its last node complete.
def add(w: String): Unit = {
  var t: Trie = this
  var i = 0
  while (i < w.length) {
    val k = toIndex(w.charAt(i))
    if (t.children(k) == null) t.children(k) = new Trie
    t = t.children(k)
    i += 1
  }
  t.complete = true
}
The loop invariant is that the path for w.take(i) exists and ends at t, while the set of complete words remains unchanged from entry. A fresh node has all children null and complete == false, so creating an unfinished path introduces no stored word. The loop variant is . At termination the full path exists; setting its final flag gives
(1)
Existing paths and terminal flags are untouched, so adding an existing word is idempotent. Adding the empty string marks the root. The time complexity is because the alphabet size is fixed; at most new trie nodes are allocated.

Ancestors (11)

  1. 4
  2. Imperative programming
  3. 2013
  4. Past exam of the year 1 of the computer science course of the University of Oxford
  5. Year 1 of the computer science course of the University of Oxford
  6. Computer science course of the University of Oxford
  7. Undergraduate course of the University of Oxford
  8. Course of the University of Oxford
  9. University of Oxford
  10. List of universities
  11. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version