首页 / 算法 / 算法学习笔记：Trie 树（字典树）
算法学习笔记：Trie 树（字典树）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法学习笔记：Trie 树（字典树），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2882字，纯文字阅读大概需要5分钟。
内容图文
算法学习笔记：Trie 树（字典树）
1. 概述
Trie 树，中文名为字典树，是一种字符串的高效处理算法。
Trie 树实现的功能就是快速的查找一堆字符串里面有没有某个串是另一个串的前缀，后缀等等。
2. 详解
2.1 Trie 树的概念
Trie 树首先是一棵树，比如下面这棵树就是一棵 Trie 树。
这棵树是由 ab,abd,ac,bd 四个字符串构成的。
那么结合图示，我们会发现 Trie 树有以下几个特点：
- 每个字符串一定是根节点到某个节点的路径。
- 根节点是虚拟节点。
- 红色节点表示这个字母是某个字符串的末尾。
那么根据上面这三条性质，我们就可以方便的将每一个字符串唯一的插入 Trie 树而且不引起歧义。
那么 Trie 树的操作有什么呢？要怎么实现呢？
2.2 Trie 树的操作
接下来的所有字符串，如果没有特殊说明，都只包含小写字母。
2.2.1 Trie 树的存储
我们需要一个结构体来存储 Trie 树。
Trie 树中需要包含两个变量： c h [ ] , f l a g ch[],flag ch[],flag，分别表示当前节点的孩子编号和当前节点是不是一个单词的节点。
特别的，0 为超级根，不会存下任何字母信息。
同时我们需要一个 init ? \operatorname{init} init 函数来初始化。
代码：
struct node
{
int ch[26], flag;
void init()
{
for (int i = 0; i <= 25; ++i) ch[i] = 0;
flag = 0;
}
}
2.2.2 Trie 树的插入-Insert
我们看看 Trie 树要如何插入。还是看图。
假设我们现在要插入字符串 acd。
那么首先看第一位 a，有了，那么我们沿着 a 向下。
然后我们看到 c 有了，向下。
然后我们看 d，没有，那么我们新建一个节点 d 跟在 c 后面。
然后走到头了，于是标记 d 是一个单词的重点，所以最后的字典树如下。
Trie 树插入的代码如下：
void Insert(int k)//k 表示第 k 个字符串，采用字符数组存储，下标从 1 开始
{
int len = strlen(a[k] + 1), p = root;
for (int i = 1; i <= len; ++i)
{
int q = a[k][i] - 'a';
if (!tree[p].ch[q])
{
++cnt;//计数器 +1
tree[cnt].init();//预先初始化，多测的时候尤其有用(好像比 memset 快)
tree[p].ch[q] = cnt;
}
p = tree[p].ch[q];
}
tree[p].flag = 1;//标记当前为一个单词的结尾
}
需要注意的是，如果字符串有重复，那么 f l a g flag flag 就要 +1 而不是 =1。
2.2.3 Trie 树的查询-Find
Trie 树的查询。
还是刚才那个 Trie 树。假设我们要查询 acd 和 bda 是否存在。当然正式的时候是一个一个查询的，这里因为懒方便我就两个一起了。
首先看 a 和 b，都在根节点的儿子内，那么往下走。
然后看 c 和 d，都在，继续往下走：
最后看 d 和 a，发现 d 在 a 不在，那么可以判断 bda 不在，将
P
1
P_1
P1? 往下走。
最后第一个字符串遍历完了 而且 P 1 P_1 P1? 节点的 f l a g flag flag 为 1 （这一点很重要，因为可能出现找到了却不是个字符串的情况），那么就存在。
查询操作的代码如下：
bool Find(int k)
{
int len = strlen(b[k] + 1), p = root;
for (int i = 1; i <= len; ++i)
{
int q = b[k][i] - 'a';
if (!tree[p].ch[q]) return 0;//节点不存在
p = tree[p].ch[q];
}
if (!tree[p].flag) return 0;//这不是一个字符串
return 1;
}
2.3 Trie 树的适用范围
Trie 树适用于那些有多个文本串和多个模式串，询问某个串是否为另一个串的 前缀 等等问题。注意 Trie 树是不能直接进行字串匹配的，需要使用一点科技，这个就是 AC 自动机解决的了。注意不是自动 AC 机
3. 总结
Trie 树形象直观，就是一个简单插入，删除的过程。
内容总结
以上是互联网集市为您收集整理的算法学习笔记：Trie 树（字典树）全部内容，希望文章能够帮你解决算法学习笔记：Trie 树（字典树）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。