CS310 Strie

Overview: Storing a Dictionary with a Tree

Strie is a tree data structure that stores a set of words in a very space efficient way. The following is an example of basic structures of a Strie and Strie nodes. see image.

To provide this unique capability of storing character strings, Stries need to follow some rules. Each node of a Strie, except the root node, contains a character and can have up to 26 children. Root node (and all other nodes) store(s) links to other nodes, one for each possible character in the English alphabet. Following is a sample Strie that has 4 words (bar, barn, bat, cat) stored in it. see image.

If you look carefully at the above Stries, you would notice some interesting properties that may help you in implementing this project! For example, since there are 26 possible slots for the children of a node and since the alphabet is in order, you will always find a particular character at a particular index! Also, words with common prefix share a common branch! Note that words sharing common prefixes may affect the implementation of some operations. For example, if you remove the word "bat", your Strie would look like the following picture. see image.

The character 't' does not exist in the Strie anymore under ba but it does still exist under ca for cat. In contrast, if you remove the word "bar", your Strie would look like following picture. Notice that the character r still exists in Strie, but it no longer marks the end of a word. see image.

You can use the Strie for many different purposes. For example, you can store words, look up a word, search for words having common prefix, search for similar words for a given query, and many more. To implement such a Strie, you need to complete all required classes, and possibly some (or all) optional classes depending on which functionality you want your Strie to provide.

Requirements

An overview of the requirements are listed below, please see the grading rubric for more details.

• Implementing the classes - You will need to implement required classes in the provided template files.
• Big-O - The template files provided to you contains instructions on the REQUIRED Big-O runtime for many methods. Your implementation of those methods should NOT have a higher Big-O.
• Style - You must follow the coding and conventions specified by the style checker.
• JavaDocs - You are required to write JavaDoc comments for all the required classes and methods.

Implementation/Classes

This project will be built using a number of classes representing the component pieces of the project. Here we provide a description of these classes. Template files are provided for each class in the project folder and these contain further comments and additional details.

Completed Class

• The StrieDemo Class (see StrieDemo.java) This class is done for you and you can use it to interact with a Strie you've created.

Required Classes

The StrieNode Class (see StrieNode.java) This class represents a single Strie node. It provides some methods required to manipulate a node. Check the included template file for all required methods and their corresponding big-O requirements.

The Strie Class (see Strie.java) This class implements the Strie data structure. It must use StrieNode objects for storing a node. It supports some basic Strie operations such as inserting a word, removing a word, searching for a word, and more.

Required methods:

• All methods in StrieNode class
• Strie class methods:
  • insert(String word) ): inserts a word in Strie
  • remove(String word) : removes a word from Strie
  • contains(String word): search the Strie for word
  • levelOrderTraversal(Strie myStrie): do a breadth first traversal
  • isEmptyStrie(Strie myStrie): check if your Strie is Empty
• In summary, all methods except the ones mentioned below are required.

Choose your own adventure methods:

• Implement one (or all) of the following methods. There is a maximum number of points you can earn with these methods (please see the Grading Rubric) no matter how many methods you implement. These methods are each fairly complex, but provide you with the practice you'll need to really understand this data structure.
  • getStrieWords(Strie myStrie): get all existing words in your Strie
  • getLongestPrefix(Strie myStrie, String query): get from Strie the longest prefix for a given query
  • getAllSuffixes(Strie myStrie, String query): suggest all words from your Strie for a given prefix (i.e., query)
  • getClosestMatch(Strie myStrie, String query): get from your Strie the closest match for a given word

Testing

• Some tests are provided for you in the main method of Strie class.
• You can run the simulation StrieDemo once everything is done.
  • Note: Testing via the simulation only is not a good idea. Some of the methods you need to write are not used by the simulation, but are still a graded part of the project.
• Make sure you're running the code style checker and JavaDoc style checker.