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