**C++ implementations** of WSplay algorithms are available here.
The code is implemented with the simple top-down version of splaying.
However the version of splaying can easily be changed. Four different
versions for WSplay are included:

- The original version introduced in [1]
- A similar but more simple version without a provable worst case bound for time usage. However in practice the time usage seems to be same.
- Simple version that is also effectively usable for bottom-up splaying.
- The version used in experiments with randomized splay trees in [1]. This is
the original version with a modification. The version includes dynamic
limit depth which is tuned to execute given
*p*amount of splay operations.

- The discount factor
*d*that defines how much the history of access depths affect the depth counter. - A limit for acceptable depths. Informally accesses deeper than this indicate the need for splaying.

Please contact Timo Aho if you have bug reports or comments either on WSplay or the material on this page. He is also interested to know if you use the WSplay algorithm for any purpose.

[1] Aho, Elomaa, and Kujala (2008): "Reducing Splaying by Taking Advantage of Working Sets",
Proceedings of the 7th International Workshop on
Experimental Algorithms, Provincetown, MA, USA.

Lecture Notes in Computer
Science vol. 5038, Springer Verlag.
Kujala, J.
PDF

[2] Sleator and Tarjan (1985): "Self-adjusting Binary Search Trees",
Journal of the ACM Volume 32, No 3, pp. 652-686. Link to PDF

Last modified: 17.1.2010. (corrected implementation link)