4.11.4 Suppose we want to lay out a full undirected binary tree on an integrated circuit...

 

Transcribed Image Text:

4.11.4 Suppose we want to lay out a full undirected binary tree on an integrated circuit chip, with the nodes at the intersections of a rectangular grid and the edges along lines of the grid. The H-tree is a recursive method of doing this. Define the H-tree H; by induction as follows: The tree Ho has a single node and no edges. For any number k, H2k+1 is made by taking a new root node and connecting it to the roots of two copies of H2k, each with roots a distance 2k away from the new root, one copy directly above and the other directly below. . For any positive number k, H2k is made by taking a new root node and connecting it to the roots of two copies of H2k-1, each with roots a distance 2k-1 away from the new root, one copy directly to the left and the other directly to the right. H Ho(1x1) H (1x3) H(3x3) H3(3x7) H4(7x7) Figure 4-27 shows the first few H-trees, through H4. (b) How many nodes are in H? How large a grid is needed to hold the layout? (For example, H4 fits on a 7 x 7 grid.) As n increases, approximately what percentage of the nodes on the grid become nodes of the H-tree Hn? (c) How much total wire is used in Hn? How far are the leaves from the root node? 4.11.4 Suppose we want to lay out a full undirected binary tree on an integrated circuit chip, with the nodes at the intersections of a rectangular grid and the edges along lines of the grid. The H-tree is a recursive method of doing this. Define the H-tree H; by induction as follows: The tree Ho has a single node and no edges. For any number k, H2k+1 is made by taking a new root node and connecting it to the roots of two copies of H2k, each with roots a distance 2k away from the new root, one copy directly above and the other directly below. . For any positive number k, H2k is made by taking a new root node and connecting it to the roots of two copies of H2k-1, each with roots a distance 2k-1 away from the new root, one copy directly to the left and the other directly to the right. H Ho(1x1) H (1x3) H(3x3) H3(3x7) H4(7x7) Figure 4-27 shows the first few H-trees, through H4. (b) How many nodes are in H? How large a grid is needed to hold the layout? (For example, H4 fits on a 7 x 7 grid.) As n increases, approximately what percentage of the nodes on the grid become nodes of the H-tree Hn? (c) How much total wire is used in Hn? How far are the leaves from the root node?