Een trie (prefix tree) is een boom waarin elke edge een karakter voorstelt en elk pad vanaf de root een prefix spelt. Woorden die een prefix delen, delen hetzelfde pad, wat prefix-lookups uiterst snel maakt.
Structuur
text
Insert "cat", "car", "dog":
root
/ \
c d
| |
a o
/ \ |
t* r* g* (* marks end-of-word)
