trie iteration dovrebbe includere root?

Question

trie iteration dovrebbe includere root?

#1 da (4 voti)

2

Sto lavorando su una struttura dati trie. La mia semplice comprensione iniziale: le strutture dati trie richiedono un nodo radice fisso. Questo nodo non può essere cancellato.

Durante l'iterazione di tutti i nodi in un trie (in pre-ordine), il nodo radice dovrebbe essere incluso?

La "dimensione" del trie dovrebbe includere il nodo radice? Sembra che dovrebbe corrispondere al numero di elementi restituiti durante l'iterazione.

Forse le dimensioni e gli iteratori dovrebbero riflettere solo i nodi foglia? C'è qualche punto in iterando attraverso tutti i nodi interni?

Forse il mio trie dovrebbe iniziare veramente vuoto? Posso permetterti di inserire, modificare, eliminare il nodo radice?

data-structures trees trie

posta Brannon 30.08.2018 - 19:34

fonte

1 risposta

Leggi altre domande sui tag data-structures trees trie

Per implementare la pagina di registrazione con Vaadin o no? Gestione della dipendenza hardware durante il test dell'unità

score 4 · Accepted Answer

Un trie è una struttura dati in cui:

rappresentano stringhe corrispondenti,
rappresentano le transizioni di un nodo al successivo in base a un determinato carattere aggiuntivo e
il nodo radice corrisponde alla stringa vuota che corrisponde sempre quando nessun carattere è ancora processato.

Sulla base di questa comprensione e da un punto di vista teorico:

root è un nodo come qualsiasi altro. Corrisponde solo ad una situazione estrema speciale (cioè la lunghezza 0 raggiunta quando vengono elaborati 0 caratteri).
la profondità di un nodo corrisponde al numero di spigoli attraversati, quindi in linea di principio alla lunghezza della stringa.
contando il numero di nodi, significa contare quante diverse stringhe possono essere identificate dal trie. La radice vuota è solo una stringa speciale in quel set.
iterando attraverso il trie, significa scorrere tutte le stringhe che il trie è in grado di eguagliare. Ancora una volta, riconoscere solo il nulla - il nodo radice - è solo un caso speciale.

Se pensi che gli utenti del tuo trie non siano interessati alla stringa vuota, nulla ti impedisce di ignorarlo. Tuttavia, è una decisione arbitraria basata sul dominio dell'applicazione e non sulla struttura intrinseca del trie. ( Joke: è arbitrario come avviare gli array di indicizzazione da 1; -) ).