Twists, turns, cascades, deque conjecture, and scanning theorem
Rajamani Sundar · 1989
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.>