Weighted dynamic finger in binary search trees

John Iacono, Stefan Langerman

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

    Abstract

    It is shown that the online binary search tree data structure GreedyASS performs asymptotically as well on a sufficiently long sequence of searches as any static binary search tree where each search begins from the previous search (rather than the root). This bound is known to be equivalent to assigning each item i in the search tree a positive weight wi and bounding the search cost of an item in the search sequence si,..., sm (Equation presented) This result is the strongest finger-type bound to be proven for binary search trees. By setting the weights to be equal, one observes that our bound implies the dynamic finger bound. Compared to the previous proof of the dynamic finger bound for Splay trees, our result is significantly shorter, stronger, simpler, and has reasonable constants.

    Original languageEnglish (US)
    Title of host publication27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
    EditorsRobert Krauthgamer
    PublisherAssociation for Computing Machinery
    Pages672-691
    Number of pages20
    ISBN (Electronic)9781510819672
    DOIs
    StatePublished - 2016
    Event27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 - Arlington, United States
    Duration: Jan 10 2016Jan 12 2016

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
    Volume1

    Other

    Other27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
    CountryUnited States
    CityArlington
    Period1/10/161/12/16

    ASJC Scopus subject areas

    • Software
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'Weighted dynamic finger in binary search trees'. Together they form a unique fingerprint.

    Cite this