Re: Standard iterator model and tree<>
On May 7, 3:59 am, cbarr...@ix.netcom.com (Carl Barron) wrote:
a red black tree is one of many self balancing search trees, it
reorders the nodes so the number of generations of children from the
root is almost as small as possible, making the search of a tree with
2^n generations of children of the root take about 2n tests of operator
< to find the data if present.
For search trees iterators make sense because you can get the contents
of the container in a uniform manner.
Direct use of red black tress can be useful, but I have not found any
where the stl's associative containers are not 'good enough'.
There are semantics at play here. "Tree" has multiple meanings, so
let us be clear here. There is the tree you refer to, which is
actually 2-3 tree where the 2-3'ness is captured by red/black. There
are also similar trees like AVL and regular binary trees.
All of these trees are used to implement sets. They play the same
role that a skip list, for example, would play: They implement fast
sets or associative sets.
That is not what I mean by "tree<>".
The tree<> I am thinking of is at a different level of abstraction.
It is at the same level as set<> and map<>.
A tree<> is homogeneous hierarchy. The structure of the tree<> would
show the relationships between the objects in it. It would be used to
implement, for example, the organizational chart of a company. A
taxonomist might be interested in having a look at a tree<>.
And a tree<> is a useful data structure that does not exist in STL,
which makes me wonder why.
-Le Chaud Lapin-
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]