I'm working a school lab assignment and I'm a bit frustrated with AVL trees and I'm a bit lost at how to make all my tests pass for the assignment.I'm supposed to implement ExtendedAVLTree's getNthKey() method (worst case O(log n)) and 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. I was hoping for advice or a way to approach this assignment so that I can make these tests pass. I will my code that I have for it. There are other files for this assignment (ex. AVLTree & AVLNode which get extended/overidden below)- but the only ones I can edit are the two classes listed below. I don't want to post all the code if it is not needed but if additonal is needed for ref I can provide it and the unit tests. Hopefully this is enough information to help me get advice on how to solve the rest of this assignment. Also advice for cleaner code is also much appreciated (I'm a beginner)
ExtendedAVLNode
public class ExtendedAVLNode extends AVLNode {
private int subtreeKeyCount;
public ExtendedAVLNode(int nodeKey) {
super(nodeKey);
subtreeKeyCount = 1;
}
@Override
public int getSubtreeKeyCount() {
return subtreeKeyCount;
}
public void updateSubtreeKeyCount() {
subtreeKeyCount = 1; // Start with 1 for self
if (getLeft() != null)
subtreeKeyCount += ((ExtendedAVLNode) getLeft()).getSubtreeKeyCount();
if (getRight() != null)
subtreeKeyCount += ((ExtendedAVLNode) getRight()).getSubtreeKeyCount();
}
}
ExtendedAVLTree.java
public class ExtendedAVLTree extends AVLTree {
@Override
protected BSTNode makeNewNode(int key) {
return new ExtendedAVLNode(key);
}
@Override
protected void insertNode(BSTNode node) {
super.insertNode(node);
updateSubtreeKeyCounts(root);
}
@Override
protected boolean removeNode(BSTNode nodeToRemove) {
boolean removed = super.removeNode(nodeToRemove);
if (removed) {
updateSubtreeKeyCounts(root);
}
return removed;
}
// Recursively update subtreeKeyCount for all nodes starting from the given node
private void updateSubtreeKeyCounts(BSTNode node) {
if (node != null) {
((ExtendedAVLNode) node).updateSubtreeKeyCount();
updateSubtreeKeyCounts(node.getLeft());
updateSubtreeKeyCounts(node.getRight());
}
}
@Override
public int getNthKey(int n) {
return getNthKey(root, n);
}
// Helper method to get nth-largest key starting from a given node
private int getNthKey(BSTNode node, int n) {
if (node == null)
return 0; // Return 0 for invalid input or empty tree
int rightCount = node.getRight() != null ? ((ExtendedAVLNode) node.getRight()).getSubtreeKeyCount() : 0;
if (n == rightCount)
return node.getKey();
else if (n < rightCount)
return getNthKey(node.getRight(), n);
else
return getNthKey(node.getLeft(), n - rightCount - 1);
}
}
(errors/results)
1:Unit test
Test feedback
Inserting keys: 10, 20, 30, 55, 42, 19, 77
PASS: Inorder key verification
Expected: [10, 19, 20, 30, 42, 55, 77]
Actual: [10, 19, 20, 30, 42, 55, 77]
PASS: Node with key 10 has a subtree key count of 2
PASS: Node with key 19 has a subtree key count of 1
FAIL: Node with key 20 has a subtree key count of 6, but the expected subtree key count is 7.
PASS: Node with key 30 has a subtree key count of 1
FAIL: Node with key 42 has a subtree key count of 3, but the expected subtree key count is 4.
PASS: Node with key 55 has a subtree key count of 2
PASS: Node with key 77 has a subtree key count of 1
2:Unit test (Test insertion, removal, and subtree key counts)
Inserting keys: 86, 75, 23, 30, 98, 67, 53, 9, 19, 58, 14
PASS: Inorder key verification
Expected: [9, 14, 19, 23, 30, 53, 58, 67, 75, 86, 98]
Actual: [9, 14, 19, 23, 30, 53, 58, 67, 75, 86, 98]
PASS: Node with key 9 has a subtree key count of 2
PASS: Node with key 14 has a subtree key count of 1
FAIL: Node with key 19 has a subtree key count of 3, but the expected subtree key count is 4.
PASS: Node with key 23 has a subtree key count of 1
PASS: Node with key 30 has a subtree key count of 11
PASS: Node with key 53 has a subtree key count of 1
PASS: Node with key 58 has a subtree key count of 3
PASS: Node with key 67 has a subtree key count of 1
FAIL: Node with key 75 has a subtree key count of 7, but the expected subtree key count is 6.
PASS: Node with key 86 has a subtree key count of 2
PASS: Node with key 98 has a subtree key count of 1
3:Unit test (Test insertion, subtree key counts, and getNthKey() with two distinct trees)
---- Tree 1 of 2 ----
Inserting keys: 88, 38, 98, 28
PASS: Inorder key verification
Expected: [28, 38, 88, 98]
Actual: [28, 38, 88, 98]
PASS: Node with key 28 has a subtree key count of 1
PASS: Node with key 38 has a subtree key count of 2
FAIL: Node with key 88 has a subtree key count of 3, but the expected subtree key count is 4.
PASS: Node with key 98 has a subtree key count of 1
---- Tree 2 of 2 ----
Inserting keys: 21, 64, 32, 91, 87, 66, 15, 88, 58, 20, 67, 82, 19, 44, 51
PASS: Inorder key verification
Expected: [15, 19, 20, 21, 32, 44, 51, 58, 64, 66, 67, 82, 87, 88, 91]
Actual: [15, 19, 20, 21, 32, 44, 51, 58, 64, 66, 67, 82, 87, 88, 91]
PASS: Node with key 15 has a subtree key count of 1
PASS: Node with key 19 has a subtree key count of 3
PASS: Node with key 20 has a subtree key count of 1
PASS: Node with key 21 has a subtree key count of 8
PASS: Node with key 32 has a subtree key count of 1
FAIL: Node with key 44 has a subtree key count of 3, but the expected subtree key count is 4.
PASS: Node with key 51 has a subtree key count of 1
PASS: Node with key 58 has a subtree key count of 2
FAIL: Node with key 64 has a subtree key count of 13, but the expected subtree key count is 15.
PASS: Node with key 66 has a subtree key count of 1
PASS: Node with key 67 has a subtree key count of 3
PASS: Node with key 82 has a subtree key count of 1
PASS: Node with key 87 has a subtree key count of 6
PASS: Node with key 88 has a subtree key count of 1
PASS: Node with key 91 has a subtree key count of 2
4:Unit test (Test insertion, removal, subtree key counts, and getNthKey()
Inserting keys: 10, 58, 66, 18, 34, 96, 5, 48, 73, 62, 36, 16, 23, 99, 92, 95, 46, 97
PASS: Inorder key verification
Expected: [5, 10, 16, 18, 23, 34, 36, 46, 48, 58, 62, 66, 73, 92, 95, 96, 97, 99]
Actual: [5, 10, 16, 18, 23, 34, 36, 46, 48, 58, 62, 66, 73, 92, 95, 96, 97, 99]
FAIL: getNthKey(11) should have returned 66, but instead returned 34
5:Unit test (Test insertion, multiple removals, subtree key counts, and getNthKey()
Inserting keys: 88, 38, 98, 28, 48, 12, 9, 73, 61, 47, 51, 66
PASS: Inorder key verification
Expected: [9, 12, 28, 38, 47, 48, 51, 61, 66, 73, 88, 98]
Actual: [9, 12, 28, 38, 47, 48, 51, 61, 66, 73, 88, 98]
PASS: Node with key 9 has a subtree key count of 1
PASS: Node with key 12 has a subtree key count of 3
PASS: Node with key 28 has a subtree key count of 1
PASS: Node with key 38 has a subtree key count of 7
PASS: Node with key 47 has a subtree key count of 1
PASS: Node with key 48 has a subtree key count of 3
PASS: Node with key 51 has a subtree key count of 1
FAIL: Node with key 61 has a subtree key count of 13, but the expected subtree key count is 12.
PASS: Node with key 66 has a subtree key count of 1
PASS: Node with key 73 has a subtree key count of 2
FAIL: Node with key 88 has a subtree key count of 3, but the expected subtree key count is 4.
PASS: Node with key 98 has a subtree key count of 1
Assignment Steps (for ref of what the assignment expects) 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:
Sample AVL tree with subtree key counts shown outside each node. Root node has key=20 and a subtreeKeyCount=7. Root's left child has key=10 and subtreeKeyCount=2. Root's right child has key=42 and subtreeKeyCount=4. Node 10's left child has key=19 and subtreeKeyCount=1. Node 42's left child has key=30 and subtreeKeyCount=1. Node 42's right has key=55 and subtreeKeyCount=2. Node 55's right child has key=77 and subtreeKeyCount=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 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:
TreeInsertCommand 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(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.
I tried debugging myself and looking for ways to approach this problem, the code is far along in the assignment I'm just stuck on the last parts.