CS314 Assignment - Binary Search Trees CS 314 - Specification 9 - Binary Search Trees Programming Assignment 9: Individual Assignment. You must complete this assignment on your own. You may not acquire from any source (e.g. another student or an internet site) a partial or complete solution to a problem or project that has been assigned. You may not show another student your solution to an assignment. You may not have another person (current student, former student, tutor, friend, anyone) “walk you through” how to solve an assignment. You may get help from the instructional staff. You may discuss general ideas and approaches with other students but you may not develop code together. Review the class policy on collaboration from the syllabus. Placed online: Tuesday, November 9 20 points, ~2% of final grade. Due: no later than 11 pm, Thursday, November 18 General Assignment Requirements The purposes of this assignment are: implement a binary search tree observe the behavior of binary search trees when adding data in no particular order and data already in sorted order Description: Implement a binary search tree class. Make the data structure generic using Java's generics and parameterized data types. You are free to use the code we developed together in lecture, just put a comment stating the code came from lecture. I expect you to use the simple insertion algorithm we developed in class. Like assignment 1, you may not look up algorithms, in this case for balanced binary search trees. You may not use the TreeSet or TreeMap classes from the Java standard library when implementing your Binary Search Tree. You will use the Java TreeSet class in some experiments. Provided Files: File Responsibility Source Code Stopwatch.java. Used to record times of experiments in questions.java. Provided by me. Do not alter. Implementation BinarySearchTree.java An implementation of a binary search tree. Provided by you and me. Mostly you. Documentation Javadoc for the BinarySearchTree class. Provided by me. Test code BSTTester.java contains several tests for the BinarySearchTree class. You must ensure the tests are correct and your class must pass these tests. Delete the original tests. Add at least 2 more tests per method. Provided by you and me. Reflection questions.txt Place your answers to these questions in a comment at the top of your BSTTester.java file. Provided by me. All Files All files in one zip. Provided by me. BinarySearchTree.java is class that implements a binary search tree as discussed in lecture. It is acceptable to use the naive insertion and removal algorithms. I have specified the methods for the class. Complete the implementation under the constraints of the general requirements. There is a method named printTree which prints out a representation of the current tree. It is a horizontal representation. This method is already done and can be useful in debugging. Read the documentation for details. BinarySearchTree.BSTNode. This is a class nested inside the BinarySearchTree class. Use instances of this class to store the data in the binary search tree. This is very similar to the BSTNode class presented in class, but now we are nesting it inside the BinarySearchTree class. This allows you to access the instance variables of a BSTNode object directly. BSTTester.java contains several tests for the BinarySearchTree class. After you are sure the original tests are correct and that your class passes them, delete the original tests. Add at least 2 tests per method in the BinarySearchTree class. questions.txt contains a number of questions to and experiments regarding your completed BinarySearchTree class. Place your answers in a comment at the top of your BSTTester class. Note: The get(int kth), getAllLessThan(E val), and getAllGreaterThan(E val) methods shall be as efficient as possible in terms of time and space. Meaning make the T(N) as small as possible. You could use the getAll method but you will very likely fail some stress tests if you take that approach. You must stop your search or processing as soon as you can. Don't do any extra work. All 3 of these methods can be solved with recursive backtracking. (No loops for choices, due to limited number of choices, but recursive backtracking nonetheless.) Submission: Complete the header in the BinarySearchTree and BSTTester classes. Replace with your name. Note, you are stating, on your honor, that you did the assignment on your own. Create a zip file name a9.zip with your BinarySearchTree.java and BSTTester.java files. The zip file must not contain any directory structure, just the required file. See this page for instructions on how to create a zip via Eclipse. Turn in a9.zip via your Canvas account to programming assignment 9. Ensure you files are named BinarySearchTree.java and BSTTester.java.. Failure to do so will result in points off. Ensure BinarySearchTree.java and BSTTester.java are part of the default package. Do not add a package statement to either file. Ensure your zip has no internal directory structure. When the file is unzipped no directories (folders) are created. (Note, the built in unzip feature of some versions of Windows and Apple OS X "help" by adding a directory when you unzip with the same name as the file. The unzip we use on the CS Linux system does not do this. Neither do unzip programs such as 7zip.) Ensure you submit the assignment under Programming Assignment 9 in Canvas. We will compile and run our tester harness on the CS department Linux machines. To ensure you have no problems (strange imports, package statements) I suggest you move your files to a directory on your CS department account and compile and run them from the command line. Checklist: Did you remember to: review and follow the general assignment requirements? work on the assignment by yourself? fill in the header in your BSTTester.java and BinarySearchTree.java files? ensure your version of BinarySearchTree passes the tests in BSTTester.java and add your own tests? ensure your program does not suffer a compile error or runtime error? run the experiments described in questions.txt and answer the questions in questions.txt? place your answers in a comment at the top of your BSTTester.java file.? turn in your a9.zip file with your files named BinarySearchTree.java and BSTTester.java to Canvas assignment 9 before 11 pm, Thursday, November 18.
