Re: n-ary ordered tree template in boost ??

From: Marc Cromme (yg-boost-users_at_[hidden])
Date: 2002-09-02 13:54:41

On Mon, 02 Sep 2002 10:47:42 +0200, Matthias Kronenberger wrote:

> You could chose to emulate such an tree using a std::multimap. Which
> maps the father vertex id to the child vertices. you can also specify
> your own ordering relation.
> To access all children is trivial, if you want to access all grandchilds
> and so own, you'd have to create a nice adapter class, that connects all
> children of children ranges together.

I thought of this, too, but then, there is a simpler emulation 
using the property that an N-ary ordered tree has nodes with either
no child or exactly N childeren. This menas that we can number the 
nodes of a complete tree by (if N=3)

level 0:    0
level 1:  1 2 3
level 2: 4 5 6  7 8 9  10 11 12

and so on. Very simple calculations then give the id numbers of all
children of a given parent, or the parent of a given child, and so 
on. If the tree is not complete, some of the groups are missing, but
the same ordering can still be applied.

Putting this in a pair<size_t id, Node data>, we can store it in a 
map, not a multimap, and we have automagically iterators which parse
the tree in levels.

The concept is quite simple, but usefull, at least if you want to 
parse efficiently  horizontally.

If you want to parse up-down, it requires an O(log n) lookup in 
the map, and then you probably want to implement this thing in a
pointer-to-children and pointer-to  parent fashion for efficiency.

But this get us back to the original question:

2) An N-ary ordered tree is such a basic concept that it is funny 
   that neither STL or Boost offers it. Would it be welcome by the 
   Boost community if it get proposed and
   included into the Boost libs ???

cheers, Marc Cromme