A100624 Cost of traversing complete tree of height n through splaying.

0, 3, 10, 27, 62, 135, 282, 589, 1204, 2437, 4904, 9847, 19734, 39511, 79066, 158187, 316430, 632919, 1265898, 2531865, 5063800, 10127673, 20255420, 40510931

Offset

0,2

Comments

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

Links

Table of n, a(n) for n=0..23.

Colm O Dunlaing (odunlain(AT)maths.tcd.ie), Inorder Traversal of Splay Trees.

Crossrefs

Cf. A100625.

Sequence in context: A105660 A056681 A192959 * A320586 A088809 A364534

Adjacent sequences: A100621 A100622 A100623 * A100625 A100626 A100627

Keyword

nonn

Author

N. J. A. Sloane, Dec 04 2004

Status

approved