CSC148 - Introduction to Assignment 2: Treemaps
The goal of this worksheet is to help you get familiar with some of the concepts you’ll need to complete key parts of A2.
1. Let’s jump right in and draw a treemap. Take a look at the diagram below representing a data tree. The value beside
each node represents the size of the data for that node. In this example, each interior node’s data size is the sum of its
child data sizes plus 5. Fill in the grid on the right with a treemap representation of the entire data tree. (You can use
the letters for each leaf in the tree to label your treemap, or use colour to relate each leaf to its rectangle in the treemap.)
(55, 0)(0, 0)
(0, 30) (55, 30)
(20, 24)
(5, 5)
(45, 25)(35, 25)
(40, 15)
(35, 10)
(30, 12)
2. Here’s the same tree, but this time we’ve used a double-circle to indicate that a tree node is expanded. Indicate for yourself
what part of the tree is the displayed-tree, and then draw the treemap representation of this displayed-tree in the grid on
the right.
(55, 0)(0, 0)
(0, 30) (55, 30)
(20, 24)
(5, 5)
(45, 25)(35, 25)
(40, 15)
(35, 10)
(30, 12)
3. Complete the table below. For each point given, fill in the letter for the tree node whose rectangle includes that point
(the points have also been indicated on the grids). Do so for each of the two treemaps. In the case that a point lies on a
boundary, choose the node that would be encountered first in a pre-order traversal of the tree, starting from the root.
(x, y) Treemap #1 Treemap # 2
(5, 5)
(20, 24)
(30, 12)
(35, 10)
(35, 25)
(40, 15)
(45, 25)