Bug in Data.Map
Tyson Whitehead
twhitehead at gmail.com
Wed Aug 4 12:51:49 EDT 2010
On August 4, 2010 05:33:15 Milan Straka wrote:
> I am able to proof that for delta >= 5 the construction fails.
> I also think I am able to proof that for delta = 4 the construction
> works.
I guess it depends on what value you are using for the ratio (1/alpha in Adams
paper), but if you are using the standard ratio = 2 (alpha = 1/2), then delta
= 4 (w = 4 in Adams paper) violates the
alpha >= (2w+1)/(w^2-1)
#3 single rotation constraint (page 27).
It is actually a simplification of the full constraint, however, which was
alpha >= (wn+w+n)/(n(w^2-1)).
The key is then to realize that this is only violated when n = 1 for alpha =
1/2 and w = 4, and that this cannot actually occur in his Fig 6. diagram. It
would require a right-right tree with 1/2 items. For n = 2 and above you are
okay, so it would seem at least single rotations are guaranteed to work.
Actually, I was surprised to hear about the w = 5 case as when I last
implemented this (for a different language) I went over all the math (due to
the comment in the Haskell code). Despite not agreeing with all his double
rotation simplifications, I also got that alpha = 1/2 and w = 5 were okay.
I'll have to take a closer look when I get more time.
Cheers! -Tyson
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part.
Url : http://www.haskell.org/pipermail/libraries/attachments/20100804/70acc3ce/attachment.bin
More information about the Libraries
mailing list