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

Stability | stable |

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

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.