Pure Haskell Red-Black tree implementation

- data Color
- data RBTree a
- emptyRB :: RBTree a
- data Interval a = Interval (RealOrd a, RealOrd a)
- data RealOrd a
- (<</) :: Ord a => RBTree a -> a -> RBTree a
- insert :: (a -> a -> Ordering) -> RBTree a -> a -> RBTree a
- insertOrd :: Ord a => RBTree a -> a -> RBTree a
- insertOrdList :: Ord a => RBTree a -> [a] -> RBTree a
- (<<\) :: Ord a => RBTree a -> a -> RBTree a
- delete :: (a -> a -> Ordering) -> RBTree a -> a -> RBTree a
- deleteOrd :: Ord a => RBTree a -> a -> RBTree a
- deleteOrdList :: Ord a => RBTree a -> [a] -> RBTree a
- (<<?) :: Ord a => RBTree a -> a -> Maybe a
- search :: (b -> a -> Ordering) -> RBTree a -> b -> Maybe a
- searchOrd :: Ord a => RBTree a -> a -> Maybe a
- searchFast :: (b -> a -> Ordering) -> RBTree a -> b -> Maybe a
- searchMax :: Ord a => RBTree a -> Maybe a
- searchMin :: Ord a => RBTree a -> Maybe a
- searchInterval :: (b -> a -> Ordering) -> RBTree a -> b -> Interval a
- searchIntervalOrd :: Ord a => RBTree a -> a -> Interval a
- vD :: RBTree a -> Maybe Int
- vR :: RBTree a -> Bool

# Tree Types

Color of a `Node`

.
Leaf is assumed to be Black.

Basic RBTree Structure.

# Interval Types

used for range query.

Interval value from -INF to +INF.

# Insertion

insert :: (a -> a -> Ordering) -> RBTree a -> a -> RBTree aSource

Insert anything. |you have to provide a compare function.

insertOrdList :: Ord a => RBTree a -> [a] -> RBTree aSource

Insert a bunch of 'Ord' things.

# Delete

delete :: (a -> a -> Ordering) -> RBTree a -> a -> RBTree aSource

If there is no relevant element in tree, tree will be returned unmodified.

deleteOrdList :: Ord a => RBTree a -> [a] -> RBTree aSource

Delete a sequence of elements.

# Search

search :: (b -> a -> Ordering) -> RBTree a -> b -> Maybe aSource

search for any thing, you should provide proper compare function.

searchFast :: (b -> a -> Ordering) -> RBTree a -> b -> Maybe aSource

a faster `search`

function implemetation. strongly recommanded.

searchMax :: Ord a => RBTree a -> Maybe aSource

Search the Maximum value in the tree, equals to get the right-most element.

searchMin :: Ord a => RBTree a -> Maybe aSource

Search the Minimum value in the tree, equals to get the left-most element.

searchInterval :: (b -> a -> Ordering) -> RBTree a -> b -> Interval aSource

Search for a Interval.

For example: tree has 1,3,5,7. search for 3 returns [3,3] that indicates itself search for 4 returns [3,5] indicates that 4 is between the element 3 and 5

The given value be or not be an element of the tree.

searchIntervalOrd :: Ord a => RBTree a -> a -> Interval aSource

Search 'Ord' things, see `searchInterval`