Datová struktura trie svůj název získala nejspíše kombinací slov retrieval a tree. Jedná se o strom, který umožňuje uchovávat páry klíč - hodnota a získávat hodnoty podle klíče. Klíčem však musí být řetězec. Nejprve je třeba definovat, co tvoří jeho uzly a hrany. Každý uzel reprezentuje jeden znak klíče a každý hrana jejich zřetězení. Klíč získáme jako cestu od kořene k zadanému uzlu.

Příklad

Dejme tomu, že chceme uložit hodnoty s klíčem baby, ban, damn, do.

diagram

Operace

add(key)
přidá klíč key
containsPrefix(key)
ověří, zda se mezi klíči nachází nějaký, který má zadaný klíč jako prefix (například klíč he je prefixem klíče hello).

Implementace

Deklarace uzlu

package ds.trie;

public interface Trie {
    /**
     * Returns the number of words stored in the trie.
     * @return number of words in the trie
     */
    default int numWords() {
        return numWords(new char[0]);
    }

    /**
     * Returns the number of prefixes stored in the trie.
     * @return number of prefixes in the trie
     */
    default int numPrefixes() {
        return numPrefixes(new char[0]);
    }

    /**
     * Checks if the trie contains the given key.
     * @param key key to check
     * @return TRUE if the key is present, FALSE otherwise
     */
    boolean containsWord(char[] key);

    /**
     * Checks if the trie contains the given key as prefix.
     * @param keyPrefix key prefix to check
     * @return TRUE if the key is present as prefix, FALSE otherwise
     */
    boolean containsPrefix(char[] keyPrefix);

    int numWords(char[] key);

    int numPrefixes(char[] key);

    /**
     * Adds key to the trie.
     * @param key key to add
     */
    void addWord(char[] key);

    // CONVENIENCE METHODS FOR STRINGS

    default void addWord(final String key) {
        addWord(key.toCharArray());
    }

    default boolean containsWord(final String key) {
        return containsWord(key.toCharArray());
    }

    default boolean containsPrefix(final String key) {
        return containsPrefix(key.toCharArray());
    }
}

Zdrojový kód Pokrytí testy

Datová struktura

package ds.trie;

public class GenericTrie implements Trie {
    private final Node root;

    public GenericTrie() {
        this.root = new Node(Character.MIN_VALUE, createNewCharacterToNodeMap());
    }

    @Override
    public boolean containsWord(final char[] key) {
        final Node found = lookup(key, false);
        return found != null && found.isWord();
    }

    @Override
    public boolean containsPrefix(final char[] keyPrefix) {
        final Node found = lookup(keyPrefix, false);
        return found != null;
    }

    @Override
    public int numWords(final char[] key) {
        final Node found = lookup(key, false);
        return found != null ? found.sizeWords() : 0;
    }

    @Override
    public int numPrefixes(final char[] key) {
        final Node found = lookup(key, false);
        return found != null ? found.sizePrefixes() : 0;
    }

    @Override
    public void addWord(final char[] key) {
        lookup(key, true).markAsWord();
    }

    private Node lookup(final char[] key, final boolean createNodes) {
        Node activeRoot = root;

        for (final char activeKeyFragment : key) {
            Node child = activeRoot.getChild(activeKeyFragment);

            if (child == null) {
                if (createNodes) {
                    // must create new child of the current node
                    child = new Node(activeKeyFragment, createNewCharacterToNodeMap());
                    activeRoot.putChild(child);
                } else {
                    // child is missing but we are not allowed to create it
                    return null;
                }
            }

            activeRoot = child;
        }

        return activeRoot;
    }

    private static CharacterToNodeMap createNewCharacterToNodeMap() {
        //return new CharacterToNodeHashMap('z' - 'a');
        return new CharacterToNodeArrayMap();
    }
}

Zdrojový kód Pokrytí testy

Tato implementace umožňuje vnitřní strukturu řešit různým způsobem.

První řešení využívá hash tabulku a je univerzální co do datových typů, zabírá však mnoho místa v paměti navíc.

package ds.trie;

import java.util.HashMap;
import java.util.Map;

public class CharacterToNodeHashMap implements CharacterToNodeMap {
    private final Map<Character, Node> nodes;

    public CharacterToNodeHashMap(final int expectedNumberOfChildren) {
        this.nodes = new HashMap<>(expectedNumberOfChildren);
    }

    @Override
    public Node get(final char keyFragment) {
        return nodes.get(keyFragment);
    }

    @Override
    public void put(final char keyFragment, final Node newNode) {
        nodes.put(keyFragment, newNode);
    }

    @Override
    public Iterable<Node> children() {
        return nodes.values();
    }
}

Zdrojový kód Pokrytí testy

Druhé řešení je mnohem úspornější, ale funguje pouze pro malá písmena latinky. Podobná řešení lze připravit i pro jiné množiny znaků s podobnou kardinalitou (ASCII a podobně).

package ds.trie;

import java.util.Arrays;
import java.util.Objects;

public class CharacterToNodeArrayMap implements CharacterToNodeMap {
    private final Node[] array;

    public CharacterToNodeArrayMap() {
        array = new Node['z' - 'a'];
    }

    @Override
    public Node get(final char keyFragment) {
        return array[charToIndex(keyFragment)];
    }

    @Override
    public void put(final char keyFragment, final Node newNode) {
        array[charToIndex(keyFragment)] = newNode;
    }

    @Override
    public Iterable<Node> children() {
        return () -> Arrays.stream(array).filter(Objects::nonNull).iterator();
    }

    private int charToIndex(final char keyFragment) {
        final int index = keyFragment - 'a';

        if (index < 0 || index >= array.length) {
            throw new IllegalArgumentException("Only supports lower case ASCII characters. Not this: " + keyFragment);
        }

        return index;
    }
}

Zdrojový kód Pokrytí testy

Reference