wilson@uicbert.eecs.uic.edu (Paul Wilson) (05/21/91)
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