Data.Tree.AVL.Write

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

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 writeL, but returns Nothing if applied to an empty tree.

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 writeR, but returns Nothing if applied to an empty tree.

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 (e) of the (Eq e) constructor returned by the selector. If the search fails this function returns the original tree.

Complexity: O(log n)

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

Functionally identical to genWrite, 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 and will return an element which is different from that already present.

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 (e) of the (Eq e) constructor returned by the selector. This function returns Nothing if the search failed.

Complexity: O(log n)

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

Similar to genWrite, but also returns the original tree if the search succeeds but the selector returns (Eq Nothing). (This version is intended to help reduce heap burn rate if it's likely that no modification of the value is needed.)

Complexity: O(log n)

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

Similar to genTryWrite, but also returns the original tree if the search succeeds but the selector returns (Eq Nothing). (This version is intended to help reduce heap burn rate if it's likely that no modification of the value is needed.)

Complexity: O(log n)