You are to implement a binary search tree and use it to store and retrieve articles. The tree will be sorted by keyword, and each node will contain an unordered linked list of Record objects which contain information about each article that corresponds to that keyword. 

A Data file which contains records to be read into the data structure.

Record.java: The Record" class will be the objects stored in the value for each keyword in the tree. This class also has a "next" pointer which provides the structure for the linked list. Objects of this type will be the value of each node in your search tree. This code should not be modified.

Test.java: This code performs reading from the data file as well as allowing test operations of your binary search tree. Performing changes to this file can be done to test particular cases, but this is for your benefit, since it will not be collected. The code provided will print the contents of the tree in inorder, which is alphabetical order. At each node of the tree, it will print the key word and then the titles of all the records in the list that you have created at that node. The test code also performs a few deletions and checks the result to ensure that delete() works correctly.

bst.java This file contains the basic shell for the data structure we will ask you to implement in this assignment. All functions that you will be asked to implement are marked with a \\TODO comment and are listed below with their expected operation. You will need private functions for implementing these recursively.

Node constructor: This function should initialize a record with keyword `k'. It will not require the other fields to be set because every Node construction will be updated either by directly modifying the children or by performing an update() to add a record to its linked list.

Node update(Record r): This function should add the Record r to the linked list for a particular keyword. You should add new Records to the front of the list.

insert(String keyword, FileData fd): This function includes code that turns the FileData fd into a Record recordToAdd. The function should insert recordToAdd to the node of keyword. If keyword is not in the tree, it should create a node.

contains(String keyword): This function should return true if the keyword keyword is in the tree.

get_records(String keyword): This function returns the linked list of Records associated with a given String keyword.

delete(String keyword): This function removes the node associated with the input string keyword. If no such node exists, the code should do nothing.

class bst{ Node root; private class Node{ // These attributes of the Node class will not be sufficient for those attempting the AVL extra credit. // You are free to add extra attributes as you see fit, but do not remove attributes given as it will mess with help code. String keyword; Record record; int size; Node l; Node r; private Node(String k){ // TODO Instantialize a new Node with keyword k.  } private void update(Record r){ //TODO Adds the Record r to the linked list of records. You do not have to check if the record is already in the list.  //HINT: Add the Record r to the front of your linked list. } } public bst(){ this.root = null; } public void insert(String keyword, FileData fd){ Record recordToAdd = new Record(fd.id, fd.author, fd.title, null); //TODO Write a recursive insertion that adds recordToAdd to the list of records for the node associated  //with keyword. If there is no node, this code should add the node. } public boolean contains(String keyword){ //TODO Write a recursive function which returns true if a particular keyword exists in the bst  return false; } public Record get_records(String keyword){ //TODO Returns the first record for a particular keyword. This record will link to other records  //If the keyword is not in the bst, it should return null. return null; } public void delete(String keyword){ //TODO Write a recursive function which removes the Node with keyword from the binary search tree.  //You may not use lazy deletion and if the keyword is not in the bst, the function should do nothing. } public void print(){ print(root); } private void print(Node t){ if (t!=null){ print(t.l); System.out.println(t.keyword); Record r = t.record; while(r != null){ System.out.printf("\t%s ",r.title); r = r.next; } print(t.r); } } }