Due: &trees-due; Summary: In this assignment, you will experiment with the creation and analysis of color trees. Purposes: To give you more experience working with trees. To give you experience analyzing procedures. Expected Time: Two to three hours. Collaboration: We encourage you to work in groups of size three. You may, however, work alone or work in a group of size two or size four. You may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment. Submitting: Email your answer to &grader-email;. The title of your email should have the form &trees-subject; and should contain your answers to all parts of the assignment. Scheme code should be in the body of the message. Warning: So that this assignment is a learning experience for everyone, we may spend class time publicly critiquing your work.

In exploring trees, it is always useful to be able to find the size or depth of a tree. In this assignment, we'll be emphasizing color trees, which means that we'll want a way to visualize them. You've already seen one technique for rendering color trees, in which we recursively divide the image in half vertically and render each half of the color tree in the corresponding half of the image. Here is a slightly different rendering technique that alternates how it divides the image between horizontal and vertical. But how do we get our colors trees? We've seen that we can build them manually with cons. But that's time-consuming. In this assignment, we'll explore some other ways of building color trees.

Problem 1: List-Like Color Trees One way to build color trees is to build them a lot like lists, repeatedly con-sing a color to a color tree. These color trees will be unbalanced, but produce interesting images when rendered. Write a procedure, (simple-color-tree n c1 c2 c3), that builds a color tree with n colors by repeatedly cons-ing c1, c2, and c3. For example, (simple-color-tree 1 "red" "black" "grey") Builds "red" (simple-color-tree 2 "red" "black" "grey") Builds (cons "red" "black") (simple-color-tree 3 "red" "black" "grey") Builds (cons "red" (cons "black" "grey")) (simple-color-tree 4 "red" "black" "grey") Builds (cons "red" (cons "black" (cons "grey" "red"))) (simple-color-tree 5 "red" "black" "grey") Builds (cons "red" (cons "black" (cons "grey" (cons "red" "black")))) For example, > (ctree->image (simple-color-tree 20 "red" "black" "grey") 200 200)) Problem 2: From Vectors to Color Trees These color trees are so unbalanced that they are more like lists than trees. Another way to build a color tree is to start with a vector of colors and to systematically transform that vector into a tree. That is, we repeatedly divide the vector of colors in half, and recurse on the two halves of the vector. But how do we divide a vector in half? It turns out that building new vectors for each half is inefficient. Hence, instead of building new vectors, we keep track of the starting and ending indices of the portion of interest. For example, to build a color tree from an eight element vector, we need to build the tree from the elements with indices 0..7. To build a color tree from the eight elements with indices 0..7, we need to cons together (a) a tree built from the elements with indices 0..3 and (b) a tree built from the elements with indices 4..7. To build a color tree from the four elements with indices 0..3, we need to cons together (a) a tree built from the elements with indices 0..1 and (b) a tree built from the elements with indices 2..3. To build a color tree from the two elements with indices 0..1, we need to cons together (a) a tree built from the element with index 0 and (b) a tree built from the element with index 1. To build a color tree from the element with index 0, we return the color at index 0. To build a color tree from the element with index 1, we return the color at index 1. To build a color tree from the two elements with indices 2..3, we need to cons together (a) a tree built from the element with index 2 and (b) a tree built from the element with index 3. To build a color tree from the element with index 2, we return the color at index 3. To build a color tree from the element with index 2, we return the color at index 3. To build a color tree from the four elements with indices 4..7, we need to cons together (a) a tree built from the elements with indices 4..5 and (b) a tree built from the elements with indices 6..7. To build a color tree from the two elements with indices 4..5, we need to cons together (a) a tree built from the element with index 4 and (b) a tree built from the element with index 1. To build a color tree from the element with index 4, we return the color at index 4. To build a color tree from the element with index 5, we return the color at index 5. To build a color tree from the two elements with indices 6..7, we need to cons together (a) a tree built from the element with index 6 and (b) a tree built from the element with index 7. To build a color tree from the element with index 6, we return the color at index 6. To build a color tree from the element with index 7, we return the color at index 7. We can summarize this recursive process graphically in the following diagram. So, how do we implement this process? We start with a helper procedure. ;;; Procedure: ;;; subvector->ctree ;;; Parameters: ;;; colors, a vector of colors ;;; start-index, an integer ;;; end-index, an integer ;;; Purpose: ;;; Build a color tree from the portion of vector with indices ;;; start-index to end-index, inclusive. ;;; Produces: ;;; ctree, a color tree ;;; Preconditions: ;;; colors is nonempty. ;;; 0 <= start-index lt;= end-index <= (vector-length colors) ;;; Postconditions: ;;; The colors at indices start-index to end-index of colors appear ;;; in ctree, in the same order. ;;; (tree-size ctree) is (+ 1 (- end-index start-index)) We can then turn a whole vector into a tree by calling this procedure. (define vector->ctree (lambda (colors) (subvector->ctree colors 0 (- (vector-length colors) 1)))) Implement subvector->tree. Note: Our example above always used even size subvectors. If the subvector has an odd length, you can split it either way (with the first half larger or with the second half larger). For example, If you need to split the seven-element subvector at positions 7..13, you can either split into the 7..10 and 11..13 or into 7..9 and 10..13. Problem 3: Testing vector->tree Write a set of unit tests for vector->tree. Include a brief comment for each test (or set of tests) describing the purpose of the test. Problem 4: Randomized Color Trees A potential disadvantage of the two procedures we've written to generate color trees is that they are completely predictable. Given particular values, we can always determine in advance how the trees they build will be structured. It is sometimes interesting to create randomized color trees, color trees whose particular structure is difficult to determine. How can we create these color trees? Recursively, of course. To build a random color tree of size 1 from a vector of colors, randomly choose one of those colors. To build a color tree of size N from a vector of colors, pick a random size, M, for the left subtree (e.g., between 1 and N-1), build random color trees of size M and N-M, and cons them together. Document and write a procedure, (random-color-tree size colors), that builds a random color tree of the specified size from the vector of colors using the process described above. Problem 5: Balanced Trees As you may have noted, the trees we've been building vary significantly in how the sizes of the two halves relate. The trees built in problem 1 always had a left subtree of size 1 and a right subtree of size N-1. The trees built in problem 2 should have been a bit more balanced, with approximately N/2 values on each side of the tree. Computer scientists tend to like balanced trees (although not necessarily for this application). Hence, it is useful to have a predicate that tests whether a tree is balanced. How do we decide if a tree is balanced? The sizes of the subtrees differ by no more than 1. The left subtree is balanced. The right subtree is balanced. It is relatively straightforward to turn this definition into a procedure. (define tree-balanced? (lambda (tree) (or (not (pair? tree)) (let ((left-size (tree-size (car tree))) (right-size (tree-size (cdr tree)))) (and (<= (abs (- left-size right-size)) 1) (tree-balanced? (car tree)) (tree-balanced? (cdr tree))))))) Ideally, for a tree of size N, this procedure would make about N calls to tree-balanced and about N calls to tree-size. But does it? a. Build a variety of trees of sizes 4, 8, and 16 (perhaps three of each size) and determine how many calls to tree-balanced and how many calls to tree-size are made. b. You will find that your procedure makes significantly more than N calls to tree-size for a tree of size N. Explain why. c. Write a new version of tree-balanced? that has a total number of procedure calls that is no more than a constant times the size of the tree. Hint: Write a helper that combines the purposes of tree-size and tree-balanced?. If a tree is balanced, the helper should return its size. If a tree is unbalanced, the helper should return #f.