Data.Tree.AVL.Delete

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

Deleting.

Deleting from extreme left or right.

assertDelL :: AVL e -> AVL e

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 e

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)

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)

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

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

This version only deletes the element if the supplied selector returns (Eq True). If it returns (Eq False) or if no matching element is found then this function returns the original tree.

Complexity: O(log n)

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

This version only deletes the element if the supplied selector returns (Eq Nothing). If it returns (Eq (Just e)) then the matching element is replaced by e. If no matching element is found then this function returns the original tree.

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

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)

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 Nothing if the search fails.

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 (Just e) then the new value (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 genAssertPopMaybe, but returns Nothing if the search fails.

Complexity: O(log n)

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

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)

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

Similar to genPopIf, but returns Nothing if the search fails.

Complexity: O(log n)