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
- showSet :: Show a => RBTree a -> String
- printSet :: 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 to 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.Set.LLRBTree.null empty
True>>>
Data.Set.LLRBTree.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
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)
>>>
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)
True
minimum :: RBTree a -> aSource
Finding the minimum element. O(log N)
>>>
minimum (fromList [3,5,1])
1>>>
minimum empty
*** Exception: minimum