Homework 4 - Binary Search Trees

CS 1101 - Cterm 12

Homework 4 - Binary Search Trees

Due: Tuesday, February 14 at 5pm

Note that the due date for this assignment is the same day as Exam 2. Please 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 (ancestor) trees.
To make sure you can write programs over ancestor trees, specifically, binary search trees.

The Assignment

An important variant of the ancestor 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 ancestor tree.

An online auto parts distributor keeps a database of all the items in its inventory. Write a data definition for a binary search tree that contains records for auto parts. In addition to the components that provide access to the left and right branches of the tree, each node in the tree contains a part number (the key value), a description of the part (for example, "distributor cap", "fan belt", etc.) the unit price of the part, and number of parts in stock. (Hints: the data definition for a binary search tree follows exactly the same model as we used for an ancestor 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. Also, your data definition should include a comment that describes the properties of ordering the records in a bst.)
Provide an example of binary search tree containing at least 5 records. Make sure you construct your example so that the items in the tree are ordered according to the binary search tree property, on the part number.
Write the template(s) for the data definitions in Problem 1.
Write a function number-in-stock which consumes a binary search tree and a part number and returns a number. The number returned is the number of items in stock for the given part. You may assume the part number exists in the tree. Your function should be written efficiently, such that it examines as few records as is necessary.
Write a function restock which consumes a binary search tree, a part number, and the number of additional parts, and produces a binary search tree. The tree that is produced is the same as the original except that the number of parts in stock for the given item has been increased by the number of additional parts. You may assume that the given part number exists in the tree. Your function should be written efficiently, such that it examines as few records as is necessary.
Write a function list-all-parts, which consumes a binary search tree and produces a list of numbers. The function produces a list of the part numbers of every item in the tree, such that the list of numbers is in ascending numeric order. (Hint: take advantage of what you know about binary search trees to lead you to a way of constructing a sorted list. You do not need to (nor should you) design a separate sorting function.)
Write a function add-part. The function consumes a binary search tree, a part number, a description of the part, the unit price, and the number of parts in stock and adds a new record with the given information to the binary search tree. Make sure that the tree that is produced is a binary search tree. You may assume that the part number 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.) Your function should be written efficiently, such that it examines as few records as is necessary.

What to Turn In

Here is the grading rubric the graders will use when grading Homework 4.

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 homework files. Make sure both partners' names and wpi login names appear in a comment at the top of the file.