Randomized splay trees

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.