Portability | portable |
---|---|
Stability | stable |
Maintainer | http://homepages.nildram.co.uk/~ahey/em.png |
AVL Tree data type definition and a few simple utility functions.
Types.
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
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.
Controlling Strictness.
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 Data.Tree.AVL.List.asListL
function (it could just as well have been Data.Tree.AVL.List.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.
E | Empty Tree |
N (AVL e) e (AVL e) | BF=-1 (right height > left height) |
Z (AVL e) e (AVL e) | BF= 0 |
P (AVL e) e (AVL e) | BF=+1 (left height > right height) |
Functor AVL | AVL trees are an instance of |
Typeable1 AVL | |
Foldable AVL | |
Traversable AVL | |
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.
isNonEmpty :: AVL e -> BoolSource
Returns True
if an AVL tree is non-empty.
Complexity: O(1)
Create an AVL tree of two elements, occuring in same order as the arguments.
tryGetSingleton :: AVL e -> Maybe eSource
If the AVL tree is a singleton (has only one element e
) then this function returns (
.
Otherwise it returns Nothing.
Just
e)
Complexity: O(1)