threaded red-black tree

[Tom Pledger]

Carl Witty writes:
 | On Sun, 2003-09-14 at 21:48, Lex Stein wrote:
 | > Hi, No one responded to my question several weeks ago about a purely
 | > functional implementation of a threaded, red-black tree. 
 | 
 | I'm not sure what you mean by "threaded".  By simply ignoring that word,
 | I come up with the following solution :-)

IIRC a threaded tree (in an imperative language) is one where 'unused'
child pointers are made to point to the next (right child pointer) or
previous (left child pointer) node in an in-order traversal.  The
pointers have to be flagged to show whether they're normal or
threading.

For example, if this tree

         R
        / \
       L   S
        \
         M

were threaded, the unused pointers would be pressed into service thus:

        L's left:  still nil, because L is the least element
        M's left:  thread to L (predecessor)
        M's right: thread to R (successor)
        S's left:  thread to R (predecessor)
        S's right: still nil, because S is the greatest element

A benefit of threading is that you can make an in-order traversal in
constant space, because you don't have to remember the whole path from
the root to your current position.

You *could* translate it into a purely functional representation,
along these lines

    data TRBT a = Empty | Node Colour (Ptr a) a (Ptr a)
    data Colour = Red | Black
    data Ptr  a = Child (TRBT a) | Thread (TRBT a)

but you'd have to do some tricky stuff

    http://haskell.org/hawiki/TyingTheKnot

to deal with the circular nature of the data structure (e.g. in the
above tree, R points to L, L points to M, and M points to R).  Also
note that every insert or delete is O(n) instead of O(log n), because
*every* node in the old tree can see the part you change.

I suggest you (Lex) either go imperative (with STRef or IORef) or do
without threading, unless you're sure that you'll be doing many more
lookups and traversals than inserts and deletes.

Regards,
Tom