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.