The class named BTreeNode is defined for you and is not to be modified. The BTreeNode class contains the

following data members $($with T being the data type of the keys and M being the B$-$Tree's order$)$:

bool leaf $$ a bool value that is true if the BTreeNode is a leaf node

int keyTally $$ an int value that is the number of key values currently stored in the BTreeNode

T keys$[$M$-1]$ an array of type T $($the key type stored in the BTreeNode$)$ that contains the key values

BTreeNode $*$pointers$[$M$]$ an array of pointers to the children BTreeNode instances $($if any$)$

There are also associated methods for these data members.

The class named BTree is also defined $--$ you will supply methods for this class as described here:

$$ Define a BTree method bool insertKey$($T newKey$)$ that will do part of the job in inserting the value

newKey into the BTree. Your method will navigate to the appropriate leaf node to insert the new

value, then try to insert the value by updating the data members in the BTreeNode as appropriate.

Remember than the key values in a BTreeNode must be kept in ascending order, so shifting the

values within the keys and pointers array is important! NOTE: If a leaf BTreeNode is determined to

be full, then all your method should do is call the supplied splitNode method $($which actually doesn't

do anything except print to the screen that the node is full and needs to be split!$)$ In this case, your

method should return the bool value that the splitNode method returns when called $($which will be

false, because there's no room to insert the key!$).$ A successful insertion of the new key value should

result in your method returning true.

$$ Define a BTree method bool deleteKey$($T oldKey$)$ that will do part of the job in deleting the value

oldKey from the BTree. This method will navigate to a node where oldKey is found. If the node is

not a leaf node, then simply call the supplied mergeNodes method $($which actually doesn't do

anything except print to the screen that removing the node requires more than just deleting the

value!$).$ If the value is in a leaf BTreeNode, then delete the value by updating the data members in

the leaf BTreeNode as appropriate. If this makes the leaf BTreeNode contain too few values, then

call the supplied mergeNodes method $($which$,$ again, doesn't do anything except print to the screen

and return false$).$ If the oldKey is not found in the tree, then the method should return false.

Note than the key values in a BTreeNode must be kept in consecutive indexes of the arrays, so

shifting the values within the keys and pointers array is important! If a BTreeNode ends up being

less than half full, then your method should call the supplied mergeNodes method $($which actually

doesn't do anything except print to the screen that the node is less than half full and needs to be

merged!$)$ In this case, your method should NOT remove the value and instead return the bool value that the mergeNodes method returns when called $($which is false$).$

HINT: You might want to consider using a recursive helper function for deleteKey, and maybe for

insertKey as well. See the supplied printBTree and printBTreeRecursive methods to see how such a

recursive helper function can be used to navigate the BTree. Such methods have already been

defined in the H file for your use $$ you are not required to use them, however.