Re: Standard iterator model and tree<>
On May 8, 12:34 am, Seungbeom Kim <musip...@bawi.org> wrote:
First of all, it's hard to agree on a single representation of a tree
that fits all needs. In the most general case, a parent node can have
arbitrary number of children, which would probably be represented as a
container of pointers to the children, but would someone in need of a
binary tree, which is a significant portion of demand for trees, like
that? There's a much more efficient representation of a binary tree:
having left and right members. On the other hand, if you need more than
two, which container should be used for the children? Should they be
ordered or unordered? And what about the pointer to the parent? Do you
need one or not? To have one anyway would be an unnecessary overhead for
those not in need of it.
No, no binary trees. A tree<> would not be used to implement a binary
tree. I think that would be an inappropriate breach of abstraction
barrier. If I decided to call the data structure Rottweiler<>, for
example, then that might lessen the tendency to ask if binary trees
should be included. At this level of abstraction, the ADT level, one
should first ask what is it nature? What does it do? What are the
operations? Then, beneath that, there will be many implementations.
Thinking in this way, there requires a certain degree of honesty. If
one were to take the Rottweiller data structure and say, "Aha...your
making a tree in fact. I think I shall use it to make a binary
tree..." then the contract has been broken. My Rottweiller<> data
structure had the property of having a single node at the root, and
each node may have N children. I would like to be able to determine
if a node is in the Rottweiller<> very quickly, remove nodes quickly,
insert nodes quickly, etc. Nodes must be unique at a given level
(siblings must be distinct). The Rottweiller<> may be devoid of nodes
(empty).
Note that I have done nothing special in specifying this ADT. If I
find a taxonomist who is computer illiterate and begin to describe
this structure to him, it would be unbearably obvious to him, as he
works with the concept of such a structure on a daily basis.
So it is we, computer scientists, who make the unwarranted association
between the Rottweiller<> structure that a taxonomist might be
interested in having, and another structure that is not an ADT, the
binary tree.
Semantics also matters. Are you going to ensure or not that the left
child has a value less than or equal to that of the right child? The
simple problem of "searching" for an element in the tree depends a lot
on this assumption. And do you want the parent to have a value greater
than or equal to those of the children, as in heaps? That surely affects
a lot on how the operations, including addition and removal, should be
performed.
No, as mentioned, I would start from ADT level of abstraction first.
With so many question unanswered, a tree<> class doesn't look like a
right level of abstraction. You could make everything virtual and turn
it into a "fits-all"" abstract base class, but that won't be very
appealing to many applications where performance matters, while still
requiring lots of specializations, and that's not the way that the C++
Standard Library has taken.
I must mention that I have a high-performance tree<> in my personal
library that does not conform to STL.
That having been mentioned, the following shows a basic idea of a
general tree representation:
template <typename T>
struct tree
{
struct node
{
node* parent;
std::vector<node*> children;
T value;
node(node* p = 0) : parent(p) { }
};
node* root;
tree(node* r = 0) : root(r) { }
};
and you can certainly add things to make it into a full-blown, STL-
compliant tree class. Or take a look at an example implementation at
<http://www.aei.mpg.de/~peekas/tree/>.
Yes, this is the general idea. But as you noted, to find out if a
certain level contains an element would be slow in this structure as
well as the one in the link above, based on my initial cursory
examination of his implementation.
-Le Chaud Lapin-
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]