Randomized splay trees

Research output: Contribution to conferencePaperpeer-review

19 Scopus citations


The performance of the original version of the splay tree algorithm has been unchallenged for over a decade. We propose three randomized versions with better upper bounds on the expected running times (by constant factors). The improvements are particularly strong if the number of insertions is relatively small. All expectations are taken over the coin tosses of the randomized algorithms for worst case inputs. Hence slow running times are very unlikely for any request sequence. Algorithm A improves the expected running time, but could be very slow (with tiny probability). Algorithm B shows that without any loss in the original amortized running time, the expected running time can still be improved by a constant percentage. Algorithm C has the same efficient expected running time as Algorithm A, while its (worst case) amortized running time deteriorates only by a constant factor compared to standard deterministic splaying.

Original languageEnglish (US)
StatePublished - Jan 1 1999
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
Duration: Jan 17 1999Jan 19 1999


OtherProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
CityBaltimore, MD, USA

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


Dive into the research topics of 'Randomized splay trees'. Together they form a unique fingerprint.

Cite this