login
Cost of traversing complete tree of height n through splaying.
2

%I #3 Mar 30 2012 16:50:06

%S 0,3,10,27,62,135,282,589,1204,2437,4904,9847,19734,39511,79066,

%T 158187,316430,632919,1265898,2531865,5063800,10127673,20255420,

%U 40510931

%N Cost of traversing complete tree of height n through splaying.

%C It would be nice to have a formula or recurrence. These numbers were computed by brute force.

%H Colm O Dunlaing (odunlain(AT)maths.tcd.ie), <a href="http://citeseer.ist.psu.edu/650738.html">Inorder Traversal of Splay Trees</a>.

%Y Cf. A100625.

%K nonn

%O 0,2

%A _N. J. A. Sloane_, Dec 04 2004