avl-static-0.1.0.0: A compile-time balanced AVL tree.

Safe HaskellSafe-Inferred

Data.Tree.AVL.Static

Synopsis

Documentation

data AVLTree a Source

An AVLTree a is a statically balanced tree, whose non-nil values have type a.

Instances

Functor AVLTree 
Foldable AVLTree 
Traversable AVLTree 
Show a => Show (AVLTree a) 

data Zipper a Source

A Zipper is a useful construct for functional datastructure traversals. For us, it can be thought of as a pointer to a subtree in an AVLTree.

See Functional Pearls: Zippers for more information.

Instances

Show a => Show (Zipper a) 

empty :: AVLTree aSource

An empty AVLTree.

O(1).

size :: AVLTree a -> IntegerSource

The number of nodes of an AVLTree.

O(1).

insert :: Ord a => a -> AVLTree a -> AVLTree aSource

Insert a value into an AVLTree. If the value already exists, does nothing.

O(log n).

search :: Ord a => a -> AVLTree a -> Maybe (Zipper a)Source

Search for a node with a given value. Returns a Zipper pointing to a subtree whose root has that value, or Nothing if the value is not in the tree.

O(log n).

delete :: Ord a => a -> AVLTree a -> AVLTree aSource

Deletes a value from an AVLTree. If the value does not exist in the tree, does nothing.

O(log n).

value :: Zipper a -> aSource

Gets the value at the root of the subtree pointed by that Zipper.

begin :: AVLTree a -> Maybe (Zipper a)Source

Returns a Zipper to the smallest element in the tree, or Nothing if the tree is empty.

O(log n).

end :: AVLTree a -> Maybe (Zipper a)Source

Returns a Zipper to the greatest element in the tree, or Nothing if the tree is empty.

O(log n).

predecessor :: Ord a => Zipper a -> Maybe (Zipper a)Source

Returns a Zipper to the predecessor of a value in a tree. If the input Zipper points to the smallest element in the tree, returns Nothing.

O(log n).

successor :: Ord a => Zipper a -> Maybe (Zipper a)Source

Returns a Zipper to the successor of a value in a tree. If the input Zipper points to the greatest element in the tree, returns Nothing.

O(log n).