Portability | portable |
---|---|

Stability | stable |

Maintainer | http://homepages.nildram.co.uk/~ahey/em.png |

`AVL`

tree related test and verification utilities. The functions defined
here are not exported by the main Data.Tree.AVL module. You need to
import this module explicitly if you want to use any of them.

- isBalanced :: AVL e -> Bool
- checkHeight :: AVL e -> Maybe Int
- isSorted :: (e -> e -> Ordering) -> AVL e -> Bool
- isSortedOK :: (e -> e -> Ordering) -> AVL e -> Bool
- type TestTrees = [(Int, [(AVL Int, Int)])]
- allAVL :: TestTrees
- allNonEmptyAVL :: TestTrees
- numTrees :: Int -> Integer
- flatAVL :: Int -> AVL Int
- exhaustiveTest :: (Int -> Int -> AVL Int -> Bool) -> TestTrees -> IO ()
- minElements :: Int -> Integer
- maxElements :: Int -> Integer
- pathTree :: AVL Int

# Correctness checking.

isBalanced :: AVL e -> BoolSource

Verify that a tree is height balanced and that the BF of each node is correct.

Complexity: O(n)

checkHeight :: AVL e -> Maybe IntSource

Verify that a tree is balanced and the BF of each node is correct. Returns (Just height) if so, otherwise Nothing.

Complexity: O(n)

isSorted :: (e -> e -> Ordering) -> AVL e -> BoolSource

Verify that a tree is sorted.

Complexity: O(n)

isSortedOK :: (e -> e -> Ordering) -> AVL e -> BoolSource

Verify that a tree is sorted, height balanced and the BF of each node is correct.

Complexity: O(n)

# Test data generation.

type TestTrees = [(Int, [(AVL Int, Int)])]Source

AVL Tree test data. Each element of a the list is a pair consisting of a height, and list of all possible sorted trees of the same height, paired with their sizes. The elements of each tree of size s are 0..s-1.

allNonEmptyAVL :: TestTreesSource

Same as `allAVL`

, but excluding the empty tree (of height 0).

numTrees :: Int -> IntegerSource

Returns the number of possible AVL trees of a given height.

Behaves as if defined..

numTrees h = (\(_,xs) -> length xs) (allAVL !! h)

and satisfies this recurrence relation..

numTrees 0 = 1 numTrees 1 = 1 numTrees h = (2*(numTrees (h-2)) + (numTrees (h-1))) * (numTrees (h-1))

# Exhaustive tests.

exhaustiveTest :: (Int -> Int -> AVL Int -> Bool) -> TestTrees -> IO ()Source

Apply the test function to each AVL tree in the TestTrees argument, and report progress as test proceeds. The first two arguments of the test function are tree height and size respectively.

# Tree parameter utilities.

minElements :: Int -> IntegerSource

Detetermine the minimum number of elements in an AVL tree of given height. This function satisfies this recurrence relation..

minElements 0 = 0 minElements 1 = 1 minElements h = 1 + minElements (h-1) + minElements (h-2) -- = Some weird expression involving the golden ratio

maxElements :: Int -> IntegerSource

Detetermine the maximum number of elements in an AVL tree of given height. This function satisfies this recurrence relation..

maxElements 0 = 0 maxElements h = 1 + 2 * maxElements (h-1) -- = 2^h-1