tree traversal from recursive to iterative
-
I have a tree data structure that I use for my scene graph that I traverse each frame to update 20.000 nodes, I am currently doing the typical recursive traversal but probably it would be quicker if I converted the recursive traversal in an iterative one, does anyone have any hint on how to do that? Here is how my data structure looks like:
class Node
{
public:... some data ...
std::vector Children;
};void do_something_before(Node*)
{
...
}void do_something_after(Node*)
{
...
}// function to translate into an iterative one
void traverse(Node* node)
{
do_something_before(node);for(int i=0; iChildren.size(); ++i )
traverse(node->Children[i]);do_something_after(node);
}Thanks
-
I have a tree data structure that I use for my scene graph that I traverse each frame to update 20.000 nodes, I am currently doing the typical recursive traversal but probably it would be quicker if I converted the recursive traversal in an iterative one, does anyone have any hint on how to do that? Here is how my data structure looks like:
class Node
{
public:... some data ...
std::vector Children;
};void do_something_before(Node*)
{
...
}void do_something_after(Node*)
{
...
}// function to translate into an iterative one
void traverse(Node* node)
{
do_something_before(node);for(int i=0; iChildren.size(); ++i )
traverse(node->Children[i]);do_something_after(node);
}Thanks
-
I already saw that example of wikipedia, unfortunately it is for a binary tree meanwhile I would need a more general N-ary tree and with operations on the node performed before and after visiting the children. I thought there would be a "text-book" solution to this but it seems that this is a much more complex problem than I expected...
-
I already saw that example of wikipedia, unfortunately it is for a binary tree meanwhile I would need a more general N-ary tree and with operations on the node performed before and after visiting the children. I thought there would be a "text-book" solution to this but it seems that this is a much more complex problem than I expected...
Michele Bosi wrote:
I thought there would be a "text-book" solution to this but it seems that this is a much more complex problem than I expected...
It is not trivial, but it is still pretty straightforward: replace recursive calls with a loop and a stack. Local variables would take values from the stack, much like function parameters, and recursive function calls would translate to putting parameters on the stack and going to the beginning of the loop.
-
Michele Bosi wrote:
I thought there would be a "text-book" solution to this but it seems that this is a much more complex problem than I expected...
It is not trivial, but it is still pretty straightforward: replace recursive calls with a loop and a stack. Local variables would take values from the stack, much like function parameters, and recursive function calls would translate to putting parameters on the stack and going to the beginning of the loop.
In theory I would also do as you say, but when you actually try to translate it into practice everything becomes much more foggy, especially the management of the 2 functions "do_something_before()" and "do_soemthing_after()".
-
I have a tree data structure that I use for my scene graph that I traverse each frame to update 20.000 nodes, I am currently doing the typical recursive traversal but probably it would be quicker if I converted the recursive traversal in an iterative one, does anyone have any hint on how to do that? Here is how my data structure looks like:
class Node
{
public:... some data ...
std::vector Children;
};void do_something_before(Node*)
{
...
}void do_something_after(Node*)
{
...
}// function to translate into an iterative one
void traverse(Node* node)
{
do_something_before(node);for(int i=0; iChildren.size(); ++i )
traverse(node->Children[i]);do_something_after(node);
}Thanks
Thanks to all the replies, it turned out that a easier way of optimizing such code is to make the data structures as cache friendly as possible making the nodes smaller and careful allocation, so one can forget about iterative traversal for another bit...