The geometry of binary search trees

Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, Mihai Pǎtraşcu

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms
    PublisherAssociation for Computing Machinery (ACM)
    Number of pages10
    ISBN (Print)9780898716801
    StatePublished - 2009
    Event20th Annual ACM-SIAM Symposium on Discrete Algorithms - New York, NY, United States
    Duration: Jan 4 2009Jan 6 2009

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


    Other20th Annual ACM-SIAM Symposium on Discrete Algorithms
    Country/TerritoryUnited States
    CityNew York, NY

    ASJC Scopus subject areas

    • Software
    • General Mathematics


    Dive into the research topics of 'The geometry of binary search trees'. Together they form a unique fingerprint.

    Cite this