I am having trouble coming up with a predict function for my program.I am missing the predict function. I have coded up everything else. I have attached the assignment instruction and attached my code. I also have attched the instructors notes on the predict function,. Please come up with the predict function. Please use Java. Thanks.

Assigment:

Instructors Notes:

My Code in JAVA :

/*-----------------------------------Java implementation of Trie---------------------------------------------------------------*/

public class Trie { //----------------------------The Alphabet Size (# of symbols)----------------------------------------------------------// static final int ALPHABET_SIZE = 26; //--------------------------------The node of Trie-------------------------------------------------------------------// static class TrieNode { TrieNode[] children = new TrieNode[ALPHABET_SIZE]; //--------------------------------------isEndOfWord is true if the node represents the end of a word-------------------------------// boolean isEndOfWord; int count; TrieNode(){ isEndOfWord = false; for (int i = 0; i

//-----------------------------------------------------------This is the end of the program---------------------------------------------------------------------------//

Write a program that creates a Trie data structure. Well will use this data structure to main- tain stringx it has already seen. So each node in the trie will maintain four variables alue, is End, count, and children. The four are described as follows: value: is End: count: children: The alphabet value associated to this node (-2) A boolean value to determine whether this is the end of a word The number of times this node has been visited through An array of Nodes that are the children of that current Node The Trle data structure will be very similar to that of a Tree with a root Node that allows you to search through the data in the Trie. The Trie will need to be created as it's own object, this way you can instantiate a reference of the class Trie. The Trie will have the following methods you will need to implement: constructor: The constructor of the class insert(s: String): A method given a word as a parameter will insert it into the Trie. If the word already exists the count of every Node along the path will increase find(s: String): A method given a word as a parameter will check if the word exists in the Trie. the count of every Node along the path will not increase predict(s: String, n: int): A method given a partial word will return the top n likely words this word could be. predict (String key, int top) Example predict (th, 2 ) 1. Traverse from the root So in this example root to rode of the the u t child 2. with the highest count and conta Find the traversing. add it to 3. When you the results find and a node with us and Time keep traversing the len(results) - top 4. Repeat until s. If you reach a leat nade while traversing go buck a to the parent and redo from 2 except traverse the next highest 6. If you traverse the entre subfree and len (results)