$8\mathrm{.}12$ LAB: Red$-$black 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 RBTNode and RedBlackTree inherit from BSTNode and BinarySearchTree, respectively. Each class is implemented in a read only file.

Classes ExtendedRBTNode and ExtendedRedBlackTree are declared, but implementations are incomplete. Both classes must be implemented in this lab.ExtendedRBTNode'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 ExtendedRedBlackTree and ExtendedRBTNode

Each node in an ExtendedRedBlackTree must have a correct subtreeKeyCount after an insertion or removal operation. Determine which methods in RedBlackTree and RBTNode must be overridden in ExtendedRedBlackTree and ExtendedRBTNode 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 ExtendedRBTNode class. The method requires each child node's subtreeKeyCount to be correct, and updates the node's subtreeKeyCount appropriately. Overridden methods in both ExtendedRBTNode and ExtendedRedBlackTree can call a node's updateSubtreeKeyCount$()$ method as needed.

Once determinations are made, complete the implementation of both the ExtendedRedBlackTree and ExtendedRBTNode classes. Do not implement ExtendedRedBlackTree'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 i

Program output displayed here

Test $1-$ insertion and getSubtreeKeyCount$()$

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]$

FAIL: Node with key $10$ has a subtree key count of $1,$ but the expected subtree key count is $2$

PASS: Node with key $19$ has a subtree key count of $1$

FAIL: Node with key $20$ has a subtree key count of $1,$ 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 $1,$ but the expected subtree key count is $4$

FAIL: Node with key $55$ has a subtree key count of $1,$ but the expected subtree key count is $2$

PASS: Node with key $77$ has a subtree key count of $1$

Test $2-$ insertion, removal, and getSubtreeKeyCount$()$

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]$

FAIL: Node with key $9$ has a subtree key count of $1,$ but the expected subtree key count is $2$

PASS: Node with key $14$ has a subtree key count of $1$

FAIL: Node with key $19$ has a subtree key count of $1,$ but the expected subtree key count is $4$

PASS: Node with key $23$ has a subtree key count of $1$

FAIL: Node with key $30$ has a subtree key count of $1,$ but the expected subtree key count is $11$

PASS: Node with key $53$ has a subtree key count of $1$

FAIL: Node with key $58$ has a subtree key count of $1,$ but the expected subtree key count is $3$

PASS: Node with key $67$ has a subtree key count of $1$

FAIL: Node with key $75$ has a subtree key count of $1,$ but the expected subtree key count is $6$

FAIL: Node with key $86$ has a subtree key count of $1,$ but the expected subtree key count is $2$

PASS: Node with key $98$ has a subtree key count of $1$

Test $3-$ insertion, removal, getSubtreeKeyCount$(),$ 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)$ returned $0,$ but expected key is $66$

Summary:

Test $1$: FAIL

Test $2$: FAIL

Test $3$: FAIL

help pass test $1-3$ cannot figure it out