Worst-Case Optimal Tree Layout in External Memory

Erik D. Demaine, John Iacono, Stefan Langerman

    Research output: Contribution to journalArticle

    Abstract

    Consider laying out a fixed-topology binary tree of N nodes into external memory with block size B so as to minimize the worst-case number of block memory transfers required to traverse a path from the root to a node of depth D. We prove that the optimal number of memory transfers is (Formula Presented.)

    Original languageEnglish (US)
    Pages (from-to)369-378
    Number of pages10
    JournalAlgorithmica
    Volume72
    Issue number2
    DOIs
    StatePublished - Jun 1 2015

    Keywords

    • Data structures
    • External-memory
    • Trees

    ASJC Scopus subject areas

    • Computer Science(all)
    • Computer Science Applications
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'Worst-Case Optimal Tree Layout in External Memory'. Together they form a unique fingerprint.

  • Cite this

    Demaine, E. D., Iacono, J., & Langerman, S. (2015). Worst-Case Optimal Tree Layout in External Memory. Algorithmica, 72(2), 369-378. https://doi.org/10.1007/s00453-013-9856-2