Library with an implementation of redblack trees:
Serves as the base for both TableRBT and SetRBT
All the operations on trees are generic, i.e., one has to provide
two explicit order predicates ("lessThan
" and "eq
"below)
on elements.
Author: Johannes Koj, Michael Hanus, Bernd Brassel
Version: March 2005
empty
:: (a > a > Bool) > (a > a > Bool) > (a > a > Bool) > RedBlackTree a
The three relations are inserted into the structure by function empty. 
isEmpty
:: RedBlackTree a > Bool
Test on emptyness 
newTreeLike
:: RedBlackTree a > RedBlackTree a
Creates a new empty red black tree from with the same ordering as a give one. 
lookup
:: a > RedBlackTree a > Maybe a
Returns an element if it is contained in a redblack tree. 
update
:: a > RedBlackTree a > RedBlackTree a
Updates/inserts an element into a RedBlackTree. 
delete
:: a > RedBlackTree a > RedBlackTree a
Deletes entry from red black tree. 
tree2list
:: RedBlackTree a > [a]
Transforms a redblack tree into an ordered list of its elements. 
sortBy
:: (a > a > Bool) > [a] > [a]
Generic sort based on insertion into redblack trees. 
setInsertEquivalence
:: (a > a > Bool) > RedBlackTree a > RedBlackTree a
For compatibility with old version only 
A redblack tree consists of a tree structure and three order predicates.
These predicates generalize the red black tree. They define
1) equality when inserting into the tree
eg for a set eqInsert is (==),
for a multiset it is (
> False)
for a lookUptable it is ((==) . fst)
2) equality for looking up values
eg for a set eqLookUp is (==),
for a multiset it is (==)
for a lookUptable it is ((==) . fst)
3) the (less than) relation for the binary search tree
Constructors:
The three relations are inserted into the structure by function empty. Returns an empty tree, i.e., an empty redblack tree augmented with the order predicates.

Test on emptyness

Creates a new empty red black tree from with the same ordering as a give one.

Returns an element if it is contained in a redblack tree.

Updates/inserts an element into a RedBlackTree. 
Deletes entry from red black tree. 
Transforms a redblack tree into an ordered list of its elements.

Generic sort based on insertion into redblack trees. The first argument is the order for the elements. 
For compatibility with old version only
