Path: utzoo!attcan!uunet!ns-mx!pyrite.cs.uiowa.edu
From: jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879)
Newsgroups: comp.theory
Subject: Re: data structures of Tarjan, et.al an
Message-ID: <2453@ns-mx.uiowa.edu>
Date: 27 Sep 90 17:10:30 GMT
References: <37800016@m.cs.uiuc.edu>
Sender: news@ns-mx.uiowa.edu
Lines: 24

From article <37800016@m.cs.uiuc.edu>, by gillies@m.cs.uiuc.edu:
> 
> Has anyone written a splay that is faster?  I suspect the splays just
> posted are not as fast.  However, my splay is just a benchmark and
> does not contain the all trivial amenities (like delete() or join()).

It is easy to delete the delete() and join() operations from my Pascal
code or Brower's C code.  Just delete the uplink field from each node
in the data structure, and delete every statement in the code containing
a reference to this field.  This breaks the bottom-up splay procedure,
and all procedures depending on bottom-up splaying, but it leaves the
basic top-down splay procedures fully operational (and faster!), allowing
a fair comparison with your code.

On a side issue, splay trees are particularly well suited to use as priority
queues because of the way they unbalance when half of the operations are
delete-min (or get-next in discrete-event simulation).  Each delete-min
operation shortens the leftmost branch of the tree by roughly a factor
of two, with the result that, on average, this path is of constant length
independent of the tree size.  Thus, you get O(1) time for delete-min and
O(log n) time for insert (all bounds are amortized).

					Doug Jones
					jones@herky.cs.uiowa.edu