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)
>>>
insert 5 (fromList [5,3]) == fromList [3,5]
True>>>
insert 7 (fromList [5,3]) == fromList [3,5,7]
True>>>
insert 5 empty == singleton 5
True
fromList :: Ord a => [a] -> RBTree aSource
Creating a tree from a list. O(N log N)
>>>
empty == fromList []
True>>>
singleton 'a' == fromList ['a']
True>>>
fromList [5,3,5] == fromList [5,3]
True
Converting a list
toList :: RBTree a -> [a]Source
Creating a list from a tree. O(N)
>>>
toList (fromList [5,3])
[3,5]>>>
toList empty
[]
Membership
member :: Ord a => a -> RBTree a -> BoolSource
Checking if this element is a member of a tree?
>>>
member 5 (fromList [5,3])
True>>>
member 1 (fromList [5,3])
False
Deleting
delete :: Ord a => a -> RBTree a -> RBTree aSource
Deleting this element from a tree. O(log N)
>>>
delete 5 (fromList [5,3]) == singleton 3
True>>>
delete 7 (fromList [5,3]) == fromList [3,5]
True>>>
delete 5 empty == empty
True
deleteMin :: RBTree a -> RBTree aSource
Deleting the minimum element. O(log N)
>>>
deleteMin (fromList [5,3,7]) == fromList [5,7]
True>>>
deleteMin empty == empty
True
deleteMax :: RBTree a -> RBTree aSource
Deleting the maximum
>>>
deleteMax (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(3,"b"), (5,"a")]
True>>>
deleteMax empty == empty
True
Checking
null :: Eq a => RBTree a -> BoolSource
See if the red black tree is empty.
>>>
Data.RBTree.null empty
True>>>
Data.RBTree.null (singleton 1)
False
Set operations
union :: Ord a => RBTree a -> RBTree a -> RBTree aSource
Creating a union tree from two trees. O(N + M)
>>>
union (fromList [5,3]) (fromList [5,7]) == fromList [3,5,7]
True
intersection :: Ord a => RBTree a -> RBTree a -> RBTree aSource
Creating a intersection tree from trees. O(N + N)
>>>
intersection (fromList [5,3]) (fromList [5,7]) == singleton 5
True
difference :: Ord a => RBTree a -> RBTree a -> RBTree aSource
Creating a difference tree from trees. O(N + N)
>>>
difference (fromList [5,3]) (fromList [5,7]) == singleton 3
True