Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2000 Copyright 2000 Universität Bonn, Institut für Informatik, Abt. V

Randomized Splay Trees: Theoretical and Experimental Results
Susanne Albers and Marek Karpinski
[Download PostScript] [Download PDF]

Splay trees are self-organizing binary search trees that were introduced by Sleator and Tarjan [12]. In this paper we present a randomized variant of these trees. The new algorithm for reorganizing the tree is both simple and easy to implement. We prove that our randomized splaying scheme has the same asymptotic performance as the original deterministic scheme but improves constants in the expected running time. This is interesting in practice because the search time in splay trees is typically higher than the search time in skip lists and AVL-trees. We present a detailed experimental study of our algorithm. On request sequences generated by fixed probability distributions, we can achieve improvements of up to 25% over deterministic splaying. On request sequences that exhibit high locality of reference, the improvements are minor.

Last Change: 07/16/02 at 15:23:34
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope