| Portability | portable |
|---|---|
| Stability | stable |
| Maintainer | http://homepages.nildram.co.uk/~ahey/em.png |
Data.Tree.AVL.Join
Contents
Description
Functions for joining AVL trees.
Joining trees.
join :: AVL e -> AVL e -> AVL eSource
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 eSource
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 eSource
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.