CS 1101 - Aterm 12
Homework 5 - Binary Search Trees
Due: Tuesday, September 25 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 fixed-width trees, specifically,
binary search trees.
The Assignment
An important variant of the binary 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
binary tree.
- A social networking website stores information about its
users 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 user number (the key value), the user's name,
and a list of the names of each of the user's
friends. 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 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
a binary search tree.)
- Provide an example of binary search tree containing at least 5 user
records. Make sure you construct your example so that the items in the tree
are ordered according to the binary search tree property, i.e. on the user
number.
- Write the template(s) for the data definition(s) in Problem 1.
- Write a function
friend-count which consumes a binary search tree and a user
number and returns a number. The number returned is the number of
friends the person with the given user number has.
You may assume the user number exists in the tree. Your function should be
written efficiently, such that it performs as few comparisons in the tree as is
necessary.
- Write a function
friend-everyone. The function consumes a
binary search tree and the name of a person and returns a new binary search tree
such that the named person has been added to each user's friend list.
- Write a function
list-names-in-order.
The function consumes a
binary search tree and produces a list of the names of users in the tree,
such that the list of names is in ascending numeric order by user number.
(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-user. The function consumes a
binary search tree, a user number, and a user name, and adds a
new user with the given information to the binary search tree. The user's
list of friends should be empty. Make sure
that the tree that is produced is a binary search tree. You may assume that the
user 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
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.