CS 1101 - Aterm 08
Homework 7 - Ancestor Trees
Due: Friday, September 26 at 11:59pm
Read the expectations on homework.
Also, read Section 14.2 in the text.
Assignment Goals
- 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. Each node in the tree
contains a unique employee id number (key value), the employee's name, and the
employee's annual salary.
- Provide an example of binary search tree containing at least 4 employee
records.
- 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.
- 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.
What to Turn In
Using web-based turnin,
turn in a single file hw7.scm containing
all code and documentation for this assignment. Make sure both partners' names and wpi login names appear in a comment at the top of the file.