Trees

Important and common, but not standardized in Scheme.

Made from leaves and nodes. We'll do "binary trees" meaning each node has two children. We'll assume that the tree has been ordered using a relation (like < or >=) so that one branch contains only leaves whose value is less than the value at the parent node, while the other branch contains only values greater-than or equal-to that of the parent node.. We'll assume that the leaves are all n-dimensional points.

See tree.scm for all of the code.

A typical tree recursion is needed to find the point farthest from the origin:

(define (tree.farthest node-or-leaf)
  (if (is-node? node-or-leaf)
      (tree.farthest (node.outside node-or-leaf))
      node-or-leaf))

Sometimes we need a "generic operation" that can work on either a leaf or a non-leaf node in a tree:

(define (distance node-or-leaf)
  (if (is-node? node-or-leaf)
      (node.distance node-or-leaf)
      (point.to-origin (leaf.point node-or-leaf))))

And a more complicated tree recursion: Note: The following code was presented in lecture, claiming to guarantee that a tree has the property that all the leaves in the node.on-or-in branch under a given node have a distance that is less-than-or-equal-to the distance to the given node, and that all leaves in the node.outside branch have a distance greater than that to the node. This is not true.

(define (tree.valid? node-or-leaf)
  (if (is-node? node-or-leaf)
      (let ((smaller (node.on-or-in node-or-leaf))
            (not-smaller (node.outside node-or-leaf))
            (my-distance (node.distance node-or-leaf)))
        (and (< (distance smaller) my-distance)
             (>= (distance not-smaller) my-distance)
             (tree.valid? smaller)
             (tree.valid? not-smaller)))
        #T))

The following, more complicated program, does work correctly.

Extra credit question: Can you draw a tree, t, for which (tree.valid? t) returns #T but for which (valid? t) returns #F?

(define (valid? node-or-leaf)
  (define (min previous new)
    (if (and previous (<= previous new)) previous new))

  (define (max previous new)
    (if (and previous (>= prevous new)) previous new))

  (define (walk node-or-leaf min-OK max-OK)
    (if (is-node? node-or-leaf)
        (let ((smaller (node.on-or-in node-or-leaf))
              (not-smaller (node.outside node-or-leaf))
              (my-distance (node.distance node-or-leaf)))
          (and (or (not min-OK) (>= (distance smaller) min-OK))
               (or (not max-OK) (<= (distance not-smaller) max-OK))
               (walk smaller (min min-OK my-distance) max-OK)
               (walk not-smaller min-OK (max max-OK my-distance))))
        #T))

  (walk node-or-leaf #F #F))

Jim Miller