Path: utzoo!attcan!uunet!tut.cis.ohio-state.edu!ucbvax!ATHENA.MIT.EDU!quixote
From: quixote@ATHENA.MIT.EDU
Newsgroups: comp.theory
Subject: Splay Trees
Message-ID: <9007271827.AA10942@E40-008-5.MIT.EDU>
Date: 30 Jul 90 18:13:13 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: quixote%athena.mit.edu@VM1.NoDak.EDU
Lines: 9

Is anyone familiar with a proof that top-down splaying satisfies the
same amortized log n time bound as bottom-up?  There is one in Erkki
Makinen's "On Top-Down Splaying" (BIT 27 (1987) 330-339), but I am
looking for alternative approaches. (Makinen proves that top-down
splaying effectively gives the same result as bottom-up).  In fact, if
anyone can recommend recent articles/references on self-adjusting tree
structures, I would be most grateful.

-- Daniel Tunkelang