Path: utzoo!attcan!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!ucsd!pacbell.com!pacbell!osc!jgk
From: jgk@osc.COM (Joe Keane)
Newsgroups: comp.theory
Subject: Re: data structures of Tarjan, et.al an
Keywords: splay trees
Message-ID: <3842@osc.COM>
Date: 28 Sep 90 22:49:38 GMT
References: <193541@<1990Sep23> <37800016@m.cs.uiuc.edu>
Reply-To: jgk@osc.COM (Joe Keane)
Organization: Versant Object Technology, Menlo Park, CA
Lines: 6

What we really need is an algorithm that lets you get away with little or no
modification when everything is going well, but keeps the amortized upper
bound of the original splaying algorithm.  Sleator and Tarjan talk about this
in their paper, for example you could do a full splay only when the path
length is greater than some threshold.  However, to my knowledge no one has
come up with a really good way of doing this.