Trie

Trie nebo prefixový strom je datová struktura, která se používá pro uchovávání dvojic klíč-hodnota, kde klíči jsou obvykle řetězce. Na rozdíl od binárního vyhledávacího stromu, kde se podle hodnoty uzlu rozhoduje, do které větve sestoupit, trie v každém uzlu obsahuje všechny podřetězce, kterými může pokračovat řetězec v dosud prohledané cestě. Všichni následníci uzlu mají společný prefix, který je shodný s řetězcem přiřazeným k danému uzlu. Kořen je asociovaný s prázdným řetězcem. Hodnoty obvykle nejsou asociovány se všemi uzly, ale jen s listy a některými vnitřními uzly, které odpovídají klíčům.

Slovo trie pochází z anglického „retrieval“ – získávání, vyhledávání.

V uvedeném příkladu jsou klíče v uzlech a hodnoty pod nimi. Na trie může být nazíráno jako deterministický konečný automat, ačkoli symbol na každé hraně je často implicitní v pořadí větví.

Přestože je to obvyklé, trie nemusí mít jako klíče textové řetězce. Stejné algoritmy mohou být snadno upraveny, aby sloužily podobným funkcím na seznamech jakékoliv podoby, např. permutace na seznamu číslic, permutace na seznamu tvarů atd.