CS 1101 - A-term 10

Homework 7 - Binary Search Trees

Due: Friday, September 24 at 5pm Saturday, September 25 at 5pm

Read the expectations on homework. Also, read Section 14.2 in the text.

Assignment Goals

The Assignment

An important variant of the fixed-width tree is the binary search tree (section 14.2). In a binary search tree, the tree is organized such that the key value in a given node of the tree meets the condition that all key values in the node's left subtree are less than the key value in the given node, and all the key values in the node's right subtree are greater than the key value in the given node. This organization makes the task of searching the tree much more efficient (in terms of the number of comparisons needed to find a given value) than would be the case for a regular tree.

A book publisher keeps track of its books by storing the information about each book in a binary search tree ordered on the ISBN number. For each book, in addition to the ISBN number (and the left and right branches in the tree), the following information is stored: the title, author, year of publication, cost, and number of copies sold.

  1. Write the data definition for a binary search tree that contains books. (Hint: the data definition for a binary search tree follows exactly the same model as we used for a family tree. The step that will differentiate a binary search tree from a tree like a family tree is the step in which you construct examples - see the next problem.)

  2. Provide an example of binary search tree containing at least 5 books. Make sure you construct your example so that the items in the tree are ordered according to the binary search tree property, on the ISBN number.

  3. Write the template for the data definition in Problem 1.

  4. Write a function increase-price that consumes a binary search tree of books and a number representing a per cent increase and produces a binary search tree the same as the original except that the cost of each book in the tree has been increased by the given percentage.

  5. Write a function copies-sold which consumes a binary search tree and an ISBN number, and returns the number of copies sold for the book with the given ISBN. If a book with the given ISBN doesn't exist in the tree, the function should return -1. Your function should be written efficiently, such that it performs as few comparisons as is necessary to find the correct ISBN number in the tree.

  6. Write a function add-new-book. The function consumes a binary search tree, an ISBN, title, author, and price and adds a new book with the given ISBN, title, author, and price to the binary search tree. The new book has a publication date of 2010 and has no copies sold. Make sure that the tree that is produced is a binary search tree. You may assume that the ISBN number of the book to be added does not already exist in the given tree. (Hint: new records are always added at the "leaf" end of the tree; records are never inserted into the middle layers of a binary search tree.)

What to Turn In

Here is the grade sheet for Homework 7 that the TAs will use when grading your assignment.

Using web-based turnin, turn in a single file containing all code and documentation for this assignment. Name your file according to the naming conventions for files. Make sure both partners' names and wpi login names appear in a comment at the top of the file.