Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!know!zaphod.mps.ohio-state.edu!julius.cs.uiuc.edu!ux1.cso.uiuc.edu!aquinas.csl.uiuc.edu!gooley
From: gooley@aquinas.csl.uiuc.edu (Mark. Gooley)
Newsgroups: comp.theory
Subject: Re: data structures of Tarjan, et.al and actual applications?
Message-ID: <1990Sep26.021208.29411@ux1.cso.uiuc.edu>
Date: 26 Sep 90 02:12:08 GMT
References: <1990Sep23.193541.33486@eagle.wesleyan.edu> <2430@ns-mx.uiowa.edu>
Sender: news@ux1.cso.uiuc.edu (News)
Reply-To: gooley%aquinas@uxc.cso.uiuc.edu (Mark. Gooley)
Organization: University of Illinois at Urbana-Champaign
Lines: 25

In article <2430@ns-mx.uiowa.edu> jones@pyrite.cs.uiowa.edu
(Douglas W. Jones,201H MLH,3193350740,3193382879) writes:
>From article <1990Sep23.193541.33486@eagle.wesleyan.edu>,
>by aliao@eagle.wesleyan.edu:
>
>> Has anyone else been using the data structures that Bob Tarjan, et. al
>> in any actual applications?
>
>Dave Brower of Sun Microsystems transliterated my Pascal version of splay
>trees to C some time ago, and an early version of his transliteration is
>in the Gnu C++ library.  Unfortunately, that version has a bug (it won't
>delete the last item from a tree!) but I gather it's been fairly widely
>used with no complaints (because few people delete randomly in a tree, I
>guess).
>
Yep.  That bug cost me weeks.  In a fit of pique I wrote my own package,
which works quite nicely (though the code looks hideous and I won't swear
that it lacks bugs); however, in my application it turns out that
the speed of the pri-queue isn't terribly important.

Skip lists look interesting (recent article in CACM), and seem about as
fast to me as splay trees, but I haven't had time to compare them closely.

Mark.
gooley@aquinas.csl.uiuc.edu