Data.RBTree.LL

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 structures

data RBTree a

Constructors

Leaf

Node Color !BlackHeight !(RBTree a) a !(RBTree a)

Instances

Eq a => Eq (RBTree a)

Show a => Show (RBTree a)

data Color

Constructors

B

Black

R

Red

Instances

Eq Color

Show Color

type BlackHeight = Int

Red nodes have the same BlackHeight of their parent.

Creating red-black trees

empty :: RBTree a

Empty tree.

>>> height empty
0

insert :: Ord a => a -> RBTree a -> RBTree a

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

singleton :: Ord a => a -> RBTree a

Singleton tree.

>>> height (singleton 'a')
1

fromList :: Ord a => [a] -> RBTree a

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]

Creating a list from a tree. O(N)

>>> toList (fromList [5,3])
[3,5]
>>> toList empty
[]

Membership

member :: Ord a => a -> RBTree a -> Bool

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 a

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 a

Deleting the minimum element. O(log N)

>>> deleteMin (fromList [5,3,7]) == fromList [5,7]
True
>>> deleteMin empty == empty
True

deleteMax :: RBTree a -> RBTree a

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 -> Bool

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 a

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 a

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 a

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 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 ()