A simple bound for sequential access in splay trees

Source: https://www.maths.tcd.ie/report_series/abstracts/tcdm0724.html Parent: https://www.maths.tcd.ie/research/papers/

A simple bound for sequential access in splay trees

This note improves upon an earlier analysis of the author's. Using methods from that paper, we give a different proof that the cost of traversing a binary tree by repeated splay-to-root is O(n), a result originally due to Tarjan.