The geometry of binary search trees

ABSTRACT

We present a novel connection between binary search trees (BSTs) and points in the plane satisfying a simple property. Using this correspondence, we achieve the following results:

1. A surprisingly clean restatement in geometric terms of many results and conjectures relating to BSTs and dynamic optimality.

2. A new lower bound for searching in the BST model, which subsumes the previous two known bounds of Wilber [FOCS'86].

3. The first proposal for dynamic optimality not based on splay trees. A natural greedy but offline algorithm was presented by Lucas [1988], and independently by Munro [2000], and was conjectured to be an (additive) approximation of the best binary search tree. We show that there exists an equal-cost online algorithm, transforming the conjecture of Lucas and Munro into the conjecture that the greedy algorithm is dynamically optimal.

REFERENCES

• 1: Mihai Bdoiu , Richard Cole , Erik D. Demaine , John Iacono, A unified access bound on comparison-based dynamic dictionaries, Theoretical Computer Science, v.382 n.2, p.86-96, August, 2007 [doi>10.1016/j.tcs.2007.03.002]
• 2: Richard Cole , Bud Mishra , Jeanette Schmidt , Alan Siegel, On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences, SIAM Journal on Computing, v.30 n.1, p.1-43, 2000 [doi>10.1137/S0097539797326988]
• 3: Richard Cole, On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof, SIAM Journal on Computing, v.30 n.1, p.44-85, 2000 [doi>10.1137/S009753979732699X]
• 4: Erik D. Demaine , Dion Harmon , John Iacono , Mihai Paˇtras¸cu, Dynamic Optimality—Almost, SIAM Journal on Computing, v.37 n.1, p.240-251, April 2007 [doi>10.1137/S0097539705447347]
• 5: {DSW05} J. Derryberry, D. D. Sleator, and C. C. Wang. A lower bound framework for binary search trees with rotations. Tech. Rep. CMU-CS-05-187, Carnegie Mellon University, 2005.
• 6: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Journal of Computer and System Sciences, v.66 n.4, p.614-656, 1 June 2003 [doi>10.1016/S0022-0000(03)00026-6]
• 7: Dion Harmon , Erik Demaine, New bounds on optimal binary search trees, Massachusetts Institute of Technology, Cambridge, MA, 2006
• 8: John Iacono, Alternatives to splay trees with O(log n) worst-case access times, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.516-522, January 07-09, 2001, Washington, D.C., United States
• 9: {Iac05J} J. Iacono. Key-independent optimality. Algorithmica, 42(1):3--10, 2005.
• 10: {Knu71} D. E. Knuth. Optimum binary search trees. Acta Informatica, 1:14--25, 1971.
• 11: {Luc88} J. M. Lucas. Canonical forms for competitive binary search tree algorithms. Tech. Rep. DCS-TR-250, Rutgers University, 1988.
• 12: J. Ian Munro, On the Competitiveness of Linear Search, Proceedings of the 8th Annual European Symposium on Algorithms, p.338-345, September 05-08, 2000
• 13: Seth Pettie, Splay trees, Davenport-Schinzel sequences, and the deque conjecture, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1115-1124, January 20-22, 2008, San Francisco, California
• 14: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 15: D D Sleator , R E Tarjan , W P Thurston, Rotation distance, triangulations, and hyperbolic geometry, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.122-135, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12143]
• 16: {Sun92} R. Sundar. On the deque conjecture for the splay algorithm. Combinatorica, 12(1):95--124, 1992.
• 17: R E Tarjan, Sequential access in splay trees takes linear time, Combinatorica, v.5 n.4, p.367-378, Sept. 1985 [doi>10.1007/BF02579253]
• 18: Chengwen Chris Wang , Jonathan Derryberry , Daniel Dominic Sleator, O(log log n)-competitive dynamic binary search trees, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.374-383, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109600]
• 19: R. Wilber, Lower bounds for accessing binary search trees with rotations, SIAM Journal on Computing, v.18 n.1, p.56-67, Feb. 1989 [doi>10.1137/0218004]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies