Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
What is your requirement to retrieve nodes from the tree: by node path or by the node key which must be found in the tree? Are you allowed duplicate keys within a node? Are you populating the tree in one go or will it grow over time? –  Hand-E-Food Sep 27 '12 at 23:23
    
Do you know how many elements are in the tree before you start? –  Loki Astari Sep 27 '12 at 23:42
    
Whats the content in each node? It is strings or digits or an unsortable structure? –  techfoobar Sep 28 '12 at 5:13
    
@Hand-E-Food I will retrieve them by node path. And it will be populated in one go, and then read many times. –  Topo Sep 28 '12 at 5:29
    
@LokiAstari No, but I know that all of the elements are inserted at the start, and then all the reading/fetching of the elements begin. –  Topo Sep 28 '12 at 5:31

1 Answer 1

up vote 5 down vote accepted

A natural way to implement an updateable tree with arbitrary numbers of children per node is to reinterpret a binary tree such that the "left hand" link points to the node's first child, and the "right hand" link points to the next child of the same parent. This takes two links per node, and requires linear list traversal to locate a particular child. However, if the order of the children doesn't matter, you can simply insert each child at the head of the child list.

You can construct a read-only tree with only one link per node, by concatenating all children of a given node into a sub-vector, and dropping the right-hand link in favor of iteration. You will need to include either a boolean last_child flag or a child_count field as part of your read-only node structure; note that the child_count version will permit random access of child lists.

If your read-only queries frequently iterate through long child lists, this may dramatically improve your cache usage. Alternately, if your read-only queries frequently iterate in a depth-first manner, it may be more efficient to drop the left-hand link in favor of iteration, by concatenating all first-child chains into a sub-vector.

In either case, you can use an STL vector<> to do memory-management for the read-only tree -- by doing a traversal (in the appropriate order) of your updateable tree, and using push_back() to append the read-only version of each tree node, in order. Remember that you will need to use indices rather than pointers for your links, as pushing an element may reallocate the vector<>.

Finally, minimizing the size of your read-only node structure can improve your performance. If your read-only node includes a link to the original datastructure, you can profitably strip out any data not needed during a query's traversal but only used when the query finds its target. (Come to think of it, the updateable tree might also benefit from this.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.