Data.Set.WBTree

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/

Data structures

data WBTree a

Constructors

Leaf

Node Size (WBTree a) a (WBTree a)

Instances

Eq a => Eq (WBTree a)

Show a => Show (WBTree a)

type Size = Int

size :: WBTree a -> Size

Creating sets

empty :: WBTree a

Empty set.

>>> size empty
0

singleton :: a -> WBTree a

Singleton set.

>>> size (singleton 'a')
1

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

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

Creating a set 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 :: WBTree a -> [a]

Creating a list from a set. O(N)

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

Membership

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

Checking if this element is a member of a set?

>>> member 5 (fromList [5,3])
True
>>> member 1 (fromList [5,3])
False

Deleting

delete :: Ord a => a -> WBTree a -> WBTree a

Deleting this element from a set. 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 a

Deleting the minimum element. O(log N)

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

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

See if the set is empty.

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

Set operations

union :: Ord a => WBTree a -> WBTree a -> WBTree a

Creating a union set from two sets. O(N + M)

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

intersection :: Ord a => WBTree a -> WBTree a -> WBTree a

Creating a intersection set from sets. O(N + N)

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

difference :: Ord a => WBTree a -> WBTree a -> WBTree a

Creating a difference set from sets. O(N + N)

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

Helper functions

join :: Ord a => WBTree a -> a -> WBTree a -> WBTree a

Joining two sets with an element. O(log N)

Each element of the left set must be less than the element. Each element of the right set must be greater than the element.

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

Merging two sets. O(log N)

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

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

Splitting a set. 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 -> a

Finding the minimum element. O(log N)

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

maximum :: WBTree a -> a

Finding the maximum element. O(log N)

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

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

Checking validity of a set.