Autor: Andreja Ilić
Struktura Trie predstavlja jednu od lakših struktura podataka namenjenih indeksiranju i pretrazi stringova. Većina struktura ovog tipa nisu podržane od strane standardnih biblioteka. Neka word predstavlja konkretan strig a sa dinctionary označimo skup različitih reči. Želimo da konstruišemo takvu ’strukturu’ kojoj ćemo moći brzo ispitati da li odredjena reč pripada skupu ili ne. Postoje dosta standardnih struktura podataka koje podržavaju dati upit (npr. set, HashSet …). Medjutim strukturu Trie karakterišu dve osobine koje navedene strukture nemaju:
- Ubacivanje nove reči kao i ispitivanje pripadnosti je složenosti O(|word|) (dakle ne zavisi od veličine rečnika)
- Pored same činjenice da li reč pripada skupu ili ne, iz strukture Trie možemo pronaći: reči čije je edit-distance rastojanje 1 (reči dobijene zamenom, brisanjem ili dodavanjem jednog karaktera); reči koje počinju na dati prefiks…
Naziv Trie potiče iz reči retrival što znači pretraživanje. Edward Fredkin je 1960. godine izdao rad pod nazivom ’Trie Memory’ u kome je opisao ovu strukturu. Ideja koja se krije iza samog naziva, kako je on rekao, se odnosi na povezivanje dve osnovne karakteristike strukture: oblik stabla i funkcija pretrage.