Trie 字典树 详解

😊 | Powered By HeartFireY | Tire Algorithm 一、字典树 1.字典树简介

字典树，英文名Trie，如其名：就是一棵像字典一样的树。

我们首先通过一张图来理解字典树的结构：

我们假定结点的顺序按照图中给定的顺序进行编号，容易发现，在一个给定的树上，从每个根节点出发到达子节点的路径边代表一个字母。实际上，每个节点出发的几条边所代表的字母是从左到右的顺序按照字典序排列的。

那么我们可以知道：从根节点出发，到达某个指定的结点的路径可以构成一个字符串。

一个例子： 1 → 4 → 8 → 13 ⟹ c a a 1\to4\to 8\to 13 \Longrightarrow caa 1→4→8→13⟹caa

在实际应用中，我们在建立Trie字符集之前，应当首先确定边所映射的字符集，然后可以根据边的编号一一对应映射的字符构成目的字符串。

Trie 的结构非常好懂，我们用 δ ( u , c ) \delta(u,c) δ(u,c) 表示结点 u u u 的 c c c 字符指向的下一个结点，或着说是结点 u u u 代表的字符串后面添加一个字符 c c c 形成的字符串的结点。（ c c c 的取值范围和字符集大小有关，不一定是 0 ∼ 26 0\sim 26 0∼26。）

有时需要标记插入进 Trie 的是哪些字符串，每次插入完成时在这个字符串所代表的节点处打上标记即可。

2.字典树的特性以及优缺点 1.优缺点

优点：我们不难发现字典树中实际上记录了多个字符串的公共前缀，因此用于查询公共前缀时是十分高效的，他减少了无意义的字符串匹配，其查询效率要优于哈希树。

缺点：字典树的内存消耗非常大。

我们不难发现，字典树的核心思想是用空间来换时间(利用公共前缀来降低查询时间的开销以达到提高效率的目的)。

2.特性

1. 根节点不包含字符，除根结点之外每一个结点都只包含一个字符；
2. 字典树用边表示字母表示
3. 从根节点到某一结点， 路径上经过的字符连接起来，为该结点对应的字符串
4. 每个节点的所有子结点包含的字符都不同。每个结点最多有26个子节点(假设给定字符集中包含26个英文字母)
5. 有相同前缀的单词共用前缀节点
6. 整棵树的根节点是空的，便于插入和查找
7. 每个单词结束的时候用一个特殊字符表示，那么从根节点到任意一个特殊字符，所经过的边的所有字母表示一个单词

3.字典树的应用：

从字典树的结构不难发现：字典树可以用来保存大量的字符串(包括但不限于字符串)，同时在一些高级的应用中可以用来统计和排序大量的字符串。在实际生产生活的应用中，我们经常将字典树用于文本的词频统计。

二、字典树操作及模板 1.字典树相关操作及实现 1).插入操作

基本思路：从左到右扫描这个单词，如果扫描指针指向的字母在相应的根节点下没有出现过，就插入这个字母；否则沿着字典树往下走，扫描指针后移。

在插入的过程中我们需要给每个字符进行编号。

我们设 t r e e [ i ] [ j ] = k tree[i][j] = k tree[i][j]=k，表示编号为 i i i的结点的第 j j j个孩子是编号为 k k k的结点。

这里需要特别注意结点的编号问题！

我们通常将编号 ( i ,   j ) (i,\ j) (i, j)分为两类：

实际编号： ( i ,   k ) (i,\ k) (i, k)即为我们在实际储存树结构时的编号，是相对于整棵树而言的；

关系编号：表示当前结点是结点 i i i的第 j j j个孩子，是相对于单个结点而言的。

因此我们可以知道：对于给定的 t r e e [ i ] [ j ] = k tree[i][j] = k tree[i][j]=k，表示那么实际编号为 ( i ,   k ) (i,\ k) (i, k)，关系编号为 j j j。

那么插入操作就应该分为以下的步骤：

• 首先我们需要记录根结点的编号，初始化为0；
• 从左到右扫描这个单词，每次计算关系编号 i d id id(在字符集{a~z}中，关系编号为’当前字符’ - ‘a’)；
• 如果之前没有从 r o o t root root到 i d id id的前缀，则插入该编号(需要预先在声明计数变量，对一种编号进行记录)；
• 执行 r o o t = t r e e [ r o o t ] [ i d ] root = tree[root][id] root=tree[root][id]，表示顺着字典树继续向下走。

2).查找单词

我们可以使用一个数组 v i s [ s t r . l e n ( ) ] vis[str.len()] vis[str.len()]记录到字符第 i i i个字符为止的串是否存在。 v i s [ i ] vis[i] vis[i]表示节点 i i i 是否是单词结束的标志。

搜索完成后直接返回 v i s [ r o o t ] vis[root] vis[root]的值即可。

3).前缀出现次数的记录

在需要统计前缀个数的题目中，我们额外引入一个 s u m [ ] sum[] sum[]数组，表示位置 i 被访问过的次数。

那么最后返回 s u m [ r o o t ] sum[root] sum[root]即可，插入操作中每访问一个节点，都要让其对应的 s u m [ i ] + + sum[i]++ sum[i]++，

但值得注意的是：此处前缀次数标记在前缀的最后一个字母对应位置的后一个位置上

例如上图中的字符串前缀"abc"，那么对应储存的 s u m sum sum值如图所示。

2.字典树模板

这里放一个用结构体封装的模板：

在使用数组进行储存的时候，由于数组的空间是预先分配好的，因此不需要单独进行释放。

struct trie{
    int tree[100000][26], cnt;
    bool exist[100000];			//以该结点结尾的字符串是否存在

    void insert(char *s, int l){
        int root = 0;
        for(int i = 0; i  Next[id];
        }
        //如果存在则继续往下走
        else{
            p = p->Next[id];
            (p -> flag)++;
        }
    }
}

//2、查询操作
int Query(string s){
    int len = s.size();
    trie *p = root;
    //在trie树上顺序搜索s的每一个字符
    for (int i = 0; i Next[id];
        //如果是空集，表示不存在以此为前缀的信息
        if (p == NULL) return 0;
    }
    //返回以该信息为前缀的信息的个数
    return p->flag;
}

//3、删除操作
void Free(trie *t){
    if (t == NULL) return;
    //逐个释放结点所占用的内存
    for (int i = 0; i  Next[i]) free(t -> Next[i]);
    delete (t);
}

注：以上模板参考自博客_链接

三、字典树的高级应用 1.字典树::排序算法

在许多场景下，我们需要对多个字符串进行排序；我们都知道在传统排序算法下时的时间复杂度为 O ( n log ⁡ n ) O(n\log{n}) O(nlogn)，而如果我们通过字典树对给定的串进行排序，则可以将时间复杂度降至 O ( n ) O(n) O(n)。

那么如何利用字典树对多个字符串进行排序呢？

首先，我们根据多个字符串建立Trie树，之后，通过先序遍历此树，即可得到字符串从小到大的顺序。

如何证明这个过程？我们都知道在字典树中，我们对于每个节点的出边是按照字典序进行编号，因此在执行先序遍历的时候会首先访问字典序较小的结点，容易得知经过先序遍历可得到有序的字符串组合。

这里给出使用指针建树的先序遍历方式：

void trie_sort(trie *root){
    if(!root) return;
    if(root -> flag){ cout  w;
        add(u, v, w);
        add(v, u, w);
    }
    dfs(1, 0);
    cout