llrbtree-0.0.1: Left-Leaning Red-Black Tree

Data.RBTree

Description

Purely functional red-black trees.

Synopsis

Data structures

data RBTree a Source

Constructors

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

Instances

 Eq a => Eq (RBTree a) Show a => Show (RBTree a)

data Color Source

Constructors

 B Black R Red

Instances

 Eq Color Show Color

type BlackHeight = IntSource

Red nodes have the same BlackHeight of their parent.

Creating red-black trees

Empty tree.

````>>> ````height empty
```0
```

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

Singleton tree.

````>>> ````height (singleton 'a')
```1
```

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

Helper functions

join :: Ord a => RBTree a -> a -> RBTree a -> RBTree aSource

merge :: Ord a => RBTree a -> RBTree a -> RBTree aSource

split :: Ord a => a -> RBTree a -> (RBTree a, RBTree a)Source

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