RBTree-0.0.5: Pure haskell Red-Black-Tree implemetation

Data.Tree.RBTree

Contents

Description

Pure Haskell Red-Black tree implementation

Synopsis

Tree Types

data Color Source

Color of a Node. Leaf is assumed to be Black.

Constructors

Red 
Black 

Instances

Eq Color 
Show Color

for distinguish Red/Black, show '*' for Red and nothing for Black.

data RBTree a Source

Basic RBTree Structure.

Constructors

Node Color a !(RBTree a) !(RBTree a)

A Node that holds an element and has two leaves.

Leaf

A Black leaf.

Instances

Show a => Show (RBTree a)

Simply show tree in (), hard to read but easy to parse.

emptyRB :: RBTree aSource

Gen an empty Tree.

Interval Types

data Interval a Source

used for range query.

Constructors

Interval (RealOrd a, RealOrd a) 

Instances

Show a => Show (Interval a) 

data RealOrd a Source

Interval value from -INF to +INF.

Constructors

PInfinity

positive infinity

NInfinity

positive infinity

RealValue a

Normal value, not need to be Ord.

Instances

Show a => Show (RealOrd a) 

Insertion

(<</) :: Ord a => RBTree a -> a -> RBTree aSource

Insert Operator for insertOrd

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

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

insertOrd :: Ord a => RBTree a -> a -> RBTree aSource

Insert 'Ord' things.

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

Insert a bunch of 'Ord' things.

Delete

(<<\) :: Ord a => RBTree a -> a -> RBTree aSource

Delete Operator for deleteOrd

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

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

deleteOrd :: Ord a => RBTree a -> a -> RBTree aSource

Delete an 'Ord' thing. see delete.

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

Delete a sequence of elements.

Search

(<<?) :: Ord a => RBTree a -> a -> Maybe aSource

Search operator for searchOrd

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

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

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

Search for 'Ord' things. see search

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

Verification

vD :: RBTree a -> Maybe IntSource

Verify black-depth are all the same. Return Just 'depth' on success, otherwise Nothing.

vR :: RBTree a -> BoolSource

vR : verify no 'red-red' pattern in x and x's parent