CS 351/751: Data Structures & Algorithms Homework #8
Homework # 8
due Wednesday, November 7, 10:00 PM
In this homework assignment, you will re-implement the ApptBook ADT using a binary search
tree (BST) data structure. A BST permits more efficient insert and lookup mechanisms (compared
to an a
ay or a linked list) and so there is an efficiency test to make sure that your code can handle
a million entries.
https:
classroom.github.com/a/sRam5YE4
1 The Binary Search Tree Data Structure
Please read section 9.5 in the textbook for a description of the binary search tree data structure.
Alternatively, there are tons of webpages/lecture notes on BST, the wiki page maybe a good start
point (https:
en.wikipedia.org/wiki/Binary_search_tree). In the textbook (as well as some
online sources), a separate BTNode class is used; we will not do that. Use a nested node classes as
efore.
Linked lists and a
ays support insertion, removal or finding an entry in time proportional to the
number of entries in the container. Trees, on the other hand, offer a significant efficiency advantage
in that they generally support these operations in time proportional to the log of the number of
entries (assuming the tree is kept balanced).
In order to achieve the potential time efficiency of binary search trees, one needs to keep the
tree roughly balanced. In CompSci 535, you will learn some of the techniques used to do this (as
it happens, the tree-based containers in Java’s li
aries use “red-black” trees). But in this course,
we will ignore the problems of unbalanced trees. Do not make any attempt to re-balance your tree.
The efficiency tests we run will make sure to construct a balanced tree.
2 Concerning the ApptBook ADT
You have already implemented the ApptBook twice (in Homeworks #2 and #4 along with a related
ADT in Homework #6). The ADT for this assignment is the same, except that we don’t implement
the removeCu
ent operation. The data structure is more complex than a dynamic a
ay or linked
lists (even a doubly-linked list), and so we delay removal until the following week.
2.1 Duplicates
As designed, appointment books can contain duplicates, and so our binary search tree will need
to implement duplicates as well. If a duplicate is added to the tree, it should appear in the right
subtree of any existing equivalent elements.
2.2 Concerning the Curso
In the following week, we will implement an iterator over a binary search tree, but this week, we
just have a cursor, which (as with the DLL-based sorted sequence) points to the node with the
cu
ent element.
We start the iteration at the first element in the binary tree, all the way to the left from the
oot.
Fall 2022 page 1 of 4
https:
classroom.github.com/a/sRam5YE4
https:
en.wikipedia.org/wiki/Binary_search_tree
CS 351/751: Data Structures & Algorithms Homework #8
Advancing the cursor is perhaps surprisingly difficult compared to how it worked in previous
assignments. There are two cases:
• The cursor node has a non-null right child. In that the case the next node can be found by
going to the furthermost left of the right subtree.
• The cursor’s node has a null right child. In that case the next element is guaranteed not
to be equivalent to the cu
ent element (why?) and so we can find the cursor by doing an
equality-rejecting search, as described in section 2 of the “Navigating Trees” handout. (You
only need to look at section 2 this week.)
The basic idea is that we look for the cu
ent element, but even if we find the element, we
keep looking (because we want the next element).
The setCu
ent operation performs an equality-accepting search to find the place to start the
cursor. This operation is very similar to the equality-rejecting search needed for advance—we
implement them together with a helper method taking a boolean indicating whether equality is
acceptable or not.
Similarly, both the first case of advance as well as start need to find the first node in a subtree,
and so we will define (and use) a helper method to do this task.
3 Helper Methods
The data structure is highly recursive, and so many tasks are very difficult to do if you do not use
ecursion. But the main ADT methods (such as clone) don’t have arguments that enable recursive
calls. Thus, we will use private recursive helper methods to do most of the work of methods such
as clone, insertAll and optionally insert.
We will also have helper methods to check tha the tree is height-bounded (not having any
cycles), to count the number of nodes in a tree and to check that elements are placed co
ectly in
the tree. There are so many helper methods that you are provided documentation comments fo
many of them, and tests to make sure they are working co
ectly.
In particular, for this homework, you are required to implement the following helper methods,
each of which take a parameter “r” that refers to a subtree, which can always be null (except fo
one of these):
checkHeight(r,max) Check that the height of the tree is bounded by the given maximum.
countNodes(r) Count all the nodes in the subtree.
allInRange(r,lo,hi) Check that all elements in the subtree are in legal places, and report any
problems (helper for wellFormed).
foundCursor(r) Return true if the cursor is found in the subtree.
firstInTree(r) Return the first node of a non-empty subtree.
nextInTree(r,a,eq?,alt) Return the next element after the given appointment in the tree,
The “eq?” parameter indicates whether equality is acceptable. The “alt” parameter is used
if there no accpetable element in the subtree.
Fall 2022 page 2 of 4
CS 351/751: Data Structures & Algorithms Homework #8
All of these methods have documentation comments and (along with wellFormed) are tested in
TestInternals. All except the last two must be recursive.1
Furthermore, you will need to design helper methods for clone, insertAll and (optionally)
insert. We don’t prescribe a form, and have no tests. But we recommend you impement the first
two as a form of pre-order traversal.
4 What you need to do
You need to do the following tasks:
1. Unlock the tests so that you understand the concepts used by the helper methods.
2. Define the data structure (Node class and fields of the main class). Define the constructo
and size.
3. Implement each of the documented helper methods, and use the internal tests to check you
implementation. The tests are a
anged in an order of approximate increasing complexity.
4. Implement wellFormed using the helper methods, which do most of the work. Check with
the last internal tests.
5. Implement each of the cursor methods: start, isCu
ent (easy), getCu
ent (also easy),
advance, setCu
ent. (No removeCu
ent this week.) Even the harder methods require
only a few lines of code since the helper methods can be used to do all the difficult work.
6. Implement insert. You can closely follow what we do in lecture with a helper method, o
use non-recursive and somewhat clunky code.
7. Debug your implementation with the regular tests. Don’t wo
y about insertAll and clone
for now.
8. Next implement clone with a helper method to copy each node recursively. Test with the
clone tests (test6n). Setting the new cursor requires that you send the answer result into
the recursive helper method so that it can update the cloned cursor, when it encounters the
cursor while copying the tree.
9. Finally, implement insertAll. You need to use a different implementation than before. You
cannot use the cursor on the addend, even if you clone it, because it will cause a severely
unbalanced tree. Instead use a new helper method to do a traversal on the addend and insert
each element in pre-order.
10. Once you are passing all the regular tests, it is time to check with random tests and efficiency
tests as with previous assignments.
This assignment is the hardest of all semester so far, so make sure to start early. Make sure to use
ecursion and try not be alarmed by null pointers. The simplest and cleanest code will be more
likely to be co
ect (or fail on simple example).
1As it happens, writing the first few without recursion is vastly harder. We require recursion because otherwise
you will waste time trying something that won’t work.
Fall 2022 page 3 of 4
CS 351/751: Data Structures & Algorithms Homework #8
5 Files
Your git repository for this homework includes a skeleton of the ApptBook class and some test
suites:
UnlockTest.java Unlock all the locked tests without running them.
TestInternals.java A test of the helper methods and the invariant.
TestApptBook.java An JUnit test case for the ADT. It is similar to what you have used
efore, except all the tests that used removal have been rewritten.
TestEfficiency.java A JUnit test case that should take at most a few seconds. If it takes much
longer, you are doing something wrong.
The JAR file includes random testing, as with many of our assignments.
Fall 2022 page 4 of 4
The Binary Search Tree Data Structure
Concerning the ApptBook ADT
Duplicates
Concerning the Curso
Helper Methods
What you need to do
Files