Che cos'è un Trie?

Un trie (pronunciato «try», abbreviazione di retrieval) è una struttura dati ad albero progettata per memorizzare e cercare stringhe in base ai loro caratteri. Ogni arco dell’albero è etichettato con un singolo carattere e ogni percorso dalla radice a un nodo contrassegnato rappresenta una parola memorizzata.

Questa struttura rende estremamente rapide le ricerche di prefissi. Verificare se il trie contiene una parola che inizia con "car" richiede solo tre ricerche di caratteri a partire dalla radice, indipendentemente dalle migliaia di parole memorizzate. I trie sono alla base di funzionalità come il completamento automatico, il controllo ortografico e le tabelle di routing IP.

Ogni nodo del trie contiene due elementi di stato:

• children: una mappa da un carattere al successivo TrieNode.
• isEndOfWord: un flag che vale true quando il percorso dalla radice a questo nodo rappresenta una parola completa che è stata inserita.

Le cinque operazioni principali su un trie sono:

1. Insert: aggiunge una parola, creando tutti i nodi mancanti lungo il percorso.
2. Search: verifica se una parola completa è memorizzata.
3. StartsWith: verifica se una parola memorizzata ha il prefisso indicato.
4. Delete: rimuove una parola ed elimina eventuali rami inutilizzati.
5. WordCount: conta quante parole distinte sono memorizzate.

Creiamo una classe Trie!