  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 the task is the sum of the time spent searching and
the time spent optimizing the searches with restructuring operations. Sleator
and Tarjan introduced this notion in 1985, along with an algorithm and a
conjecture. The algorithm, Splay, is an elegant procedure for performing
adjustments that move searched items to the top of the tree. The conjecture,
called dynamic optimality, is that the cost of splaying is always within a
constant factor of the optimal algorithm for performing searches. We lay a
foundation for proving the dynamic optimality conjecture. Central to our method
is approximate monotonicity. Approximately monotone algorithms are those whose
cost does not increase by more than a fixed multiple after removing searches
from the sequence. As we shall see, Splay is dynamically optimal if and only if
it is approximately monotone. This result extends to a weaker form of
approximate monotonicity as well as insertion, deletion, and related
algorithms. We prove that a lower bound on optimal execution cost is
approximately monotone and outline how to adapt this proof from the lower bound
to Splay, and how to overcome the remaining barriers to establishing dynamic
optimality.
