Lab 7: Ordered Lists and Binary Trees

• Lab 7 Template

In this lab you will define operations for ordered lists and binary trees.

What to do:

Set: A collection of elements, all of which are unique within the set. An element will not appear twice in a set.

Union: If A and B are sets, then the union of A and B contains all elements of A and all elements of B.

Intersection: If A and B are sets, then the intersection of A and B contains all the elements that are in both A and B.

1. Step 1: Adjoin to a Set (Ordered List) - 1 points

   [This is exercise 2.61 from the textbook.] Define a procedure adjoin-ordered which adjoins an integer x to a set ordered. Your solution must take advantage of the fact that the elements of ordered are in increasing order. adjoin-ordered should behave as follows:

   (adjoin-ordered 3
                   (list 1 2 4 5))
     (1 2 3 4 5)
   

2. Step 2: Union of Sets (Ordered List) - 3 points

   [This is exercise 2.62 from the textbook.] Define a procedure union-ordered which returns the ordered list representation of the set which is the union of sets ordered1 and ordered2. Your solution must have a runtime complexity of O(n). You may be tempted to use a solution such as this:

   (define (union-ordered ordered1 ordered2)
     (if (null? ordered1)
       ordered2
       (adjoin-ordered (car ordered1)
                       (union-ordered (cdr ordered1)
                                      ordered2))))
   

   Why is this solution invalid?

   For Steps 3 - 5 we'll be using the book's implementation of a binary tree; some of the book's procedures for manipulating trees are defined in the template file.

   A good method for checking whether the trees you've built are correct would be to use STk's (view __) command.

   Example: (view '(1 (3 (4 3)) 2))

3. Step 3: Convert a Set to a Binary Tree - 2 points

   Define a procedure set->tree which returns a (possibly unbalanced) binary tree representation of the unordered list set. The means to make binary trees and a few of the procedures to manipulate them are defined for you in the template file, if you're having trouble understanding them read up on binary trees on p. 155 - 158.

4. Step 4: Union of Sets (Binary Tree) - 2 points

   Define a procedure union-tree which returns a (possibly unbalanced) binary tree representation of the set which is the union of sets tree1 and tree2. What procedures, if any, could be used to simplify this problem?

5. Step 5: Intersection of Sets (Binary Tree) - 2 points

   Define a procedure intersection-tree which returns a (possibly unbalanced) binary tree representation of the set which is the intersection of set tree1 and tree2. Again, what procedures, if any, could be used to simplify this problem?

Bonus Questions

1. Bonus Question 1 - 1 bonus point

   What are the runtime complexities of your solutions to Steps 3 - 5?

Congratulations on completing Lab 7!
Lab 7 total: 10 pts

This is what you will learn in this lab

• gain familiarity with manipulating ordered lists and binary trees