0
\$\begingroup\$

Ok, code reviewers, I want you to pick my code apart and give me some feedback on how I could make it better or more simple.

public class Trie {

    private static final int ASCII = 256;

    private TrieNode root;

    public Trie () {
        root = new TrieNode();
    }

    private static class TrieNode {
        TrieNode[] alphabets;
        char ch;
        String word;
        String meaning;

        public TrieNode() {
            this.alphabets = new TrieNode[ASCII];
        }

        public TrieNode (char ch) {
            this.alphabets = new TrieNode[ASCII];
            this.ch = ch;
        }
    }


    public void add (String word, String meaning) {
        TrieNode node = root;
        char[] ch = word.toCharArray();

        for (char c : ch) {
            if (node.alphabets[c] == null) {
                node.alphabets[c] = new TrieNode(c);
            }
            node = node.alphabets[c];
        }
        node.word = word;
        node.meaning = meaning;
    }

    public String getMeaning (String word) {
        TrieNode node = root;
        char[] ch = word.toCharArray();

        for (char c : ch) {
            node = node.alphabets[c];
            if (node == null) {
                return null;
            }
        }
        return node.meaning;
    }

    /**
     * Deletes all its children, but does not delete itself.
     */
    public void prune (String string) {
        TrieNode node = root;
        char[] ch = string.toCharArray();

        for (char c : ch) {
            node = node.alphabets[c];
            if (node == null) {
                return;
            }
        }
        node.alphabets = new TrieNode[ASCII];
        return;
    }

    public void print() {
        printWhole(root);
    }

    private void printWhole(TrieNode node) {
        if (node == null) {
            return;
        }
        if (node.word != null) {
            System.out.println("Word: " + node.word + " Meaning: " + node.meaning);
        }
        for (int i = 0; i < ASCII; i++) {
            printWhole(node.alphabets[i]);
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.add("mouse", "rat");
        trie.add("cop", "police");
        trie.add("cope", "endure");

        System.out.println("Expected rat, Actual: " + trie.getMeaning("mouse"));
        System.out.println("Expected police, Actual: " + trie.getMeaning("cop"));
        System.out.println("Expected endure, Actual: " + trie.getMeaning("cope"));
        System.out.println("Expected null, Actual: " + trie.getMeaning("co"));

        trie.print();

        trie.prune("cop");

        System.out.println("Expected police, Actual: " +trie.getMeaning("cop"));
        System.out.println("Expected null, Actual: " +trie.getMeaning("cope"));

        trie.print();
    }
}
\$\endgroup\$
  • \$\begingroup\$ What is the code doing?? \$\endgroup\$ – Gnanz Sep 30 '13 at 5:32
  • 3
    \$\begingroup\$ It is hopefully being a Trie. One thing I would say right away is that using arrays is not common in modern java. Replace your arrays with more powerful data structures like lists or maps, or include comments on why you don't do that -- Maybe in this case it doesn't make sense, but explain so. Just noting that arrays are much less common now that java has generics. \$\endgroup\$ – scott_fakename Sep 30 '13 at 7:06
  • 1
    \$\begingroup\$ I know that this post is old, but thought the feedback would still be useful. You should not be storing the word itself in the node, This goes against the structure of the Trie itself. The idea is that each node should hold a specific letter, and together the nodes chain to make a word. \$\endgroup\$ – Evan Bechtol Mar 11 '15 at 13:18
4
\$\begingroup\$

The TrieNode[] alphabets can probably be changed to a Map<Character, TrieNode>.

This would have some important advantages:

  • First, you would not consume all characters domain space (256 in your sample code) unless you actually have nodes defined for all of them.
  • Second, if you use a HashMap or LinkedHashMap as implementation, the search algorithm is pretty fast, you won't have to iterate over the entire collection to find an element since the search is based on hashes.
  • Third, it will make it simpler to improve your code when you want to support other languages out there using more than just 256 characters.
| improve this answer | |
\$\endgroup\$

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.