Map for FGL

[Adrian Hey]

On Monday 09 Jan 2006 6:28 pm, Adrian Hey wrote:
> I suspect it doesn't compare too well with Data.Tree.AVL, though I've
> never measured it to be honest. It's based on "AVL trees" (or rather
> trees where left and right sub-tree heights differ by at most 1), but
> doesn't seem to use the AVL algorithm itself. IIRC it stores (boxed!)
> height in each tree node, not "balance factor". As well as requiring
> an extra field (same as Adams) this also causes other inefficiencies.
> Insertion requires inspection of nodes which aren't on the insertion
> path to determine the balance factor, which has gotta slow things down.

Oh, and not forgeting that it's lazy (no strict fields of seqs)
anywhere. This may be good thing, but I suspect (for AVL trees at
least) it's a bad thing because of the way height/balance information
propogates up the tree.

Regards
--
Adrian Hey