[boost] Re: boost::tree advice?

From: David B. Held (dheld_at_[hidden])
Date: 2005-03-29 20:59:15

Dan Rosen wrote:

> On Tue, 29 Mar 2005 01:53:44 -0600, David B. Held
> <dheld_at_[hidden]> wrote:
> 
>>Also, I'm not familiar with any use-cases for a tree with an unbounded
>>number of keys per node.
> 
> I'm getting the feeling we're talking about different things. I'm not
> suggesting that the tree would have multiple keys per node -- I'm not
> even sure what you mean by "keys" in this context -- I was saying that
> a node in a tree may have an unbounded number of *children*.

In general terms, a tree node has N children and K keys.  The keys
are simply the values stored in that node.  For a typical binary
tree, K == 1.  For a btree, K typically is N - 1.  However, there
is no reason to disallow configurations that have a different
relationship between K and N.  I didn't invent this terminology.

> [...]
> Well, a couple things:
> 
> 1. There is no precedent for having an array of values at any given
> node.

Apparently, you've never heard of a btree.  Perhaps you'd like to
brush up on your database implementation theory going back several
decades. ;)

> In my experience, the precedent in container design is to let
> clients fully specify the value type (and key type if appropriate).
> If a client wants a node to contain an array of values, the code
> indicates that by passing an array as the value type.

Well, there's two things wrong with that.  First, that is not the
precedent (witness std::map, for which the value_type is
std::pair<key_type, mapped_type>).  Second, you are confusing the
value_type with an implementation detail of the node_type.  Setting
T = U[N] is entirely different from implementing node_type as T[N].
In the former, the node does not know whether T is an array or not,
which implies that each tree node has a single value.  If you think
that nodes should all have single values, then you not only need to
look at btrees (and all its relatives), but also compact tries.

> 2. For the list of children, you've also specified array storage.
> But what if I want to insert between two children?

Obviously, you have to shift the keys, if that makes sense for the
tree type.  But more typically, you would insert the value further
down the tree.  A tree isn't an array, after all.  The arrays in
each node merely represent the branching factor of the tree.

> What if I don't want to allocate K pointers for each node?

Then set N = K.

> What if I simply don't want the number of children per node to be
> bounded?

Then you obviously need a different design.

> The implementation you suggest here is decent for a k-ary tree,
> but it does have its inherent restrictions.

Obviously.  But those restrictions circumscribe a very large class
of trees which can be implemented fairly efficiently with the given
design.  If you were to implement std::map with a tree that had,
say, a std::list in each node, there's no way you could convince
me to use such a beast.  The point being, of course, that if total
generality significantly raises the cost of the average case, then
it's more expensive than many people will want to pay.  Remember
one of the guiding principles of C++ design: "Don't make them pay
for what they don't use."  Most std::map<>s are backed by a simple
red-black tree that has three pointers per node.  Changing that to
five would significantly increase the size of the tree, for
absolutely no benefit to std::map users.  If the node type itself
were parameterized, and defined by an interface rather than a type,
then you could simply provide an appropriate node type.  But then
you end up with something closer to Jeff Mirwaisi's design, which
is something you should carefully consider anyway.

> Simply put, I can't use it in any context where I don't know how
> many children a given node might have, such as a parse tree or a
> game tree, hence my "draconian" comment.

Depends on the game.  Tic-tac-toe, for instance, has a rather fixed
branching game tree, if you collapse rotations.  Connect-4 has a
fixed branching factor as well.  Chess is obviously a more difficult
proposition.  But if you're writing a chess program with a general
tree type, you get what you deserve.  Parse trees typically don't
have a large unbounded number of children, though some of the nodes
may certainly get arbitrarily large.

> Anyway, I've posted a more complete document in response to João's
> post, which I hope will better illustrate my intent. Have a look!

I will.

Dave