Comp 210 Lab 5: Trees

Index: Binary Search Trees, Arithmetic Expressions

In class, we've been using various forms of family trees as examples. This week in lab, we'll use more example forms of trees. Trees are a very common form of data. In fact, lists are simply trees with at most one branch at each node.

We often want to be able to build a data structure that allows us to look up information based on some key value. One simple idea would be to just create a list of all the data items. The disadvantage is that it can then take a long time to find the items at the end of the list, since we have to look at all the prior items first. Many data structures can be used for this problem, one of which is a binary search tree.

For simplicity, let's assume we just want to keep track of a bunch of numbers, remembering which ones we've seen. From this, we could easily generalize our results to, for example, keeping track of a sports team's player information indexed by player number, or to indexing on names rather than numbers.

The following are some binary search trees for the numbers 1,3,4,6,9:

•         4
        /   \
       1     6
        \     \
         3     9
       

•         3
        /   \
       1     6
            / \
           4   9
       

•         3
        /   \
       1     4
              \
               6
                \
                 9
       

To do:

1. Make a data definition for these binary search trees.

2. Make example data representing the above three trees.

3. Develop a function search which consumes a binary search tree and a number and returns the boolean indicating whether the number is in the tree. (Follow the design recipe, of course.)

4. Develop a function insert which consumes a binary search tree and a number and returns a new binary search tree. The resulting tree should contain all the numbers from the first tree, plus the new number. However, if the number was already in the given tree, the resulting tree shouldn't have the number duplicated.

   This function gives you the freedom to make the input and output trees structured very differently. Hint: The easiest option is to do no rearrangements, and add the new node at the bottom of the appropriate branch. For the curious... In Comp 212, you'll see why rearranging the tree in certain ways can make a "better" tree.

   For examples of this function, use insert to generate the above three trees.

5. Develop a function in-order which consumes a binary search tree and returns a list of the numbers in the tree in sorted order. You'll want to use the built-in function append to append lists together. (Later in the course, we'll see how to implement append.) Hint: Note that the leaves of the tree are sorted left-to-right.

6. For the curious... Describe how long search and insert take in terms of the shape of the input tree.

   Many operations on binary search trees would be faster if the trees were also balanced, i.e., the branches were all more-or-less equally deep. Implementing balanced binary trees is much more difficult, as you'll see in Comp 212.

7. For the curious... Change the definition of a node to also store more information than just the index. E.g., consider each number to be a team player's number, and add the player's stats. Adapt search and insert to look up and add this information to the tree.

Arithmetic expressions can also be modeled as trees. For example, the Scheme expression

     (+ 5 (* (- 1 8) (+ 7 1)))

        +
      /   \
     5     *
         /   \
        -     +
       / \   / \
      1   8 7   1

An A-Expression is one of the following:

• n, where n is a number,
• (make-add m n), where m, n are A-Expressions,
• (make-sub m n), where m, n are A-Expressions,
• (make-mul m n), where m, n are A-Expressions, or
• (make-div m n), where m, n are A-Expressions.

Thus the above Scheme expression is represented by

     (make-add 5
               (make-mul (make-sub 1 8)
                         (make-add 7 1)))

To do:

1. Make more example data. Make a template for functions using A-Expressions.

2. Develop the function evaluate which consumes an A-Expression and returns a number. Your function should be like a mini-DrScheme, computing the number that the A-Expression represents.

   DrScheme, like any language interpreter, is just a generalization of evaluate. A Scheme expression is like an arithmetic expression, but with more cases.

3. For the curious... Let's say we had many basic operations, not just these four. We would want to have one structure for any binary operation, using a separate data definition enumerating all of our operations. Rewrite the data definitions, examples, and evaluate for this.

4. For the very curious... Adapt the previous idea to also allow unary operations.