Tree Iterators

quote:

---

Given a red-black tree, is there a way to write an iterator that will support structural changes to the tree during iteration?

---

It would appear so, as C++ Standard Library implementations I use use a red-black tree for maps and have proper iteration. I don''t really see that you have to do anything special to achieve this (even if a rotate occurs, the process to go to the next highest and next lowest value remains the same); obviously, if the node the iterator refers to is destroyed then it''ll stop working, but that''s OK.

The easiest way to iterate a tree is recursively, in which the stack gets absolutely destroyed during rotations, but I realized later in the day that I posted this that you can use a state machine for the iterator. Assuming an in-order traversal, there are states for ascending, descending, and if ascending, then whether ascention is from the left or right. The iterator stays in the switch loop, only yielding results if ascending from the left, or if attempting to descend when there is no left child. I wrote up the code for it but it''s at work and as such not in front of me, but i can post if there''s interest.
I forget whether STL sets support modifications outside of the iterators. std::list does, I believe, which is the behavior I was trying to simulate.

An iterator in a tree only needs to know the node it''s pointing to. Iterating forwards looks like:

void Iterator::increment()
{
    if (node->hasRightChild())
    {
        node = node->rightChild;
        while (node->hasLeftChild()) node = node->leftChild;
    }
    else if (node->isLeftChild())
    {
        node = node->parent;
    }
    else
    {
        while (!node->isLeftChild()) node = node->parent;
        node = node->parent;
    }
}

Try it out on paper.

quote:

---

The easiest way to iterate a tree is recursively

---

No it isn''t, as a recursive function isn''t much good for a c++ iterator (it may work for something like Python, with its "yield", I don''t know).

For C++ the thing to do is something along the lines of what Beer Hunter wrote. Or take a look at your C++ library''s map iterator.