CS 1101 - C-term 11
Homework 5 - Binary Search Trees
Due: Thursday, February 17 at 5pm
Note: There are no classes on February 17 (Academic Advising Day). Office hours on that
day may be canceled or rescheduled, so plan accordingly.
Read the expectations on homework.
Also, read Section 14.2 in the text.
Assignment Goals
- To make sure you can write data definitions for fixed-width trees.
- To make sure you can write programs over fixed-width trees, specifically,
binary search trees.
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 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.
- 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 fixed-width ancestor tree, with an additional comment
that describes the binary search tree property given above.)
- 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.
- Write the template for the data definition in Problem 1.
- Write a function
increase-10-percent that consumes a binary
search tree of books 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 10 percent.
- Write a function
copies-sold which consumes a binary search tree 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.
- Write a function
add-new-book. The function consumes a
binary search tree and a book and adds the book to the binary search tree.
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. So you
may assume that the book that is being added has empty left and right subtrees.)
What to Turn In
Here is the grade sheet for Homework 5 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.