Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!uwm.edu!linac!att!ucbvax!bloom-beacon!dont-send-mail-to-path-lines
From: cph@altdorf.ai.mit.EDU (Chris Hanson)
Newsgroups: comp.lang.scheme
Subject: looking for balancing (binary/avl) tree programs
Message-ID: <9105210031.aa21207@mc.lcs.mit.edu>
Date: 21 May 91 04:29:58 GMT
References: <5863@goanna.cs.rmit.oz.au>
Sender: daemon@athena.mit.edu (Mr Background)
Organization: The Internet
Lines: 36


   Date: 21 May 91 01:43:27 GMT
   From: "Richard A. O'Keefe" <ok@goanna.cs.rmit.oz.au>

   In article <MARKF.91May20135551@montreux.ai.mit.edu>, markf@zurich.ai.mit.edu (Mark Friedman) writes:
   > I have placed pub/btree.scm on altdorf.ai.mit.edu available for
   > anonymous FTP. Chris Hanson wrote it (based on Knuth). I believe that
   > it is vanilla Scheme, except for some DEFINE-INTEGRABLE's that you may
   > feel free to change to DEFINE's.

   The thing that really worries me is that the last line of the file that
   I picked up was incomplete.  It read
   "          (case-3)))))"
   (minus the quotes), and the file just *stopped* at that point without
   even the LF that one expects to terminate every line.  Is anything more
   than the LF missing?

There's nothing else missing.  I never add a final newline to a Scheme
source file, because Scheme doesn't require it.  I refuse to give in
to the short-sighted unix designers who have decided that every file
should end in a newline.

   Is there some documentation for this file?  What is "wrapping" and
   "unwrapping" a key about?  Not having a copy of Knuth V3 handy, what
   is the method used here?  It looks as though it might be AVL, but
   there seems to be too much code for it to be that.

There's no documentation.  This is an implementation of balanced
binary trees -- the tree is rebalanced on each insertion or deletion.
I have never read the papers on AVL trees, but my naive understanding
is that the AVL algorithm is more sophisticated than this one.

WRAP-KEY and UNWRAP-KEY allow the objects stored in the tree to be
compound objects that contain the key as one of their components.
Alternatively you could build the functionality of UNWRAP-KEY into the
< predicate, in which case the wrapping wouldn't be needed.