Data.Tree.AVL.Push

This module defines functions for searching AVL trees and pushing a new element in the tree (or modifying the value of an existing element). The functions defined here may alter the content of a tree (value of an existing tree element) and also the structure of a tree (by adding a new element).

Pushing on extreme left or right.

pushL :: e -> AVL e -> AVL e

Push a new element in the leftmost position of an AVL tree. No comparison or searching is involved.

Complexity: O(log n)

pushR :: AVL e -> e -> AVL e

Push a new element in the rightmost position of an AVL tree. No comparison or searching is involved.

Complexity: O(log n)

Pushing on sorted trees.

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

General push. This function searches the AVL tree using the supplied selector. If a matching element is found it's replaced by the value (e) returned in the (Eq e) constructor returned by the selector. If no match is found then the default element value is added at in the appropriate position in the tree.

Note that for this to work properly requires that the selector behave as if it were comparing the (potentially) new default element with existing tree elements, even if it isn't.

Note also that this function is non-strict in it's second argument (the default value which is inserted if the search fails or is discarded if the search succeeds). If you want to force evaluation, but only if it's actually incorprated in the tree, then use genPush'

Complexity: O(log n)

genPush' :: (e -> COrdering e) -> e -> AVL e -> AVL e

Almost identical to genPush, but this version forces evaluation of the default new element (second argument) if no matching element is found. Note that it does not do this if a matching element is found, because in this case the default new element is discarded anyway. Note also that it does not force evaluation of any replacement value provided by the selector (if it returns Eq). (You have to do that yourself if that's what you want.)

Complexity: O(log n)

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

Similar to genPush, but returns the original tree if the combining comparison returns (Eq Nothing). So this function can be used reduce heap burn rate by avoiding duplication of nodes on the insertion path. But it may also be marginally slower otherwise.

Note that this function is non-strict in it's second argument (the default value which is inserted in the search fails or is discarded if the search succeeds). If you want to force evaluation, but only if it's actually incorprated in the tree, then use genPushMaybe'

Complexity: O(log n)

genPushMaybe' :: (e -> COrdering (Maybe e)) -> e -> AVL e -> AVL e

Almost identical to genPushMaybe, but this version forces evaluation of the default new element (second argument) if no matching element is found. Note that it does not do this if a matching element is found, because in this case the default new element is discarded anyway.

Complexity: O(log n)