Sign in to follow this  
SirLuthor

Iterating through a Tree Structure

Recommended Posts

SirLuthor    364
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..

Share this post


Link to post
Share on other sites
gcs584    280
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.


//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

Share this post


Link to post
Share on other sites
SirLuthor    364
Yep, I suck at detailed explanations.. Anyway, here's how my AllocTree might look if it were charted on paper at some point:

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!

Share this post


Link to post
Share on other sites
doynax    850
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.
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;
}

Share this post


Link to post
Share on other sites
iMalc    2466
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.

Share this post


Link to post
Share on other sites
SirLuthor    364
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!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this