A coefficient related to splay-to-root traversal, correct to thousands of decimal places

Colm Ó Dúnlaing

This paper takes another look at the cost of traversing a binary tree using repeated splay-to-root. This was shown to cost $O(n)$ (in rotations) by Tarjan and later, in different w…