Classe TrieNode: inserimento e ricerca

Un Trie (albero dei prefissi) è una struttura dati ad albero in cui ogni nodo rappresenta un carattere. Le parole vengono memorizzate concatenando i caratteri dalla radice alla foglia. La radice rappresenta una stringa vuota. Ogni percorso dalla radice a un nodo is_end = True forma una parola memorizzata. I Trie sono ideali per le query basate sui prefissi, come il completamento automatico, il controllo ortografico e il routing IP, per i quali offrono prestazioni migliori delle mappe hash.

Un TrieNode ha due campi: children — un dizionario che associa i caratteri ai TrieNode figli — e is_end — un booleano che indica se questo nodo è la fine di una parola memorizzata. L'utilizzo di un dizionario, invece di un array fisso di 26 caratteri, generalizza la struttura a qualsiasi insieme di caratteri e consente di risparmiare memoria nei Trie sparsi. Ogni nodo del Trie rappresenta esattamente una posizione carattere nelle parole sottostanti.

Per inserire una parola, si percorra il Trie dalla radice, creando un nuovo TrieNode per ogni carattere che non esiste già nei children del nodo corrente. Dopo aver elaborato tutti i caratteri, si imposti is_end = True sul nodo finale. L'inserimento di 'apple' e 'app' crea la catena a→p→p→l→e (is_end=True per 'apple'), con la p in posizione 3 contrassegnata anch'essa come is_end=True per 'app'.

Per cercare una parola esatta, si percorra il Trie seguendo ogni carattere. Se un carattere manca nei children del nodo corrente, si restituisca False. Se vengono trovati tutti i caratteri, si restituisca node.is_end — True solo se una parola termina esattamente in quel punto, non se esiste soltanto un prefisso. Questa distinzione tra «esiste il prefisso» ed «esiste la parola esatta» è fondamentale e viene spesso verificata.

Il metodo starts_with verifica se una parola inserita ha il prefisso indicato. Segue lo stesso percorso della ricerca, ma invece di verificare is_end restituisce True non appena tutti i caratteri del prefisso sono stati seguiti correttamente: ciò significa che il percorso del prefisso esiste nel Trie.

Ogni operazione sul Trie (insert, search, starts_with) richiede tempo O(m), dove m è la lunghezza della parola: si percorrono al massimo m nodi. Spazio: O(ALPHABET_SIZE × N × M), dove N è il numero di parole e M è la lunghezza media delle parole. Nella pratica, i prefissi condivisi riducono notevolmente lo spazio. Un dizionario children basato su una mappa hash utilizza meno spazio di un array fisso di 26 caratteri per i Trie sparsi, al costo di un overhead costante leggermente maggiore per ogni ricerca.

Se si utilizzano solo lettere inglesi minuscole, si impieghi un array di dimensione fissa children = [None] * 26, usando come indice ord(c) - ord('a'). Questa soluzione è più veloce, perché la ricerca di un figlio è O(1) rispetto a una mappa hash, e ha una disposizione prevedibile in memoria. Si utilizzi la versione con dict quando l'insieme di caratteri è grande o sconosciuto, ad esempio con Unicode, e la versione con array nei problemi da competizione che prevedono esclusivamente lettere minuscole.

L'eliminazione da un Trie deve gestire tre casi: (1) parola assente — non si esegue alcuna operazione; (2) parola presente ma prefisso di un'altra parola — si azzera soltanto is_end; (3) parola presente e non prefisso — si eliminano i nodi dal basso verso l'alto, fermandosi quando un nodo ha altri figli o rappresenta la fine di un'altra parola. L'eliminazione viene verificata raramente nei colloqui, ma è utile conoscerla a livello concettuale.

Si aggiunga a ogni nodo un campo count, incrementato ogni volta che un inserimento attraversa il nodo. Per contare le parole con un determinato prefisso, si percorra il Trie fino al nodo finale del prefisso e se ne restituisca il conteggio. Questo consente di eseguire query di completamento automatico in O(m) senza percorrere tutti i figli: un'estensione utile per i sistemi di completamento automatico reali.

Una mappa hash può eseguire una ricerca esatta in tempo medio O(m), ma non può rispondere in modo efficiente alle query sui prefissi, che richiederebbero di esaminare tutte le chiavi. Un Trie risponde alle query sui prefissi in O(p), dove p è la lunghezza del prefisso, raggruppa naturalmente le parole in base ai prefissi condivisi e non richiede hashing. Si utilizzi un Trie quando sono frequenti le query sui prefissi, per il completamento automatico e il controllo ortografico. Si utilizzi una mappa hash quando servono soltanto ricerche esatte.

Tra gli utilizzi dei Trie nel mondo reale vi sono: completamento automatico (suggerimenti di ricerca di Google), correttori ortografici (ricerca delle parole corrispondenti più vicine), routing IP (ricerca del prefisso più lungo nei router), testo predittivo T9 (disambiguazione dei caratteri) e resolver DNS (ricerca gerarchica dei nomi di dominio). In ogni caso, il compromesso tra O(m) per operazione e spazio O(ALPHABET × nodes) del Trie lo rende lo strumento adatto per ricerche rapide, consapevoli dei prefissi e su larga scala.

Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.

In questa lezione ha imparato che: un TrieNode dispone di un dict children e di un booleano is_end, insert percorre i caratteri uno alla volta, creando i nodi necessari e impostando is_end alla fine e search verifica is_end, mentre starts_with controlla soltanto se esiste il percorso del prefisso. Nella prossima lezione aggiungeremo il completamento automatico basato sui prefissi e analizzeremo più approfonditamente il metodo starts_with.