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.

BibTeX

@InProceedings{BST_SODA2009,
  AUTHOR        = {Erik D. Demaine and Dion Harmon and John Iacono and
                   Daniel Kane and Mihai P\v{a}tra\c{s}cu},
  TITLE         = {The Geometry of Binary Search Trees},
  BOOKTITLE     = {Proceedings of the 20th Annual ACM-SIAM Symposium on
                   Discrete Algorithms (SODA 2009)},
  bookurl       = {http://www.siam.org/meetings/da09/},
  ADDRESS       = {New York, New York},
  MONTH         = {January 4--6},
  YEAR          = 2009,
  PAGES         = {496--505},

  withstudent   = 1,
  length        = {10 pages},
  doi           = {https://dx.doi.org/10.1137/1.9781611973068.55},
  dblp          = {https://dblp.org/rec/conf/soda/DemaineHIKP09},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1137/1.9781611973068.55">SIAM</A>.},
}

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:

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 [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.

Comments:

This paper is also available from SIAM.

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]