Splaying Preorders and Postorders

Caleb C. Levy, Robert E. Tarjan

Let $T$ be a binary search tree. We prove two results about the behavior of the Splay algorithm (Sleator and Tarjan 1985). Our first result is that inserting keys into an empty bin…