Trie Tree | 字典树

背景 #

假如我们现在有一个单词组成的数组[“apple”, “banana”, “orange”, …]，我们希望准确地知道某一个单词是否在这个数组里，有什么高效的统计方式呢？

字典树 #

字典树的设计就是用来解决上面的问题，下图就是一个字典树的示意图，它具有以下的特点：

• 它的每条边代表了一个特定的字符；
• 从根节点到每个节点的路径就是某个字符串的前缀；
• 一个父结点的子结点数目最多有 26 个，因为只有 26 个单词.

对于下面这张图来说，我们希望知道 “cat” 在不在字典里，首先我们从根节点出发，先找第一个单词 ‘c’ 在不在根节点的子结点里；如果在，就找第二个单词 ‘a’ 在不在 ‘c’ 的子结点里，这样不断地查找下去。

我们不难发现，对于这棵树来说，它的深度取决于当前字典里最长单词的字母个数，而单词的长度一般不会超过 50，所以这棵树的查找是非常高效的。

字典树除了能很好地判断一个单词是否在这个字典里，它同样可以应用于自动补全和拼写检查。

代码实现 #

要实现这棵树也非常简单，首先我们需要把这棵树的节点构造出来，这里用一个长度为 26 的数组用来表示某一个字母是否有对应的子结点，还有一个 int 的变量用来表示在这颗树里有多少个单词以当前这个节点结尾。

class Node {
    Node[] next;
    int end;

    public Node() {
        next = new Node[26];
    }
}

然后我们需要实现 Trie 的代码，我们只需要通过迭代的方式去插入和查询即可。

public class Trie {
    Node root;
    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        char[] arr = word.toCharArray();
        Node cur = root;
        for (int i = 0; i < arr.length; i++) {
            int idx = arr[i] - 'a';
            if (cur.next[idx] == null) {
                cur.next[idx] = new Node();
            }
            cur = cur.next[idx];
        }
        cur.end++;
    }

    public boolean search(String word) {
        char[] arr = word.toCharArray();
        Node cur = root;
        for (int i = 0; i < arr.length; i++) {
            int idx = arr[i] - 'a';
            if (cur.next[idx] == null) {
                return false;
            }
            cur = cur.next[idx];
        }
        return cur.end > 0 ? true : false; 
    }

    public void erase(String word) {
        char[] arr = word.toCharArray();
        Node cur = root;
        for (int i = 0; i < arr.length; i++) {
            int idx = arr[i] - 'a';
            cur = cur.next[idx];
        }
        cur.end--;
    }
}

Last modified on 2023-02-19