Data.Tree.AVL

Documentation

data AVLTree k v

Instances

(Eq k, Eq v) => Eq (AVLTree k v)

(Ord k, Ord v) => Ord (AVLTree k v)

(Show k, Show v) => Show (AVLTree k v)

head :: Ord k => AVLTree k v -> v

O(1). head returns the head of a tree.

tail :: Ord k => AVLTree k v -> AVLTree k v

O(lg n). tail discards the head of the tree and returns a tree.

singleton :: Ord k => k -> v -> AVLTree k v

O(1). singleton constructs a singleton AVL tree

empty :: Ord k => AVLTree k v

O(1). empty produces an empty tree

null :: AVLTree k v -> Bool

O(1). null returns True if a tree is empty, otherwise False.

fromList :: Ord k => [(k, v)] -> AVLTree k v

O(n lg n).

fromAscList :: Ord k => [(k, v)] -> AVLTree k v

O(n lg n).

toList :: Ord k => AVLTree k v -> [(k, v)]

O(n lg n).

toAscList :: Ord k => AVLTree k v -> [(k, v)]

O(n lg n).

insert :: Ord k => k -> v -> AVLTree k v -> AVLTree k v

O(lg n).

delete :: Ord k => k -> AVLTree k v -> AVLTree k v

O(lg n).

lookup :: Ord k => k -> AVLTree k v -> Maybe v

O(lg n).

(!!) :: Ord k => AVLTree k v -> Int -> (k, v)

size :: AVLTree k v -> Int

O(1). size reports the number of children in a tree