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

private static class Node {
    private char keyContribution;
    private Node nextSibling;
    private Node nextChild;
}

Vyhledávací algoritmus

public class ValuelessTrie {
    private final Node root = new Node();

    // ...

    private Optional<Node> findNode(char[] key, boolean createMissingNodes) {
        Node temp = root;
        int level = 0;

        while (true) {
            if (temp.keyContribution == key[level]) {
                if (level == key.length - 1) {
                    // FOUND
                    return Optional.of(temp);
                } else {
                    // need to go further: deeper level
                    if (temp.nextChild == null) {
                        if (createMissingNodes) {
                            // need to create child
                            temp.nextChild = new Node();
                            temp.nextChild.keyContribution = key[level];
                        } else {
                            return Optional.empty();
                        }
                    }
                    level++;
                    temp = temp.nextChild;
                }
            } else {
                // need to go further: current level
                if (temp.nextSibling == null) {
                    if (createMissingNodes) {
                        // need to create sibling
                        temp.nextSibling = new Node();
                        temp.nextSibling.keyContribution = key[level];
                    } else {
                        return Optional.empty();
                    }
                }
                temp = temp.nextSibling;
            }
        }
    }
}

Vyhledávání prefixu

public boolean containsPrefix(char[] key) {
    return findNode(key, false).isPresent();
}

Uložení slova

public void add(char[] key) {
    findNode(key, true);
}

Reference