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

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

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

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

This module defines useful functions for searching AVL trees and writing information to a particular element. The functions defined here may alter the content of a tree (values of tree elements) but not the structure of a tree (no insertion or deletion). | |||||||||||||||||

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

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

Writing to extreme left or right. | |||||||||||||||||

I'm not sure these are likely to be much use in practice, but they're simple enough to implement so are included for the sake of completeness. | |||||||||||||||||

writeL :: e -> AVL e -> AVL e | |||||||||||||||||

Replace the left most element of a tree with the supplied new element. This function raises an error if applied to an empty tree. Complexity: O(log n) | |||||||||||||||||

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

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

writeR :: AVL e -> e -> AVL e | |||||||||||||||||

Replace the right most element of a tree with the supplied new element. This function raises an error if applied to an empty tree. Complexity: O(log n) | |||||||||||||||||

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

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

Writing to sorted trees.
| |||||||||||||||||

genWrite :: (e -> COrdering e) -> AVL e -> AVL e | |||||||||||||||||

A general purpose function to perform a search of a tree, using the supplied selector.
If the search succeeds the found element is replaced by the value ( Complexity: O(log n) | |||||||||||||||||

genWriteFast :: (e -> COrdering e) -> AVL e -> AVL e | |||||||||||||||||

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

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

A general purpose function to perform a search of a tree, using the supplied selector.
The found element is replaced by the value ( Nothing if the search failed.
Complexity: O(log n) | |||||||||||||||||

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

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

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

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

Produced by Haddock version 0.7 |