WSplay is a binary search tree data structure that is based on splay tree algorithm
introduced in . There are some visualizations for splay tree e.g.
WSplay heuristic has been introduced in  and it reduces the amount of
executed splay operations by tracking the working sets in the input.
I.e. splay operations are executed only if the approximated average
of recent access depths is greater than the predefined limit depth.
A logarithmic running time bound for WSplay has been proven in .
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:
All WSplay versions depend on two predefined variables:
- The original version introduced in 
- 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 . 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.
How the variables affect the behaviour of WSplay algorithm? Here are some additional experiment results (not
reported in ) for it. Feel free to use them however you want.
- 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.
 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.
 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)