[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Bug-mit-scheme] Re: Bugs of wttree.scm on deletion.
From: |
Taylor R Campbell |
Subject: |
[Bug-mit-scheme] Re: Bugs of wttree.scm on deletion. |
Date: |
Fri, 3 Dec 2010 06:04:03 +0000 |
User-agent: |
IMAIL/1.21; Edwin/3.116; MIT-Scheme/9.0.1 |
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!
- [Bug-mit-scheme] Re: Bugs of wttree.scm on deletion.,
Taylor R Campbell <=