[Nathan Jennings <njen@xxxxxxxxxxxx>]

ronnie sahlberg wrote:
> i guess this is a pefect example of our previous discussion about the
> only drawback with rb trees,    while very fast and efficient,   they
> are not trivial to implement :-)

Have you looked at GNU libavl? Maybe it'll help.

http://www.stanford.edu/~blp/avl/index.html

<snip>
GNU libavl is the most complete, well-documented collection of binary 
search tree and balanced tree library routines anywhere. It supports 
these kinds of trees:

   Plain binary trees:
      o Binary search trees
      o AVL trees
      o Red-black trees
</snip>

<snip>
Version 2.0 of libavl was released on January 6, 2002. It is a complete 
rewrite of earlier versions implemented in a �literate programming� 
fashion, such that in addition to being a useful library, it is also a 
book describing in full the algorithms behind the library.
</snip>

-Nathan