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