Haskell Hierarchical Libraries (collections package)ContentsIndex
Data.Tree.AVL.Join
Portabilityportable
Stabilitystable
Maintainerhttp://homepages.nildram.co.uk/~ahey/em.png
Contents
Joining trees.
Description
Functions for joining AVL trees.
Synopsis
join :: AVL e -> AVL e -> AVL e
concatAVL :: [AVL e] -> AVL e
flatConcat :: [AVL e] -> AVL e
Joining trees.
join :: AVL e -> AVL e -> AVL e

Join two AVL trees. This is the AVL equivalent of (++).

 asListL (l `join` r) = asListL l ++ asListL r

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

concatAVL :: [AVL e] -> AVL e

Concatenate a finite list of AVL trees. During construction of the resulting tree the input list is consumed lazily, but it will be consumed entirely before the result is returned.

 asListL (concatAVL avls) = concatMap asListL avls

Complexity: Umm..Dunno. Uses a divide and conquer approach to splice adjacent pairs of trees in the list recursively, until only one tree remains. The complexity of each splice is proportional to the difference in tree heights.

flatConcat :: [AVL e] -> AVL e

Similar to concatAVL, except the resulting tree is flat. This function evaluates the entire list of trees before constructing the result.

Complexity: O(n), where n is the total number of elements in the resulting tree.

Produced by Haddock version 0.7