CSC 321: Data Structures
Fall 2013

HW5: Tries & Dynamic Structures

This assignment is to be completed independently (with help from the instructor, as needed). You may not look up existing solutions!

A trie is an interesting tree variant that utilizes structure sharing to save space when storing strings. Unlike a binary tree (where each node has at most two children), a node in a standard trie can have up to 26 children, corresponding to the letters of the alphabet. Within each node, a flag can be set to mark whether the path of letters leading to that node corresponds to a stored string. For example, the diagram below shows a trie that stores 6 words: A, ARM, ART, I, IS, and THE. In this diagram, (1) edges are labeled with their corresponding letters, (2) null edges are not shown, and (3) nodes with set flags are marked with an X.

An empty trie consists of a single, unmarked node whose edges are all null. As words are added to a trie, nodes must be created and linked using the appropriate edges corresponding to the letters.

You are to create a Trie class that implements this data structure. Your class must provide the following constructor and methods:

public Trie() // constructs an empty Trie public boolean add(String word) // attmepts to add word, returns true // if success (not already stored) public boolean contains (String word) // returns true if word is already // stored in the Trie public boolean containsPrefix(String pre) // returns true if pre is the prefix // of a word in the tree public int size() // returns the number of words stored public void clear() // clears the Trie

Your Trie implementation should be case-insensitive, so adding "foo" and "Foo" would result in a single entry. You may assume that the Strings to be stored in a Trie consist of letters only (no spaces or punctuation marks). As part of your Trie class definition, you will need to define an inner class to represent the nodes in a Trie (similar to the Node, DNode and TreeNode inner classes we have previously studied). Your TrieNode class should have two fields, a boolean (for the flag) and an array of 26 TrieNode references (for the edges).

For extra credit, you may implement other useful Trie methods, such as remove and iterator. Be sure to test your class thoroughly.

Fun Time

A trie can be used in any application that requires storing and searching a dictionary of words. It may or may not take more space than an ArrayList or LinkedList implementation (depending on the number and characteristics of the words stored). However, it does provide much faster searches: O(L) where L is the length of the string being searched for. Also, a trie make it just as easy to search for prefixes (i.e., sequences of characters that appear at the start of some word in the dictionary). A particular application where this is useful is searching a Boggle board for words.

Boggle (® Hasbro) is a game in which a 4x4 grid of letters is randomly chosen, and then the players try to identify as many words in that grid as possible. Words can be formed by any sequence of adjacent letters in the grid. For example, consider the following grid.

c k s z x o t h d g r n z n a m

The word "sock" is formed starting at the letter "s" in the top row, moving down diagonally to the "o", moving up diagonally to the "c", and finally moving right to the "k". Note that letters can be connected horizontally, vertically, and diagonally. The same occurrence letter may not be used more than once in the same word, however. Thus, "tot" is not a valid word in the above grid.

An implementation of a Boggle game has been provided for you in the form of the classes:

The BoggleBoard class uses a Trie object to store the dictionary of words and search for the board, testing character sequences to see if they are words or prefixes in the dictionary. Once you have your Trie class working, feel free to create a Boggle project (using your class and the provided files) and play the game.