From: Joao Abecasis (jpabecasis_at_[hidden])
Date: 2005-02-25 08:07:47
christopher diggins wrote:
> You do bring up very good points, and I am not sure what my position is
> yet so I will play the Devil's advocate for now. A useful tree iterator,
> in my view should provide access to the parent node from a given
> position in the tree. Without that algorithms, etc. are harder to write,
> and the tree is much harder to manage. Being able to move to a parent
> node makes the various traversals trivial (and without overhead as far
> as I can tell). I also do not believe that implementation should dictate
> interface. Implementations that try to save a pointer by not providing a
> pointer to the parent, are really just making life complicated for the
> sake of a few bytes. Arguably if space is that much of a concern perhaps
> the tree is not the right data structure for the job?
I agree with some of the points you make but perhaps I didn't make
myself completely clear in the first place. I was not trying to make
space or efficiency constraints limit the interface. My point was that
the Concepts themselves should allow different implementations, the same
way a you can have single- and double-linked lists implementations of a
Sure, for many applications you'll want every kind of traversal
possible. But not in all important applications. For example, searching
a binary search tree only requires parent-to-child traversal. My point
is that you can have different trees, all exposing the same basic
interface that can provide different traversal possibilities and
different complexity tradeoffs.
In my design a tree_iterator is categorized according to a
VerticalTraversalCategory which can be Forward (only parent-to-child) or
Bidirectional. So if a tree_iterator supports it you could:
++it /* next sibling */;
--it /* previous sibling */;
A separate traits class tells us the particular traversal category of a
tree_iterator. Based on this any algorithm can choose an implementation
for the particular traversal categories or require tree_iterators of a
>> Inorder, preorder and postorder traversals are possible using a stack
>> of ancestors. In the general case, though you shouldn't have to pay
>> for this extra overhead at all times.
> I am not convinced that there is *significant* overhead.
Well, IMO, *if and when* a tree_iterator does not provide access to the
parent, keeping a stack of pointers to allow for traversals I may not
need is significant overhead for a tree_iterator. If we also allow
traversals to be reversible we would end up with an iterator that holds
a pointer to every node in the tree.
But my point is not that the overhead is significant in all cases. Only
that it may be in some, so we cannot assume that every tree
implementation will provide a single iterator for
inorder/preorder/postorder and general tree traversal.
>> IMO a tree container should be just that. Preorder, postorder and
>> inorder are ways to turn a tree into a sequence, I see them as views
>> of the tree.
> Yes. However traversing a tree is a rather common and important task for
> a tree data structure.
>> This is the main reason I'd prefer to have them as separate entities.
> That or the overhead? If there is no *significant* overhead then why not
> allow a tree to provide a direct treatment as a sequence. Clearly the
> question becomes, what overhead is significant?
IMO, if this can be provided in a general way outside the tree it would
keep the interface of a tree simpler. I see no reason why linear
traversals cannot be provided in a general way outside trees without
loss of efficiency or added overhead. Still, Thorsten makes the point
that this will make for more cryptic error messages and less "pleasant"
code. I'm not sure I agree with him on that, but only an implementation
will tell ;)
>> Btw, here's my short view of a tree:
>> template <typename T>
>> struct Tree
>> typedef /**/ tree_iterator;
>> typedef /**/ const_tree_iterator;
>> typedef /**/ sibling_iterator;
>> typedef /**/ const_sibling_iterator;
>> tree_iterator root();
>> tree_const_iterator root() const;
> This appears to be good code (upon cursory examination) however I am
> really at only concerned with binary trees at this point. They are in my
> view very separate things from k-ary trees and mandate separate
> implementations. Do you agree?
I think we can single out binary trees and give them a specific
interface (I did!) where it makes sense to do so, but without putting
aside the general tree interface. I also think a Boost Tree library
should not lose the opportunity to define general concepts that can work
with different trees and not only k-ary trees.
> As I said before, you make excellent points but I am not *yet* convinced
> that a tree should not be inherently treatable as a sequence.
If you can have a tree that is only a tree and outside means of
linearizing the tree (as in a LinearView or something) can be provided
only once in a general way, what keeps us from doing that? I view this
as the member/non-member functions debate.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk