Title :
Twists, turns, cascades, deque conjecture, and scanning theorem
Author :
Sundar, Rajamani
Author_Institution :
Courant Inst., New York Univ., NY, USA
fDate :
30 Oct-1 Nov 1989
Abstract :
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
Keywords :
search problems; trees (mathematics); binary tree; cascades; deque conjecture; inverse Ackerman bound; scanning theorem; splay tree; turns; Binary search trees; Binary trees; Costs; Dictionaries; Upper bound;
Conference_Titel :
Foundations of Computer Science, 1989., 30th Annual Symposium on
Conference_Location :
Research Triangle Park, NC
Print_ISBN :
0-8186-1982-1
DOI :
10.1109/SFCS.1989.63534