Data.Tree.AVL.Internals.HJoin
 Portability portable Stability stable Maintainer http://homepages.nildram.co.uk/~ahey/em.png
Description
Functions for joining AVL trees of known height.
Synopsis
 spliceH :: AVL e -> Int# -> e -> AVL e -> Int# -> (#AVL e, Int##) joinH :: AVL e -> Int# -> AVL e -> Int# -> (#AVL e, Int##) joinH' :: AVL e -> Int# -> AVL e -> Int# -> AVL e
Documentation
spliceH :: AVL e -> Int# -> e -> AVL e -> Int# -> (#AVL e, Int##)

Splice two AVL trees of known height using the supplied bridging element. That is, the bridging element appears "in the middle" of the resulting AVL tree. The elements of the first tree argument are to the left of the bridging element and the elements of the second tree are to the right of the bridging element.

This function does not require that the AVL heights are absolutely correct, only that the difference in supplied heights is equal to the difference in actual heights. So it's OK if the input heights both have the same unknown constant offset. (The output height will also have the same constant offset in this case.)

Complexity: O(d), where d is the absolute difference in tree heights.

joinH :: AVL e -> Int# -> AVL e -> Int# -> (#AVL e, Int##)

Join two AVL trees of known height, returning an AVL tree of known height. It's OK if heights are relative (I.E. if they share same fixed offset).

Complexity: O(d), where d is the absolute difference in tree heights.

joinH' :: AVL e -> Int# -> AVL e -> Int# -> AVL e

Join two trees of known height, returning an AVL tree. It's OK if heights are relative (I.E. if they share same fixed offset).

Complexity: O(d), where d is the absolute difference in tree heights.