Data.RBTree.LL
Contents
Description
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
- 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
- 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
- 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.