WSplay is a binary search tree data structure that is based on splay tree algorithm introduced in [2]. There are some visualizations for splay tree e.g. here and here. WSplay heuristic has been introduced in [1] 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 [1].

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:

  1. The original version introduced in [1]
  2. 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.
  3. Simple version that is also effectively usable for bottom-up splaying.
  4. 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.
All WSplay versions depend on two predefined variables:
  1. The discount factor d that defines how much the history of access depths affect the depth counter.
  2. A limit for acceptable depths. Informally accesses deeper than this indicate the need for splaying.
How the variables affect the behaviour of WSplay algorithm? Here are some additional experiment results (not reported in [1]) for it. Feel free to use them however you want.

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)