Assignment 8: Trees

In exploring trees, it is always useful to be able to find the size or depth of a tree.

;;; Procedure:
;;;   tree-depth
;;; Parameters:
;;;   tree, a tree
;;; Purpose:
;;;   Computes the length of the longest path from the start of the tree
;;;   to the furthest value.
;;; Produces:
;;;   dep, a nonnegative integer
;;; Preconditions:
;;;   None.
;;; Postconditions:
;;;   If tree contains no pairs, then dep is 0.
;;;   Otherwise, dep is one more than the depth of the deepest subtree.
(define tree-depth
  (lambda (tree)
    (if (pair? tree)
        (+ 1 (max (tree-depth (car tree))
                  (tree-depth (cdr tree))))
        0)))

;;; Procedure:
;;;   tree-size
;;; Parameters:
;;;   tree, a tree
;;; Purpose:
;;;   Count the number of values in tree.
;;; Produces:
;;;   count, a non-negative integer
;;; Preconditions:
;;;   (none)
;;; Postconditions:
;;;   count is the number of values in tree.  (pairs are not considered
;;;   values but null is considered a value).
(define tree-size
  (lambda (tree)
    (if (pair? tree)
        (+ (tree-size (car tree))
           (tree-size (cdr tree)))
        1)))

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.

;;; Procedures:
;;;   image-render-color-tree!
;;; Parameters:
;;;   image, an image
;;;   ctree, a tree of colors
;;;   left, a real number
;;;   top, a real number
;;;   width, a real number
;;;   height, a real number
;;; Purpose:
;;;   Render the tree into the portion of the image bounded at
;;;   the left by left, at the top by top, and with the specified
;;;   width and height.
;;; Produces:
;;;   [Nothing; Called for the side effect.]
;;; Preconditions:
;;;   image is a valid image
;;;   ctree is a valid color tree
;;;   0 <= left < (image-width image)
;;;   0 <= top < (image-height image)
;;;   width < 0
;;;   height < 0
;;;   0 <= (+ left width) < (image-width image)
;;;   0 <= (+ top height) < (image-height image)
;;; Postconditions:
;;;   The tree has now been rendered.
(define image-render-color-tree!
  (lambda (image ctree left top width height)
    (let kernel ((ctree ctree)
                 (hsplit? #t)
                 (left left)
                 (top top)
                 (width width)
                 (height height))
      (cond
        ; If it's too small, just stop.
        ((or (< width 1) (< height 1)))
        ; If it's a pair, and we're to split horizontally, do so
        ((and (pair? ctree) hsplit?)
         (kernel (car ctree) (not hsplit?) 
                 left top 
                 (/ width 2) height)
         (kernel (cdr ctree) (not hsplit?)
                 (+ left (/ width 2)) top
                 (/ width 2) height))
        ; If it's a pair, and we're to split vertically, do so
        ((pair? ctree) ; NOT hsplit?
         (kernel (car ctree) (not hsplit?) 
                 left top 
                 width (/ height 2))
         (kernel (cdr ctree) (not hsplit?)
                 left (+ top (/ height 2))
                 width (/ height 2)))
        ; Otherwise, it's just a single color, so render in the
        ; given space.
        (else
         (image-select-rectangle! image REPLACE
                                  left top (round width) (round height))
         (context-set-fgcolor! ctree)
         (image-fill-selection! image)
         (context-update-displays!)
         (image-select-nothing! image))))))

;;; Procedure:
;;;   ctree->image
;;; Parameters:
;;;   ctree, a color-tree
;;;   width, a positive integer
;;;   height, a positive integer
;;; Purpose:
;;;   Create a new width-by-height image from ctree, by rendering it  
;;;   using one of the color-tree rendering procedures.
;;; Produces:
;;;   image, a new image
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   image is an image
;;;   image contains a rendering of ctree.
(define ctree->image
  (lambda (ctree width height)
    (let ((image (image-new width height)))
      (image-render-color-tree! image ctree 0 0 width height)
      image)))

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,

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.

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.

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.

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?

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.