Trie
Struttura dati ad albero in cui ogni nodo rappresenta un carattere, così la ricerca per prefisso costa O(lunghezza-del-prefisso).
Usi classici: autocompletamento, correzione ortografica, tabelle di routing IP (longest-prefix match). Variante: radix tree (compresso). Utilizzatori moderni: il routing di nginx, il routing del kernel Linux, molti indici di database.