AVL Tree data type definition and a few simple utility functions.
AVL tree data type.
The balance factor (BF) of an
AVL tree node is defined as the difference between the height of
the left and right sub-trees. An
AVL tree is ALWAYS height balanced, such that |BF| <= 1.
The functions in this library (Data.Tree.AVL) are designed so that they never construct
an unbalanced tree (well that's assuming they're not broken). The
AVL tree type defined here
has the BF encoded the constructors.
Some functions in this library return
AVL trees that are also "flat", which (in the context
of this library) means that the sizes of left and right sub-trees differ by at most one and
are also flat. Flat sorted trees should give slightly shorter searches than sorted trees which
are merely height balanced. Whether or not flattening is worth the effort depends on the number
of times the tree will be searched and the cost of element comparison.
In cases where the tree elements are sorted, all the relevant
AVL functions follow the
convention that the leftmost tree element is least and the rightmost tree element is
the greatest. Bear this in mind when defining general comparison functions. It should
also be noted that all functions in this library for sorted trees require that the tree
does not contain multiple elements which are "equal" (according to whatever criterion
has been used to sort the elements).
It is important to be consistent about argument ordering when defining general purpose comparison functions (or selectors) for searching a sorted tree, such as ..
myComp :: (k -> e -> Ordering) -- or.. myCComp :: (k -> e -> COrdering a)
In these cases the first argument is the search key and the second argument is an element of
AVL tree. For example..
key `myCComp` element -> Lt implies key < element, proceed down the left sub-tree key `myCComp` element -> Gt implies key > element, proceed down the right sub-tree
WARNING: The constructors of this data type are exported from this module but not from
the top level
AVL wrapper (Data.Tree.AVL). Don't try to construct your own
trees unless you're sure you know what your doing. If you end up creating and using
AVL trees that aren't you'll break most of the functions in this library.
AVL data type is declared as non-strict in all it's fields,
but all the functions in this library behave as though it is strict in its
recursive fields (left and right sub-trees). Strictness in the element field is
controlled either by using the strict variants of functions (defined in this library
where appropriate), or using strict variants of the combinators defined in Data.COrdering,
seq etc. in your own code (in any combining comparisons you define, for example).
AVL trees the defined instances of
Eq are based on the lists that are produced using
Data.Tree.AVL.List.asListL function (it could just as well have been
the choice is arbitrary but I can only chose one). This means that two trees which contain the same elements
in the same order are equal regardless of detailed tree structure. The same principle has been applied to
the instances of
Show. Unfortunately, this has the undesirable and non-intuitive effect
of making "equal" trees potentially distinguishable using some functions (such as height).
All such functions have been placed in the Data.Tree.AVL.Internals modules, which are not
included in the main Data.Tree.AVL wrapper. For all "normal" functions (f) exported by Data.Tree.AVL
it is safe to assume that if a and b are
AVL trees then (a == b) implies (f a == f b), provided the same
is true for the tree elements.
|N (AVL e) e (AVL e)|
BF=-1 (right height > left height)
|Z (AVL e) e (AVL e)|
|P (AVL e) e (AVL e)|
BF=+1 (left height > right height)
AVL trees are an instance of
|Eq e => Eq (AVL e)|
Eq is based on equality of the lists produced by
|Ord e => Ord (AVL e)|
Ordering is based on ordering of the lists produced by
|Read e => Read (AVL e)|
|Show e => Show (AVL e)|
Show is based on showing the list produced by
|Typeable e => Typeable (AVL e)|
Simple AVL related utilities.
Create an AVL tree of two elements, occuring in same order as the arguments.