Red Black Trees
Here are three different implementations of red-black trees in Haskell.
The first version adds deletion to Okasaki's
operations of this structure.
The second version uses stronger types
and insures that all red-black trees are properly balanced.
The third version is a more efficient
variant which employs existential types. It also ensures balancing,
provided we hide certain things, especially the polymorphic Empty