Trie (etuliitepuu) on puu, jossa jokainen kaari edustaa merkkiä ja jokainen polku juuresta muodostaa etuliitteen. Sanat, jotka jakavat etuliitteen, jakavat saman polun, mikä tekee etuliitehakusta erittäin nopeaa.
Rakenne
text
Insert "cat", "car", "dog":
root
/ \
c d
| |
a o
/ \ |
t* r* g* (* marks end-of-word)
