I want to design a binary tree with preallocated nodes, in order to avoid calling malloc/free every time I want to insert/delete a node. The problem is I don't know ahead of time how many nodes the tree will have, so I am thinking I need to allocate a block of nodes at a time, then allocate another block when the first gets used up, etc.
As far as I can tell, I need 3 data structures to accomplish this, but I'm hoping someone can recommend a simpler, more elegant method.
The three data structures I am thinking of are:
- Binary tree
- Stack (to store the preallocated nodes and easily find the next one to use)
- Linked list (to store the different allocated node blocks so they can be located and freed eventually).
The way these would work is:
- Allocate one block of N nodes
- Push each node in the block onto the Stack
- Append block to Linked List.
- If stack is empty, allocate another block of N nodes, push them onto the Stack and append it to Linked List
- Pop node from stack and store tree node data in it
- Add node to tree structure, do balancing, etc
- Find item in tree and remove from tree
- Push node back onto Stack to be used later for insert
- Destroy tree
- Traverse Linked List and delete all node blocks
Using a Stack to store all the preallocated nodes seems like a good idea, since insert/delete operations would be $O(1)$. However, each time a new block of N nodes needs to be allocated, I need to push them all onto the Stack $(O(N))$ and insert it into the Linked List $(O(1))$. Finally, cleanup at the end requires traversing the Linked List $(O(NB))$ where $NB$ is the number of node blocks allocated.
It seems to me I should able to do this with less complexity (maybe 2 data structures instead of 3). Does anyone know of a more elegant method?