You have been asked to write a program to count the number of times each word occurs in a text file, and print them grouped according to word length. Below is a sample text file on the left, and the expected output of your program on the right:

This is the first line, and this line is the ultimate line,

is: 2

the: 2

and: 1

this: 2

line: 3

first: 1

ultimate: 1

Note that words are counted ignoring case, and are printed in order of word length. In any group of words of the same length, the printout can be in any order (e.g. the and and are both printed before words of greater length, but they need not be in any specific relative sequence.) You choose to store the words in an AVL tree. Each node in the AVL tree has a word (with its count), and words (alphabetical) are the basis of the AVL ordering. a) Show the final AVL tree after all the words from the sample input file have been inserted. (Remember that words will be inserted one at a time as they are read in, but you only need to show the final tree, not all the intermediate trees). Make sure you show balance factors at all the nodes. There is only one correct AVL tree answer, following the AVL insertion algorithm you have learned in class.

b) If there are k distinct words, and n words in all (in the sample input file, k = 7 and n = 12), how much time will it take in the worst case (big O) to store all the words with counts? Assume that all word comparisons take constant time, and ignore the time taken to read a word from input.

c) What would be the worst case time (big O) to print the output, if the maximum word length is m? Describe the process, and clearly state the basic operations (ignore the time to actually write to disk). Clearly describe any additional data structures you may use to get the job done. Show your work in summing up the basic operations toward the final big O answer. (Assume that determining the length of a word takes constant time.)