CS 1101 - C-term 10
Homework 7 - Binary Search Trees
Due: Friday, February 12 at 5pm
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 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, 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 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.)
- 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
total-copies-sold that consumes a binary
search tree of books and produces the total number of all books that have been
sold.
- Write a function
this-edition? which consumes a binary search tree, an ISBN
number, and a year, and returns a boolean. The function returns true if the year
of publication of the book with the given ISBN number is the same as the
given year.
If the ISBN number doesn't exist in the tree, or if the year of publication of the
book is different from the given year, the function returns false. 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
best-sellers. The function consumes a
binary search tree and produces a list of the titles of all books that have sold over
100,000 copies. (Hint: use the built-in DrScheme operator append).
What to Turn In
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.