| |||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||

Description | |||||||||||||||||||||||||||||||||||

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

Synopsis | |||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||

Deleting. | |||||||||||||||||||||||||||||||||||

Deleting from extreme left or right. | |||||||||||||||||||||||||||||||||||

assertDelL :: AVL e -> AVL e | |||||||||||||||||||||||||||||||||||

Delete the left-most element of a Complexity: O(log n) | |||||||||||||||||||||||||||||||||||

assertDelR :: AVL e -> AVL e | |||||||||||||||||||||||||||||||||||

Delete the right-most element of a Complexity: O(log n) | |||||||||||||||||||||||||||||||||||

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

Try to delete the left-most element of a Complexity: O(log n) | |||||||||||||||||||||||||||||||||||

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

Try to delete the right-most element of a Complexity: O(log n) | |||||||||||||||||||||||||||||||||||

Deleting from sorted trees.
| |||||||||||||||||||||||||||||||||||

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

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

Functionally identical to Complexity: O(log n) | |||||||||||||||||||||||||||||||||||

genDelIf :: (e -> COrdering Bool) -> AVL e -> AVL e | |||||||||||||||||||||||||||||||||||

This version only deletes the element if the supplied selector returns ( or if no matching element is found then this function returns
the original tree.
Eq False)Complexity: O(log n) | |||||||||||||||||||||||||||||||||||

genDelMaybe :: (e -> COrdering (Maybe e)) -> AVL e -> AVL e | |||||||||||||||||||||||||||||||||||

This version only deletes the element if the supplied selector returns ( then the matching element is replaced by e.
If no matching element is found then this function returns the original tree.
Eq (Just e))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) | |||||||||||||||||||||||||||||||||||

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

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

Same as Complexity: O(log n) | |||||||||||||||||||||||||||||||||||

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

Same as Complexity: O(log n) | |||||||||||||||||||||||||||||||||||

Popping from sorted trees.
| |||||||||||||||||||||||||||||||||||

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

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

Similar to genPop, but this function returns Complexity: O(log n) | |||||||||||||||||||||||||||||||||||

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

In this case the selector returns two values if a search succeeds.
If the second is 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) | |||||||||||||||||||||||||||||||||||

Similar to Complexity: O(log n) | |||||||||||||||||||||||||||||||||||

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

A simpler version of Complexity: O(log n) | |||||||||||||||||||||||||||||||||||

genTryPopIf :: (e -> COrdering (a, Bool)) -> AVL e -> Maybe (a, AVL e) | |||||||||||||||||||||||||||||||||||

Similar to genPopIf, but returns Complexity: O(log n) | |||||||||||||||||||||||||||||||||||

Produced by Haddock version 0.7 |