字典树学习笔记

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

字典树学习笔记

2023-01-30 15:06:43 来源：博客园

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

字典树(Trie)简介

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

【资料图】

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

\[\scriptsize\color{grey}{字典树(Trie)}\]

字典树概念

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

\[\scriptsize\color{grey}{字典树构造}\]\[\color{red}{注意，其中灰色的点表示该节点是一个字符串结束的位置}\]

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

1.查找

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

\[\scriptsize\color{grey}{字典树查找acu}\]

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

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

\[\scriptsize\color{grey}{字典树查找what}\]

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

2.插入(建树)

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

点击查看详细

$\qquad\qquad\qquad\qquad\qquad\qquad\qquad$

\[\scriptsize\color{grey}{一颗空树}\]

1. 插入“ac”

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

\[\scriptsize\color{grey}{新建节点a~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~新建节点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$

\[\scriptsize\color{grey}{新建节点e}\]

3. 插入“acu”

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

$~~~~~~~~~~~~~~$$~~~~~~~~$

\[\scriptsize\color{grey}{经过节点a~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~经过节点c}\]

$\qquad\qquad\qquad\qquad\qquad\qquad\qquad$

\[\scriptsize\color{grey}{新建节点u}\]

4. 插入“wa”

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

\[\scriptsize\color{grey}{新建节点w~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~新建节点a}\]

5. 插入“who”

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

\[\scriptsize\color{grey}{经过节点a~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~新建节点h}\]

$\qquad\qquad\qquad\qquad\qquad\qquad\qquad$

\[\scriptsize\color{grey}{新建节点u}\]

6. 插入“pc”

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

\[\scriptsize\color{grey}{新建节点p~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~新建节点c}\]

\[{\color[RGB]{80,80,100} {\Large \mathsf{插入(建树)就这样结束了，Trie的插入思路可以总结为一点：\mathbf{如果有就过，没有就新建}} } } \]

关键词：树形结构搜索引擎