Worst-Case Optimal Tree Layout in External Memory

Erik D. Demaine, John Iacono, Stefan Langerman

    Research output: Contribution to journalArticlepeer-review

    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

    • General Computer Science
    • 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