Re: [boost] Re: boost::tree advice?

From: Dan Rosen (dan.rosen_at_[hidden])
Date: 2005-03-28 20:01:29

Hi Dave,

> My personal intuition, not at all tested on real experience, is that
> you want to make the nodes as thin as possible.

Agreed.

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

But the question I really wanted to ask in response to your thoughts
was, how big do you think is too big? The way I'd think of
implementing a node in a binary tree is something like:

  struct node {
    node* parent_;
    node* first_;
    node* second_;
    T* value_;
  };

In a k-ary tree, it would be:

  struct node {
    node* parent_;
    node* children_; // allocated using allocator::allocate(k, 0);
    T* value_;
  };

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?

Cheers,
dr