Worst-Case Optimal Tree Layout in External Memory
<|reference_start|>Worst-Case Optimal Tree Layout in External Memory: Consider laying out a fixed-topology 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 $$ \cases{   \displaystyle   \Theta\left( {D \over \lg (1{+}B)} \right)   & when $D = O(\lg N)$, \cr   \displaystyle   \Theta\left( {\lg N \over \lg \left(1{+}{B \lg N \over D}\right)} \right)   & when $D = \Omega(\lg N)$ and $D = O(B \lg N)$, \cr   \displaystyle   \Theta\left( {D \over B} \right)   & when $D = \Omega(B \lg N)$.   } $$<|reference_end|>
@article{demaine2004worst-case,
    title={Worst-Case Optimal Tree Layout in External Memory},
    author={Erik D. Demaine and John Iacono and Stefan Langerman},
    journal={arXiv preprint arXiv:cs/0410048},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0410048},
    primaryClass={cs.DS}
}