• Advertisement

Archived

This topic is now archived and is closed to further replies.

STL style n-ary trees

This topic is 5050 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello I’m writing an STL like n-ary tree container so i can use it for stuff like Scene Graphs, and other interesting things. I need your advice please, I know there is one on the net but I think its been implemented horribly in my opinion. Basically I took GCC implementation of Red-Black tree, modified it into a n-ary tree and all is fine so far I can build generic trees very efficiently, if people are interested and i''m more than happy to release it for use by anyone once its complete. At the moment the problem I’m having is figuring out how to deal with begin and end methods in amortized constant time as the standard specifies with the various methods of iteration also what would be a valid begin and end?. I have written some Iterators for pre, post order iteration (others to follow) the problem is that begin and end iterators are different for the type of traversal. In the tree type there is a header member that maintains a pointer to the root of the tree I was wondering if I should also use the other members of the header to point to the very bottom most last and first child that always gets updated when another value is inserted. Then the begin and end methods would become constant time, do you think this is a good idea?

Share this post


Link to post
Share on other sites
Advertisement
If you use different kinds of iterators for different traversals, I don''t think there''s any good method of specifying a single begin() member function. It''s probably better to specify a different member function for each kind of traversal, like how standard container classes have both begin() for forward traversal and rbegin() for reverse traversals.

For specifying the end() for a tree traversal, I can think of two basic approaches. One is to just to use a sentinal value of some sort, like a special empty node in your tree. The other is to have a special end representation for your iterator. For example, if your iterators store pointers to nodes, then have an end iterator have a null pointer.

Share this post


Link to post
Share on other sites
quote:
Original post by SiCrane
If you use different kinds of iterators for different traversals, I don't think there's any good method of specifying a single begin() member function. It's probably better to specify a different member function for each kind of traversal, like how standard container classes have both begin() for forward traversal and rbegin() for reverse traversals.

For specifying the end() for a tree traversal, I can think of two basic approaches. One is to just to use a sentinal value of some sort, like a special empty node in your tree. The other is to have a special end representation for your iterator. For example, if your iterators store pointers to nodes, then have an end iterator have a null pointer.


The way i'm handling the different types of traversal is by making it a policy so i have only two Iterators iterator & const_iterator that are parameterized by traversal schemes, and delegates the algorithm to one of the traversal schemes. There is also methods of reverse iterators, i just use a typedef std::reverse_iterators passing my iterator type to its parameter.

I make a typedef default iterators for pre-order and normal begin/end/rbegin/rend methods with that i also provide templated versions of begin/end/rbegin/rend that take a traversal schemes. The problem with that is because the tree is already a parameterized type when i try specialize the inner templated methods i get errors. Can you specialize templated methods of an already parameterized type?

With your two approaches i'm acutally doing your first one already and using the address of the header as a sentinal, i just thought it might not be the same begin/end for all the types of traversal. Like with post-order iteration the first iterator will have to refer to the bottom most first child.

[edited by - snk_kid on June 10, 2004 3:52:06 AM]

Share this post


Link to post
Share on other sites
I've always wondered why there wasnt a generalised tree in the STL. Seems like a fairly common data structure to me.
Would you mind posting your code when your done?
Cheers.

EDIT:
found a gpl n-ary tree implementation here

(fixed link)

[edited by - aboeing on June 10, 2004 9:00:12 AM]

Share this post


Link to post
Share on other sites
Yes i've seen that one already but i don't like it, it seems like it could be implementated way better and its interface is completely bloated, they also make distinction between a iterators i believe you don't need to.

There is also one in the Game Programming Gems 4 but its a completely ridiculous implementation there view is of it is rubbish.

I'd say that the advantage of mine is that its been implementated in terms of an already robust and very efficent implementation of already simillar type, gcc's version of red-black tree.

You can think of its interface is an intersection of STL's red-black tree & the STL's sets, a simple interface.

Also its extendable, just provide a new traversal policy/scheme type, chuck it into a iterator/const_iterator that comes with it and thats it.

[edited by - snk_kid on June 10, 2004 6:02:09 AM]

Share this post


Link to post
Share on other sites
cool, I've been wanting to do this for some time. more specificly, doing a quad/oct-tree that follows the flow of STL. But my idea was kinda hammered and I was to dum to believe that STL can't be predictable in terms of speed, since it would be MY tree it would be super predictable!

Please post the code when you're done. Sorry I don't have any tips, but my old thread might have some? Click here.

}-- Programmer/Gamer/Dreamer --{
I didn't choose to code, coding choose me.

(edit: forgot the bloody link )

[edited by - seriema on June 10, 2004 5:39:23 AM]

Share this post


Link to post
Share on other sites
I'm almost ready to post/submit the code; it has 4 standard iterator types, iterator & const_iterator and reverse versions. They are parameterized by traversal schemes. Depth first iteration via pre & post order which are reversible and end up being the other e.g. a reverse pre-order is identical to post-order the other way. Breadth first iteration currently no proper reverse support because I thought it didn’t make sense to have a begin method for it but you can move backwards with the forward iterators.

I believe sibling iterators are pointless so I’m thinking of having a method called children that returns a std:: pair of suitable iterators to the beginning and end of the children list.

If people are interested I would like to read any standard features that should be included before I post soon.

edit: Compiled on GCC 3.4 & VS.NET 2003

[edited by - snk_kid on June 13, 2004 5:56:30 PM]

Share this post


Link to post
Share on other sites
Do you need your own reverse iterator type?

Won''t std::reverse_iterator do the trick?

Share this post


Link to post
Share on other sites
quote:
Original post by DrPizza
Do you need your own reverse iterator type?

Won''t std::reverse_iterator do the trick?



Yep already using it, sorry if i wasn''t clear enough

Share this post


Link to post
Share on other sites
I'll try to think of some, and update (i.e. edit) this post when something pops up.

1) Do you have the standard typedefs such as value_type and others?

2) Have you tested your iterators with different std::algorithms?

Share this post


Link to post
Share on other sites

  • Advertisement