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)
myCComp :: (k -> e -> COrdering a)
In these cases the first argument is the search key and the second argument is an element of
the 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
This convention is same as that used by the overloaded compare method from Ord class.
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 AVL
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.
The 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,
or using seq etc. in your own code (in any combining comparisons you define, for example).
A note about Eq and Ord class instances.
For AVL trees the defined instances of Ord and Eq are based on the lists that are produced using
the asListL function (it could just as well have been asListR,
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 Read and 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.