Dan Rosen wrote:
On Tue, 29 Mar 2005 01:53:44 -0600, David B. Held <dheld@codelogicconsulting.com> 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