Alberi binari e nodi preallocati

Question

Voglio progettare un albero binario con nodi preallocati, al fine di evitare di chiamare malloc/liberi ogni volta che voglio inserire/eliminare un nodo. Il problema è che non so in anticipo quanti nodi avrà l'albero, quindi sto pensando di dover assegnare un blocco di nodi alla volta, quindi allocare un altro blocco quando il primo viene esaurito, ecc.

Per quanto ne so, ho bisogno di 3 strutture di dati per raggiungere questo obiettivo, ma spero che qualcuno possa raccomandare un metodo più semplice ed elegante.

Le tre strutture di dati a cui sto pensando sono:

1. Albero binario
2. Stack (per archiviare i nodi preallocati e trovare facilmente quello successivo da utilizzare)
3. Elenco collegato (per archiviare i diversi blocchi di nodi allocati in modo che possano essere posizionati e liberati alla fine).

Il modo in cui funzionerebbero è:

Inizializzazione

1. Allocare un blocco di N nodi
2. Spingere ogni nodo nel blocco sullo stack
3. Appendice blocco all'elenco collegato.

Inserto per alberi

1. Se lo stack è vuoto, assegna un altro blocco di N nodi, spingili sullo stack e aggiungilo all'elenco collegato
2. Nodo pop da stack e archivia i dati del nodo albero in esso
3. Aggiungi nodo alla struttura dell'albero, bilanciamento, ecc.

Elimina albero

1. Trova l'oggetto sull'albero e rimuovi dall'albero
2. Spingere il nodo di nuovo sullo stack da utilizzare più tardi per l'inserto

Pulire

1. Distruggere l'albero
2. Traverse collegate elenco ed eliminare tutti i blocchi di nodi

L'uso di uno stack per archiviare tutti i nodi preallocati sembra una buona idea, poiché le operazioni di inserto/eliminazione sarebbero $ O (1) $. Tuttavia, ogni volta che deve essere assegnato un nuovo blocco di N nodi, devo spingerli tutti sulla pila $ (O (n)) $ e inseriscilo nell'elenco collegato $ (O (1)) $. Infine, la pulizia alla fine richiede di attraversare l'elenco collegato $ (O (nb)) $ dove $ NB $ è il numero di blocchi di nodi assegnati.

Mi sembra che dovrei farlo con meno complessità (forse 2 strutture di dati anziché 3). Qualcuno sa un metodo più elegante?