186 citations · 243 across the 28 of their papers we have counts for
Showing 2019 · cs.DSShow all
2 papers · 2 filters
cs.DS2019
Splaying Preorders and Postorders
Caleb C. Levy, Robert E. Tarjan
Let 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…
cs.DS2019
A Foundation for Proving Splay is Dynamically Optimal
Caleb C. Levy, Robert E. Tarjan
Consider the task of performing a sequence of searches in a binary search tree. After each search, we allow an algorithm to arbitrarily restructure the tree. The cost of executing…