Details posted 2/22/00.

This homework assignment is a written one, not a machine problem. It deals with binary search trees (BST) and is based on portions of Chapter 12 of the text. For the readings that are appropriate for this assignment, see the syllabus entry for February 24th. (Syllabus link)

For the general requirements for homework in this class, see the Homework #1 page.

1. Insert the following sequence of elements into an initially empty BST and draw the resulting BST: 3, 5, 1000, 450, 12, 30, 2, 200, 17.

2. Insert the same elements as before into an empty BST but in the following order, and draw the resulting BST: 2, 3, 5, 12, 17, 30, 200, 450, 1000.

3. Discuss the differences between 1 and 2 and how the different tree morphology might affect search and insert efficiency.

4. Suppose that we have an estimate ahead of time of how often search keys are accessed in a binary tree. Should the keys be inserted into the tree in increasing or decreasing order of likely frequency of access? Explain your answer. (This is Exercise 12.52 of the textbook.)

5. Students sometimes confuse the organization, purpose and manipulations of the binary tree making up the heap and binary search trees. Write a brief paragraph that points out the similarities of the two and more importantly, the very great differences between the two types of trees. For example, what would be a quick way to look at a tree and immediately know that it is one or the other?

6. Build a BST by insertion of items in the following order: 3, 9, 4, 8, 7, 1, 5, 2, 6 Compute the average number of steps (number of links followed) to search for and find an item that is present in the tree. That is, do one search for each of the distinct keys and average the result.