Purely functional left-leaning red-black trees.

- Robert Sedgewick, "Left-Leaning Red-Black Trees", Data structures seminar at Dagstuhl, Feb 2008. http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
- Robert Sedgewick, "Left-Leaning Red-Black Trees", Analysis of Algorithms meeting at Maresias, Apr 2008 http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf

- data RBTree a
- data Color
- type BlackHeight = Int
- empty :: RBTree a
- insert :: Ord a => a -> RBTree a -> RBTree a
- singleton :: Ord a => 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 to 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.Set.LLRBTree.null empty`

`>>>`

False`Data.Set.LLRBTree.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`