Splay Operations

Recall that inserts, deletes, and finds in a splay tree all consist of some number of splay operations (moving a node to the root) and a constant amount of pointer diddling.

We will show that splay operations have $O(\log n)$ amortized time and it will follow that a sequence of n inserts and deletes on an initially empty tree takes $O(\log n)$ per operation.

Like a balanced tree, but not!