Homework 5 - Binary Search Trees

CS 1101 - Aterm 15

Homework 5 - Binary Search Trees

Due: Thursday, October 1 at 5pm

Assignment Goals

To make sure you can write data definitions for binary search trees.
To make sure you can write programs over binary search trees.

The Assignment

An important variant of the binary tree is the binary search tree. In a binary search tree, the tree is organized such that the key in any given node of the tree meets the conditions that all keys in the node's left subtree are less than the key in the given node, and all the keys in the node's right subtree are greater than the key 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 key) than would be the case for a regular binary tree.

An internet-based retailer stores information about customers' orders in a binary search tree. In addition to the components that provide access to the left and right branches of the tree, each node in the tree contains a unique order number (the key value), the customer's name, the customer's credit card number, and a list of the items ordered. Each item in the list consists of an item number, a description of the item, the quantity of that item ordered, and the price per item. Write the data definitions needed for this binary search tree. (Hints: the data definition for a binary search tree follows exactly the same model as we used for a plain binary 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, the interpretation part of your data definition should include a comment that describes the binary search tree invariant.)
Provide an example of a binary search tree containing at least 5 orders. Make sure you construct your example so that the orders are placed in the tree so that the order numbers satisfy the binary search tree invariant.
Write the template(s) for the data definition(s) in Problem 1.
Write a function order-cost which consumes a binary search tree, and an order number, and returns a number. The function calculates the total cost of all the items in the order. If no such order number exists in the tree, the function should return the value -1 (we'll discuss better ways to handle errors later). Your function should be written efficiently, such that it performs as few comparisons in the tree as is necessary.
Sometimes items are discontinued, and can't be shipped. Write a function remove-item-from-all-orders. The function consumes a binary search tree and an item number, and returns a new binary search tree such that if the given item exists in any order's item list, that item has been removed.
Write a function list-sorted-order-numbers. The function consumes a binary search tree and produces a list of the order numbers sorted in ascending order. (Hint: you don't have to write a sorting algorithm. Use what you know about the order of items in a binary search tree to help you. You will need to use the built-in function append for this problem.)
Write a function add-new-order. The function consumes a binary search tree, an order number, a customer name, a credit card number, and a list of items, and adds a new order 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 order 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.)

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