Problem 2 - Indexing Text with an AVL Tree - 30 points

Fill in the class FileAvl.java such that it indexes the words contained in a text file. The constructor of the FileAvl object should take in the file name as a parameter. It will then go through the input file line by line. For each line, it extracts each word, and inserts that word along with its line number into an AVL tree. Each element of the AVL tree should contain a unique word and a java.util.LinkedList of line numbers where that word occurs.

Add the following functionality to the AvlTree class by modifying the file:

Make sure the elements in the AvlTree are pairs of a word and a linked list storing line numbers. The relative order of elements in the data structure should depend on the word only. To do this I recommend adding a LinkedList object to the existing AVLNode class. You will also need to edit the add method insert method to take both a word and a line number. In this particular case its also not necessary for AVLTree to be generic, so you may remove generics and make the class simply an AvlTree of String objects.

Give the following functionality to your FileAvl class:

Write the method public void indexWord(String word, int line) that adds an occurrence of the word word in line line to the AvlTree instance of the FileAvl object. If a word already exists in the AVL Tree, simply add the new line number to the existing node. If a word appears on the same line twice, it should only have one entry in the list for that line. You may assume that word and line are valid inputs to the function.

Write the method public List getLinesForWord(String word) that looks up a word and returns a list of lines in which it occurs for a given FileAVL object. If the word does not exist in the AvlTree, return an empty list.

Write the method public void printIndex() the prints out each unique word that is stored in the AvlTree along with a list of line numbers in which that word appears, in alphabetical order. The output format should be as given below. Any deviation from the prescribed format may result in point deductions.