Implementing Sets with binary search trees

---

Goals 

• Learn about the implementation of Sets using binary search trees, both unbalanced and

balanced

• Implement methods for a NavigableSet, including contains and remove

• Get more practice writing JUnit tests

• Get more practice with version control

Purpose

Binary search trees can be used to build efficient Sets that perform lookups and inserts in □□(□□□□□□ □□)

time, which is fairly efficient. As we've seen in class, Sets are useful for applications where you need to  look things up by a "key" like checking airline tickets or looking up the existence of a word in a
dictionary. In this homework, you will study the implementation of Sets using binary search trees. We
have provided Java files that contain code for a Set implemented with an unbalanced binary search tree  (BSTSet.java) and a Set implemented using an AVLTree (AVLTreeSet.java), and your job is to finish them.

Submission Checklist

By April 17, 11:59pm: answers to the PROGRESS_REPORT.txt in your GitHub repository. No slip days  accepted.

By April 20, 11:59 pm: You should have changes in GitHub to the following files:
• BSTSet.java

• AVLTreeSet.java

• BSTSetTest.java

• AVLTreeTest.java (if you added optional tests)

• answers.pdf

Slip days: Your submission time is the date of the last commit we see in your GitHub repository. As  usual, we will process slip days automatically, so you do not need to tell us you are using them.

You will submit them via GitHub. Follow the directions in setup_hw7.pdf on "Setup your own private
repository to push your commits to". Before you are done submitting, you must check the following.

ü Do the tests pass?

ü Did I write the required tests?

ü Does my github.uiowa.edu repository reflect the code I intend to turn in? (You must view this in

your web browser, not in NetBeans. If still in doubt, you can also clone your completed code
into a second NetBeans project and check it by running all the tests).

Getting HW7

Follow all the directions in setup_hw7.pdf

Part 0

Examine the TreeNode class. In particular, answer the following questions for yourself (you do not need  to submit the answers, but this part will help you with the rest of the assignment).

• How do you test if this is a leaf?

• How does isBST work?

• What is the result of toString() when called on the root TreeNode of the following tree?

Part 1: Contains method

The Set.contains method returns true if and only if the element exists in the Set.

a) The BSTSetTest.java file has test cases for BSTSet. Devise three different tests for the contains

method (put them in testContainsA,B, and C) so that you are confident that contains() works.
Your tests for this part should be "black box", that is, they don't depend on the implementation:
they only call public methods of BSTSet (in this case, the constructor, add(), and contains()). Your
3 tests need to be different: that is, your add methods should be such that they cause different
underlying tree structures and there should be cases where contains() returns each true and
false.

b) Implement the BSTSet.contains method.
Part 2: A method for NavigableSet
Take a look at the NavigableSet interface. It adds a new method subSet to the methods already

provided by Set. The subSet method requires that keys stored in the NavigableSet have a total order.

Therefore, you'll see that the generic type is constrained to be a Comparable. The Comparable interface  provides the compareTo method.

public interface NavigableSetextends Set

Read the Java 8 API on Comparable