threaded red-black tree

Tom Pledger Tom.Pledger at
Tue Sep 16 09:36:52 EDT 2003

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

For example, if this tree

        / \
       L   S

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

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.


More information about the Haskell-Cafe mailing list