Given a node in a standard searchable binary tree (i.e. one where nodes are inserted via a comparator, so a node has a value and can have 0, 1 or 2 children, where the left child < the right child, no equal node values allowed), how can an arbitrary node find the next or previous node in the tree?
Given a node in a standard searchable binary tree (i.e. one where nodes are inserted via a comparator, so a node has a value and can have 0, 1 or 2 children, where the left child < the right child, no equal node values allowed), how can an arbitrary node find the next or previous node in the tree?
I'm trying to make a tree node perform the walking, rather than the tree perform the walking, since if a node knows its children & parent, IMO it should have enough info to navigate the tree. Ultimately this is part of an enumeration object, which stores the current node it's looking at, and can go forward or backwards. (This assumes walking in "in-order" traversal order, not pre/post-order. If a tree contains A, B, C and D I want to start with node A, and calling Next repeatedly gives nodes B, C, D and nil.) My implementation isn't quite correct and since this lovely German summer weather has made me sick (yes I'm home wearing a scarf and drinking hot tea in June) I'm not sure I'm going to get it correct tonight. Can anyone spot the flaw in this algorithm?
Given a node, and given node child ordering L < R, to get the next node in the sorted binary tree:
1. If self (the node in question) has a left child, get the left child's rightmost final descendant
2. If self is its parent's right child, get the rightmost final descendant of the parent's left child
3. If self is its parent's left child, perform step 2 but for the node's grandparent instead of parent
?
I have a working implementation in which the tree recursively iterates calling a callback for each node it visits, but I want a stateless version with no callback, just a way for a node to get its next or previous node.
My current implementation is an unbalanced binary tree, which is for simplicity since I want to get walking etc right before introducing balancing mechanisms. My unit tests show the node ordering itself is correct, but iterating by starting with the rightmost node in the tree and calling Next occasionally gives the wrong node and right now I can't figure out why, except that I think I have a bug in my logic above. I suspect the logic is in the exceptional cases where the current node is the left or rightmost, or close to it. Normally I'd solve it, but today... input appreciated. Thanks :)
I'm trying to make a tree node perform the walking, rather than the tree perform the walking, since if a node knows its children & parent, IMO it should have enough info to navigate the tree. Ultimately this is part of an enumeration object, which stores the current node it's looking at, and can go forward or backwards. (This assumes walking in "in-order" traversal order, not pre/post-order. If a tree contains A, B, C and D I want to start with node A, and calling Next repeatedly gives nodes B, C, D and nil.) My implementation isn't quite correct and since this lovely German summer weather has made me sick (yes I'm home wearing a scarf and drinking hot tea in June) I'm not sure I'm going to get it correct tonight. Can anyone spot the flaw in this algorithm?
Given a node, and given node child ordering L < R, to get the next node in the sorted binary tree:
1. If self (the node in question) has a left child, get the left child's rightmost final descendant
2. If self is its parent's right child, get the rightmost final descendant of the parent's left child
3. If self is its parent's left child, perform step 2 but for the node's grandparent instead of parent
?
I have a working implementation in which the tree recursively iterates calling a callback for each node it visits, but I want a stateless version with no callback, just a way for a node to get its next or previous node.
My current implementation is an unbalanced binary tree, which is for simplicity since I want to get walking etc right before introducing balancing mechanisms. My unit tests show the node ordering itself is correct, but iterating by starting with the rightmost node in the tree and calling Next occasionally gives the wrong node and right now I can't figure out why, except that I think I have a bug in my logic above. I suspect the logic is in the exceptional cases where the current node is the left or rightmost, or close to it. Normally I'd solve it, but today... input appreciated. Thanks :)
Stefan Glienke Recursion is fine. (I have considered building a stack of nodes and popping/pushing to go back and forth, but that seems a lot of work when creating an enumerator. I'd like to have the node do a small amount of work each time. Another non-recursive algorithm might also be possible, looping while examining the parent in steps 2-3?)
ReplyDelete"The threaded binary tree" - is there a standard Delphi implementation of a binary tree in the RTL or Spring I'm not aware of?
I would prefer not to modify the tree while traversing; with my current code, I can guarantee that while the enumerator lives, the tree is not modified. For more general use (i.e. a library implementation rather than mine) that might not be true though.
I think that should do: http://pastebin.com/PArqe1Tq
ReplyDeleteStefan Glienke That works beautifully, thank you.
ReplyDeleteFor interest, to others, he implemented much the same algorithm I described above (I think? I did not describe it very well) but I had two bugs, one when going multiple generations backwards, and one when handling the intermediate step of visiting the node as you cross from left to right