$\backslash$table$[[$Screenshot $2024-03-11$ at $6\mathrm{.}03\mathrm{.}53$ PM$,$Screenshot $2024-03-11$ at $6\mathrm{.}04\mathrm{.}01$ PM$,$Screenshot $2024-03-11$ at $6\mathrm{.}04\mathrm{.}38$ PM$],[,,]]$Extend BSTreeMap with another class called RBTreeMap. The red$-$black tree is a balanced binary search tree. It is comprised of RBNodes. The RBTreeMap and RBNode classes are shown in the attachment.

Use the files provided to get started $($RBTreeMap$.$java, RBNode.java$).$Test your work with JUnit test cases. It is up to you to test your work thoroughly.

A fully working remove method is important. It must at least pass testRemove$01()$supplied in the JUnit file.

Create a zip file with just RBTreeMap.java inside, not any other files. Of course, that means that you cannot change anything in those other classes.

FILE $1$: RBTreeMap.java contains:

$/**$

$*$ Class that implements a red$-$black tree which implements the MyMap interface.

$*$ @version $1\mathrm{.}2\mathrm{.}1$ March $5,2024$

$*/$

public class RBTreeMap, V$>$ extends BSTreeMap

implements MyMap $\{$

$/**$

$*$ Creates an empty red$-$black tree map.

$*/$

public RBTreeMap$()\{\}$

$/**$

$*$ Creates a red$-$black tree map from the array of key$-$value pairs.

$*$ @param elements an array of key$-$value pairs

$*/$

public RBTreeMap$($Pair$[]$ elements$)\{$

insertElements$($elements$)$;

$\}$

$/**$

$*$ Creates a red$-$black tree map of the given key$-$value pairs. If

$*$ sorted is true, a balanced tree will be created via a divide$-$and$-$conquer

$*$ approach. If sorted is false, the pairs will be inserted in the order

$*$ they are received, and the tree will be rotated to maintain the red$-$black

$*$ tree properties.

$*$ @param elements an array of key$-$value pairs

$*/$

public RBTreeMap$($Pair$[]$ elements, boolean sorted$)\{$

if $(!$sorted$)\{$

insertElements$($elements$)$;

$\}$ else $\{$

root $=$ createBST$($elements$,0,$ elements.length $-1)$;

$\}$

$\}$

$/**$

$*$ Recursively constructs a balanced binary search tree by inserting the

$*$ elements via a divide$-$snd$-$conquer approach. The middle element in the

$*$ array becomes the root. The middle of the left half becomes the root's

$*$ left child. The middle element of the right half becomes the root's right

$*$ child. This process continues until low $>$ high, at which point the

$*$ method returns a null Node.

$*$ All nodes in the tree are black down to and including the deepest full

$*$ level. Nodes below that deepest full level are red. This scheme ensures

$*$ that all paths from the root to the nulls contain the same number of

$*$ black nodes.

$*$ @param pairs an array of pairs sorted by key

$*$ @param low the low index of the array of elements

$*$ @param high the high index of the array of elements

$*$ @return the root of the balanced tree of pairs

$*/$

protected Node createBST$($Pair$[]$ pairs, int low, int high$)\{$

$//$ TODO

$\}$

$/**$

$*$ Associates the specified value with the specified key in this map. If the

$*$ map previously contained a mapping for the key, the old value is replaced

$*$ by the specified value.

$*$ @param key the key with which the specified value is to be associated

$*$ @param value the value to be associated with the specified key

$*$ @return the previous value associated with key, or null if there was no

$*$ mapping for key

$*/$

@Override

public V put$($K key, V value$)\{$

$//$ TODO

$\}$

$/**$

$*$ Removes the mapping for a key from this map if it is present.

$*$ @param key key whose mapping is to be removed from the map

$*$ @return the previous value associated with key, or null if there was no

$*$ mapping for key

$*/$

public V remove$($K key$)\{$

$//$ TODO, otherwise return null.

$\}$

$/**$

$*$ Fixup method described on p$.339$ of CLRS$,4$e$.$

$*/$

private void insertFixup$($RBNode z$)\{$

$//$ TODO

$\}$

$/**$

$*$ Fixup method described on p$.351$ of CLRS$,4$e$.$

$*/$

private void deleteFixup$($RBNode x$)\{$

$//$ TODO, optionally

$\}$

$/**$

$*$ Left$-$rotate method described on p$.336$ of CLRS$,4$e$.$

$*/$

private void leftRotate$($Node x$)\{$

$//$ TODO

$\}$

$/**$

$*$ Right$-$rotate method described on p$.336$ of CLRS$,4$e$.$

$*/$

private void rightRotate$($Node x$)\{$

$//$ TODO

$\}$

$\}$