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:
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
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
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
Be sure to test your class thoroughly.
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
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.
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:
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.