Bug in Data.Map
twhitehead at gmail.com
Wed Aug 4 13:57:24 EDT 2010
On August 4, 2010 05:33:15 Milan Straka wrote:
> If the rebalancing is done in the case of broken balance, ie. in
> sizeR > delta*sizeL, there is a simple counterexample (you will need
> fixed-width font):
> 2 (A)
> 1 5
> 4 6
> 3 7
> and delete 1.
Urk. I see where the problem is. The first equation on page 27 gives the
state of things once they are out of balance in conjunction with Fig 6.
n + alpha n + 1 = wx + 1
In other words, an element has been added to the right side (containing n +
alpha n + 1) items so it now contains one more item than w times the x items
on the left side. The equalities and such that follow ensure a re-balance
will always fix this situation.
What they don't show, however, is what happens if things get out of balance in
by deleting an item from the left-hand side. In this case, the right side can
windup exceed the left by anywhere up to w times (i.e., as in your example).
The required fix is to redo all the inequalities using
n + alpha n + 1 = wx + e,
for e = 1, 2, ..., w (in most cases only e = w will also need checking).
PS: In short, unless I'm missing something, Adam only gave a proof/conditions
for insertion. The deletion case still needs to be done.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Size: 198 bytes
Desc: This is a digitally signed message part.
Url : http://www.haskell.org/pipermail/libraries/attachments/20100804/ab622b5d/attachment.bin
More information about the Libraries