$13\mathrm{.}12$ LAB: Red$-$black tree Nth largest operation

Step $1$: Inspect the BSTNode.py and BinarySearchTree.py files

Inspect the BSTNode class declaration for a binary search tree node in BSTNode.py$.$ Access BSTNode.py by clicking on the orange arrow next to main.py at the top of the coding window. The BSTNode class has attributes for the key, reference to the parent, reference to the left child, and reference to the right child. Accessor methods exist for each.

Inspect the BinarySearchTree class declaration for a binary search tree node in BinarySearchTree.py$.$ The get$\_$nth$\_$key$()$ 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.

Six class names are shown in boxes. White boxes representing read only, completed class implementations. Four white boxes exist: BinarySearchTree, RedBlackTree, BSTNode, and RBTNode. Yellow boxes represent incomplete class implementations. Two yellow boxes exist: ExtendedRedBlackTree and ExtendedRBTNode. Arrows between boxes indicate inheritance. ExtendedRedBlackTree inherits from RedBlackTree, RedBlackTree inherits from BinarySearchTree, ExtendedRBTNode inherits from RBTNode, and RBTNode inherits from BSTNode.

Step $3$: Understand the purpose of the subtree$\_$key$\_$count variable

The ExtendedRBTNode class inherits from RBTNode and adds one integer attribute, subtree$\_$key$\_$count. Each node's subtree key count is the number of keys in the subtree rooted at that node. Ex:

Sample red$-$black tree with subtree key counts shown outside each node. Root node is black, has key$=20,$ and subtree$\_$key$\_$count$=7.$ Root's left child is black, has key$=10,$ and subtree$\_$key$\_$count$=2.$ Root's right child is red, has key$=42,$ and subtree$\_$key$\_$count$=4.$ Node $10\text{'}$s right child is red, has key$=19,$ and subtree$\_$key$\_$count$=1.$ Node $42\text{'}$s left child is black, has key$=30,$ and subtree$\_$key$\_$count$=1.$ Node $42\text{'}$s right is black, has key$=55,$ and subtree$\_$key$\_$count$=2.$ Node $55\text{'}$s right child is red, has key$=77,$ and subtree$\_$key$\_$count$=1.$

ExtendedRBTNode's constructor and get$\_$subtree$\_$key$\_$count$()$ methods are already implemented and should not be changed. Additional methods are needed to ensure that subtree$\_$key$\_$count remains accurate.

Step $4$: Implement ExtendedRedBlackTree and ExtendedRBTNode

Each node in an ExtendedRedBlackTree must have a correct subtree$\_$key$\_$count 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 subtree$\_$key$\_$count correct. New methods can be added along with overridden methods, if desired.

Hint: Consider an update$\_$subtree$\_$key$\_$count$()$ method for the ExtendedRBTNode class. The method requires each child node's subtree$\_$key$\_$count to be correct, and updates the node's subtree$\_$key$\_$count appropriately. Overridden methods in both ExtendedRBTNode and ExtendedRedBlackTree can call a node's update$\_$subtree$\_$key$\_$count$()$ method as needed.

Once determinations are made, complete the implementation of both the ExtendedRedBlackTree and ExtendedRBTNode classes. Do not implement ExtendedRedBlackTree's get$\_$nth$\_$key$()$ in this step. get$\_$nth$\_$key$()$ 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 TreeCommands.py$.$ A TreeTestCommand object is an executable command that operates on a binary search tree. Classes inheriting from TreeTestCommand are also declared in TreeCommands.py:

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 get$\_$nth$\_$key$()$ returns an expected value

Code in main.py contains three automated test cases. Each test executes a list 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 main.py pass. Then submit code and ensure that the first two unit tests pass.

Step $6$: Implement ExtendedRedBlackTree's get$\_$nth$\_$key$()$ method $($worst case O$($log n$))$

get$\_$nth$\_$key$()$ 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 get$\_$nth$\_$key$(0)$ returns $10,$ get$\_$nth$\_$key$(1)$ returns $19,...,$ get$\_$nth$\_$key$(5)$ returns $55,$ and get$\_$nth$\_$key$(6)$ returns $77.$

Determine an algorithm that uses the