quote:Original post by Magmai Kai Holmlor
Thread the BSP tree.
Use the Next pointer (threaded trees do !).
Good luck, dynamic tree threading is hard. I mean hard .
Look up Threaded AVL trees for some pointers...
no stacks, no recurrsion; just another 4bytes a node and a lot of programmer''s grease.
Have none of you never heard of threaded trees!? Or am I on acid, and dreaming of something that doesn''t exist?
...
In order to program any [unthreaded] binary tree traversal without explicit recursion (not just a BSP), you need to manually maintain a stack
If you want to get technical, then you might say that you are maintaining the stack by threading the tree.... After all by threading the tree you''re maintaining a linked list layer on top of the tree which stores traversal order....
And of course, in order to thread a non-threaded tree you have to do an inorder traversal anyway.
quote:
------------
[MSCV optimizes] tail recursion into a simple loop.
------------
Using the stack as a non-recursive stack implementation? or how? You mentioned this before, I''m just curious how it does it...
Given
class Node { public: Node * left; Node * right; int data;};void Traverse(Node * root) { if (root == NULL) return; Traverse(root->left); printf("%d\n", root->data); Traverse(root->right);}
(Yes, it''s a brain-dead traversal implementation, but it''s the code that most clearly illustrates how the tail-recursion is handled.)
MSVC on /Ox will turn it into
_root$ = 8?Traverse@@YAXPAVNode@@@Z PROC NEAR ; Traverse; File node.cpp; Line 10 push esi; Line 11 mov esi, DWORD PTR _root$[esp] test esi, esi je SHORT $L551$L548:; Line 12 mov eax, DWORD PTR [esi] push eax call ?Traverse@@YAXPAVNode@@@Z ; Traverse; Line 13 mov ecx, DWORD PTR [esi+8] push ecx push OFFSET FLAT:$SG539 call _printf; Line 14 mov esi, DWORD PTR [esi+4] add esp, 12 ; 0000000cH test esi, esi jne SHORT $L548$L551: pop esi; Line 15 ret 0?Traverse@@YAXPAVNode@@@Z ENDP ; Traverse
So basically what it does, rather than pushing the arguments and using a call on the second call to Traversal, it just replaces the original argument on the stack with the new argument and jumps to the top of the call.
However, the first call to traversal still has the normal calling overhead. So a completely psycho hand coded assembly implementation will still beat out the MSVC optimized version, but the MSVC optimized version still beats a naive assembly implementation of the code.
quote:
Doesn''t a bsp''s do most of its work by virtual of the transversal? ie little work to do when visiting a node, it''s either in or out, next node?
If I understand what you''re saying (by virtual??) then usually to use a BSP, you start at the top and move to one side or the other, and don''t need to do a full in-order traversal. However, traversals are still useful. Ex: dumping debugging information to a log file.
)
