<title>Solution</title>

**

Dictionary Tree Assignment - Matthew Jones

**

Note that this was origionally done in gitlab and is simply coppied across so only the latest version is here.

Explanation of each method:

• void insert(String word)

  • This method simply checked that the word was not already in the tree and then called the insert(String word, int popularity) method with the word and a popularity of 0 since none was specified.

• void insert(String word, int popularity)

  • This method recursively added the word to the tree and once there was only one letter left to add it would set the popularity in the dictionary tree responding to the last letter marking it as the end of a word and marking the popularity.
  • If any part of the word was already in the tree it would instead go down the path until it was no longer already in the tree or the end of the word had been reached and then overwrite the popularity.

• boolean remove(String word)

  • This method would first recursively go down the tree until it reached the word it was given, if the word wasn’t reached it would return false and exit as the word isn’t there to be removed.
  • If the end of the word was reached and it was marked as a word (has a popularity) it would check if the word could be deleted without effecting the rest of the tree.
  • If it could (the tree had no children) then the method would return true informing the recursive call that called it that it was safe to remove the tree from its list of children. That tree would then return true if it also had no children and wasn’t itself marked as the end of a word informing the tree above it can be removed or false if not.

• boolean contains(String word)

  • This method works by following the branches down the tree letter by letter recursively, if the letter is not found in the map children the false is returned.
  • Once the word is down to the final letter true is only returned if the letter is marked as the end of a word (It has a popularity).

• Optional <String> predict(String prefix)

  • This method works by building the word and traversing the tree at the same time using recursion.
  • If the prefix is not empty yet then the tree still needs to be traversed to the end of the prefix if at any point during this it can’t an empty optional will be returned.
  • While traversing the tree the letter of the prefix that has been traversed is added to the word.
  • If the prefix is empty it will get the first character from the map and choose that as the next letter of the word since there is no popularity to be considered in this method.
  • Once there are no more children in the tree the method will return the word it has built as long as it is at least as long as the prefix it was given this is to ensure that the word is actually a word.

• String longestWord()

  • This method works by finding the tree with the biggest height out of all the children of the tree and then adding the tree’s character to the word before traversing further.
  • This ensures the word is the longest in the tree as the higher the tree the longer the word.

• List<String> allWords()

  • This method makes use of the recursive helper method List<String> buildWords(List<String> words, String word)
  • The helper method holds a list to contain the words and a string to build the words.
  • Firstly it checks if the letter its currently at is a word and if it is it will add the word(the string) to the list.
  • Then it calls itself on each child continuing the building and preserving the current list by assigning its result to the list.
  • In the event of an empty tree there will be no children to loop through and the empty list given as a parameter will be returned avoiding the use of null.

• List predict(String prefix, int n)

  • This method uses the helper method predictRec that is almost the same as predict but with an additional parameter.
  • This String allows for the prefix to be remembered as the tree is traversed
  • While the prefix isn’t empty the method goes down the tree returning an empty list if it cant.
  • Once the tree has been traversed the to the end of the prefix the buildPop method comes in. This method returns a TreeMap with the words coming after the prefix and their popularity.
  • With this TreeMap the n most popular words (if there are that many) can be found easily and inserted into the list with the original prefix appended to the front of them.
  • That list is then returned.

• <A> A fold(BiFunction<DictionaryTree, Collection<A>, A> f)

  • To implement the fold I made a collection in the form of an ArrayList and added each child to the collection after calling fold on them.
  • The method returns the result of applying the function to the collection for the final result.

• int numLeaves()

  • The method is implemented using fold
  • It returns the sum of the results in the collection + 1 if the Tree is a leaf (has no children) and simply just the sum of the results in the collection if not.

• int maximumBranching()

  • The method is implemented using fold
  • It returns the highest value out of the number of children the tree has and the highest result from the collection. If there are none then it will return the highest between the the size of its children and 0.

• int height()

  • The method is implemented using fold
  • It returns 1 + the sum of the results in the collection (the height of the rest of the tree)
  • If there are no results in the rest of the tree it returns 0 (1 + -1)

• int size()

  • The method is implemented using fold
  • returns 1 + the sum of the results in the collection (the size of the rest of the tree)

  Using a tree for word prediction

  • Advantages

    • Possible in logarithmic time compared to linear time of a normal algorithm.
    • It only looks at words that have the prefix in them.
    • Just simply retrieving the words is faster.

  • Disadvantages

    • all words with that prefix are found first as its not a ordered list so if you only want the top two words there is much more computation if there are 10000 words with that prefix than going down a ordered list of all words looking for words with that prefix.
    • The Tree is less efficient if your looking for a small number of words and/or are using a common prefix.