[Bug-mit-scheme] Re: Bugs of wttree.scm on deletion.

[Taylor R Campbell]

   Date: Fri, 03 Dec 2010 05:28:52 +0000
   From: Kazu Yamamoto <address@hidden>

   "wttree.scm" has a bug on the delete operation. In
   some cases, the delete operation on a given balanced tree breaks its
   balance.

   More concrete information, fix, and tests are available at:

   https://github.com/kazu-yamamoto/wttree

   Please give a look.

Heh -- I believe I was the one who originally found this problem,
while writing <http://mumble.net/~campbell/scheme/bb-tree.scm> and
testing it with <http://mumble.net/~campbell/scheme/test-bb-tree.scm>.
I noticed this about a year ago, but never got around to finding the
error in Adams' paper or to fixing wttree.scm -- I think I planned to
replace it by bb-tree.scm, which has a number of advantages other than
using parameters that I wasn't able to break.  I'm glad to see that
someone has finally gone through the math.  Thanks!