  We consider the problem of laying out a tree with fixed parent/child
structure in hierarchical memory. The goal is to minimize the expected number
of block transfers performed during a search along a root-to-leaf path, subject
to a given probability distribution on the leaves. This problem was previously
considered by Gil and Itai, who developed optimal but slow algorithms when the
block-transfer size B is known. We present faster but approximate algorithms
for the same problem; the fastest such algorithm runs in linear time and
produces a solution that is within an additive constant of optimal.
  In addition, we show how to extend any approximately optimal algorithm to the
cache-oblivious setting in which the block-transfer size is unknown to the
algorithm. The query performance of the cache-oblivious layout is within a
constant factor of the query performance of the optimal known-block-size
layout. Computing the cache-oblivious layout requires only logarithmically many
calls to the layout algorithm for known block size; in particular, the
cache-oblivious layout can be computed in O(N lg N) time, where N is the number
of nodes.
  Finally, we analyze two greedy strategies, and show that they have a
performance ratio between Omega(lg B / lg lg B) and O(lg B) when compared to
the optimal layout.
