Haskell Hierarchical Libraries (collections package)ContentsIndex
Data.Tree.AVL.Internals.HeightUtils
Portabilityportable
Stabilitystable
Maintainerhttp://homepages.nildram.co.uk/~ahey/em.png
Description

AVL tree height related utilities.

The functions defined here are not exported by the main Data.Tree.AVL module because they violate the policy for AVL tree equality used elsewhere in this library. You need to import this module explicitly if you want to use any of these functions.

Synopsis
height :: AVL e -> Int#
addHeight :: Int# -> AVL e -> Int#
compareHeight :: AVL a -> AVL b -> Ordering
fastAddSize :: Int# -> AVL e -> Int#
Documentation
height :: AVL e -> Int#

Determine the height of an AVL tree.

Complexity: O(log n)

addHeight :: Int# -> AVL e -> Int#

Adds the height of a tree to the first argument.

Complexity: O(log n)

compareHeight :: AVL a -> AVL b -> Ordering

A fast algorithm for comparing the heights of two trees. This algorithm avoids the need to compute the heights of both trees and should offer better performance if the trees differ significantly in height. But if you need the heights anyway it will be quicker to just evaluate them both and compare the results.

Complexity: O(log n), where n is the size of the smaller of the two trees.

fastAddSize :: Int# -> AVL e -> Int#

Fast algorithm to calculate size. This avoids visiting about 50% of tree nodes by using fact that trees with small heights can only have particular shapes. So it's still O(n), but with substantial saving in constant factors.

Complexity: O(n)

Produced by Haddock version 0.7