Introduction

A Map is a type of collection that associates a key with a value. The mapping of keys to values can be accomplished using different underlying data structures. In this three$-$part assignment, you will be working with two such data structures and then using them to implement a Map. One is called a Linked List and the other is called a Tree.

A tree data structure can be defined recursively as a collection of nodes $($starting at a root node$),$ where each node is a data structure consisting of a value, together with references to nodes $($the "children"$),$ with the constraints that no reference is duplicated, and none points to root. A Binary Search Tree $($BST$)$ is a specific type of tree where each node can only have up to two children, and all of the data values in the left subtree of any node is always less than the node value and all of the data values in the right subtree of any node is always to the right of the node value.

In part III, you will be implementing a BST$,$ and then creating a Map that uses the BST to store and retrieve entries. As before, your Map should only use the BST by calling its methods. It should not touch inner variables like root or create node objects itself. That is the BST$\text{'}$s job to do internally.

Since the key$-$value pairs stored in the map could be of any type, we will be using Generics to implement all our classes. For example, we could have $<$Andrew$,1>$ as a key$-$value pair $($which is of type $)$ and we could also have $<432,34>$ as a key$-$value pair $($which is of type $).$ Hence, it is important that we provide a way to reuse the same code with different inputs. Generics enable types $($classes and interfaces$)$ to be parameters when defining classes, interfaces and methods. Much like the more familiar formal parameters used in method declarations, type parameters provide a way for you to re$-$use the same code with different inputs. The difference is that the inputs to formal parameters are values, while the inputs to type parameters are types.

Note: You are NOT allowed to use any built$-$in Java data structures for any part of this assignment.

Program and Starter Code

You are being provided with starter code which is an interface representing a Tree. You can find it in the course public folder $.$ It contains the signatures of the methods that you need to implement. Do not change Tree.java. You will also need Map.java from previous parts of this project.

BST$.$java inner class Node

You will need to create BST$.$java. It will declare a class BST$,($declared as BST implements Tree $.)$ This ensures that all data stored in your BST will have the compareTo method. When you begin writing the BST class, you will first need to define its own inner class Node $($declared as public class Node implements Tree.Node $.)$ You will need to add fields $($such as the left child, right child, and parent$)$ and possibly other methods to make it behave as a BST node. It will need to implement the following methods:

public Node$($ T value $)$

The constructor for Node. It should initialize any necessary fields.

public void setValue$($ T value $)$

Sets the value of this node to the given parameter.

public T getValue$()$

Gets the value of this node. Required for testing.

public Node getLeft$()$

Gets the left child of this node. Required for testing.

public Node getRight$()$

Gets the right child of this node. Required for testing.

public Node getParent$()$

Gets the parent of this node. Required for testing.

BST$.$java

Note: Your code may generate warnings about "unchecked call to compareTo" in BST$.$java. You can put @SuppressWarnings$("$unchecked$")$ before the signature of any methods that use compareTo to suppress these warnings. We are bending some Java rules, so the compiler will warn you of that unless you use the above annotation.

You also have to implement the following methods for the BST class:

public BST$()$

The constructor for BST$.$ It should initialize any necessary fields.

public Node getRoot$()$

Returns the root of the BST$.$ Required for testing.

public boolean add$($ T value $)$

Appends the specified value to the correct location in this BST$.$ You should use the compareTo method of the BST$\text{'}$s nodes' data when comparing to o$.($You should not call o$.$compareTo$($node$.$value$),$ but node.value.compareTo$($o$)$ for nodes' values in the tree.$)$ Should not add duplicate items to the BST$.$

public String toString$()$

Returns a string representation of this BST using indentation to represent each "level" of the tree. The root should be the furthest left when the string is printed, its children should be indented by $6$ spaces, their children by $12$ spaces, etc. Each node other than the root should be labeled as L for left children and R for right children. For example:

L even

the

L undo

R word

L zag

R zig

R zoo

public void clear$()$

Removes all of the elements in this map.