Paper by Erik D. Demaine
- 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.
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:
- A surprisingly clean restatement in geometric terms of many
results and conjectures relating to BSTs and dynamic optimality.
- A new lower bound for searching in the BST model, which subsumes
the previous two known bounds of Wilber [FOCS'86].
- The first proposal for dynamic optimality not based on splay trees.
A natural greedy but offline algorithm was presented by Lucas ,
and independently by Munro , 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.
- The paper is 10 pages.
- 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
Last updated January 8, 2018 by