9
\$\begingroup\$

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 Node class
  • 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
\$\endgroup\$
5
\$\begingroup\$

In the Node's constructor you can omit the call to

for (int i = 0; i < 26; i++) {
    children[i] = null;
}  

because by initializing the children array with children = new Node[26]; the items in the array are null anyway.

I find it odd that you restrict the children array to 26 elements, but I see that you want to store the alphabet in there. But what about Unicode characters ?.

If it is allowed to add an overloaded constructor passing in a different upper bound of the children array, you should consider to to so.

Node (int numberOfChildren) {
    terminal  = false;
    outDegree = 0;
    children  = new Node[numberOfChildren];
}

which could be called from the parameterless constructor like

Node () {
    this(26);
}  

Also the javadoc / class summary is misleading. English is not my first language, but I assume in the english alphabet ther are only 26 letters.


You should do some validation on the passed in parameters. E.g. in the insert() method, if one passes null or an empty string, either a NullPointerException or an ArrayIndexOutOfBoundsException would be thrown.


If a method returns a boolean, one would expect that there are cases where the method will return false too. A method which only ever returns true like the insert() method does not need a return value and could be void.


If you need a value which is retrieved by calling a method like word.charAt(0) you should retrieve the value once and store it in variable.


The Trie's getRoot() method does not need to check isEmpty() and also the isEmpty() method is not implemented correctly, because it won't ever return false because root is final and will be set in the constructor and can't be changed afeterwards ( setting to null).

So a better approach would be to check inside the isEmpty() method if any word had been added like

public boolean isEmpty () {
    return !root.getTerminal();
}  

whereas I would suggest to extract magical numbers like this to meaningful constants.


Comments should describe why something is done. Let the code speak for itself about what is done by using meaningful and descriptive names for classes, methods and variables.

Comments like

// If the child does not exist, return false
if (!childExists(index)) {
    return false;
}  

are superfluous, because they don't add any value to the code.


The test client has some flaws which should be mentioned here too.

Assume a user will enter S for searching for a word but doesn't add anything else. Your application would exit with an ArrayIndexOutOfBoundsException. You need to check for tokens.length() before you access tokens[1].


\$\endgroup\$
7
  • \$\begingroup\$ Thanks for the great input! I have corrected the constructor in my code (not edited on post), the "27" letters was a typo :P I was having some problems with my insert method; where if the last return statement was set to false, the method was always returning false, even if it had correctly inserted the word. I haven't figured out how to correct that yet. I also corrected the word.charAt(0) problem prior to your post (Updated in code here). \$\endgroup\$ Mar 9 '15 at 13:56
  • \$\begingroup\$ For what case should the insert() method return false ? \$\endgroup\$
    – Heslacher
    Mar 9 '15 at 14:00
  • \$\begingroup\$ Well, none really. The isPresent() method checks the structure before insert() is even called. So, if there were a case that would cause it to return false, it would never be called in the first place. A constraint not mentioned above was that the insert, isPresent, and delete methods must contain the return type and signature listed above. \$\endgroup\$ Mar 9 '15 at 14:01
  • \$\begingroup\$ I just adjusted my code to account for 'ArrayIndexOutOfBoundsException', I also removed superfluous commenting, and finally adjusted the isEmpty() method in my Trie class. :) Thank you for your great feedback \$\endgroup\$ Mar 9 '15 at 14:44
  • \$\begingroup\$ Quick question for you... I opted to use getters/setters to not expose the data of the class, but felt that they really could have been omitted. What is your opinion on this? \$\endgroup\$ Mar 9 '15 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.