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.