Twists, turns, cascades, deque conjecture, and scanning theorem

Nearly tight upper and lower bounds on the maximum number of various rotational operations that can be performed on a binary tree are proved. One of the lower bound results refutes D.E. Sleator´s turn conjecture for binary trees (see R.E. Tarjan, SIAM J. Alg. Disc. Meth., vol.2, p.306-318, 1985). The upper bound results are used to derive an inverse Ackerman bound for Tarjan´s deque conjecture on the performance of the splay tree. Two new proofs of Tarjan´s scanning theorem are provided. One proof generalizes the theorem, whereas the other is a simple, potential-based proof