Homework 6: Binary Search Trees

Due November 26 @ 8:00pm on Autolab

1. Introduction

In this assignment, you’ll be writing the code for a binary search tree. It will be based on the tree we construct and deal with in class. (So, it is ok to copy-and-paste code from our class demo code into your assignment.)

Download a pre-prepared Eclipse Project hw6.zip and import it into Eclipse using these instructions. You will make all of your changes inside of the Java files in this project.

2. Your Tasks

You have two main tasks.

  1. Finish the KeyValueBinarySearchTree implementation with all of the requested methods.
  2. Write the AnagramTree class that can be used to find anagrams from a dictionary.

2.1. Finishing KeyValueBinarySearchTree

Fill in all of the empty methods in KeyValueBinarySearchTree.java. They are documented inside of the file.

2.2. Building the AnagramTree

You’re going to write an anagram finder, AnagramTree. (If you don’t know what an anagram is, try Wikipedia on the subject.)

The AnagramTree will make use of the KeyValueBinarySearchTree class to store lists of anagrams. At a high-level, it will read in a file of words (one per line) and store them in a binary tree using their sorted letters as the search key. What does this mean? When you read a word from the file (a String), you must sort it (by creating another, sorted, String that has all the letters of the original word in sorted order) and then insert original word into the tree using the sorted word as the key. The sorted word (a String) will be the search key for the binary search tree, and all the words that have the same sorted form (like “rats” and “tars” and “arts”) will all be stored in an ArrayList at the node with the sorted word key (in this case, with key “arst”).

The AnagramTree method loadWords takes a file name and maximum word size and builds a tree with all the words that are less than or equal to the length specified. To do this, you read words from a file one line at a time, and for each word if it is the correct length then construct its sorted form and add the original word into your tree, using the sorted form as the key. (Remember: The key finds the node, and the node contains an ArrayList of words that are anagrams of the sorted key.)

If you use the small file and a maximum word size of 7, you should have 16 words in 9 nodes in the tree. If you use the big file with a maximum word size of 7, you should have 51913 words in 41121 nodes. (Or, with a maximum word size of 8, 80314 words in 66538 nodes.)

We have provided some simple driver code in AnagramTester.java that should use your AnagramTree class. Your code must be compatible with this tester as provided.

3. Grading and Submission

The assignment will be graded as follows:

3.1. Testcases

In this homework we are not providing any testcases.

For KeyValueBinarySearchTree you need to provide at least three testcases for each of the new methods. At least one of those three must be non-basic. All of your testcases should be in the KeyValueBinarySearchTree class included with the skeleton code.

For AnagramTree you need to provide at least three complete testcases that demonstrate overall functionality. (And, of course, we expect that you will also be testing manually using the AnagramTester).

You must follow the model of our testcases (meaning you print when you start, print when you finish, etc.) Additionally, you must comment each testcase with a note describing what it tests.

When grading, in addition to counting testcases we will also look at the quality of what you are testing.

3.2. Style

In this homework you will be strictly graded according to the style guide. A style checker has been incorporated with Autolab and will assign these style points automatically. You can see your style score and feedback as part of the Autolab output.

3.3. How to Submit

For this assignment you are limited to 15 submissions on Autolab. Use them wisely. If you run out of submissions, you will automatically receive a 0.

You will submit your program to Autolab. Login to the system and you will see the homework.

You’ll need to submit a zip file containing your code. Lucky for you, however, Eclipse can create this zip file for you. Check out these instructions. On Autolab, you’ll submit that exported zip file. On the page that follows your submission you will see your live score. It may take up to a few minutes for your score to appear; during that time just hit refresh in your browser. If you receive a lower score than you expect, you can click on the score to see the feedback from the autograder.

4. Restrictions

You may only use the following Java libraries in this assignment:

java.util.ArrayList
java.util.Scanner
java.io.FileReader
java.util.Arrays

5. Important Notes