8.11 LAB: AVL tree Nth largest operation Step 1: Inspect the BSTNode.java and BinarySearch Tree.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 BinarySearch Tree class declaration for a binary search tree node in BinarySearch Tree.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 Binary Search Tree, respectively. Each class is implemented in a read only file. Classes Extended AVLNode and ExtendedAVLTree are declared, but implementations are incomplete. Both classes must be implemented in this lab. BinarySearch Tree BSTNode Read only, completed class implementation Incomplete class implementation AVLTree ExtendedAVLTree AVLNode ExtendedAVLNode 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: 20 7 10 42 4 10 2 19 30 30 1 55 2 Subtree key count 77 1 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() 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 Extended AVLNode classes. Do not implement Extended AVLTree'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: ⚫ TreeinsertCommand inserts keys into the tree ⚫ TreeRemoveCommand removes keys from the tree TreeVerifyKeysCommand verifies the tree's keys using an inorder traversal TreeVerifySubtreeCounts Command 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(log n)) getNthKey() 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(log n) time. 551800.4148644x37 LAB ACTIVITY 8.11.1: LAB: AVL tree Nth largest operation 0/10 Downloadable files LabProgram.java BSTNode.java AVLNode.java ExtendedAVLNode.java BinarySearchTree.java AVLTree.java ExtendedAVLTree.java BSTNodeVisitor.java TreeInsertCommand.java BSTNodeArrayListVisitor.java Tree RemoveCommand.java TreeVerifyKeysCommand.java , and TreeVerifySubtree Counts Command.java TreeTestCommand.java Download TreeGetNthCommand.java