[prev] 77 [next]

Tries (cont)

Each node in a trie …
  • contains one part of a key (typically one character)
  • may have up to 26 children
  • may be tagged as a "finishing" node
  • but even "finishing" nodes may have children
Depth d of trie = length of longest key value

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