It has been proven that splay tree satisfies several other weaker properties. One important example of these properties is called “static optimality” which states that the cost of splay tree for accessing any access sequence is at most constant factor away from the cost of every static BST algorithm, that cannot rearrange a tree after each access. The original proof [Sleator Tarjan JACM'85] is via a so-called “sum-of-logs” potential function. Though the proof is very elegant and easy to verify, it is not clear why it works and how to come up with such potential function.
We give an arguably simpler proof of static optimality for splay tree via a new potential function called MinDepth. It is straightforward and combinatorial. We believe that this proof is a nice material for teaching in data structure classes.