Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!apple!snorkelwacker!mit-eddie!uw-beaver!uw-june!pattis
From: pattis@cs.washington.edu (Richard Pattis)
Newsgroups: comp.theory
Subject: Re: data structures of Tarjan, et.al and actual applications?
Summary: A quicky comparison of Skip lists and Splay trees
Message-ID: <13134@june.cs.washington.edu>
Date: 26 Sep 90 03:20:09 GMT
References: <1990Sep23.193541.33486@eagle.wesleyan.edu> <2430@ns-mx.uiowa.edu> <1990Sep26.021208.29411@ux1.cso.uiuc.edu>
Organization: U of Washington, Computer Science, Seattle
Lines: 12

I recently implemented Skip lists and Splay trees as generic packages in
Ada.  Using Meridian's AdaVantage compiler, I get about 50% better
performance using Splay trees (insert 1000 random integers, locate and
delete each one).   I haven't spent time optimizing either: I just translated
the code from Pugh's article (June 90 CACM) and Williams's article (Computer
Language, September 1990).

BTW, Williams,'s code also has the bug of not being able to delete the last
element in a tree: changing r->up on the top of page 56 should be prefaced
by checking that r is not 0.

Rich Pattis