@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",

}