带你理解 Trie 树（前缀树）

淡淡的烟草味﹌ 2023-07-24 08:42 48阅读 0赞

## 写在前面 ##

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

## Trie树的结构 ##

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

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

如下的图是，单词 “leet” 在 Trie 树中的表示，结构很清晰。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center]  
我们使用更复杂的图来理解，如何储存多个单词  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 1]  
Trie 树中最常见的两个操作是键的插入和查找。

#### 向 Trie 树中插入键 ####

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

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

重复以上步骤，直到到达键的最后一个字符，然后将当前节点标记为结束节点，算法完成。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 2]

#### 在 Trie 树中查找键 ####

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 3]

#### 查找 Trie 树中的键前缀 ####

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

## 基本性质和优缺点 ##

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自动机等

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/b39191fe45fd4c12916a6f47ff729023.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230528/4eb348e5e1924ee79e6e9cf61f0bff62.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230528/cb06f1e783e04f32b73b7c62b0916d55.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20230528/73e5e860abac4cf784652947d25fac1e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20230528/c9fc83e42b834b3a9492ff97636fbc5d.png