Data.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 red-black trees

empty :: WBTree a

Empty tree.

>>> size empty
0

singleton :: a -> WBTree a

Singleton tree.

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

Creating a list from a tree. 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 tree?

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

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 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 => WBTree a -> a -> WBTree a -> WBTree 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.

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

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)

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 -> 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 tree.