字典树学习笔记

友情提示：看这篇文章一定要用暗色模式(键在右上角)

字典树(Trie)简介

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
——百度百科

字典树是一种树形结构，用于用于统计，排序和保存大量的字符串。
\(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\)

字典树概念

假设现在有六个字符串，分别是：“ac”、“ace”、“acu”、“wa”、“who”、“pc”，用这几个字符串构造Trie
\(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\)

那字典树是如何运作的呢?

1.查找

• 假设我们要查找“acu”这个字符串，我们需要顺着树边往下找
  \(\qquad\qquad\qquad\qquad\qquad\qquad\)

如果最终的那个点是灰色（该节点是一个字符串结束的位置），查找就完成了，该字符串存在

• 再假设我们要查找“what”这个字符串
  \(\qquad\qquad\qquad\qquad\qquad\qquad\)

当找到“a”时，发现没有“a”,这时可以直接返回没找到，不用继续找下去了！

2.插入(建树)

插入字符串的思路很简单，假设现在我们要在一棵空Trie中按顺序插入“ac”、“ace”、“acu”、“wa”、“who”、“pc”

0.插入前

\(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\)

1. 插入“ac”

我们发现当前节点(root)没有“a”，于是新建一个节点“a”；同样的，我们也在“a”下新建一个节点“c”，“c”标记为灰色
\(~~~~~~~~~~~~~~\)\(~~~~~~~~\)

2. 插入“ace”

我们发现当前节点(root)有“a”，于是经过节点“a”；同样的，我们也经过“a”节点“c”，“c”标记为灰色；我们发现当前节点(“c”)没有“e”，于是新建一个节点“e”，“e”标记为灰色

\(~~~~~~~~~~~~~~\)\(~~~~~~~~\)$$\scriptsize\color{grey}{经过节点a~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~经过节点c}$$
\(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\)

3. 插入“acu”

我们发现当前节点(root)有“a”，于是经过节点“a”；同样的，我们也经过“a”节点“c”，“c”标记为灰色；我们发现当前节点(“c”)没有“u”，于是新建一个节点“u”，“u”标记为灰色

\(~~~~~~~~~~~~~~\)\(~~~~~~~~\)

\(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\)

4. 插入“wa”

我们发现当前节点(root)没有“w”，于是新建一个节点“w”；同样的，我们也在“w”下新建一个节点“a”，“a”标记为灰色
\(~~~~~~~~~~~~~~\)\(~~~~~~~~\)

5. 插入“who”

我们发现当前节点(root)有“w”，于是经过节点“w”；我们发现当前节点(“w”)没有“h”，于是新建一个节点“h”；同样的，我们发现当前节点(“w”)没有“o”，于是也新建一个节点“o”，“o”标记为灰色
\(~~~~~~~~~~~~~~\)\(~~~~~~~~\)

\(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\)

6. 插入“pc”

我们发现当前节点(root)没有“p”，于是新建一个节点“p”；同样的，我们也在“p”下新建一个节点“c”，“c”标记为灰色
\(~~~~~~~~~~~~~~\)\(~~~~~~~~\)

字典树实现

3
3 3
fusufusu
fusu
anguei
fusu
anguei
kkksc
5 2
fusu
Fusu
AFakeFusu
afakefusu
fusuisnotfake
Fusu
fusu
1 1
998244353
9

2
1
0
1
2
1