数据结构 - Trie - 字典树 - Prefix tree - 前缀树

旧城等待， 2022-10-25 01:25 210阅读 0赞

# **数据结构 - Trie - 字典树 - Prefix tree - 前缀树** #

## 1. Trie - 字典树 - Prefix tree - 前缀树 ##

Trie (\[traɪ\])：字典树，单词查找树  
Prefix tree (\['priːfɪks\])：前缀树

利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。一次建树，多次查询。

根节点不包含字符，除根节点之外每一个节点都只包含一个字符。从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。每个节点的所有子节点包含的字符都不相同。

In computer science, a `trie`, also called `digital tree` or `prefix tree`, is a kind of search tree - an ordered tree data structure used to store a dynamic set or associative array where the keys are usually strings.  
用于存储动态集合或关联数组的有序树数据结构，其中键通常是字符串。

A `trie`, or `prefix tree`, is a tree data structure for storing strings (keywords) in sorted order.  
`trie` or `prefix tree` 是一种树数据结构，用于按照排序顺序存储字符串 (关键字)，Trie 是一棵多叉树。

Trie 树是一个有根的树，其结点有以下字段：

*  最多 MAX\_NUM 个指向子结点的链接，其中每个链接对应字母表数据集中的一个字母。假定 MAX\_NUM 为 26，小写拉丁字母的数量。指向子节点的指针数组 `struct TRIE *children[ALPHABET]; // [] > *`。数组长度为 26，即小写英文字母的数量。此时 `children[0]` 对应小写字母 `a`，`children[1]` 对应小写字母 `b`，…，`children[25]` 对应小写字母 `z`。
 *  布尔字段，以指示该节点是否为字符串的结尾。

单词 `leet` 在 Trie 树中的表示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]

## 2. 搜索字典项目 ##

(1) 从根结点开始。  
(2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索。  
(3) 在相应的子树上，取得要查找关键词的第二个字母，并进一步选择对应的子树进行检索。  
(4) 迭代过程。  
(5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。

## 3. 向 Trie 树中插入字符串 ##

通过搜索 Trie 树来插入一个键，从根开始搜索它对应于第一个键字符的链接。

*  链接存在。沿着链接移动到树的下一个子层。算法继续搜索下一个键字符。
 *  链接不存在。创建一个新的节点，并将它与父节点的链接相连，该链接与当前的键字符相匹配。  
    重复以上步骤，直到到达键的最后一个字符，然后将当前节点标记为结束节点，算法完成。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]  
    时间复杂度： O ( m ) O(m) O(m)，其中  m m m 为键长。在算法的每次迭代中，检查/创建一个节点，直到到达键尾。只需要  m m m 次操作。  
    空间复杂度： O ( m ) O(m) O(m)。最坏的情况下，新插入的键和 Trie 树中已有的键没有公共前缀。此时需要添加  m m m 个结点，使用  O ( m ) O(m) O(m) 空间。

## 4. 在 Trie 树中查找字符串 ##

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

*  存在链接。移动到该链接后面路径中的下一个节点，并继续搜索下一个键字符。
 *  不存在链接。若已无键字符，且当前结点标记为 isEnd，则返回 true。  
    还有键字符剩余，但无法跟随 Trie 树的键路径，找不到键，返回 false。  
    没有键字符剩余，但当前结点没有标记为 isEnd。待查找键只是 Trie 树中另一个键的前缀。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]

时间复杂度： O ( m ) O(m) O(m)。算法的每一步均搜索下一个键字符。最坏的情况下需要  m m m 次操作。  
空间复杂度： O ( 1 ) O(1) O(1)。

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

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

## 6. Trie 或前缀树的应用 ##

一次建树，多次查询。  
Trie 或前缀树是一种树数据结构，用于检索字符串数据集中的键。

### 6.1 自动补全 ###

![在这里插入图片描述][20210130231242746.png_pic_center]

### 6.2 拼写检查 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 4]

### 6.3 IP 路由 (最长前缀匹配) ###

使用 Trie 树的最长前缀匹配算法，Internet 协议 （IP） 路由中利用转发表选择路径。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 5]  
哈希表可以在  O ( 1 ) O(1) O(1) 时间内寻找键值，却无法高效的完成以下操作：

*  找到具有同一前缀的全部键值。
 *  按词典序枚举字符串的数据集。

随着哈希表大小增加，会出现大量的冲突，时间复杂度可能增加到  O ( n ) O(n) O(n)，其中  n n n 是插入的键的数量。与哈希表相比，Trie 树在存储多个具有相同前缀的键时可以使用较少的空间。此时 Trie 树只需要  O ( m ) O(m) O(m) 的时间复杂度，其中  m m m 为键长。在平衡树中查找键值需要  O ( m log ⁡ n ) O(m \\log n) O(mlogn) 时间复杂度。

Trie 是多叉树，每个结点的分支数量可能为多个。在结点的数据结构设计上，它和一般的多叉树不同。

TrieNode 结点中并没有直接保存字符值的数据成员，字母映射表 next 的妙用就体现了，`TrieNode *next[26]` 中保存了对当前结点而言下一个可能出现的所有字符的链接，因此我们可以通过一个父结点来预知它所有子结点的值。

下标引用的优先级高于间接访问，指针数组 (array of pointers)。

包含三个单词 `"sea"`, `"sells"`, `"she"` 的 Trie：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 6]

Trie 中一般都含有大量的空链接，在绘制一棵单词查找树时一般会忽略空链接：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 7]

## References ##

[https://leetcode-cn.com/][https_leetcode-cn.com]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/c07046f0a04c456bb1557bf444991f93.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221024/0dcf0eb6b7bf46e2ad4e3912ed56990d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221024/548b1cb28b8a4ef3b0c387b27b3d8b90.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221024/ea99d02921464efdbd5efd54fa99939c.png
[20210130231242746.png_pic_center]: /images/20221024/292ab325091b4ba899c23f9b417fed2b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221024/e3acf08797794282a22c8daeb4353d43.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221024/ce15b60213e34fce902b93b58ae8308e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221024/1faee807408e4ccb81bdebd1fc8cb2c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221024/a98548a4db724e07ab79aa402b952ac2.png
[https_leetcode-cn.com]: https://leetcode-cn.com/