Newsgroups: comp.lang.scheme
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!sdd.hp.com!elroy.jpl.nasa.gov!decwrl!parc!cutting
From: cutting@parc.xerox.com (Doug Cutting)
Subject: Re: looking for balancing (binary/avl) tree programs
In-Reply-To: ok@goanna.cs.rmit.oz.au's message of 21 May 91 10:38:45 GMT
Message-ID: <CUTTING.91May21105843@skye.parc.xerox.com>
Sender: news@parc.xerox.com
Organization: Xerox PARC, Palo Alto, CA
References: <1991May20.150025.16099@uicbert.eecs.uic.edu>
	<CUTTING.91May20211202@kolsaas.parc.xerox.com>
	<5877@goanna.cs.rmit.oz.au>
Distribution: comp
Date: 21 May 91 10:58:43

In article <5877@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
> 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)).

This is certainly the wrong group for this discussion.  Sorry.

I've not seen these C skip-lists and I've never seen clean AVL code.
As for the number of comparisons, Pugh's 'Skip List Cookbook'
describes a simple technique which mends this problem.  And as for the
worst case behaviour, it can only be achieved if your random number
generator delivers the same value N consecutive times -- a very
unlikely event which is completely independent of the objects stored.

C & Pascal code and the 'Skip List Cookbook' can be found in
mimsy.umd.edu:pub/skipLists.

I'm not the designer of skip lists, just a happy implementor & user.

	Doug