$8\mathrm{.}11$ LAB: AVL tree Nth largest operation

Step $4$: Implement ExtendedAVLTree and ExtendedAVLNode

Each node in an ExtendedAVLTree must have a correct subtreeKeyCount after an insertion or removal operation. Determine which member functions in AVLTree and AVLNode must be overridden in ExtendedAVLTree and ExtendedAVLNode 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 ExtendedAVLNode class. The function requires each child node's subtreeKeyCount to be correct, and updates the node's subtreeKeyCount appropriately. Overridden functions in both ExtendedAVLNode and ExtendedAVLTree can call a node's UpdateSubtreeKeyCount$()$ function 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 $6$: Implement ExtendedAVLTree's GetNthKey$()$ member function $($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. #ifndef EXTENDEDAVLNODE$\_$H

#define EXTENDEDAVLNODE$\_$H

#include "AVLNode.h$"$

class ExtendedAVLNode : public AVLNode $\{$

private:

int subtreeKeyCount;

public:

ExtendedAVLNode$($int nodeKey$)$ : AVLNode$($nodeKey$)\{$

subtreeKeyCount $=1$;

$\}$

virtual int GetSubtreeKeyCount$()$ override $\{$

return subtreeKeyCount;

$\}$

$//$ Your code here

$\}$;

#endif