Iterating through a Tree Structure
Author
Hello again good people! The bearer of bad tidings cometh!
Anyway, I have yet another (don't they seem just about endless?) question which has me rather stumped. Here's the setting..
We start with an AllocTree, which is a basic tree of AllocTree::Keys, henceforth reffered to as Keys. Now, the way this tree should work is that when the user calls Allocate(ASCINT size) the AllocTree will search to see if it has any empty Keys which fit the size argument, and validate them. Note that this the branches split like binary, half to one branch, half to the next. So, I find myself needing a way to iterate through the tree reliably. Note that the AllocTree only has access to the head Key, but I can easily change that.
Basically, I need a method to iterate through a tree which will, on hitting each Key, leave me with a pointer to that key, which I can then use to access it's data, and test against it. I have been thinking on this, but the best I came up with so far is marking each Key as I test it's left/right offshoots, and going up (each Key has a pointer to it's parent) the branch when no more offshoots are found on the Key. But working this way, we end up with a recursive function which will get called a huge amount of times, and a number of markings I have to clean up after the call, but can't, because I need to be able to mark while iterating, and if marks are already there, I'm screwed.
Clearly this is not a good way. And yet, it's all that I came up with, which says something about the state of a famished person's mind [smile] Anyway, I did some googling, didn't come up with much of anything. Looked through Boost's offerings, didn't find anything there (although I may well have missed a tree container if it was there).
A few things about my tree, to better help willing helpers (bad pun..) come up with solid solutions to ease my aching skull [smile] Here's how the AllocTree works. When it is first created, it creates a basic Key as it's head. When Keys are created, they have a number of possible flags (ASCBYTE, 8 bits), but the only one they start with set is ASC_REF_ISBRANCH, signifying that it is a branch. Now, if when allocating memory, you need to split a Key to get a better fit, you can call Key::Split(), which flags ASC_REF_LOPEN and ASC_REF_ROPEN (which signify that the left branch is now open, as well as the right one) and create 2 new Keys. Note that the child Keys are stored as AllocTree::Key * child[2], child[0] begin left, and child[1] being right.
Now, once a Key has been split down to optimal size, one of the branches is taken, and Key::MakeValid() is called on it, which un-sets (is that even a word) ASC_REF_ISBRANCH. That's the way things work so far.
Now, as I said earlier, I need a method to iterate through that sort of tree, that is, a garuentee that I would get a pointer to each and every Key as I go through it, missing none. I'm completely stumped on this one, to tell the truth.
Terribly sorry, I'm pretty horrible at explaining this sort of thing..
Hi,
Well, to be honest you do have me a bit stumped on your explanation. What I think you're wanting to do is traverse a tree breadth-first?
I had to make use of trees the other day. I was required to traverse them breadth-first, and one method I thought of was using Queues.
I'm just thinking, you could easily do it using a stack; although, a queue would bit much easier. I hope I'm on the right track on what you're looking for.
Anyways...Later,
GCS584
Well, to be honest you do have me a bit stumped on your explanation. What I think you're wanting to do is traverse a tree breadth-first?
I had to make use of trees the other day. I was required to traverse them breadth-first, and one method I thought of was using Queues.
//Ptr would be a pointer to the root node of the tree.void TraverseTreeBreadthFirst(Tree *ptr){ // Temp Queue Queue queue; // Temp Ptr holder for Tree Tree *traverse; if (ptr == NULL) //Check data exists in parent return; queue.create(); queue.push( tree ); //Push a tree pointer onto Queue while ( !queue.IsEmpty() ) { traverse = queue.front(); //Current node we're working with //Visit the left node first if it exists if (traverse->leftTree != NULL) queue.push( traverse->leftTree ); //Now visit the right node if it exists if (traverse->rightTree != NULL) queue.push( traverse->rightTree ); } //Empty the queue queue.empty();}I'm just thinking, you could easily do it using a stack; although, a queue would bit much easier. I hope I'm on the right track on what you're looking for.
Anyways...Later,
GCS584
Author
Yep, I suck at detailed explanations.. Anyway, here's how my AllocTree might look if it were charted on paper at some point:
Not an even tree, by any means.. What I'm wanting is a mtheod that would work something like an iterator, ie. you would call it, and it would return the next node, you would call it again, it would return the node after that, etc. I like your idea, to push every key onto a queue, and then just pop them off as necessary. But wouldn't this have a significant performance problem, were I to call this method quite often (as would be the case, since it's my memory allocator), seeing as it creates a queue, fills it, and destroyes it every call? Or perhaps I'll simply scrap the tree, and implement the memory management some other way.. Anyway, thanks!
Damned formatting... Nothing works for me.. No ASCII art here, I fear.Not an even tree, by any means.. What I'm wanting is a mtheod that would work something like an iterator, ie. you would call it, and it would return the next node, you would call it again, it would return the node after that, etc. I like your idea, to push every key onto a queue, and then just pop them off as necessary. But wouldn't this have a significant performance problem, were I to call this method quite often (as would be the case, since it's my memory allocator), seeing as it creates a queue, fills it, and destroyes it every call? Or perhaps I'll simply scrap the tree, and implement the memory management some other way.. Anyway, thanks!
So you're asking about how to perform an in-order binary tree iteration non-recursively, right? This is far from impossible, although you'll need to keep track of the parent nodes but in return the iterator only needs to store the current node.
The algorithm then takes one node as input and tries to find the next one.
If the original node has a right child then either it or it's leftmost grandchild must be the node we seek. Otherwise we have to find the first grandparent of the original node which has the previous child on the left side.
Here's a sample implementation in C.
The algorithm then takes one node as input and tries to find the next one.
If the original node has a right child then either it or it's leftmost grandchild must be the node we seek. Otherwise we have to find the first grandparent of the original node which has the previous child on the left side.
Here's a sample implementation in C.
struct node { node *left, *right, *parent };node *iterate(node *p) { node *next, *prev; next = p->right; if(next) { do { p = next; next = p->left; } while(next); } else { do { prev = p; p = p->parent; } while(p->left != prev); } return p;}
I propose 3 options.
Breadth-first traversal using a queue.
Depth first traversal maintaining an explicit stack.
Parent pointers in your nodes and an algorithm for stepping through the nodes in order.
In many cases recursively traversing a tree is just fine though, and would be preferable when possible I think.
Breadth-first traversal using a queue.
Depth first traversal maintaining an explicit stack.
Parent pointers in your nodes and an algorithm for stepping through the nodes in order.
In many cases recursively traversing a tree is just fine though, and would be preferable when possible I think.
Author
Okay folks, thanks for the input, and sorry for the belated reply.. Anyway, I did some more thinking, and ended using this solution:
The AllocTree has a std::vector of AllocTree::Keys, the node registry. Every time a Key is split, it is removed from the node registry, and it's 2 children are added. Also, when a node is made valid, it is removed from the registry. This way nodes manage themselves, the AllocTree doesn't have to worry about what is valid and what isn't, whether it has children or not, etc.
Now, when you wish to iterate through the available open nodes, you can simply iterate through the node registry. Although you should never really be going manually through the registry, which is why I also made a spate of utility functions available such as SmallestLargerThen() and so on.
Again, thanks for the help people, I appreciate it!
The AllocTree has a std::vector of AllocTree::Keys, the node registry. Every time a Key is split, it is removed from the node registry, and it's 2 children are added. Also, when a node is made valid, it is removed from the registry. This way nodes manage themselves, the AllocTree doesn't have to worry about what is valid and what isn't, whether it has children or not, etc.
Now, when you wish to iterate through the available open nodes, you can simply iterate through the node registry. Although you should never really be going manually through the registry, which is why I also made a spate of utility functions available such as SmallestLargerThen() and so on.
Again, thanks for the help people, I appreciate it!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
