Trie 树

[yifanzheng]

Trie 树

Trie 树，也叫“字典树”、“前缀树”。它是一个树形结构，一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

假设我们有 6 个字符串，它们分别是：how，hi，her，hello，so，see。我们希望在里面多次查找某个字符串是否存在。如果每次查找，都是拿要查找的字符串跟这 6 个字符串依次进行字符串匹配，那效率就比较低，有没有更高效的方法呢？

这个时候，我们就可以先对这 6 个字符串做一下预处理，组织成 Trie 树的结构，之后每次查找，都是在 Trie 树中进行匹配查找。Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

其中，根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串。

实现一棵 Trie 树

Trie 树主要有两个操作，一个是将字符串集合构造成 Trie 树，即将一个将字符串插入到 Trie 树的过程。另一个是在 Trie 树中查询一个字符串。

示例：构建一个字符串只有 a-z 的 26 个小写字母的 Trie 树，我们在数组中下标为 0 的位置，存储指向子节点 a 的指针，下标为 1 的位置存储指向子节点 b 的指针，以此类推，下标为 25 的位置，存储的是指向的子节点 z 的指针。如果某个字符的子节点不存在，我们就在对应的下标的位置存储 null。

public class Trie {
    /**
     * 构建 Trie 树根节点
     */
    private TrieNode root = new TrieNode('/');

    public void insert(char[] str) {
        TrieNode p = root;
        for (int i = 0; i < str.length; i++) {
            int index = str[i] - 'a';
            if (p.chilren[index] == null) {
                TrieNode trieNode = new TrieNode(str[i]);
                p.chilren[index] = trieNode;
            }
            p = p.chilren[index];
        }
        p.isEndChar = true;
    }

    public boolean find(char[] str) {
        TrieNode p = root;
        for (int i = 0; i < str.length; i++) {
            int index = str[i] - 'a';
            if (p.chilren[index] == null) {
                return false;
            }
            p = p.chilren[index];
        }
        // 如果节点不是最后的字符，不能完全匹配，是前缀匹配
        return p.isEndChar;
    }

    private static class TrieNode {
        private char data;
        private TrieNode[] chilren = new TrieNode[26];
        private boolean isEndChar = false;

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

}

构建 Trie 树的过程，需要扫描所有的字符串，时间复杂度是 O(n)（n 表示所有字符串的长度和）。但是一旦构建成功之后，后续的查询操作会非常高效。

每次查询时，如果要查询的字符串长度是 k，那我们只需要比对大约 k 个节点，就能完成查询操作。跟原本那组字符串的长度和个数没有任何关系。所以说，构建好 Trie 树后，在其中查找字符串的时间复杂度是 O(k)，k 表示要查找的字符串的长度。

小结

Trie 树是非常耗内存的，用的是一种空间换时间的思路，它对要处理的字符串有及其严苛的要求。

• 第一，字符串中包含的字符集不能太大。我们前面讲到，如果字符集太大，那存储空间可能就会浪费很多。即便可以优化，但也要付出牺牲查询、插入效率的代价。
• 第二，要求字符串的前缀重合比较多，不然空间消耗会变大很多。
• 第三，如果要用 Trie 树解决问题，那我们就要自己从零开始实现一个 Trie 树，还要保证没有 bug，这个在工程上是将简单问题复杂化，除非必须，一般不建议这样做。
• 第四，我们知道，通过指针串起来的数据块是不连续的，而 Trie 树中用到了指针，所以，对缓存并不友好，性能上会打个折扣。

综上，Trie 树只是不适合精确匹配查找，这种问题更适合用散列表或者红黑树来解决，而 Trie 树比较适合的是查找前缀匹配的字符串。