Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!sdd.hp.com!spool.mu.edu!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.scheme
Subject: Re: looking for balancing (binary/avl) tree programs
Message-ID: <5877@goanna.cs.rmit.oz.au>
Date: 21 May 91 10:38:45 GMT
Article-I.D.: goanna.5877
References: <1991May20.150025.16099@uicbert.eecs.uic.edu> <CUTTING.91May20211202@kolsaas.parc.xerox.com>
Distribution: comp
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 46

In article <CUTTING.91May20211202@kolsaas.parc.xerox.com>, cutting@parc.xerox.com (Doug Cutting) writes:
> In article <1991May20.150025.16099@uicbert.eecs.uic.edu> lam@uicbert.eecs.uic.edu (Michael Lam) writes:
> FYI, Skip lists are an attractive alternative to balanced trees.  The
> order of the various operations is similar (log insert & delete,
> linear enumeration) but the constant factors (space & time) tend to be
> lower and the implementation is *much* simpler.  They're described in
> the June 1990 CACM (v33#6) pp668-680.

I've not seen that CACM issue.  I _have_ seen two implementations of
skip lists in "The C Users' Journal".  Compared with a clean AVL code,
the code looked amazingly complicated.  Maybe that was just their
style.  I was not charmed by the statement that skip lists do on the
average twice as many comparisons as balanced trees, and I was not
charmed by the worst-case behaviour (O(N), not O(lgN)).

A node in a skip list has to hold the key (and any satellite information),
a randomly selected number of pointer fields, averaging 1.35ish, and a
number which tells you how many pointers there are.  In C, this would be
	struct foo { key_type the_key; short n; struct foo ptrs[n]; }
if only that were legal.  In Lisp you might use
	#(key ptr-1 ... ptr-n)
for a skip-list node with n pointers.  Now the space cost depends on
how vectors are implemented.  A possible implementation would take n+2
words for such a vector.  I'm not quite sure of the best way to encode
an AVL tree node in Lisp; in Prolog <bal>(Key,L,R) would do it,
e.g. <(K,L,R), =(K,L,R), or >(K,L,R), for a cost of 4 cells per node.
A similar approach in Lisp might use one of three record types, again
for a cost of 4 cells per node.  Compare then a cost of 4 cells per node
for a data structure with *guaranteed* logarithmic performance with an
average of 3.35 cells per node for a data structure with linear worst case.

Is a (average) constant factor of 3.35 really such a huge improvement
over 4?  Depending on how your Lisp implements structs and vectors,
skip-list nodes might _always_ be _bigger_ than AVL nodes!
There doesn't seem to be any time saving either; scanning a balanced
tree can be done iteratively:
	(let loop ((n (top-of-tree)))
	    (if (null? n)
		(not-found)
		(case (compare key n)
		    ((=) (found n))
		    ((<) (loop (left-son n)))
		    ((>) (loop (right-son n))))))
This is a lot simpler than the code for scanning a skip-list!
-- 
There is no such thing as a balanced ecology; ecosystems are chaotic.