Optimizing the Layout of a Balanced Tree

R. A. Legenstein and W. Maass


It is shown that the total wire length of layouts of a balanced binary tree on a 2-dimensional grid can be reduced by 33``symmetric'' layout strategy. Furthermore it is shown that the more efficient layout strategy that is presented in this article is optimal, not only for binary trees but for m-ary trees with any m >= 2.

Reference: R. A. Legenstein and W. Maass. Optimizing the layout of a balanced tree. Technical Report, 2001.