Brian Hurt writes:
 > 
 > I may take this opportunity to offer a red-black tree implementation of 
 > Map as a replacement, if people are interested.  The advantage a 
 > red-black tree is that it uses one less word of memory per element in a 
 > map.

For  information, I  wrote an  implementation of  Set  using red-black
trees a long time ago. It is available here:

  http://www.lri.fr/~filliatr/software.en.html

Note:  this  code was  even  formally  proved  correct using  a  proof
assistant. Getting Map from Set is rather straightforward.

I also did some benchmarks  to compare red-black trees, patricia trees
and  Ocaml AVLs  and, as  time is  concerned, the  AVLs  were (almost)
always the most efficient.

-- 
Jean-Christophe Filliâtre (http://www.lri.fr/~filliatr)