How Do You Implement a Trie In Java?
There was a request for some Java assignment help today that involved tries, and so I decided to do a blog post about them. A trie is a data structure that is a tree with multiple children per node (26 children per node, one for each letter). So to store test, it does
t → e → s → t. To check if a word exists in the trie, it gets the root node and finds the corresponding node for each letter, if there is no node for any of the letters then the word does not exist, and on the last letter, it checks to see if it is a valid ending and if it is then the word exists. The code below is missing any checks for invalid words and does not make sure the input is all lowercase letters, you may want to extend it.
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Arrays;
import java.util.Scanner;
public class Trie {
private Trie[] next;
private boolean end;
public Trie() {
next = new Trie[26];
}
public void add(String word) {
int index = word.charAt(0) - 'a';
Trie root = next[index];
if (root == null) {
root = new Trie();
next[index] = root;
}
if (word.length() == 1) {
root.end = true;
} else {
root.add(word.substring(1));
}
}
public boolean contains(String word) {
if (word.length() == 0) return end;
int index = word.charAt(0) - 'a';
Trie root = next[index];
if (root == null) return false;
return root.contains(word.substring(1));
}
public static void main(String[] args) {
Trie trie = new Trie();
try (BufferedReader br = new BufferedReader(new FileReader("words_alpha.txt"))) {
String line;
while ((line = br.readLine()) != null) {
trie.add(line);
}
} catch (Exception e) {
System.out.println("Exception:" + e);
}
Scanner input = new Scanner(System.in);
String word = "";
while (!word.equalsIgnoreCase("quit")) {
System.out.print("Enter word to check: ");
word = input.next().toLowerCase().trim();
System.out.println(trie.contains(word));
}
}
}
If you were the student who submitted the assignment for a quote, don’t worry someone else will be working on the implementation for you, but I thought this was an interesting subject for a blog post. We can handle assignments involving complex data structures with ease, or even implement a full game using Java graphics and key and mouse interaction, with multiple sound channels. Each assignment we do is always implemented from scratch to make sure that any anti-plagiarism detection software can not catch the assignment. Given this is a fairly simple assignment, it is hard to make an alternate version, but rather than using the boolean end, we could use an array of 27 elements, and use the extra entry to indicate that we have a valid word. Another possible change is rather than using an array, to use a HashTable where the key is the letter, which would have the advantage of being able to support Unicode so you could have foreign words as well as proper nouns included.
You can rely on ProgrammingAssignmentHelper.com to provide any Java assignment help you may have.