Tries & Trees

• Trie: Digital Search Tree over strings in alphabet C

• Each edge is a symbol, and siblings represent distinct symbols

• Final character of string cannot occur elsewhere in string

  • Add marker symbol (“$”) to alphabet, if needed

• Inefficient
  • Eliminate Unary Nodes

• Suffix Tree
  • Arcs are non-empty substrings
  • Each non-terminal, non-root has two children
  • Sibling arcs begin with different characters

Previous slide

Next slide

Back to first slide

View graphic version