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