-
Exported names:
-
Imported modules:
Module Data.RedBlackTree
Library with an implementation of red-black trees:
Serves as the base for both TableRBT and SetRBT All the operations on trees are generic, i.e., one has to provide order predicates on elements.
Author: Johannes Koj, Michael Hanus, Bernd Brassel
Version: December 2018
Summary of exported operations:
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 red-black 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. |
toList
:: RedBlackTree a -> [a]
Transforms a red-black tree into an ordered list of its elements. |
sortBy
:: Eq a => (a -> a -> Bool) -> [a] -> [a]
Generic sort based on insertion into red-black trees. |
setInsertEquivalence
:: (a -> a -> Bool) -> RedBlackTree a -> RedBlackTree a
For compatibility with old version only |
Exported datatypes:
RedBlackTree
A red-black 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 treebr
eg for a set eqInsert is (==),
for a multiset it is (
-> False)
for a lookUp-table it is ((==) . fst)
2) equality for looking up values
eg for a set eqLookUp is (==),
for a multiset it is (==)
for a lookUp-table it is ((==) . fst)
3) the (less than) relation for the binary search tree
Constructors:
Exported operations:
|
The three relations are inserted into the structure by function empty. Returns an empty tree, i.e., an empty red-black 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 red-black tree.
|
|
Updates/inserts an element into a RedBlackTree. |
|
Deletes entry from red black tree. |
|
Transforms a red-black tree into an ordered list of its elements.
|
|
Generic sort based on insertion into red-black trees. The first argument is the order for the elements. |
|
For compatibility with old version only
|