CS 1101 - Aterm 11
Homework 5 - Binary Search Trees
Due: Tuesday, September 27 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 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 much 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.
- Write a data definition for a binary search tree that models employee
records. 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 employee ID number (key value), the employee's name, and the
employee's annual salary. (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
the records in a bst.)
- Provide an example of binary search tree containing at least 5 employee
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 employee ID
number.
- Write the template for the data definition in Problem 1.
- Write a function
salary which consumes a binary search tree and an employee ID
number and returns a number. The number returned is the salary of the employee
with the given ID. You may assume the ID exists in the tree. Your function should be
written efficiently, such that it performs as few comparisons as is
necessary.
- Write a function
apply-raise. The function consumes a
binary search tree and a percent raise and returns a new binary search tree
such that the raise has been applied to each employee's salary. (If the
number provided to the function is 0.05, for example, the employees' salaries
would be increased by 5%.)
- Write a function
list-names-in-order.
The function consumes a
binary search tree and produces a list of the names of employees in the tree,
such that the list of names is in ascending numeric order by the employees' IDs.
-
Write a function
add-new-employee. The function consumes a
binary search tree, an employee ID, employee name, and salary and adds a
new employee 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
employee ID 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 grading rubric the graders will use when grading Homework 5.
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.