Data.Set.LLRBTree

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 to 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.Set.LLRBTree.null empty
True
>>> Data.Set.LLRBTree.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

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 a

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)

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

Finding the minimum element. O(log N)

>>> minimum (fromList [3,5,1])
1
>>> minimum empty
*** Exception: minimum

maximum :: RBTree a -> a

Finding the maximum element. O(log N)

>>> maximum (fromList [3,5,1])
5
>>> maximum empty
*** Exception: maximum

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

Checking validity of a tree.

showSet :: Show a => RBTree a -> String

printSet :: Show a => RBTree a -> IO ()