Purely functional red-black trees.

- Chris Okasaki, "Red-Black Trees in a Functional Setting", Journal of Functional Programming, 9(4), pp 471-477, July 1999 http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp99
- Stefan Kahrs, "Red-black trees with types", Journal of functional programming, 11(04), pp 425-432, July 2001

- data RBTree a
- data Color
- type BlackHeight = Int
- empty :: RBTree a
- singleton :: Ord a => a -> RBTree a
- insert :: Ord a => a -> RBTree a -> RBTree a
- fromList :: Ord a => [a] -> RBTree a
- toList :: RBTree a -> [a]
- member :: Ord a => a -> RBTree a -> Bool
- delete :: Ord a => a -> RBTree a -> RBTree a
- deleteMin :: RBTree a -> RBTree a
- deleteMax :: RBTree a -> RBTree a
- null :: Eq a => RBTree a -> Bool
- union :: Ord a => RBTree a -> RBTree a -> RBTree a
- intersection :: Ord a => RBTree a -> RBTree a -> RBTree a
- difference :: Ord a => RBTree a -> RBTree a -> RBTree a
- join :: Ord a => RBTree a -> a -> RBTree a -> RBTree a
- merge :: Ord a => RBTree a -> RBTree a -> RBTree a
- split :: Ord a => a -> RBTree a -> (RBTree a, RBTree a)
- valid :: Ord a => RBTree a -> Bool
- minimum :: RBTree a -> a
- maximum :: RBTree a -> a
- showTree :: Show a => RBTree a -> String
- printTree :: Show a => RBTree a -> IO ()

# Data structures

type BlackHeight = IntSource

Red nodes have the same BlackHeight of their parent.

# Creating red-black trees

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

Insertion. O(log N)

`>>>`

True`insert 5 (fromList [5,3]) == fromList [3,5]`

`>>>`

True`insert 7 (fromList [5,3]) == fromList [3,5,7]`

`>>>`

True`insert 5 empty == singleton 5`

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

Creating a tree from a list. O(N log N)

`>>>`

True`empty == fromList []`

`>>>`

True`singleton 'a' == fromList ['a']`

`>>>`

True`fromList [5,3,5] == fromList [5,3]`

# Converting a list

toList :: RBTree a -> [a]Source

Creating a list from a tree. O(N)

`>>>`

[3,5]`toList (fromList [5,3])`

`>>>`

[]`toList empty`

# Membership

member :: Ord a => a -> RBTree a -> BoolSource

Checking if this element is a member of a tree?

`>>>`

True`member 5 (fromList [5,3])`

`>>>`

False`member 1 (fromList [5,3])`

# Deleting

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

Deleting this element from a tree. O(log N)

`>>>`

True`delete 5 (fromList [5,3]) == singleton 3`

`>>>`

True`delete 7 (fromList [5,3]) == fromList [3,5]`

`>>>`

True`delete 5 empty == empty`

deleteMin :: RBTree a -> RBTree aSource

Deleting the minimum element. O(log N)

`>>>`

True`deleteMin (fromList [5,3,7]) == fromList [5,7]`

`>>>`

True`deleteMin empty == empty`

deleteMax :: RBTree a -> RBTree aSource

Deleting the maximum

`>>>`

True`deleteMax (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(3,"b"), (5,"a")]`

`>>>`

True`deleteMax empty == empty`

# Checking

null :: Eq a => RBTree a -> BoolSource

See if the red black tree is empty.

`>>>`

True`Data.RBTree.null empty`

`>>>`

False`Data.RBTree.null (singleton 1)`

# Set operations

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

Creating a union tree from two trees. O(N + M)

`>>>`

True`union (fromList [5,3]) (fromList [5,7]) == fromList [3,5,7]`

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

Creating a intersection tree from trees. O(N + N)

`>>>`

True`intersection (fromList [5,3]) (fromList [5,7]) == singleton 5`

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

Creating a difference tree from trees. O(N + N)

`>>>`

True`difference (fromList [5,3]) (fromList [5,7]) == singleton 3`