Struttura dati Trie con implementazione

Hai visto le parole AutoSuggestions / Completamento automatico durante la ricerca in base al prefisso della stringa? Come sotto:


Questi suggerimenti sono anche molto rapidi ed efficienti .

Sai come sono venuti questi suggerimenti? Con quale struttura dati possiamo renderlo efficiente e veloce?

La maggior parte di noi pensa che l’indicizzazione della colonna / chiave risolverà questo problema. I grandi sistemi con enormi set di dati non possono fare affidamento solo su questa cosa.

La migliore struttura di dati da utilizzare per questo problema è ”Trie”

Cos’è la struttura dei dati Trie?

Quale sarà il numero massimo di nodi dalla radice?

Se con s ider solo caratteri alfabetici, il numero massimo di nodi figlio da root solo è 26 (a-z).

Se consideriamo anche i numeri, possiamo pensare che il numero sarà 36 (a-z + 0–9) – Non utilizzato generalmente.

Perché considerare Trie se abbiamo già set e hashmap?

Con i set e le mappe hash, la complessità temporale non è efficiente. Anche con le mappe hash dobbiamo considerare anche le collisioni di hash. In Confronto per ricerca / inserimento Trie la complessità temporale è O (P) dove P è la lunghezza della stringa del prefisso.

Implementazione di Trie:

Finora abbiamo affrontato solo la parte teorica. Creiamo una struttura trie di esempio e saremo in grado di digerire tutto ciò di cui abbiamo discusso:

Prendi un sistema di dipendenti con un elenco di nomi contenente: [“rahul”, “raju”, “rishabh”, “radhe”, “rockey”].

Rappresentazione del set di dati di cui sopra con Trie:

Nell’istantanea sopra possiamo vedere r è al nodo radice e tutti i percorsi successivi che abbiamo disegnato.

Ora prova a trovare tutte le parole che iniziano con il prefisso “ra”. Guarda come funziona:

Ora considera set con diversi prefissi parole come [“rahul”, “raju”, “rishabh”, “radhe”, “rockey”, “javascript”, “trie”].

Secondo il nostro approccio, dobbiamo creare un Trie separato per ogni prefisso. Quindi questo approccio non è del tutto corretto.

L’approccio corretto è avere un elemento nullo alla radice e quindi aggiungere gli elementi successivi nell’albero. Se non esiste, creane uno nuovo e collegalo a root.

Codice Trie per inserimento, suggerimento automatico e verifica se Word esiste:

Nota: alcune applicazioni utilizzano Trie con alcune modifiche come l’assegnazione del ranking alle parole più cercate. In base al posizionamento, restituiremo i suggerimenti di ricerca più comuni in caso di suggerimenti limitati.

Applicazioni di Trie:

Il codice è disponibile su: https://github.com/rishabhjj/Datastructure_Algorithm/blob/master/LinkedList/Geeks/Trie.js

In caso di domande e suggerimenti, si prega di mettersi in contatto con me <”https://www.linkedin.com/in/rishabh-jain-a5978583/ o invia una mail @ rishabh171192 @ gmail.com