Portability | portable |
---|---|

Stability | stable |

Maintainer | http://homepages.nildram.co.uk/~ahey/em.png |

This module defines functions for deleting elements from AVL trees and related utilities.

- assertDelL :: AVL e -> AVL e
- assertDelR :: AVL e -> AVL e
- tryDelL :: AVL e -> Maybe (AVL e)
- tryDelR :: AVL e -> Maybe (AVL e)
- genDel :: (e -> Ordering) -> AVL e -> AVL e
- genDelFast :: (e -> Ordering) -> AVL e -> AVL e
- genDelIf :: (e -> COrdering Bool) -> AVL e -> AVL e
- genDelMaybe :: (e -> COrdering (Maybe e)) -> AVL e -> AVL e
- assertPopL :: AVL e -> (e, AVL e)
- assertPopR :: AVL e -> (AVL e, e)
- tryPopL :: AVL e -> Maybe (e, AVL e)
- tryPopR :: AVL e -> Maybe (AVL e, e)
- genAssertPop :: (e -> COrdering a) -> AVL e -> (a, AVL e)
- genTryPop :: (e -> COrdering a) -> AVL e -> Maybe (a, AVL e)
- genAssertPopMaybe :: (e -> COrdering (a, Maybe e)) -> AVL e -> (a, AVL e)
- genTryPopMaybe :: (e -> COrdering (a, Maybe e)) -> AVL e -> Maybe (a, AVL e)
- genAssertPopIf :: (e -> COrdering (a, Bool)) -> AVL e -> (a, AVL e)
- genTryPopIf :: (e -> COrdering (a, Bool)) -> AVL e -> Maybe (a, AVL e)

# Deleting.

## Deleting from extreme left or right.

assertDelL :: AVL e -> AVL eSource

Delete the left-most element of a *non-empty* AVL tree. If the tree is sorted this will be the
least element. This function raises an error if it's argument is an empty tree.

Complexity: O(log n)

assertDelR :: AVL e -> AVL eSource

Delete the right-most element of a *non-empty* AVL tree. If the tree is sorted this will be the
greatest element. This function raises an error if it's argument is an empty tree.

Complexity: O(log n)

tryDelL :: AVL e -> Maybe (AVL e)Source

Try to delete the left-most element of a *non-empty* AVL tree. If the tree is sorted this will be the
least element. This function returns `Nothing`

if it's argument is an empty tree.

Complexity: O(log n)

tryDelR :: AVL e -> Maybe (AVL e)Source

Try to delete the right-most element of a *non-empty* AVL tree. If the tree is sorted this will be the
greatest element. This function returns `Nothing`

if it's argument is an empty tree.

Complexity: O(log n)

## Deleting from *sorted* trees.

genDel :: (e -> Ordering) -> AVL e -> AVL eSource

General purpose function for deletion of elements from a sorted AVL tree. If a matching element is not found then this function returns the original tree.

Complexity: O(log n)

genDelFast :: (e -> Ordering) -> AVL e -> AVL eSource

Functionally identical to `genDel`

, but returns an identical tree (one with all the nodes on
the path duplicated) if the search fails. This should probably only be used if you know the
search will succeed.

Complexity: O(log n)

# Popping.

"Popping" means reading and deleting a tree element in a single operation.

## Popping from extreme left or right.

assertPopL :: AVL e -> (e, AVL e)Source

Pop the left-most element from a non-empty AVL tree, returning the popped element and the modified AVL tree. If the tree is sorted this will be the least element. This function raises an error if it's argument is an empty tree.

Complexity: O(log n)

assertPopR :: AVL e -> (AVL e, e)Source

Pop the right-most element from a non-empty AVL tree, returning the popped element and the modified AVL tree. If the tree is sorted this will be the greatest element. This function raises an error if it's argument is an empty tree.

Complexity: O(log n)

tryPopL :: AVL e -> Maybe (e, AVL e)Source

Same as `assertPopL`

, except this version returns `Nothing`

if it's argument is an empty tree.

Complexity: O(log n)

tryPopR :: AVL e -> Maybe (AVL e, e)Source

Same as `assertPopR`

, except this version returns `Nothing`

if it's argument is an empty tree.

Complexity: O(log n)

## Popping from *sorted* trees.

genAssertPop :: (e -> COrdering a) -> AVL e -> (a, AVL e)Source

General purpose function for popping elements from a sorted AVL tree. An error is raised if a matching element is not found. The pair returned by this function consists of the popped value and the modified tree.

Complexity: O(log n)

genTryPop :: (e -> COrdering a) -> AVL e -> Maybe (a, AVL e)Source

Similar to `genPop`

, but this function returns `Nothing`

if the search fails.

Complexity: O(log n)

genAssertPopMaybe :: (e -> COrdering (a, Maybe e)) -> AVL e -> (a, AVL e)Source

In this case the selector returns two values if a search succeeds.
If the second is `(`

then the new value (`Just`

e)`e`

) is substituted in the same place in the tree.
If the second is `Nothing`

then the corresponding tree element is deleted.
This function raises an error if the search fails.

Complexity: O(log n)

genTryPopMaybe :: (e -> COrdering (a, Maybe e)) -> AVL e -> Maybe (a, AVL e)Source

Similar to `genAssertPopMaybe`

, but returns `Nothing`

if the search fails.

Complexity: O(log n)

genAssertPopIf :: (e -> COrdering (a, Bool)) -> AVL e -> (a, AVL e)Source

A simpler version of `genAssertPopMaybe`

. The corresponding element is deleted if the second value
returned by the selector is `True`

. If it's `False`

, the original tree is returned.
This function raises an error if the search fails.

Complexity: O(log n)