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