Advertisement

object iterator for a red-black tree [java]

Started by April 05, 2005 02:32 PM
0 comments, last by doynax 19 years, 6 months ago
What's the best way to implement an ObjectIterator for a red-black tree? Should I store each position in the tree in an array and loop through the array? (in Java, btw) thanks in advance everyone DM
So you're asking about how to perform an in-order binary tree iteration non-recursively, right?

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, it should be similar in Java.
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;}
This approach requires that you keep track of the parent nodes but in return the iterator only needs to store the current node.

This topic is closed to new replies.

Advertisement