带你理解 Trie 树（前缀树）

写在前面

如果觉得有所收获，记得点个关注和点个赞，感谢支持。
在计算机科学中，Trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。Trie中的键通常是字符串，但也可以是其它的结构。Trie的算法可以很容易地修改为处理其它结构的有序序列，比如一串数字或者形状的排列。比如，Bitwise Trie中的键是一串位元，可以用于表示整数或者内存地址。

Trie树的结构

我们这里通过对单词的储存读取来举例，更形象的来体会Trie树结构。 Trie 树是一个有根的树，其结点具有以下字段：

• 最多 $R$R 个指向子结点的链接，其中每个链接对应字母表数据集中的一个字母。
  在这个例子中假定 $R$R 为 26，小写拉丁字母的数量。
• 布尔字段，以指定节点是对应键的结尾还是只是键前缀。

如下的图是，单词 “leet” 在 Trie 树中的表示，结构很清晰。

我们使用更复杂的图来理解，如何储存多个单词

Trie 树中最常见的两个操作是键的插入和查找。

向 Trie 树中插入键

我们通过搜索 Trie 树来插入一个键。我们从根开始搜索它对应于第一个键字符的链接。有两种情况：

• 链接存在。沿着链接移动到树的下一个子层。算法继续搜索下一个键字符。
• 链接不存在。创建一个新的节点，并将它与父节点的链接相连，该链接与当前的键字符相匹配。

重复以上步骤，直到到达键的最后一个字符，然后将当前节点标记为结束节点，算法完成。

在 Trie 树中查找键

每个键在 trie 中表示为从根到内部节点或叶的路径。我们用第一个键字符从根开始，。检查当前节点中与键字符对应的链接。有两种情况：

• 存在链接。我们移动到该链接后面路径中的下一个节点，并继续搜索下一个键字符。
• 不存在链接。若已无键字符，且当前结点标记为 isEnd，则返回 true。否则有两种可能，均返回 false :
  • 还有键字符剩余，但无法跟随 Trie 树的键路径，找不到键。
  • 没有键字符剩余，但当前结点没有标记为 isEnd。也就是说，待查找键只是Trie树中另一个键的前缀。

查找 Trie 树中的键前缀

该方法与在 Trie 树中搜索键时使用的方法非常相似。我们从根遍历 Trie 树，直到键前缀中没有字符，或者无法用当前的键字符继续 Trie 中的路径。与上面提到的“搜索键”算法唯一的区别是，到达键前缀的末尾时，总是返回 true。我们不需要考虑当前 Trie 节点是否用 “isend” 标记，因为我们搜索的是键的前缀，而不是整个键。

基本性质和优缺点

Trie的强大之处就在于它的时间复杂度，插入和查询的效率很高，Trie树不用求 hash 值，对短字符串有更快的速度。因为通常，求hash值也是需要遍历字符串的。

Trie树可以对关键字按字典序排序。
基本性质

• 根节点不包含字符，除根节点意外每个节点只包含一个字符。

• 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。

• 每个节点的所有子节点包含的字符串不相同。

通常在实现的时候，会在节点结构中设置一个标志，用来标记该结点处是否构成一个单词（关键字）。

优点
可以最大限度地减少无谓的字符串比较，故可以用于词频统计和大量字符串排序。跟哈希表比较：

• 最坏情况时间复杂度比hash表好
• 没有冲突，除非一个key对应多个值（除key外的其他信息）
• 自带排序功能（类似Radix Sort），中序遍历Trie可以得到排序。

缺点
虽然不同单词共享前缀，但其实trie是一个以空间换时间的算法。其每一个字符都可能包含至多字符集大小数目的指针（不包含卫星数据）。

• 每个结点的子树的根节点的组织方式有几种。
  • 如果默认包含所有字符集，则查找速度快但浪费空间（特别是靠近树底部叶子）。
  • 如果用链接法(如左儿子右兄弟)，则节省空间但查找需顺序（部分）遍历链表。
  • alphabet reduction: 减少字符宽度以减少字母集个数。
  • 对字符集使用bitmap，再配合链接法。
• 如果数据存储在外部存储器等较慢位置，Trie会较hash速度慢（hash访问O(1)次外存，Trie访问O(树高)）。
• 长的浮点数等会让链变得很长。可用bitwise trie改进。

代码实现

class TrieNode {
    private TrieNode[] links;
    private final int R = 26;
    private boolean isEnd;

    public TrieNode() {
        links = new TrieNode[R];
    }

    public boolean containsKey(char ch) {
        return links[ch - 'a'] != null;
    }

    public TrieNode get(char ch) {
        return links[ch - 'a'];
    }

    public void put(char ch, TrieNode node) {
        links[ch - 'a'] = node;
    }

    public void setEnd() {
        isEnd = true;
    }

    public boolean isEnd() {
        return isEnd;
    }
}

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

    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char currentChar = word.charAt(i);
            if (!node.containsKey(currentChar)) {
                node.put(currentChar, new TrieNode());
            }
            node = node.get(currentChar);
        }
        node.setEnd();
    }

    private TrieNode searchPrefix(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char curLetter = word.charAt(i);
            if (node.containsKey(curLetter)) {
                node = node.get(curLetter);
            } else {
                return null;
            }
        }
        return node;
    }

    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd();
    }

    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }
}

Trie树的应用

• 字符串检索：事先将已知的一些字符串（字典）的有关信息保存到trie树里，查找另外一些未知字符串是否出现过或者出现频率。
• 文本预测、自动完成，see also，拼写检查
• 词频统计
• 排序：Trie树是一棵多叉树，只要先序遍历整棵树，输出相应的字符串便是按字典序排序的结果。
• 字符串最长公共前缀：Trie树利用多个字符串的公共前缀来节省存储空间，当我们把大量字符串存储到一棵trie树上时，我们可以快速得到某些字符串的公共前缀。
• 字符串搜索的前缀匹配：trie树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。
• 作为其他数据结构和算法的辅助结构：如后缀树，AC自动机等