quixote@ATHENA.MIT.EDU (07/31/90)
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