Need help with this assignment
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 array 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 before. Linked lists and arrays 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 libraries 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 removeCurrent operation. The data structure is more complex than a dynamic array 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 Cursor 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 current element. We start the iteration at the first element in the binary tree, all the way to the left from the root. 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 current 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 current element, but even if we find the element, we keep looking (because we want the next element). The setCurrent 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 recursion. 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 correctly in the tree. There are so many helper methods that you are provided documentation comments for many of them, and tests to make sure they are working correctly. 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 for 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 constructor and size. 3. Implement each of the documented helper methods, and use the internal tests to check your implementation. The tests are arranged 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, isCurrent (easy), getCurrent (also easy), advance, setCurrent. (No removeCurrent 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, or use non-recursive and somewhat clunky code. 7. Debug your implementation with the regular tests. Don’t worry 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 recursion and try not be alarmed by null pointers. The simplest and cleanest code will be more likely to be correct (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 before, 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 Cursor Helper Methods What you need to do Files