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)
- minimum :: RBTree a -> a
- maximum :: RBTree a -> a
- valid :: Ord a => RBTree a -> Bool
- 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`

# Helper functions

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

Joining two trees with an element. O(log N)

Each element of the left tree must be less than the element. Each element of the right tree must be greater than the element. Both tree must have black root.

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

Merging two trees. O(log N)

Each element of the left tree must be less than each element of the right tree. Both trees must have black root.

split :: Ord a => a -> RBTree a -> (RBTree a, RBTree a)Source

Splitting a tree. O(log N)

`>>>`

True`split 2 (fromList [5,3]) == (empty, fromList [3,5])`

`>>>`

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

`>>>`

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

`>>>`

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

`>>>`

True`split 6 (fromList [5,3]) == (fromList [3,5], empty)`

minimum :: RBTree a -> aSource

Finding the minimum element. O(log N)

`>>>`

1`minimum (fromList [3,5,1])`

`>>>`

*** Exception: minimum`minimum empty`