Trie

Trie 是一種 k-ary search tree。它可以儲存大量的字串，並且提供有效率的字串搜尋。

Trie & TrieNode

Trie 一般會有兩個資料結構，一個是 Trie，另一個是 TrieNode。TrieNode 被用來建構整個 tree，而 Trie 只會有一個。TrieNode.terminates 表示從 root 到該 node 的 path 是一個 word。另外，TrieNode.character 不是必要的，因為可以從 parent 的 children 就可以得知該 node 代表的字元。root 不代表任何字元。

public class Trie {
    private final TrieNode root = new TrieNode();

    public Trie(ArrayList<String> list) {
        for (String word : list) {
            root.addWord(word);
        }
    }

    public Trie(String[] list) {
        for (String word : list) {
            root.addWord(word);
        }
    }

    public boolean contains(String prefix, boolean exact) {
        TrieNode lastNode = root;
        for (int i = 0; i < prefix.length(); i++) {
            lastNode = lastNode.getChild(prefix.charAt(i));
            if (lastNode == null) {
                return false;
            }
        }
        return !exact || lastNode.terminates();
    }

    public boolean contains(String prefix) {
        return contains(prefix, false);
    }

    public void addWord(String word) {
        root.addWord(word);
    }
}

public class TrieNode {
    private final HashMap<Character, TrieNode> children = new HashMap<>();
    private boolean terminates = false;
    private char character;

    public TrieNode() {
    }

    public TrieNode(char character) {
        this.character = character;
    }

    public char getChar() {
        return character;
    }

    public void addWord(String word) {
        if (word == null || word.isEmpty()) {
            return;
        }

        char firstChar = word.charAt(0);
        TrieNode child = getChild(firstChar);
        if (child == null) {
            child = new TrieNode(firstChar);
            children.put(firstChar, child);
        }

        if (word.length() > 1) {
            child.addWord(word.substring(1));
        } else {
            child.setTerminates(true);
        }
    }

    public TrieNode getChild(char c) {
        return children.get(c);
    }

    public boolean terminates() {
        return terminates;
    }

    public void setTerminates(boolean terminates) {
        this.terminates = terminates;
    }
}

複雜度

建立字典所需的時間複雜度為 ，其中 為 word[i] 的長度。

搜尋和插入一個 word 所需的時間複雜度為 。

空間複雜度為所有 node 的數量，所以是 。

範例

下面的範例顯示，在插入 word 時，Trie 內部的變化。綠色表示該 node 的 terminates 設為 true。

參考

• Gayle Laakmann McDowell, Cracking the Coding Interview, 6th Edition.
• Trie, Wikipedia.