Very Thin VLSI-Layouts (Very Large Scale Integration-Layouts) of Complete Binary Trees

摘要

The authors give a minimum area VLSI-layout of a complete binary tree T sub k with all (2 sup k) leaves on one edge of a rectangular chip. The layout has the following additional properties: (i) there are no wire-crossings; (ii) the root of the tree is accessible; and (iii) it has minimum possible width. It is shown that any minimum area VLSI-layout of T sub k, with all leaves collinear must have width (k/2) + 1 and length (2 sup k) + 2 sup ((k/2) - 1) for k even and (2 sup k) + 2 sup ((k/2) - 1) (1 + (k/2)) for k odd.