In this assignment, we will implement some Red$-$Black tree methods to store phone contacts. The Red$-$Black tree will use a person's$$Name$$as the$$Key$$and the$$Contact$$as the$$Value$.$

Here a$$Contact$$will have two fields:

$*$ a$$phone number$$and

$*$ a$$country

An implementation is provided for that$$Contact$$class in$$RedBlackBSTTest$.$java$$so that the program can use it to store the contact information in a Red$-$Black Tree.$$Next$,$ you will need to complete the methods that throw$$UnsupportedOperationException$$in$$RedBlackBST$.$java. You can use the implementations from$$the reference book's implementation.

The input will be from a file that has been already uploaded. As the output, the program will print the number of nodes in the tree and the contact details using an in$-$order traversal.

Directions: Fill in the contact method in the RedBlackBSTTest.java file and the RedBlackBST method in the RedBlackBST.java file.

RedBlackBSTTest.java

import java.io$.$FileNotFoundException;

import java.io$.$IOException;

import java.nio.file.Paths;

import java.util.Scanner;

public class RedBlackBSTTest $\{$

class Contact $\{$

$//$ implement this class

$//$ add necessary instance variables

$//$ and constructor and accessors

$\}$

public static void main$($String$[]$ args$)\{$

RedBlackBST redblackTree $=$ new RedBlackBST$()$;

Scanner input $=$ null;

try $\{$

input $=$ new Scanner$($Paths$.$get$("$example$.$txt$"))$;

while $($input$.$hasNext$())\{$

String country $=$ input.next$()$;

String phone $=$ input.next$()$;

String name $=$ input.next$()$;

Contact contact $=$ new RedBlackBSTTest$().$new Contact$($country$,$ phone$)$;

redblackTree.put$($name$,$ contact$)$;

$\}$

System.out.printf$("$Size of the Red Black Tree:$\%$d$\%$n$",$ redblackTree.size$())$;

System.out.println$("$Red Black Tree keys in$-$order:"$)$;

for $($String s : redblackTree.keys$())\{$

Contact contact $=$ redblackTree.get$($s$)$;

System.out.printf$("\%-20$s $\%-10$s $\%-15$s$\%$n$",$ s$,$

contact.getCountry$(),$

contact.getPhone$())$;

$\}$

$\}$ catch $($FileNotFoundException e$)\{$

e$.$printStackTrace$()$;

$\}$ catch $($IOException e$)\{$

e$.$printStackTrace$()$;

$\}$

input.close$()$;

$\}$

$\}$

RedBlackBST.java

import java.util.NoSuchElementException;

public class RedBlackBST, Value$>\{$

private static final boolean RED $=$ true;

private static final boolean BLACK $=$ false;

private Node root; $//$ root of the BST

$//$ BST helper node data type

private class Node$\{$

private Key key; $//$ key

private Value value; $//$ associated data

private Node left, right; $//$links to left and right subtree

private boolean color; $//$ color of parent link

private int size; $//$ subtree count

public Node$($Key key, Value value, boolean color, int size$)\{$

this.key $=$ key;

this.value $=$ value;

this.color $=$ color;

this.size $=$ size;

$\}$

$\}$

$//$ initialize the empty tree

public RedBlackBST$()\{$

$\}$

$/*$

$*$ Node helper methods

$*/$

$//$ is the node red? false if the node is null.

private boolean isRed$($Node node$)\{$

throw new UnsupportedOperationException$("$Method not implemented yet."$)$;

$\}$

$//$ number of node is subtree rooted at node;

$//0$ if node is null

private int size$($Node node$)\{$

throw new UnsupportedOperationException$("$Method not implemented yet."$)$;

$\}$

$//$ returns the number of key$-$value pairs in the tree

public int size$()\{$

return size$($root$)$;

$\}$

$//$ is the tree empty?

public boolean isEmpty$()\{$

throw new UnsupportedOperationException$("$Method not implemented yet."$)$;

$\}$

$/*$

$*$ Standard BST search

$*/$

$//$ returns the value associated with the given key.

public Value get$($Key key$)\{$

if$($key $==$ null$)$

throw new IllegalArgumentException$("$Key cannot be null."$)$;

return get$($root$,$ key$)$;

$\}$

$//$ Value associated with the given key in subtree rooted

$//$ at node; null if no such key

private Value get$($Node node, Key key$)\{$

throw new UnsupportedOperationException$("$Method not implemented yet."$)$;

$\}$

$//$ Does this tree contains the given key?

public boolean contains$($Key key$)\{$

return get$($key$)!=$ null;

$\}$

$/*$

$*$ Red$-$Black tree insertion

$*/$

$//$ Inserts the specified key$-$value pair into the tree.

$//$ overwrites the old value with the new value if the tree

$//$ already contains the key.

$//$ Deletes the specified key from the tree if the value is null.

public void put$($Key key, Value value$)\{$

throw new UnsupportedOperationException$("$Method not implemented yet."$)$;

$\}$

$//$ insert the key$-$value pair in the subtree rooted at node

private Node put$($Node node, Key key, Value value$)\{$

throw new UnsupportedOperationException$("$Method not implemented yet."$)$;

$\}$

$/*$

$*$ Red$-$Black tree deletion

$*/$

$//$ Removes the smallest key and associated value from the tree

public void deleteMin$()\{$

throw new UnsupportedOperationException$("$Method not implemented yet."$)$;

$\}$

$//$ delete the key$-$value pair with the minimum key rooted at node

private Node deleteMin$($Node node$)\{$

throw new UnsupportedOperationException$("$Method not impleme