I want to design a binary tree with pre-assigned nodes, to avoid calling malloc / free every time I want to insert / delete a node. The problem is that I do not know in advance how many nodes the tree will have, so I think I need to assign a block of nodes at a time, then assign another block when the first one runs out, etc.
As far as I can tell, I need 3 data structures to achieve this, but I hope that someone can recommend a simpler and more elegant method.
The three data structures I'm thinking about are:
- Binary tree
- Stack (to store pre-assigned nodes and easily find the next one to use)
- Linked list (to store the different assigned node blocks so that they can be located and eventually released).
The way this would work is:
- Assign a block of nodes.
- Push each node in the block on the stack
- Add block to the linked list.
- If the stack is empty, assign another block of N nodes, insert them into the stack and add them to the linked list
- Pop stack node and store tree node data in it
- Add node to the tree structure, swing, etc.
- Find the item in the tree and remove it from the tree.
- Push the node back onto the stack to use it later to insert
- Destroy tree
- Go through the linked list and delete all the node blocks
Using a stack to store all the pre-assigned nodes seems a good idea, since the insertion / deletion operations would be $ O (1) $. However, each time a new block of N nodes must be assigned, I must push them all on the stack $ (O (N)) $ and insert it into the Linked List $ (O (1)) $. Finally, cleaning at the end requires traversing the Linked List $ (O (NB)) $ where $ NB $ is the number of node blocks assigned.
It seems to me that I should be able to do this with less complexity (maybe 2 data structures instead of 3). Does anyone know of a more elegant method?