@inproceedings{de2fc9d63ff54e69b34ea1d269e10eba,
title = "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.",
author = "Demaine, {Erik D.} and Dion Harmon and John Iacono and Daniel Kane and Mihai Pǎtra{\c s}cu",
year = "2009",
doi = "10.1137/1.9781611973068.55",
language = "English (US)",
isbn = "9780898716801",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Association for Computing Machinery (ACM)",
pages = "496--505",
booktitle = "Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms",
address = "United States",
note = "20th Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 04-01-2009 Through 06-01-2009",
}