I recently have been working on a Trie in Java. I have looked at the related posts here on Code Review to try and enhance my code, but I do have some methods and constraints not present on other posts.
Objective
To efficiently implement a Trie data structure in Java that is fast, with low memory consumption.
Constraints
- I cannot add any variables to the
Nodeclass - No secondary data structure, other than arrays, can be used anywhere in the code
Bugs Identified
- Delete method only removes 1st node of word to be removed; Inserting "hazardous" and then inserting "hazardously", then deleting "hazardously" should remove the suffix, "ly", however delete only removes the "y" and leaves the "l" resulting, incorrectly, in "hazardousl"
Goal of post
- Suggest additional methods to implement
- Possible efficiency improvements
- Overall code improvement suggestion
Node Class
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
/********************************************************************************
* @author Evan Bechtol (ecb120030)
* <h1>Project: Trie Structure</h1>
* <p>Program builds and implements a Trie to manipulate a dictionary and spell-checker.
* Identifies the total amount of words currently present, can also delete and search
* for specific words.</p>
* @since 2015-3-06
* @see https://community.oracle.com/thread/2070706
* @see en.wikipedia.org/wiki/Trie
* @see logos.cs.uic.edu/340/assignments/Solutions/Graphicalwordpopup/cvelazqu/WordPop2/
* @see http://crunchify.com/a-simple-singly-linked-list-implementation-in-java/
*
********************************************************************************/
/*
* Node class is the container class for the Trie. Each child index represents one of the 26 letters of the
* English alphabet. Only lower-case letters are used, digits are not considered. outDegree represents the
* number of children that are initialized for that node.
*/
class Node {
private boolean terminal; //Designates character as end of word
private int outDegree; //Specifies character position in the word
private Node [] children; //Holds references to 26 potential character children
/*
* Constructor for root node
*/
Node () {
terminal = false;
outDegree = 0;
children = new Node[26];
// All children are set to null initially, they are populated as needed
for (int i = 0; i < 26; i++) {
children[i] = null;
}
}
/*
* Set the terminal value
*/
public void setTerminal (boolean terminal) {
this.terminal = terminal;
}
/*
* Set the outDegree of node
*/
public void setOutDegree (int outDegree) {
this.outDegree = outDegree;
}
/*
* If the node is not null, it returns that node
* else null is returned
*/
public Node getChild (char c) {
return children [c - 'a'];
}
/*
* Returns the outDegree of the current node
*/
public int getOutDegree () {
return outDegree;
}
/*
* Return the status of terminal variable.
* True = node is end of word
* False = not end of word
*/
public boolean getTerminal () {
return terminal;
}
/*
* Attempts to insert a word into the list
*/
public boolean insert (String word) {
char character = word.charAt(0);
int index = character - 'a';
if (!childExists(index)) {
children[index] = new Node ();
this.setOutDegree(++outDegree);
}
if (word.length() > 1) {
getChild(character).insert(word.substring(1));
}
else {
getChild(character).setTerminal(true);
return true;
}
return true;
}
/*
* Recursively traverse down the Trie until we reach the last character of the word
* and it's corresponding Node in the tree.
*/
public boolean delete (String word) {
char character = word.charAt(0);
int index = character - 'a';
if (!childExists(index)) {
return false;
}
// The last character in the word does not have children
if (getChild(character).getTerminal() && getChild(character).getOutDegree() == 0) {
this.children[index] = null;
this.setOutDegree(--outDegree);
return true;
}
// If there are more characters in the word, we keep traversing
if (word.length() > 1) {
getChild(character).delete(word.substring(1));
}
// There are no more letters in the word and it has children
else {
getChild(character).setTerminal(false);
}
return true;
}
/*
* Determines if the word is currently in the Trie
*/
public boolean isPresent (String word) {
char character = word.charAt(0);
int index = character - 'a';
// If the child does not exist, return false
if (!childExists(index)) {
return false;
}
if (childExists(index) && word.length() > 1) {
return getChild(character).isPresent(word.substring(1));
}
// We reach the end of the word
else if (getChild(character).getTerminal() && word.length() == 1) {
return true;
}
return false;
}
/*
* Determines whether a node is populated or not
* Returns true if it exists, false otherwise
*/
public boolean childExists (int index) {
return this.children[index] != null;
}
} // End Node
Trie Class
/*
* The Trie class is responsible for storing and manipulating the Trie structure. It utilizes the Node container class
* to carry out specific functions; insertion/deletion/searching
*/
class Trie {
private final Node root;
private int words; // Maintains number of words in the Trie
/*
* Default constructor for Trie
*/
Trie () {
root = new Node();
words = 0;
}
/*
* Returns the root of the Trie
*/
public Node getRoot () {
if (isEmpty()) {
return null;
}
return root;
}
/*
* Set the number of words in the Trie
*/
public void setWords (int numWords) {
this.words = numWords;
}
/*
* Returns number of words in the Trie
*/
public int membership () {
return words;
}
/*
* Returns false if word is already present, true otherwise
*/
public boolean insert (String word) {
if(!root.isPresent(word) && root.insert(word.toLowerCase())) {
this. setWords(++words);
return true;
}
return false;
}
/*
* Returns true if present, false otherwise
*/
public boolean isPresent (String word) {
return root.isPresent(word);
}
/*
* If word is present recursive delete is called,
* else the word is not present for deletion
*/
public boolean delete (String word) {
if (root.isPresent(word) && root.delete(word.toLowerCase())) {
this.setWords(--words);
return true;
}
return false;
}
/*
* Returns true if the Trie is completely empty
*/
public boolean isEmpty () {
return root == null;
}
/*
* Recursively iterates through all nodes and all children to print words
* that are present in the Trie
*/
public void listAll(Node current, String word) {
if (current.getTerminal() && current.getOutDegree() >= 1) {
System.out.println(word);
}
if(current.getTerminal() && current.getOutDegree() == 0){
System.out.println(word);
}
// Our child is not a word yet, we iterate though again
else {
// Iterate through all potential letters, looking for the next child
for(int i = 0; i < 26; ++i) {
if(!current.childExists(i)) {
continue;
}
// Our child exists and we recursively call listAll to get the word to print
// cast it as a char to get the character representation of the index value
else {
listAll(current.getChild((char)(i + 'a')), word + (char)(i + 'a'));
}
}
}
}
/*
* Identifies potential spelling errors in the word
*/
public void spellCheck (String word) {
if (!root.isPresent(word)) {
System.out.println ("Spelling mistake " + word);
}
}
} // End Trie
Test client
/*
* Test client for the Trie data structure
*/
public class EVBEP2 {
public static void main(String[] args) throws FileNotFoundException {
Trie trie = new Trie ();
// Used for accepting command line arguments
Scanner sc = new Scanner (System.in);
// Used for testing purposes
//Scanner sc = new Scanner(new File("p2in4.txt"));
String line = "";
boolean done = false;
// Loop runs as long as done != true
while (!done) {
line = sc.nextLine();
String [] tokens = line.split(" ");
switch (tokens[0]) {
// Print name followed by newline
case "N": {
System.out.println("Evan Clay Bechtol");
break;
}
// Add a word to the Trie
case "A": {
String word = tokens[1];
if (trie.insert(word)) {
System.out.println("Word inserted");
}
else {
System.out.println ("Word already exists");
}
break;
}
// Delete a specific word
case "D": {
String word = tokens[1];
if (trie.delete(word)) {
System.out.println("Word deleted");
}
else {
System.out.println("Word not present");
}
break;
}
// Search for a specific word
case "S": {
String word = tokens[1];
if (trie.isPresent(word)) {
System.out.println("Word found");
}
else {
System.out.println("Word not found");
}
break;
}
// Print number of words in the Trie
case "M": {
System.out.println ("Membership is " + trie.membership());
break;
}
/*
* Check the space separated sequence of words up to the end of the line
* for presence in the Trie and list any that are not present, one per line,
* each preceded by the phrase "Spelling mistake".
* Each line can be up to 200 characters long.
*/
case "C": {
// Get the number of usable indexes (word not used for anything here)
int index = 0;
for (@SuppressWarnings("unused") String word : tokens) {
index++;
}
// Now iterate through usable indexes and check for spelling errors
int i = 1;
while (i < index) {
trie.spellCheck(tokens[i]);
i++;
}
break;
}
// Print the elements in the Trie sorted alphabetically, one word per line.
case "L": {
trie.listAll(trie.getRoot(), "");
break;
}
// End of data file, print newline and exit
case "E": {
System.out.println();
done = true; // Break the loop, end the program
break;
}
} // End switch
} // End while
sc.close();
} // End main
} // End EVBEP2
