Jump to content
  • Advertisement

Archived

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

Solstice

Trees

This topic is 5975 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

Could anyone suggest a good STL-like Tree class? I need iterators and resonable documentation. I would use STL, but ummmm, there *isn''t* an STL tree class!! -Solstice deninet.com aeris.deninet.com "...I was given three choices, the earth, the stars, or..."

Share this post


Link to post
Share on other sites
Advertisement
Do you actually _need_ a tree, or do you merely want one?

The associative containers are normally implemented with some kind of a tree (I think all the implementations I use use red-black trees).

They provide iterators and there exists good documentation. Do they not do what you want?

Binary trees are normally a means to an end rather than the desired structure. They provide a convenient mechanism for building maps and sets and things like that (they have fast lookups), and that''s normally the kind of interface you''d want to give them, as generally you don''t care to mess about with nodes and tree pointers and other such nonsense.

Share this post


Link to post
Share on other sites
As I do not completeley trust stl I made an own tree. Of course it works just fine and I used it in conjunction with a list class that I developed to sort a random file containing 1,000,000 integer numbers in less that 2 and a half minuit.(irellevant) Solstices question was quite good and I as him/her would like to know what you ''want'' a tree for. Trees can be great for sorting stuff (Hash tables are also a fine choise although it took my non-optimized hashing algorith 10 seconds longer to sort the file) but you most definateley do not want to use them as lists (as you need a recursive function to step through it from "front" to "end").

If you think the time it took my algorithm to sort the integers was very long you should keep in mind that my processors frequency is 200 MHz and the time I specified also includes I/O to two ASCII files.



Message from above:
Damn, my hair is grey!

Share this post


Link to post
Share on other sites
(*yawn* mutters: "I should have known better to have cherry coke just before going to bed...")

All very good points. Well, as of right now I''m designing a script interpreter for a game I''m developing. The idea is to have the languge define a hierarchial structure in addition to having some logic elements (Think XML plus funtions and operations). This is why I''m not using Lua or SmallC, being that their function oriented.

Later, however, when I design my game engine, the structures go into Scene tree. This is my theory: Because the script breaks down into a tree, and the Scene tree is the basis of game engine parsing...

So, I think that I need a k-ary tree that can support customizing the node data via an object. I found this class last night:
http://www.damtp.cam.ac.uk/user/kp229/tree/
but I would like to know if there''s something better I can use.



-Solstice

deninet.com
aeris.deninet.com

"...I was given three choices, the earth, the stars, or..."

Share this post


Link to post
Share on other sites
Solstice,
The tree you linked to looks GREAT! I''d recommend that you use it. Writing your own tree is not a fun proposition unless you''re nuts (I wrote my own tree, draw your own conclusions.)

One thing you MUST consider before you use this tree is the license. This tree code is GPL. It would be a violation of the code license agreement, and against the law to include this tree code in your software if your software was not "free" as in speech, by the terms of the GPL.

By using GPL code in your source, your code, by default becomes GPL. This is known as the VIRAL nature of the GPL. You can still sell your software but you MUST provide the source code to the opensource/free software community once your software hits the public domain. If you do not provide the source code you are breaking the law and damaging the free software community.

I''d give you my tree but it is GPL as well and I''m afraid this other fella did a better job than I.

RandomTask

Share this post


Link to post
Share on other sites
So how can I work around GPL? I personally don''t mind open-sourcing my project, but everyone else who is working on this might. So how can I work around it?

Currently, I''m studying the tree class I found and then writing my own based on the ideas there.

-Solstice

deninet.com
aeris.deninet.com

"...I was given three choices, the earth, the stars, or..."

Share this post


Link to post
Share on other sites
quote:
Original post by Solstice
So how can I work around GPL? I personally don''t mind open-sourcing my project, but everyone else who is working on this might. So how can I work around it?

Currently, I''m studying the tree class I found and then writing my own based on the ideas there.



Stick it in a DLL. Release the source to the DLL version. Write a wrapper DLL. Link that against the GPLed DLL. The wrapper is tainted, by the GPLed code it''s linked against, so release its source.

Link your program against the wrapper. Your program ought to be tainted by the wrapper -- but you can grant yourself (as the author of the wrapper) a special license whereby you''re permitted to link to it without releasing the source. Because you wrote the wrapper, you can release it under any license you choose (as well as the virally-induced GPL).

Or rewrite the tree using the original as the inspiration. Proving anything would be nigh impossible; one tree class is, more than likely, going to bear a striking resemblance to any other class representing the same kind of tree.

BSDL r0x0r, GPL sux0r.

Share this post


Link to post
Share on other sites
I agree with GameKeeper that a tree class is easy to code. Develop a node class that has four data members: a pointer to the left child, a pointer to the right child, a pointer to the parent node, and a data storage structure. You could templatize the data storage stucture trivially.

And as for parsing the tree, you don''t need recursion. I''ve got a routine that will parse and entire tree of the above nature in about 20 lines of code and no recursion. All that and I''m a moron. 8^)

-Kirk

Share this post


Link to post
Share on other sites
Yeah come on guys trees were the first thing we were taught at school. They are realllly simple to implement. Get yourself a Data Structures and Algorithms in C++ Book of something.

Two more hours and I can get the heck out of this office and run away to sweet sweet weekend. woooo

Tony

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!