22 users logged in
Proud partner of GDC 2025
Before posting, review our community guidelines.
Support GameDev.net with a monthly GDNet+ subscription!
Non-recursive functions on binary trees.
April 14, 2001 04:38 AM
Anyone know where I can find information on non-recursive functions on Binary trees? Pseudo code on traversals; preorder, inorder, postorder, and insertion. Also is it true that it is more desirable to have non-recursive operations on binary trees.
Thanks.
122
April 14, 2001 05:40 AM
I was also looking for information on this subject a while ago. While I have never actually implemented it(I found I didn''t need it), I believe one solution can be something like this:
You make a stack and use it to keep track of your current position in the tree. When you visit a child node, you push the current node onto the stack. When you have done what you want with the child, you just pop the node back off the stack.
Of course, this solution is still somewhat recursive in nature....
You make a stack and use it to keep track of your current position in the tree. When you visit a child node, you push the current node onto the stack. When you have done what you want with the child, you just pop the node back off the stack.
Of course, this solution is still somewhat recursive in nature....
122
April 14, 2001 12:07 PM
There really isn't any reason not to use recursion when working with trees. Trees are highly recursive structures, it's only natural. You will likely need either your own stack, or to intrusively place a 'parent' pointer in each node, along with a way to tell how many times you visited that node. If you can keep your tree in a binary heap, and thus in an array, you might have some simpler traversals, but I still don't see why you would want to.
This is simple, it runs in O(n) time, and we will never do any better than that without some aditional knowlage. The overhead is, worst case, 16*(n+1) bytes of stack space, 2n function calls.
slightly uglyer, but slightly faster
This has exactly n function calls 2n+1 compares to NULL, n ordinary compares and n increments. We have the same worst case stack space, but rember, this is most likely 16*log2(n) stack space, not very much at all. 336 bytes if all the memory is used for nothing but the tree (assuming 32 bit address space).
Note also that a parent pointer and an int will cost 8*n space, for the entire life of your tree.
Edited by - Grib on April 14, 2001 1:10:28 PM
stupid source blocks....
Edited by - Grib on April 14, 2001 1:13:25 PM
|
This is simple, it runs in O(n) time, and we will never do any better than that without some aditional knowlage. The overhead is, worst case, 16*(n+1) bytes of stack space, 2n function calls.
slightly uglyer, but slightly faster
|
This has exactly n function calls 2n+1 compares to NULL, n ordinary compares and n increments. We have the same worst case stack space, but rember, this is most likely 16*log2(n) stack space, not very much at all. 336 bytes if all the memory is used for nothing but the tree (assuming 32 bit address space).
Note also that a parent pointer and an int will cost 8*n space, for the entire life of your tree.
Edited by - Grib on April 14, 2001 1:10:28 PM
stupid source blocks....
Edited by - Grib on April 14, 2001 1:13:25 PM
122
April 14, 2001 12:39 PM
I hate to follow up to myself, but insersion can be done easily if you are not doing any rotations/balanceing
Ugly, but it safely handles most cases.
|
Ugly, but it safely handles most cases.
April 14, 2001 10:37 PM
You ''thread'' the tree.
It dramatically increases the complexity of the methods. You tack on an additional pointer to each node, which is a Next pointer. You effectively have a tree and a linked-list at the same time. When you want to search, insert, or delete, you use the tree (left/right, or whatever it is for your tree) pointers. When you iterate, you use the next pointers (need a First pointer somewhere). The hard part is efficently & correctly switching the Next pointers when you insert or delete.
Note that they don''t need to change when/if you balence.
Insertions can be done non-recursive even with balencing - easily. So can searches. If you''re recursively searching or inserting you''re blowing cpu ticks for no good reason. Depending on how heavily the tree is used, it may or may not matter.
That''s a shit load of overhead!
Compare Current = Current->Next to a function call... 2n times!
Returns elapsed CPU ticks. Happy profiling. (rolls over about every 4 seconds, depends on CPU speed...)
Magmai Kai Holmlor
- The disgruntled & disillusioned
It dramatically increases the complexity of the methods. You tack on an additional pointer to each node, which is a Next pointer. You effectively have a tree and a linked-list at the same time. When you want to search, insert, or delete, you use the tree (left/right, or whatever it is for your tree) pointers. When you iterate, you use the next pointers (need a First pointer somewhere). The hard part is efficently & correctly switching the Next pointers when you insert or delete.
Note that they don''t need to change when/if you balence.
Insertions can be done non-recursive even with balencing - easily. So can searches. If you''re recursively searching or inserting you''re blowing cpu ticks for no good reason. Depending on how heavily the tree is used, it may or may not matter.
quote:
2n function calls
That''s a shit load of overhead!
Compare Current = Current->Next to a function call... 2n times!
|
Returns elapsed CPU ticks. Happy profiling. (rolls over about every 4 seconds, depends on CPU speed...)
Magmai Kai Holmlor
- The disgruntled & disillusioned
- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara
607
April 15, 2001 11:05 AM
I''ve figured out a way to do a non-recursive inorder traversal without using threads.
First off: Threads utilize the empty child pointers of leaf nodes, or nodes which only have one child.
In order to do this, you need to have a boolean variable associated with each child, whether or not the child pointer is a thread or a real child. A thread pointer points to the next node in an inorder traversal.
The dummy header helps the traversal by connecting the stray threads on the first and last nodes in the traversal (more on this later)
an inorder traversal on the above tree would produce: 1, 5, 9. There are a total of four threads in the above tree, because there are four empty child pointers.
the left thread of 1 points to the dummy header, the right thread of 1 points to 5, the left thread of 9 points to 5, and the right thread of 9 points to the dummy header.
the algorithm for following a thread inorder:
the reverse inorder traversal is exactly the same, just switch the right and left references in the algorithm.
Now, my method of non-recursive inorder traversal involves this theory:
If you are at any node in the traversal, you can assume that the left child has already been processed, and the right child has not been processed yet.
so:
so this assumes that the nodes have a few helper functions (isleft, isright, hasleft, hasright) and pointers to the left, right, and parent nodes, but its cool, because it allows my inorder iterator classes to not require a stack when traversing.
===============================================
Have I no control, is my soul not mine?
Am I not just man, destiny defined?
Never to be ruled, nor held to heel!
First off: Threads utilize the empty child pointers of leaf nodes, or nodes which only have one child.
In order to do this, you need to have a boolean variable associated with each child, whether or not the child pointer is a thread or a real child. A thread pointer points to the next node in an inorder traversal.
|
The dummy header helps the traversal by connecting the stray threads on the first and last nodes in the traversal (more on this later)
an inorder traversal on the above tree would produce: 1, 5, 9. There are a total of four threads in the above tree, because there are four empty child pointers.
the left thread of 1 points to the dummy header, the right thread of 1 points to 5, the left thread of 9 points to 5, and the right thread of 9 points to the dummy header.
the algorithm for following a thread inorder:
|
the reverse inorder traversal is exactly the same, just switch the right and left references in the algorithm.
Now, my method of non-recursive inorder traversal involves this theory:
If you are at any node in the traversal, you can assume that the left child has already been processed, and the right child has not been processed yet.
so:
|
so this assumes that the nodes have a few helper functions (isleft, isright, hasleft, hasright) and pointers to the left, right, and parent nodes, but its cool, because it allows my inorder iterator classes to not require a stack when traversing.
===============================================
Have I no control, is my soul not mine?
Am I not just man, destiny defined?
Never to be ruled, nor held to heel!
This is my signature. There are many like it, but this one is mine. My signature is my best friend. It is my life. I must master it as I must master my life. My signature, without me, is useless. Without my signature, I am useless.
122
April 15, 2001 01:31 PM
Forgive me for asking.. but why do it this way? A threaded binary tree adds an additional pointer to each node, as well as an additional bit (to indicate if the right thread is a thread or a link to the next child). It makes no sense. I imagine that using recursion on a red-black tree would work better than threading a binary tree for inorder, preorder, and post-order. That way, you can get down to around O(log n) for searching.. instead of O(n) (at worst case). Furthermore, the fear of adding three extra bits , plus the threads, plus the messiness in inserting and deleting and updating all the threads.. it makes a threaded binary tree iffy.
Recursion isn''t bad in the case of a balanced tree.
Magnwa
Recursion isn''t bad in the case of a balanced tree.
Magnwa
122
April 15, 2001 03:43 PM
By dumping recursion, you can get a (trivial) performance increase. The fruits of the last (ahem) "discussion" on this subject can be found at:
http://users.eecs.ukans.edu/~millew/
There are three test problems set up with both iterative and recursive solutions. Tree traversal is one of them.
http://users.eecs.ukans.edu/~millew/
There are three test problems set up with both iterative and recursive solutions. Tree traversal is one of them.
100
April 15, 2001 05:13 PM
just curious why do you even want to search a binary tree with a non recursive function? sure it can be done but whats the point? its not more efficient.
607
April 16, 2001 03:05 PM
quote:
Original post by magnwa
Forgive me for asking.. but why do it this way? A threaded binary tree adds an additional pointer to each node, as well as an additional bit (to indicate if the right thread is a thread or a link to the next child). It makes no sense. I imagine that using recursion on a red-black tree would work better than threading a binary tree for inorder, preorder, and post-order. That way, you can get down to around O(log n) for searching.. instead of O(n) (at worst case). Furthermore, the fear of adding three extra bits , plus the threads, plus the messiness in inserting and deleting and updating all the threads.. it makes a threaded binary tree iffy.
Recursion isn''t bad in the case of a balanced tree.
Magnwa
The whole point of threads is to utilise the already existing NULL pointers in leaf nodes, thus not wasting any space. The booleans, you have a point with.
The entire reason of not using recursion is due to the fact that a lot of embedded systems do not support recursion, as they do not have large stacks (or even any at all), and thus require an iterative approach to the solution of the problem.
Adding nodes to a threaded BST is pretty simple, but removing nodes is a pain in the ass. It took me a few hours to code a program that removes threaded nodes, as most of the problems lie in re-configuring the threads.
But for a static Binary Search tree, this is a highly efficient method of traversal.
===============================================
Have I no control, is my soul not mine?
Am I not just man, destiny defined?
Never to be ruled, nor held to heel!
This is my signature. There are many like it, but this one is mine. My signature is my best friend. It is my life. I must master it as I must master my life. My signature, without me, is useless. Without my signature, I am useless.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
Recommended Tutorials
Advertisement