Search Trie implementation

Question

I have written a code StringTrie.java implemented through interface Trie.java:

package il.ac.tau.cs.sw1.trie;
import java.util.Set;

/**
 * Represents a generic trie data structure, where K is the type of keys that
 * are saved in the trie, and V is the type of values that can be saved for each
 * key.
 */
public interface Trie<K, V> {

    /**
     * Adds the input key to the data structure with the given value. If the key
     * is invalid for this trie (implementation-dependent) an exception is
     * thrown.
     */
    void addKey(K key, V value);

    /**
     * Searches all the keys in the trie structure with the given prefix. If
     * there are no such keys - an empty Set is returned. Otherwise, all the values saved
     * for these keys are added to the output value set. If the prefix is invalid for this
     * trie (implementation-dependent) an exception is thrown.
     * 
     * @post the return value is not null
     */
    Set<V> searchByPrefix(K prefix);

}

along with StringTrieNode.java implemented through TrieNode.java:

package il.ac.tau.cs.sw1.trie;

import java.util.List;
import java.util.Set;

/**
 * Represents a node in a generic trie, where K is the type of keys that are
 * saved in the trie, and V is the type of values that can be saved for each
 * key.
 */
public interface TrieNode<K, V> {

    /**
     * Adds the key suffix to this trie node, with the given value, by
     * recursively adding the suffix of this suffix to the relevant child node.
     * 
     * @pre suffix is a valid suffix for this trie (implementation-dependent)
     * @post if the key ends in this trie node, the input value is added to the
     *       set of values returned by getValues().
     */
    void addSuffix(K suffix, V value);

    /**
     * Returns the set of values for keys that end in this node
     */
    Set<V> getValues();

    /**
     * Returns the child trie node such that the input suffix is saved in it or
     * in its descendant
     * 
     * @pre suffix is a valid suffix for this trie (implementation-dependent)
     * @post if no key with such a suffix exists in the trie, or if suffix ends
     *       in the current node, return null; otherwise return the relevant
     *       child node
     */
    TrieNode<K, V> getNext(K suffix);

    /**
     * Returns a list with all the child trie nodes of this node. The list may
     * contain null values.
     * 
     * @post $ret != null
     */
    List<TrieNode<K, V>> getNexts();

}

now, I have implemented all functions (correctly, I hope) and now I only have a problem with Set searchByPrefix(K prefix);, I can't find an algorithm that works + I have the problem with the constructor. the user call it like this: Trie names = new StringTrie<>();so the first has to be there. but only the second initials the fields. is it OK?

There's a full implementation [here](http://stackoverflow.com/a/9320920/823393). — OldCurmudgeon, May 12 '14 at 18:47

score 1 · Answer 1 · answered May 12 '14 at 19:00

I would recommend you to use a existing implementation.

Here is a very good examples that I already used multiple times:

https://github.com/rkapsi/patricia-trie

Here is an example to use the prefix search:

PatriciaTrie<String, String> trie = new PatriciaTrie<String, String>(StringKeyAnalyzer.CHAR);
trie.put("prefix1", value);
trie.put("prefix2", value);

map = trie.prefixMap("prefix");

Search Trie implementation

1 Answers1