Safe Haskell | Safe-Inferred |
---|

- data AVLTree a
- data Zipper a
- empty :: AVLTree a
- size :: AVLTree a -> Integer
- insert :: Ord a => a -> AVLTree a -> AVLTree a
- search :: Ord a => a -> AVLTree a -> Maybe (Zipper a)
- delete :: Ord a => a -> AVLTree a -> AVLTree a
- value :: Zipper a -> a
- begin :: AVLTree a -> Maybe (Zipper a)
- end :: AVLTree a -> Maybe (Zipper a)
- predecessor :: Ord a => Zipper a -> Maybe (Zipper a)
- successor :: Ord a => Zipper a -> Maybe (Zipper a)

# Documentation

An

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

a`a`

.

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.

Show a => Show (Zipper a) |

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)*.

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