I am currently attempting to write some iterators for my red black tree implementation. I thought I would share some of my findings with the world. I sent an email to Professor Mark Allen Weiss of Florida International University for some suggestions and tips on the creation of a good iterator implementation and I got the following reply:

Hi Joseph,

You can look at the source code for the std::set class if you use the Microsoft compiler. Look in the include folder in the standard installation. The library uses red-black trees, and while the code is hard to follow you can make out the idea of how the iterators are incorporated. (The tree is threaded, to make it easy to find successor nodes).

--MW

From the STL:
void _Inc()
{    // move to node with next larger value
#if _HAS_ITERATOR_DEBUGGING
    if (this->_Mycont == 0 || _Isnil(_Ptr))
    {
        _DEBUG_ERROR("map/set iterator not incrementable");
        _SCL_SECURE_OUT_OF_RANGE;
    }
#else
    _SCL_SECURE_VALIDATE(this->_Mycont != NULL);
    if (_Isnil(_Ptr))
    {
        _SCL_SECURE_OUT_OF_RANGE;
        // end() shouldn't be incremented, don't move if _SCL_SECURE is not turned on
    }
#endif /* _HAS_ITERATOR_DEBUGGING */
    else if (!_Isnil(_Right(_Ptr)))
        _Ptr = _Min(_Right(_Ptr)); // ==> smallest of right subtree
    else
    { // climb looking for right subtree
        _Nodeptr _Pnode;
        while (!_Isnil(_Pnode = _Parent(_Ptr))
           && _Ptr == _Right(_Pnode))
            _Ptr = _Pnode; // ==> parent while right subtree
        _Ptr = _Pnode; // ==> parent (head if end())
    }
}

As you can easily see from reading the code. The _Inc() increment function thats used in the iterator implementation of the std::set template finds the successor of the current node. It does not use a threaded node approach as suggested in the above email. If still in doubt consider the following code:

My Implementation:
inline RBNode &CRedBlackTree::successor( RBNode *t )
{
    if( t->right != &NIL )
        return minimum( t->right );

    RBNode *y = t->parent;

    while( y != &NIL && t == y->right )
    {
        t = y;
        y = y->parent;
    }

    return *y;
}

déjà vu? As you can see I do it exactly how they did it?
What I still don't quite understand is why did they do it this way? I would guess that most of the time it requires log N pointer dereferences at most to find the successor?

Actually the way it works is that some iterator ++ operations will take log N, but the entire sequence from start to end takes a total of N which is as good as it gets. Almost anyway of doing it would be the same result, so it is really a matter of preference whether to use threading, extra links, or some other idea.

--MW