Tree Functions...
Author
Hi!
I just got over with my mid-semester exams and i thought i'd start a little project to advance my knowledge of general Game algorithms...
So i decided to start working on trees :)
I'm programming in C++ with OOP designs.
Right now i'm making a "CBinTree" class for a balanced binary tree.
The tree will always be balanced (left/right sides always one more element than the other or the same number of elements...).
I will have 2 functions to add elements, one will be to add in order an element , the second will add while keeping balance...
Anyways!
What i have now:
NumElem() - Returns the number of elements of the entire tree or the number of elements under a "sub tree" (takes a pointer to a branch structure as parameter, using it as a "starting point"). (Done and working fine.)
AddElementUnordered() - Add an element regardless of value, keeping tree balance. (done and working Fine.)
AddElementOrdered() - Add an element in order... I don't really know how to do this yet. should i try to keep the Tree's balance in terms of number of elements on each side, while trying to order the elements by value (possibly having to reconstruct part of the tree each time?!). Do i just add an element while keeping order without keeping balance...?
DisplayTree() - Prints the entire tree in a recursive fation. It goes first to the bottomest leftest leaf, then up and down left to the bottomest left leaf, etc... Overloaded function takes Branch struct pointer to only print "sub-tree".
SearchTree() - Takes a value as a parameter, looks for that value inside the tree. there's a couple of different possibilities here. If the tree is totally unordered, then i have to look through all elements and return pointer to the branch/leaf and print the "level" of the item in the tree.
The tree is Ordered totally. then it's a matter of using dichotomy to quickly find our element (each time we divide the list of possible "suspects" by two and only use one...)
I plan to go to Quadtrees and maybe Octrees after this.
Wich other functions do you think would be good that i put in?
Any good articles i should take a look at (besides the Articles on GameDev?)
Are there any articles on using Trees to create a Terrain engine (wich is the project i want to do after i finish up with trees...)
thank you :)
This is not an answer to your question, but possibly useful nonetheless.
You might want to look up AVL trees. They allow ordered addition of elements to a binary tree wihile keeping the tree balanced, eg each node has the property that the height of the sides can only differ by one.
This is my favourite tree to use as it is binary and has the property that the worst case complexity for all operations is equal to the best possible average complexity for the operations on any tree.
As for trees for a terrain engine, you might be referring to quadtrees. The tree you have described does not really fit the requirements for a good quadtree, since quadtrees have no need of depth balanceing or element order.
If you're not referring to quadtrees then ignore the above paragraph.
Edit: For some reason I didn't read the line that said you planned to go on with octrees and quadtrees. So yes do ignore the two lines above.
You might want to look up AVL trees. They allow ordered addition of elements to a binary tree wihile keeping the tree balanced, eg each node has the property that the height of the sides can only differ by one.
This is my favourite tree to use as it is binary and has the property that the worst case complexity for all operations is equal to the best possible average complexity for the operations on any tree.
As for trees for a terrain engine, you might be referring to quadtrees. The tree you have described does not really fit the requirements for a good quadtree, since quadtrees have no need of depth balanceing or element order.
If you're not referring to quadtrees then ignore the above paragraph.
Edit: For some reason I didn't read the line that said you planned to go on with octrees and quadtrees. So yes do ignore the two lines above.
Two common ways to keep BSTs balanced are the AVL tree and the red–black tree. The AVL tree makes sure that the depth of one subtree never exceeds the depth of the other subtree by more than one (curses! beaten again!), and the red–black tree colours each node red or black while maintaining certain rules about what colours are allowed to appear next to each other.
You won't get very far trying to keep equal numbers of nodes in each subtree. Adding a single node could require reconstruction of most of the tree—not quite the logarithmic complexity that we all know and love. [smile]
Take a look at the C++ std::set class (which is typically implemented as a balanced BST). I'd suggest that you design your class to be similar to std::set: allow addition (while keeping balance), deletion (while keeping balance), searching, and iteration. Try to keep the actual BST implementation hidden within the class, rather than allowing external access to the Branch structure.
For more information on red–black trees, I suggest looking here or here.
Good luck and have fun. [smile]
You won't get very far trying to keep equal numbers of nodes in each subtree. Adding a single node could require reconstruction of most of the tree—not quite the logarithmic complexity that we all know and love. [smile]
Take a look at the C++ std::set class (which is typically implemented as a balanced BST). I'd suggest that you design your class to be similar to std::set: allow addition (while keeping balance), deletion (while keeping balance), searching, and iteration. Try to keep the actual BST implementation hidden within the class, rather than allowing external access to the Branch structure.
For more information on red–black trees, I suggest looking here or here.
Good luck and have fun. [smile]
It really depends on what you are going to use the tree for. A generic binary tree isn't all that useful or even usable.
Quote:Original post by JohnBoltonI assumed he meant a binary search tree, considering what he wrote about searching it.
It really depends on what you are going to use the tree for. A generic binary tree isn't all that useful or even usable.
Binary trees are not necessarily the fastest. If you design your tree with various levels of fan-out, based on the index and the data already in the node, you can get great cache efficiency. Judy trees are among the fastest that exist right now!
http://judy.sourceforge.net/
http://judy.sourceforge.net/
Author
Yea forget about me using the tree, this is just something to practice C++ in general and get used a little bit to trees :)
I plan on using Quadtrees for a terrain engine, but i still don't know HOW to use them :(
I'm gonna go look on GameDev articles to see if there's something about it...
In the meantime, thanks for all the info, i'll look up AVL trees and Reb black trees :)
I'm taking a class in Graph theory (just the basics really) so i have a few notions on Graphs, don't know wether that could be useful or not... :)
I plan on using Quadtrees for a terrain engine, but i still don't know HOW to use them :(
I'm gonna go look on GameDev articles to see if there's something about it...
In the meantime, thanks for all the info, i'll look up AVL trees and Reb black trees :)
I'm taking a class in Graph theory (just the basics really) so i have a few notions on Graphs, don't know wether that could be useful or not... :)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
