From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,ac39a12d5faf5b14
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2002-04-23 17:17:15 PST
Newsgroups: comp.lang.ada
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!news-out.visi.com!hermes.visi.com!uunet!ash.uu.net!xyzzy!nntp
From: Jeffrey Carter <jeffrey.carter@boeing.com>
Subject: Re: Grace and Maps (was Re: Development process in the Ada community)
X-Nntp-Posting-Host: e246420.msc.az.boeing.com
Content-Type: text/plain; charset=us-ascii
Message-ID: <3CC5F26A.6F74BD0F@boeing.com>
Sender: nntp@news.boeing.com (Boeing NNTP News Access)
Content-Transfer-Encoding: 7bit
Organization: The Boeing Company
X-Accept-Language: en
References: <3CB46975.90408@snafu.de> <3CBAFFEE.2080708@snafu.de>
 <4519e058.0204171036.6f0a7394@posting.google.com> <3CBDD795.4060706@snafu.de>
 <4519e058.0204180800.44fac012@posting.google.com> <3CBF0341.8020406@mail.com>
 <a9n0tk$6fs$1@nh.pace.co.uk>
 <4519e058.0204190529.559a47ae@posting.google.com>
 <a9p98h$8hn$1@nh.pace.co.uk> <3CC1C6B3.6060306@telepath.com>
 <3CC21747.5000501@telepath.com> <V+UgdHreGTJg@eisner.encompasserve.org>
 <x7vr8l871it.fsf@smaug.pushface.org> <4519e058.0204220534.2eb33730@posting.go
 <3CC48F34.5A474E0F@boeing.com> <3CC4C800.10107@telepath.com>
Mime-Version: 1.0
Date: Tue, 23 Apr 2002 23:46:50 GMT
X-Mailer: Mozilla 4.73 [en]C-CCK-MCD Boeing Kit  (WinNT; U)
Xref: archiver1.google.com comp.lang.ada:23024
Date: 2002-04-23T23:46:50+00:00
List-Id: <comp.lang.ada>

Ted Dennison wrote:
> 
> Jeffrey Carter wrote:
> 
> > This is why I use skip lists. They do not waste space, and operations
> > are O(log N) but no rebalancing is needed after modification.
> Hmmm. I'm unfamiliar with skip lists.
> 
> (quick web search ensues)
> 
> It looks like they are probability based, which means that in the worst
> case it could still behave like a linked-list.

Skip lists are probabilistically balanced. Average search times are
O(log N). The good news is that even a halfway decent random-number
generator ensures decent balancing if N is large enough to matter. See
figure 8 in

ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

"Although a skip list may not be balanced, the probability of a skip
list being substantially unbalanced is insignificant. Algorithms for
insertion and deletion in skip lists are simpler and faster than
equivalent algorithms for balanced trees."

-- http://www.cs.umd.edu/~pugh/

Skip lists, like trees and unlike hash tables, provide easy traversal in
sorted order.

-- 
Jeffrey Carter