llrbtree-0.0.2: Set implementations with trees

Data.WBTree

Description

Purely functional weight balanced trees, aka trees of bounded balance.

• J. Nievergelt and E.M. Reingold, "Binary search trees of bounded balance", Proceedings of the fourth annual ACM symposium on Theory of computing, pp 137-142, 1972.
• S. Adams, "Implementing sets efficiently in a functional language", Technical Report CSTR 92-10, University of Southampton, 1992. http://groups.csail.mit.edu/mac/users/adams/BB/
• S. Adam, "Efficient sets: a balancing act", Journal of Functional Programming, Vol 3, Issue 4, pp 553-562.
• Y. Hirai and K. Yamamoto, "Balancing Weight-Balanced Trees", Journal of Functional Programming. Vol 21, Issue 03, pp 287-307. http://mew.org/~kazu/proj/weight-balanced-tree/
• M. Strake, "Adams' Trees Revisited - Correct and Efficient Implementation", TFP 2011. http://fox.ucw.cz/papers/bbtree/

Synopsis

# Data structures

data WBTree a Source

Constructors

 Leaf Node Size (WBTree a) a (WBTree a)

Instances

 Eq a => Eq (WBTree a) Show a => Show (WBTree a)

# Creating red-black trees

Empty tree.

````>>> ````size empty
```0
```

singleton :: a -> WBTree aSource

Singleton tree.

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

insert :: Ord a => a -> WBTree a -> WBTree 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] -> WBTree 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 :: WBTree a -> [a]Source

Creating a list from a tree. O(N)

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

# Membership

member :: Ord a => a -> WBTree 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 -> WBTree a -> WBTree 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 :: WBTree a -> WBTree aSource

Deleting the minimum element. O(log N)

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

deleteMax :: WBTree a -> WBTree 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 => WBTree a -> BoolSource

See if the red black tree is empty.

````>>> ````Data.WBTree.null empty
```True
`>>> ````Data.WBTree.null (singleton 1)
```False
```

# Set operations

union :: Ord a => WBTree a -> WBTree a -> WBTree 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 => WBTree a -> WBTree a -> WBTree aSource

Creating a intersection tree from trees. O(N + N)

````>>> ````intersection (fromList [5,3]) (fromList [5,7]) == singleton 5
```True
```

difference :: Ord a => WBTree a -> WBTree a -> WBTree 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 => WBTree a -> a -> WBTree a -> WBTree aSource

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.

merge :: WBTree a -> WBTree a -> WBTree aSource

Merging two trees. O(log N)

Each element of the left tree must be less than each element of the right tree.

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

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 :: WBTree a -> aSource

Finding the minimum element. O(log N)

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

maximum :: WBTree a -> aSource

Finding the maximum element. O(log N)

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

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

Checking validity of a tree.