Differenza tra Tries e Trees?

Question

Ricordo a distanza che i tentativi non memorizzano l'intero dato per nodo, ma solo il suffisso al nodo genitore.

Dove gli alberi memorizzano l'intero dato, ma si organizzano solo in base al prefisso.

Quindi i tentativi si riducono, il che può ad esempio comprimere i dizionari molto bene.

Quindi è davvero l'unica differenza?

Da applicazioni reali ricordo che i tentativi sono più rapidi nelle query di intervallo? Esistono persino campi speciali solr/lucene per accelerare le richieste di intervallo. Ma come va?

Qual è la differenza effettiva e quali sono i vantaggi/svantaggi di tentativi e alberi?

Answer 1

Un albero è una struttura generale di nodi ricorsivi. Ci sono molti tipi di alberi. Quelli più popolari sono binary tree e balanced tree. A Trie è un tipo di albero, noto con molti nomi tra cui albero di prefissi, albero di ricerca digitale e albero di recupero (da cui il nome 'trie').

Ogni tipo di albero ha uno scopo, una struttura e un comportamento diversi. Ad esempio, un albero binario memorizza una raccolta di articoli comparabili (ad es. Numeri). Può quindi essere utilizzato per memorizzare una serie di numeri o per indicizzare altri dati che possono essere rappresentati da numeri (ad es. Oggetti che possono essere sottoposti a hash). La sua struttura è ordinata in modo da poter essere cercata rapidamente per trovare un singolo oggetto. Altre strutture arboree, come un albero equilibrato, sono simili in linea di principio.

A trie rappresenta una sequenza nella sua struttura. È molto diverso in quanto memorizza sequenze di valori piuttosto che singoli valori singoli. Ogni livello di ricorsione dice "qual è il valore dell'articolo I della lista di input". Questo è diverso da un albero binario che confronta il singolo valore cercato con ciascun nodo.

Answer 2

A albero binario o bst viene in genere utilizzato per memorizzare valori numerici. La complessità temporale in un punto è O (log (n)) per l'inserimento, la cancellazione e la ricerca. Ogni nodo in un albero binario ha al massimo 2 nodi figlio.

Trie: Ogni nodo di trie è costituito da più rami. Ogni ramo rappresenta un possibile carattere di chiavi. Dobbiamo contrassegnare l'ultimo nodo di ogni chiave come nodo foglia. Verrà utilizzato un valore di campo trie per distinguere il nodo come nodo foglia (ci sono altri usi del campo valore)

Per ulteriori informazioni sui tentativi, consultare questo tutorial sul topcoder. https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/