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)
|