Worst-Case Optimal Tree Layout in External Memory

Erik D. Demaine, John Iacono, Stefan Langerman

    Research output: Contribution to journalArticlepeer-review


    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
    Issue number2
    StatePublished - Jun 1 2015


    • Data structures
    • External-memory
    • Trees

    ASJC Scopus subject areas

    • General Computer Science
    • Computer Science Applications
    • Applied Mathematics


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

    Cite this