Denominato anche Prefix tree, è un albero multiway che immagazzina un insieme di stringhe e viene salvato in memoria.
Le stringhe sono salvate nelle foglie. Gli archi rappresentano le lettere, e tutte le parole discendenti di uno specifico nodo hanno lo stesso prefisso.
graph TD
A([ ]) -->| l | B([letters])
A --> | t | C([text])
A --> | m | D([ ])
D --> | a | E([ ])
E --> | n | F([many])
E --> | d | G([made])
A --> | w | H([ ])
H --> | o | I([ ])
I --> | r | J([ ])
J --> | m | K([worm])
J --> | d | L([word])
Per accedere al trie si inizia dalla radice, e si segue il cammino carattere per carattere. Ci si ferma quando si trova una foglia o quando il carattere prossimo non è un arco.
Il costo di accesso è O(m).