trie

In informatica, un trie (pronunciato /ˈtriː/ oppure /ˈtraɪ/) è un tipo di struttura dati ad albero ordinato usata per rappresentare un set o un array associativo le cui chiavi sono tipicamente stringhe. A differenza di un albero binario di ricerca, i nodi non conservano una copia della propria chiave, che dipende invece dalla posizione del nodo nell'albero. La radice dell'albero è associata alla stringa vuota, e tutti i discendenti di un nodo condividono il prefisso associato a quel nodo. Non tutti i nodi rappresentano necessariamente una chiave significativa, che tipicamente si trova invece nelle foglie ed eventualmente in alcuni, ma non necessariamente tutti, i nodi interni. Un trie può essere visto come una particolare istanza di automa a stati finiti deterministico: tutti i linguaggi finiti hanno un corrispondente trie che li rappresenta, e ogni trie può essere associato a un automa a stati finiti deterministico aciclico.