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)
- 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.LL.null empty
True>>>
Data.RBTree.LL.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