Description
2 Background 2.1 Heaps A heap is a binary tree which has the following heap property: the item stored at a node must be at least as large as any of its descendents (if it has any). In a heap, when an item is removed, it is always the largest item (the one stored at the root) that gets removed. Also, the only item that is allowed to be inspected is the top of the heap, in much the same way that the only item of a stack that may be inspected is the top element. Stacks, queues, and heaps are all examples of collections of data items that we call dispensers. You can put stuff into a dispenser, but the user doesn’t get to specify where – the collection decides according to some rule(s). Likewise, you can take something out of a dispenser, but the dispenser decides what item you get. Dispensers maintain a current item using an internal cursor, but the dispenser always decides what is the current item, and thus the item that will next be dispensed when a user asks to remove or inspect the current item. Dispensers do not have public methods to control the cursor position because the user is not supposed to control this; it’s up to the dispenser. In a stack, the “current” item is always the item at the top of the stack. In a queue it is the item at the front of the queue. In a heap it is the item at the root of the heap. In question 1 you will implement a heap by writing a class called ArrayedHeap280 that extends the abstract class ArrayedBinaryTree280 and implements the Dispenser280 interface. Here are brief pseudocode sketches of the insert and deleteItem algorithms: Algoirthm insert (H , e ) Inserts the element e into the heap H . Insert e into H normally , as in ArrayedBinaryTreeWithCursors280 // ( put it in the left – most open position at the bottom level of the tree ) while e is larger than its parent and is not at the root : swap e with its parent Algorithm deleteItem ( H ) Removes the largest element from the heap H . // Since the largest element in a heap is always at the root … Remove the root from H normally , as in ArrayedBinaryTreeWithCursors280 // ( copy the right – most element in the bottom level , e, into the root , // remove the original copy of e.) while e is smaller than its largest child swap e with its largest child Page 2 2.2 Efficient Insertion and Deletion in AVL Trees For AVL trees, we need to be able to identify critical nodes to determine if a rotation is required. After each recursive call to insert(), we need to check whether the current node is critical (the restoreAVLProperty algorithm). This means we need to know the node’s imbalance, which means we need to know the heights of its subtrees. If we compute the subtree heights with the recursive post-order traversal we saw in class, we are in trouble, because this algorithm costs O(n) time, where n is the number of nodes in the tree. Since insertion requires O(log n) checks for critical nodes, computing imbalance in this way makes insertion O(n log n) in the worst case. To avoid this cost, in each node of the AVL tree we have to store the heights of both of its subtrees, and update these heights locally with each insertion and rotation. The insertion algorithm from the AVL tree slides becomes: // Recursively insert data into the tree rooted at R Algorithm insert ( data , R ) data is the element to be inserted R is the root of the tree in which to insert ’ data ’ // This algorithm would only be called after making sure the tree // was non – empty . Insertion into an empty tree is a special case . if data <= R . item () if( R . leftChild == null ) R. leftChild = new node containing data else insert ( data , R . left ) recompute R. leftSubtreeHeight // Can be done in constant time ! else if( R . rightChild == null ) R. rightChild = new node containing data else insert ( data , R . right ) recompute R. rightSubtreeHeight // Can be done in constant time ! restoreAVLProperty (R) Observe that if we recurse the left subtree, then when that recursion finishes, we recompute the left subtree height but not the right subtree height (since we know the right subtree didn’t change!). Likewise, if we recurse right, then only the right subtree’s height need be recomputed when the recursive call returns (the left subtree didn’t change!). As the above algorithm indicates, the key is to recompute subtree heights in constant time. Let p be a node, and let l and r be p’s left and right children, respectively. As long as l and r’s subtree heights are correct, then the subtree heights for p can be recomputed in constant time. For example, if l.leftHeight and l.rightHeight are correct, then we can recompute p’s left subtree height as: max(l.leftHeight, l.rightHeight) + 1 Since we are adjusting subtree heights starting from the bottom level of the tree where the new node was inserted, we can correct subtree heights at each level in constant time as the recursion unwinds back up the tree because all children of the current node will already have correct subtree heights. It is important to note that, in addition to recomputing subtree heights as the recursive calls to insert unwind, it is also necessary to correct subtree heights whenever a rotation occurs. Rotations rearrange nodes, and change the heights of subtrees. For both the left and right rotations, there are exactly two nodes involved for which one subtree height has to be recomputed. Again, this can be done in constant time similar to as above. It will be up to you to figure out the exact details of adjusting the subtree height during rotations. Double rotations should pose no additional problems since they can be written in terms of two single rotations. Page 3 3 Your Tasks Question 1 (14 points): Implement a heap by writing a class called ArrayedHeap280 that extends the existing abstract class ArrayedBinaryTree280 and implements the Dispenser280 interface. The only methods you should need to write are a constructor, and the insert and deleteItem methods required by Dispenser280, but you can use additional private methods if you think it makes sense to do so. The algorithms for insertion and deletion are given in Section 2.1 of this document. Note that since you need to compare items in the heap to each other, you must write the generic type parameter of your class’ header so that it is required to be a subclass of Java’s Comparable interface. This is necessary to ensure that only items that implement the Comparable interface can be stored in the heap. As a consequence, you’ll have to make sure that your constructor initializes the instance variable items (inherited from ArrayedBinaryTree280) to an array of Comparable. If this is all done properly, then any item x in the heap can be compared to another item y using x.compareTo(y). A regression test is provided for you in the heaptests.txt. Copy the two functions therein into your ArrayedHeap280 class. You do not need to write your own test. The test functions will likely exhibit compiler errors if your class does not have the correct class header. Your implementation is highly likely to be correct if it passes the provided regression test. While you should always practice good commenting habits, we will not be grading javadoc or inline comments on this question. Question 2 (53 points): Implement an AVL tree ADT. The design of the class is up to you. You may choose to use as much or as little of lib280-asn4 as you desire (including extending existing classes, implementing existing interfaces, taking pieces of code for your own methods, or not using any of lib280-asn4 at all) but you will be graded on these choices, so make good choices. Regardless of your high-level design decisions, you can earn full marks for correctness of implementation as long as the following requirements are met: • Your implementation must support insertion of new elements, one at a time. Elements may be of any object type, but all elements in a single tree are the same type. • The implementation of insertion must be O(log n) in the worst case. This means you have to store subtree heights in the nodes (see previous section) to avoid incurring the linear-time cost of a recursive height method. Part marks will be given for solutions that are at worst O(n log n), but such a solution will receive a major deduction. No marks will be given for solutions where insertion and deletion is worse than O(n log n). • The tree must restore the AVL property after insertions using (double) left and right rotations. • Your ADT must have an operation for determining whether a given element is in the tree. • Your ADT must have an operation that deletes an element. The mechanism for specifying the item to delete is up to you. • The implementation of deletion must be O(log n) in the worst case (as insertion) and must restore the AVL property after deletions using (double) left and right rotations. Again, part marks will be given for solutions that are at worst O(n log n), but such a solution will receive a major deduction. No marks will be given for solutions where insertion and deletion is worse than O(n log n). • You must include a test program (in a main() method) that demonstrates the correctness of your implementation. The purpose of this test program is to demonstrate to the markers that your Page 4 ADT meets the above requirements. Your program’s output should be designed to convince the marker that your insertion, rotation, and lookup, and search methods work correctly. Note that the goals here are different from a normal “regression test”, so console output even when there are no errors is acceptable. For example, you can print out the tree, describe what operation is about to be performed, and then print the resulting tree. The onus is on you to use your test program to demonstrate that your implementation works.. Thus you should demonstrate cases that invoke all of the different kinds of rotations and special cases that might arise. • You may not modify any existing classes in lib280-asn4. But you may make new classes as you see fit. Hints and Notes • Start on this question early! It’s not that the solution is particularly difficult, but it requires planning. Make sure you give yourself ample time to attempt it, and ask for help if you get stuck. If you wait until the day before the due date begin, there is a high probability that you will not complete this question. You don’t need to finish early, but you should start planning early. Also keep in mind that partial solutions can earn partial marks. • Your early design choices can have an impact on how hard the implementation is (indeed this is true of any non-trivial software project!). Think things through before you begin coding. Sketch out the class architecture (UML diagrams are good for this!), and/or algorithms on paper first. • Steal the toStringByLevel method (found in LinkedSimpleTree280) and modify it so that prints the left and right subtree heights along with each node’s contents. This will help immensely with debugging because even if you implement insertions and rotations correctly, you’ll get incorrect results if the subtree heights are recorded incorrectly. This is because incorrect subtree heights will trigger rotations when none are actually needed, or prevent necessary rotations from occurring. • If you choose to use a cursor, your ADT need not have methods that allow the user full control over the cursor position (e.g. goFirst(), goForth(), before(), etc.). That is, your class does not need to implement LinearIterator280. • Make sure everything else is working correctly before you attempt the delete operation. If you design things well, the delete operations should be able to re-use all of the work you did on rotations for the insertion operation. Evaluation For this question, there will be marks awarded for suitable commenting of code, and for writing appropriate javadoc comments. For this question, marks will be awarded based on the quality of the design of your class(es). Your use of modularization, encapsulation, and choices when using or not using protected/private methods will be considered. That said, there is no need to be overly fancy. If appropriate, make use of existing classes in lib280-asn4, but consider your options before you start and think about which of the possible approaches will be easier to implement. There are marks are allocated to good commenting. This includes both inline comments and Javadoc comments for each method header and instance variable. The remaining marks will be for allocated for the correctness (as demonstrated by your unit test) and efficiency of the implementation of the insertion, lookup, and deletion operations. The detailed grading rubric can be found on Moodle. Page 5 4 Files Provided lib280-asn4.zip: Contains the ArrayedBinaryTree280 class that you will extend in Question 2. heaptests.txt: Functions for testing your ArrayedHeap280 implementation. 5 What to Hand In ArrayedHeap280.java: Your arrayed heap implementation. AVLTree280.java: Your AVL tree implementation. a4q3.txt: A copy of your AVL tree test program’s output, cut and pasted from the IntelliJ console window. Other .java files: Any other .java files that you might have created for the implementation of your AVL tree. Page 6
