Xref: utzoo comp.lang.lisp:4912 comp.lang.scheme:2529 comp.sources.wanted:16749
Newsgroups: comp.lang.lisp,comp.lang.scheme,comp.sources.wanted
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!sdd.hp.com!news.cs.indiana.edu!ux1.cso.uiuc.edu!uicbert.eecs.uic.edu!wilson
From: wilson@uicbert.eecs.uic.edu (Paul Wilson)
Subject: balanced tree routines in Scheme/LISP
Message-ID: <1991May20.201244.21948@uicbert.eecs.uic.edu>
Summary: looking for balanced tree routines in Scheme or LISP
Keywords: self-balancing, trees, source code, Scheme, LISP, indexing
Organization: University of Illinois at Chicago
Date: Mon, 20 May 91 20:12:44 GMT
Lines: 34


I'm looking for code that manipulates trees efficiently.  In particular,
something like self-balancing binary trees, written in something like
Scheme.

Ideally, I'd like Scheme code for trees that are self-balancing, but which
don't rebalance too quickly.  (That is, they allow a bounded amount of
unbalancedness, and rebalance now and then, to reduce amortized cost.  I
would like something that would deal well with millions of insertions,
preferably even insertions in key order.)

Lisp code would be okay if it's written in some fairly generic dialect
of Lisp -- I'll have to translate it to Scheme.


In case you're wondering, I want to translate the SUN engineering
database benchmark into Scheme, so I can use it as a scalable GC 
benchmark -- to see how well gc's deal with huge amounts of 
long-lived data.  (I want the tree routines for indexing large
collections of objects in the heap.)


   -- Paul


Paul R. Wilson                                  lab ph.: (312) 996-9216
Interactive Computing Environments (ICE) Lab.   FAX no.: (312) 413-0024
U. of Ill. at Chicago EECS Dept. (M/C 154)      wilson@bert.eecs.uic.edu
P.O. Box 4348   Chicago,IL 60680
-- 
Paul R. Wilson                                  lab ph.: (312) 996-9216
Interactive Computing Environments (ICE) Lab.   FAX no.: (312) 413-0024
U. of Ill. at Chicago EECS Dept. (M/C 154)      wilson@bert.eecs.uic.edu
P.O. Box 4348   Chicago,IL 60680