[prev] 19 [next]

Tries (cont)

Tries are useful for prefix-search of strings (radix search)
  • e.g. as might be useful in implementing a dictionary
Each node in a trie (implementing a dictionary) ...
  • contains one part of a key (typically one char)
  • may have up to 26 children
  • may be tagged as a "finishing" node
  • but even "finishing" nodes may have children
Depth of trie d = length of longest key value

Cost of searching O(d)   (independent of N)