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]