Arbres binaires et nœuds préallocés

Question

Je veux concevoir un arbre binaire avec des nœuds préallocés, afin d'éviter d'appeler malloc / libre chaque fois que je souhaite insérer / supprimer un nœud. Le problème est que je ne sais pas à l'avance le nombre de nœuds que l'arbre aura, donc je pense que j'ai besoin d'allouer un bloc de nœuds à la fois, puis d'attribuer un autre bloc lorsque le premier s'utilise, etc.

Pour autant que je sache, j'ai besoin de 3 structures de données pour y parvenir, mais j'espère que quelqu'un pourra recommander une méthode plus simple et plus élégante.

Les trois structures de données auxquelles je pense sont:

1. Arbre binaire
2. Pile (pour stocker les nœuds préallocés et trouver facilement le suivant à utiliser)
3. Liste liée (pour stocker les différents blocs de nœuds alloués afin qu'ils puissent être localisés et libérés éventuellement).

La façon dont cela fonctionnerait est:

Initialisation

1. Allouer un bloc de n nœuds
2. Poussez chaque nœud dans le bloc sur la pile
3. Ajouter le bloc de la liste liée.

Insert d'arbre

1. Si la pile est vide, allouez un autre bloc de n nœuds, poussez-les sur la pile et ajoutez-le à la liste liée
2. Node pop de la pile et stockez les données du nœud d'arbre dedans
3. Ajouter le nœud à la structure des arbres, faire l'équilibre, etc.

Supprimer

1. Trouver un élément dans l'arbre et retirer de l'arbre
2. Pousser le nœud sur la pile pour être utilisé plus tard pour insérer

Nettoyer

1. Détruire l'arbre
2. Traverser la liste liée et supprimer tous les blocs de nœuds

L'utilisation d'une pile pour stocker tous les nœuds préallocés semble être une bonne idée, car les opérations d'insertion / supprimer seraient $ O (1) $. Cependant, chaque fois qu'un nouveau bloc de n nœuds doit être alloué, je dois les pousser tous sur la pile $ (O (n)) $ et l'insérez-le dans la liste liée $ (O (1)) $. Enfin, le nettoyage à la fin nécessite la traversée de la liste liée $ (O (nb)) $ où $ Nb $ est le nombre de blocs de nœuds alloués.

Il me semble que je devrais le faire avec moins de complexité (peut-être 2 structures de données au lieu de 3). Quelqu'un connaît-il une méthode plus élégante?