Trie vs albero rosso-nero: quale è meglio nello spazio e nel tempo?

Question

Tries e alberi rosso-nero sono molto efficienti per la memorizzazione di stringhe.

Quale ha una maggiore complessità temporale? E la complessità dello spazio?

Answer 1

Questo dipende da molti fattori, quali le stringhe che si stanno memorizzando e il modo in cui il trie è rappresentato.

In un albero rosso-nero, sarà necessario eseguire O (log n) confronti tra stringhe su ciascuna operazione (inserimento, eliminazione, ricerca, ecc.). Il costo di un confronto è piccolo se si confrontano due stringhe che non hanno un prefisso comune o se si confrontano due stringhe in cui la stringa è piccola. Il caso peggiore per un confronto è quando una stringa è un prefisso di un altro, nel qual caso devono essere letti tutti i caratteri. Di conseguenza, se si volesse cercare una stringa di lunghezza L in un albero di stringhe rosso-nero, nel peggiore dei casi si dovrebbe fare O (L log n) lavorando facendo confronti O (log n), ognuno dei quali guarda tutti i caratteri dalla stringa di input. Tuttavia, nel migliore dei casi ciò richiederebbe solo il tempo O (log n), che si verifica se i confronti falliscono sempre immediatamente.

In termini di utilizzo dello spazio, l'albero rosso/nero richiede due puntatori per nodo e un nodo per stringa. (Il bit rosso/nero può essere solitamente inserito nei bit bassi di un puntatore). Quindi lo spazio totale è 2n + (lunghezza totale di tutte le stringhe).

In un trie, inserimenti, eliminazioni e ricerche prendono O (L) nel caso peggiore (se tutti i caratteri dell'input devono essere considerati) e O (1) nel caso migliore (se cadi dal presto). Questo è più veloce dell'albero rosso-nero di un fattore di O (log n), che potrebbe potenzialmente essere significativo per le grandi raccolte. Tuttavia, il trie ha una localizzazione peggiore, dal momento che c'è molto più inseguimento del puntatore e non vi sono matrici contigue di caratteri da scansionare.

In termini di utilizzo della memoria, un trie con un alfabeto di dimensione k in genere ha bisogno di un totale di puntatori kn, dove n è il numero di nodi. Questo può essere drammaticamente peggiore dell'albero rosso/nero se la dimensione dell'alfabeto è grande. Tuttavia, il sovraccarico dello spazio può essere ridotto comprimendo il trie usando la rappresentazione dell'albero Patricia, utilizzando una struttura dati più efficiente per memorizzare i puntatori figlio o la costruzione di un DAWG dal trie.

Spero che questo aiuti!