Optimum Partitions of Tree Addressing Structures
W. H. Hosken · SIAM Journal on Computing · 1975
We consider the problem of finding the best partition of a binary tree addressing structure where the maximum block size is given and a one-block buffer is available. An algorithm is presented for finding an optimum partition. The algorithm operates in time proportional to $N \cdot n^2 $, where N is the number of nodes in the tree and n is the block size.