Worst-Case Optimal Tree Layout in a Memory Hierarchy
Erik D. Demaine, John Iacono, Stefan Langerman · arXiv (Cornell University) · 2004
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 D