public abstract class BSTNodeVisitor { // Returns true to continue traversal, false to terminate public abstract boolean visit(BSTNode node); }

import java.io.PrintWriter;

// TreeTestCommand is the abstract base class for a command that tests some // aspect of a BinarySearchTree object public abstract class TreeTestCommand { public abstract boolean execute(BinarySearchTree tree, PrintWriter testFeedback); }

8.11 LAB: AVL tree Nth largest operation Step 1: Inspect the BSTNode.java and BinarySearchTree.java files Inspect the BSTNode class declaration for a binary search tree node in BSTNode.java. Access BSTNode.java by clicking on the orange arrow next to LabProgram.java at the top of the coding window. The BSTNode class has private fields for the key, parent reference, left child reference, and right child reference. Accessor methods exist for each. Inspect the BinarySearchTree class declaration for a binary search tree node in BinarySearchTree.java. The getNthKey( method is the only abstract method that exists. Step 2: Inspect other files related to the inheritance hierarchy Classes AVLNode and AVLTree inherit from BSTNode and BinarySearchTree, respectively. Each class is implemented in a read only file. Classes ExtendedAVLNode and ExtendedAVLTree are declared, but implementations are incomplete. Both classes must be implemented in this lab. Read only, completed class implementation Incomplete class implementation Step 3: Understand the purpose of the subtreeKeyCount variable The ExtendedAVLNode class inherits from AVLNode and adds one integer field, subtreeKeyCount. Each node's subtree key count is the number of keys in the subtree rooted at that node. Ex: y count ExtendedAVLNode's constructor and getSubtreeKeyCount() methods are already implemented and should not be changed. Additional methods are needed to ensure that subtreeKeyCount remains accurate. Step 4: Implement ExtendedAVLTree and ExtendedAVLNode Each node in an ExtendedAVLTree must have a correct subtreeKeyCount after an insertion or removal operation. Determine which methods in AVLTree and AVLNode must be overridden in ExtendedAVLTree and ExtendedAVLNode to keep each node's subtreeKeyCount correct. New methods can be added along with overridden methods, if desired. Hint: Consider an updateSubtreeKeyCount 0 method for the ExtendedAVLNode class. The method requires each child node's subtreeKeyCount to be correct, and updates the node's subtreeKeyCount appropriately. Overridden methods in both ExtendedAVLNode and ExtendedAVLTree can call a node's updateSubtreeKeyCount() method as needed. Once determinations are made, complete the implementation of both the ExtendedAVLTree and ExtendedAVLNode classes. Do not implement ExtendedAVLTree's getNthKey() in this step. getNthKey() requires correct subtree counts at each node. Step 5: Run tests in develop mode and submit mode TreeTestCommand is an abstract base class defined in TreeTestCommand.java. A TreeTestCommand object is an executable command that operates on a binary search tree. Classes inheriting from TreeTestCommand are declared in their respective files: - TreelnsertCommand inserts keys into the tree - TreeRemoveCommand removes keys from the tree - TreeVerifyKeysCommand verifies the tree's keys using an inorder traversal - TreeVerifySubtreeCountsCommand verifies that each node in the tree has the expected subtree key count - TreeGetNthCommand verifies that getNthKey() returns an expected value Code in LabProgram.java contains three automated test cases. Each test executes an ArrayList of TreeTestCommand objects in sequence. The third test includes TreeGetNthCommands and will not pass until the completion of Step 6 . The first two tests should pass after completion of step 4. Before proceeding to Step 6, run code in develop mode and ensure that the first two tests in LabProgram.java pass. Then submit code and ensure that the first two unit tests pass. Step 6: Implement ExtendedAVLTree's getNthKey() method (worst case O(logn) ) getNthKey0 must return the tree's nth-largest key. The parameter n starts at 0 for the smallest key in the tree. Ex: Suppose a tree has keys: 10,19,20,30,42,55,77 Then getNthKey (0) returns 10, getNthKey (1) returns 19,, getNthKey (5) returns 55, and getNthKey (6) returns 77. Determine an algorithm that uses the subtree key counts so that getNthKey ( operates in worst case O(logn) time. 459428.2988902.q3zqy7 \begin{tabular}{l|l} LAB & 8.11.1: LAB: AVL tree Nth largest operation \end{tabular} 0/10 Downloadable files , and File is marked as read only Current file: LabProgram.java - File is marked as read only Current file: BSTNode.java File is marked as read only Current file: AVLNode.java @override public void setLeft(BSTNode newleftchiLd) \{ // Call parent class's setLeft() first super.setLeft (newLeftchild); // Update height updateHeight (); 3 @override public void setRight(BSTNode newRightChild) \{ // Call parent class's setRight() first super.setRight (newRightChild); / / Update height updateHeight (); \} // Recalculate the current height of the subtree rooted at // the node, usually called after a subtree has been // modified. public void updateHeight() \{ // Get height of left and right subtrees int leftHeight = getLeftHeight () ; int rightHeight = getRightHeight () ; // Assign height with greater of the two, plus one height = ((leftHeight > rightHeight) ? leftHeight : rightHeight +1 ; \} Current file: ExtendedAVLNode.java - Load default template... File is marked as read only Current file: BinarySearchTree.java File is marked as read only Current file: AVLTree.java - return true; QOverride protected boolean removeNode(BSTNode nodeToRemove) \{ return removeAVLNode((AVLNode) nodeToRemove); public AVLTree() \{ // Note: Parent class's constructor does all needed work Q publicide int getNthKey (int n ) \{ // Note: The ExtendedAVLTree.java implementation of // getNthKey() should override this. return 0 ; \} Current file: ExtendedAVLTree.java - Load default template... File is marked as read only Current file: BSTNodeVisitor.java - File is marked as read only Current file: BSTNodeArrayListVisitor.java - File is marked as read only Current file: TreeTestCommand.java - File is marked as read only Current file: TreelnsertCommand.java - File is marked as read only Current file: FileismarkedasreadonlyCurrentfile: File is marked as read only Current file: File is marked as read only Current file: 8.11 LAB: AVL tree Nth largest operation Step 1: Inspect the BSTNode.java and BinarySearchTree.java files Inspect the BSTNode class declaration for a binary search tree node in BSTNode.java. Access BSTNode.java by clicking on the orange arrow next to LabProgram.java at the top of the coding window. The BSTNode class has private fields for the key, parent reference, left child reference, and right child reference. Accessor methods exist for each. Inspect the BinarySearchTree class declaration for a binary search tree node in BinarySearchTree.java. The getNthKey( method is the only abstract method that exists. Step 2: Inspect other files related to the inheritance hierarchy Classes AVLNode and AVLTree inherit from BSTNode and BinarySearchTree, respectively. Each class is implemented in a read only file. Classes ExtendedAVLNode and ExtendedAVLTree are declared, but implementations are incomplete. Both classes must be implemented in this lab. Read only, completed class implementation Incomplete class implementation Step 3: Understand the purpose of the subtreeKeyCount variable The ExtendedAVLNode class inherits from AVLNode and adds one integer field, subtreeKeyCount. Each node's subtree key count is the number of keys in the subtree rooted at that node. Ex: y count ExtendedAVLNode's constructor and getSubtreeKeyCount() methods are already implemented and should not be changed. Additional methods are needed to ensure that subtreeKeyCount remains accurate. Step 4: Implement ExtendedAVLTree and ExtendedAVLNode Each node in an ExtendedAVLTree must have a correct subtreeKeyCount after an insertion or removal operation. Determine which methods in AVLTree and AVLNode must be overridden in ExtendedAVLTree and ExtendedAVLNode to keep each node's subtreeKeyCount correct. New methods can be added along with overridden methods, if desired. Hint: Consider an updateSubtreeKeyCount 0 method for the ExtendedAVLNode class. The method requires each child node's subtreeKeyCount to be correct, and updates the node's subtreeKeyCount appropriately. Overridden methods in both ExtendedAVLNode and ExtendedAVLTree can call a node's updateSubtreeKeyCount() method as needed. Once determinations are made, complete the implementation of both the ExtendedAVLTree and ExtendedAVLNode classes. Do not implement ExtendedAVLTree's getNthKey() in this step. getNthKey() requires correct subtree counts at each node. Step 5: Run tests in develop mode and submit mode TreeTestCommand is an abstract base class defined in TreeTestCommand.java. A TreeTestCommand object is an executable command that operates on a binary search tree. Classes inheriting from TreeTestCommand are declared in their respective files: - TreelnsertCommand inserts keys into the tree - TreeRemoveCommand removes keys from the tree - TreeVerifyKeysCommand verifies the tree's keys using an inorder traversal - TreeVerifySubtreeCountsCommand verifies that each node in the tree has the expected subtree key count - TreeGetNthCommand verifies that getNthKey() returns an expected value Code in LabProgram.java contains three automated test cases. Each test executes an ArrayList of TreeTestCommand objects in sequence. The third test includes TreeGetNthCommands and will not pass until the completion of Step 6 . The first two tests should pass after completion of step 4. Before proceeding to Step 6, run code in develop mode and ensure that the first two tests in LabProgram.java pass. Then submit code and ensure that the first two unit tests pass. Step 6: Implement ExtendedAVLTree's getNthKey() method (worst case O(logn) ) getNthKey0 must return the tree's nth-largest key. The parameter n starts at 0 for the smallest key in the tree. Ex: Suppose a tree has keys: 10,19,20,30,42,55,77 Then getNthKey (0) returns 10, getNthKey (1) returns 19,, getNthKey (5) returns 55, and getNthKey (6) returns 77. Determine an algorithm that uses the subtree key counts so that getNthKey ( operates in worst case O(logn) time. 459428.2988902.q3zqy7 \begin{tabular}{l|l} LAB & 8.11.1: LAB: AVL tree Nth largest operation \end{tabular} 0/10 Downloadable files , and File is marked as read only Current file: LabProgram.java - File is marked as read only Current file: BSTNode.java File is marked as read only Current file: AVLNode.java @override public void setLeft(BSTNode newleftchiLd) \{ // Call parent class's setLeft() first super.setLeft (newLeftchild); // Update height updateHeight (); 3 @override public void setRight(BSTNode newRightChild) \{ // Call parent class's setRight() first super.setRight (newRightChild); / / Update height updateHeight (); \} // Recalculate the current height of the subtree rooted at // the node, usually called after a subtree has been // modified. public void updateHeight() \{ // Get height of left and right subtrees int leftHeight = getLeftHeight () ; int rightHeight = getRightHeight () ; // Assign height with greater of the two, plus one height = ((leftHeight > rightHeight) ? leftHeight : rightHeight +1 ; \} Current file: ExtendedAVLNode.java - Load default template... File is marked as read only Current file: BinarySearchTree.java File is marked as read only Current file: AVLTree.java - return true; QOverride protected boolean removeNode(BSTNode nodeToRemove) \{ return removeAVLNode((AVLNode) nodeToRemove); public AVLTree() \{ // Note: Parent class's constructor does all needed work Q publicide int getNthKey (int n ) \{ // Note: The ExtendedAVLTree.java implementation of // getNthKey() should override this. return 0 ; \} Current file: ExtendedAVLTree.java - Load default template... File is marked as read only Current file: BSTNodeVisitor.java - File is marked as read only Current file: BSTNodeArrayListVisitor.java - File is marked as read only Current file: TreeTestCommand.java - File is marked as read only Current file: TreelnsertCommand.java - File is marked as read only Current file: FileismarkedasreadonlyCurrentfile: File is marked as read only Current file: File is marked as read only Current file