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

From: Matthias Kronenberger (mkronen_at_[hidden])
Date: 2002-09-02 18:09:33

Well, you could even use a vector for that simple n-ary tree.

Anyway, i think that trees are not an important data type.
Most of the time, you 're better of with a multimap, or even a simple
vector.

----- Original Message -----
From: "Marc Cromme" <yg-boost-users_at_[hidden]>
Newsgroups: gmane.comp.lib.boost.user
Sent: Monday, September 02, 2002 8:54 PM
Subject: Re: n-ary ordered tree template in boost ??

> 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
>
>
>
>