This package aims to fix the bugs of "wttree.scm" of "MIT/GNU Scheme" v9.0.1 and "slib" v3b3.

"wttree.scm" is a finite map (key-value store) which also provides set operations. It is based on "weight balanced trees", a variant of binary search trees.

The original weight balanced tree is invested by Nievergelt and Reingold in 1972. Its weight is "size + 1". The balance algorithm has two parameters, delta and gamma. They defined (delta,gamma) = (1 + sprt 2, sqrt 2). This algorithm and this parameter does not have bugs. That is, the balance of a tree is always maintained. However, since these parameter are not integer, implementation cost is high.

Nievergelt J. and Reingold E.M.,
"Binary search trees of bounded balance",
Proceedings of the fourth annual ACM symposium on Theory of computing,
pp 137--142,
1972

In 1992, Adams created a variant of weight balanced tree. Its weight is purely "size". He defined (delta,gamma) = (3 or larger, 1). The pair (delta,gamma) of "wttree.scm" is (5,1). They are all buggy. In some cases, the delete operation on a given balanced tree breaks its balance. To our tests, only (3,2) and (4,2) are valid. But we cannot prove it mathematically.

Adams S.,
Implementing sets efficiently in a functional language,
Technical Report CSTR 92-10,
University of Southampton,
1992

Adams S.,
Efficient sets: a balancing act,
Journal of Functional Programming,
Vol 3, No 4, pp 553--562,
1993

http://www.swiss.ai.mit.edu/~adams/BB/

We (Mr. Hirai and me) mathematically proved in Coq that (3,2) is one and only one interger solution for the original weight balanced tree (not Adams's one).

THIS IS A DRAFT

Yoichi Hirai and Kazuhiko Yamamoto,
"Balance Condition on Weight-Balanced Trees",
submitted to Journal of Functional Programming,
2010

http://hagi.is.s.u-tokyo.ac.jp/~yh/bst.pdf
http://hagi.is.s.u-tokyo.ac.jp/~yh/Balance.v

To fix "wttree.scm", we should translate the definition of weight from "size" to "size + 1" and change the parameters from (5,1) to (3,2).

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

For slib:

Gauche is required as Scheme implementation.

% cd slib
;; To run tests for the new "wttree.scm"
% make
;; All property tests are passed.

;; To run test for the old "wttree.scm"
% make old
;; Some property tests are failed.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

For MIT/GNU Scheme:

MIT/GNU Scheme is required as Scheme implementation.

% cd mit
;; To run tests for the new "wttree.scm"
% make
;; All property tests are passed.

;; To run test for the old "wttree.scm"
% make old
;; Some property tests are failed.