TreeStructures-0.0.2: A collection of heaps and search trees

Data.Tree.AVL

Synopsis

Documentation

data AVLTree k v Source

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

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

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

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

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

O(1). singleton constructs a singleton AVL tree

empty :: Ord k => AVLTree k vSource

O(1). empty produces an empty tree

null :: AVLTree k v -> BoolSource

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

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

O(n lg n).

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

O(n lg n).

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

O(n lg n).

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

O(n lg n).

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

O(lg n).

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

O(lg n).

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

O(lg n).

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

size :: AVLTree k v -> IntSource

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