Paper by Erik D. Demaine

Reference:
Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, and Mihai Pǎtraşcu, “The Geometry of Binary Search Trees”, in Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York, New York, January 4–6, 2009, pages 496–505.

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.

Length:
The paper is 10 pages.

Availability:
The paper is available in PostScript (1031k), gzipped PostScript (161k), and PDF (492k).
See information on file formats.
[Google Scholar search]


See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated July 25, 2017 by Erik Demaine.