Most efficient Implementation a Tree in C++
- by Topo
I need to write a tree where each element may have any number of child elements, and because of this each branch of the tree may have any length.
The tree is only going to receive elements at first and then it is going to use exclusively for iterating though it's branches in no specific order.
The tree will have several million elements and must be fast but also memory efficient.
My plan makes a node class to store the elements and the pointers to its children. When the tree is fully constructed, it would be transformed it to an array or something faster and if possible, loaded to the processor's cache.
Construction and the search on the tree are two different problems. Can I focus on how to solve each problem on the best way individually? The construction of has to be as fast as possible but it can use memory as it pleases. Then the transformation into a format that give us speed when iterating the tree's branches. This should preferably be an array to avoid going back and forth from RAM to cache in each element of the tree.
So the real question is which is the structure to implement a tree to maximize insert speed, how can I transform it to a structure that gives me the best speed and memory?
