Data.Tree.AVL

Many of the functions defined by this package make use of generalised comparison functions which return a variant of the Prelude Ordering data type: Data.COrdering.COrdering. These are refered to as "combining comparisons". (This is because they combine "equal" values in some manner defined by the user.)

The idea is that using this simple mechanism you can define many practical and useful variations of tree (or general set) operations from a few generic primitives, something that would not be so easy using plain Ordering comparisons (overloaded or otherwise).

Functions which involve searching a tree really only require a single argument function which takes the current tree element value as argument and returns an Ordering or Data.COrdering.COrdering to direct the next stage of the search down the left or right sub-trees (or stop at the current element). For documentation purposes, these functions are called "selectors" throughout this library. Typically a selector will be obtained by partially applying the appropriate combining comparison with the value or key being searched for. For example..

 mySelector :: Int -> Ordering               Tree elements are Ints
 or..
 mySelector :: (key,val) -> COrdering val    Tree elements are (key,val) pairs

Please read the notes in the Data.Tree.AVL.Types module documentation too.

Conversion utilities.

set2AVL :: Set a -> AVL a

Convert a Data.Set.Set (from the base package Data.Set module) to a sorted AVL tree. Elements and element ordering are preserved (ascending order is left to right).

Complexity: O(n)

avl2Set :: AVL a -> Set a

Convert a sorted AVL tree to a Data.Set.Set (from the base package Data.Set module). Elements and element ordering are preserved.

Complexity: O(n)

map2AVL :: Map key val -> AVL (key, val)

Convert a Data.Map.Map (from the base package Data.Map module) to a sorted (by key) AVL tree. Elements and element ordering are preserved (ascending order is left to right).

Complexity: O(n)

avl2Map :: AVL (key, val) -> Map key val

Convert a sorted (by key) AVL tree to a Data.Map.Map (from the base package Data.Map module). Elements and element ordering are preserved.

Complexity: O(n)

Modules.

module Data.Tree.AVL.Types

module Data.Tree.AVL.Size

module Data.Tree.AVL.Read

module Data.Tree.AVL.Write

module Data.Tree.AVL.Push

module Data.Tree.AVL.Delete

module Data.Tree.AVL.List

module Data.Tree.AVL.Join

module Data.Tree.AVL.Split

module Data.Tree.AVL.Set

module Data.Tree.AVL.Zipper