Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fixing weight-balanced tree in MIT/GNU Scheme and slib
Scheme
branch: master

Fetching latest commit…

Cannot retrieve the latest commit at this time

Failed to load latest commit information.
mit
slib
README

README

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.
Something went wrong with that request. Please try again.