Data.Tree.AVL.Types

AVL Tree data type definition and a few simple utility functions.

Types.

data AVL e

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.

Constructors

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)

Instances

Functor AVL

AVL trees are an instance of Functor. This definition has been placed here to avoid introducing cyclic dependency between Types.hs and List.hs

Typeable1 AVL

Foldable AVL

Traversable AVL

Eq e => Eq (AVL e)

Eq is based on equality of the lists produced by asListL. This definition has been placed here to avoid introducing cyclic dependency between Types.hs and List.hs

Ord e => Ord (AVL e)

Ordering is based on ordering of the lists produced by asListL. This definition has been placed here to avoid introducing cyclic dependency between Types.hs and List.hs

Read e => Read (AVL e)

Show e => Show (AVL e)

Show is based on showing the list produced by asListL. This definition has been placed here to avoid introducing cyclic dependency between Types.hs and List.hs

Typeable e => Typeable (AVL e)

Simple AVL related utilities.

empty :: AVL e

The empty AVL tree.

isEmpty :: AVL e -> Bool

Returns True if an AVL tree is empty.

Complexity: O(1)

isNonEmpty :: AVL e -> Bool

Returns True if an AVL tree is non-empty.

Complexity: O(1)

singleton :: e -> AVL e

Creates an AVL tree with just one element.

Complexity: O(1)

pair :: e -> e -> AVL e

Create an AVL tree of two elements, occuring in same order as the arguments.

tryGetSingleton :: AVL e -> Maybe e

If the AVL tree is a singleton (has only one element e) then this function returns (Just e). Otherwise it returns Nothing.

Complexity: O(1)