ExtendedRBTNode's constructor and GetSubtreeKeyCount$()$ member function are already implemented and should not be changed. Additional member functions 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 member functions in RedBlackTree and RBTNode must be overridden in ExtendedRedBlackTree and ExtendedRBTNode to keep each node's subtreeKeyCount correct. New functions can be added along with overridden functions, if desired.

Hint: Consider an UpdateSubtreeKeyCount$()$ member function for the ExtendedRBTNode class. The function requires each child node's subtreeKeyCount to be correct, and updates the node's subtreeKeyCount appropriately. Overridden functions in both ExtendedRBTNode and ExtendedRedBlackTree can call a node's UpdateSubtreeKeyCount$()$ function 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

TreeTestCommand is an abstract base class defined in TreeCommands.h$.$ A TreeTestCommand object is an executable command that operates on a binary search tree. Classes inheriting from TreeTestCommand are also declared in TreeCommands.h:

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 main.cpp contains three automated test cases. Each test executes a vector 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,$ verify that the first two tests in main.cpp pass. Then submit code and ensure that the first two unit tests pass.

Step $6$: Implement ExtendedRedBlackTree's GetNthKey$()$ member function

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

Implement an algorithm that uses the subtree key counts so that GetNthKey$()$ operates in worst case O$($log N$)$ time.