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 tree.