[boost] Re: boost::tree advice?

From: David B. Held (dheld_at_[hidden])
Date: 2005-03-29 02:53:44

Dan Rosen wrote:
> [...]
>>The only reason I
>>can think of to justify a dynamically sized node is to construct a
>>tree where the size of the nodes varies considerably.
> 
> Well, the concepts I'm hoping to support, roughly speaking, are
> binary trees (a node contains at most 2 children), k-ary trees (a
> node contains at most k children), and trees with no limit on the
> number of children per node. To say that users who want the third
> type of tree should just use boost::graph, or that a trie shouldn't
> be implemented as a tree, seems draconic to me.

Well, we could implement a single container type with a massive number
of policies that implements all the containers in the STL, but is
that a good design decision?  The points you are talking about are
{2, N, oo}.  I agree with 2 and N.  oo is a different type of beast
altogether, and trying to stuff it in a tree-sized box doesn't seem
like sound judgement to me.  I guarantee that if you tried to
implement a trie as a generic tree with std::list nodes, or perhaps
even a std::vector, that I would probably not use it.  The whole
point of a trie is to get super-fast access to strings, and fattening
it up with those containers is the antithesis of that goal.  Also,
I'm not familiar with any use-cases for a tree with an unbounded
number of keys per node.  Perhaps you could cite some?  Just because
you can build in the kitchen sink doesn't mean it's a good idea.  It's
often a better idea to build a component that does one thing well.

> I think the tree concept should be general-purpose enough to
> encompass these uses, even if it's embodied by multiple
> implementations with different space/time tradeoffs.

I'm not convinced that a trie necessarily has the same interface
as a generic tree.  And if you have a beast with nodes having an
unbounded number of keys, I'm even more skeptical of the consistency
of that interface with a generic tree.  I imagine such a container
would have very special needs that would best be served by a
specialized data structure.  I can tell you right now that such a
tree, in the absence of any further constraints, would have almost
no relevant performance guarantees (except possibly that it would
be provably easy to find use cases where its performance is
terrible).

> [...]
> And in a general-purpose tree, it would be:
> 
>   struct node {
>     node* parent_;
>     node* first_child_;
>     node* last_child_;
>     node* prev_sibling_;
>     node* next_sibling_;
>     T* value_;
>   };
> 
> Would you consider five pointers to be too much?

Yes.  I don't see what's wrong with my original suggestion:

template <int K = 2, int N = 1>
struct node
{
     node* parent_;
     node* child_[K];
     T value_[N];
};

Dave