In che modo gli alberi binari usano la memoria per archiviare i suoi dati?

Question

In che modo gli alberi binari usano la memoria per archiviare i suoi dati?

#1 da (2 voti)

0

Quindi so che gli array usano un blocco su indirizzi di memoria contigui per archiviare dati in memoria, e le liste fanno uso di array statici e quando i dati vengono aggiunti all'elenco, se non c'è spazio, viene creato un nuovo array statico altrove in memoria di dimensioni maggiori, quindi è possibile memorizzare più dati. La mia domanda è: in che modo gli alberi binari usano la memoria per archiviare i dati? Ogni nodo è una locazione di memoria che punta ad altre due posizioni di memoria altrove ... non necessariamente luoghi contigui? Oppure sono memorizzati in blocchi contigui di memoria come un array statico o un elenco dinamico?

binary-tree

posta sw123456 02.07.2015 - 08:18

fonte

1 risposta

Leggi altre domande sui tag binary-tree

Strutture dati e algoritmi per la correlazione degli eventi Quali sono i formati dei dati che forniscono informazioni strutturali? [chiuso]

score 2 · Accepted Answer

Le implementazioni sono diverse, ma tradizionalmente i nodi sono stati allocati in base alle necessità e in quanto tali sono stati generalmente considerati non contigui. In pratica, se l'albero binario veniva costruito da un set di dati (ad esempio, i dati letti da un file), le allocazioni dei nodi in genere venivano contigue, poiché in genere venivano allocate sequenzialmente e non interlacciate con altre allocazioni. Tuttavia, se la struttura ad albero è stata creata dinamicamente e la creazione del nodo è stata intervallata da altre operazioni di allocazione della memoria, i nodi non erano contigui. Si noti che, a seconda dello schema di gestione dell'heap utilizzato, anche le assegnazioni dei nodi "contigue" in genere avevano le dimensioni arrotondate alla dimensione del blocco heap, quindi un nodo non si avvia esattamente nel punto in cui è terminato il nodo precedente.