【动画】看动画轻松理解「Trie树」

Trie这个名字取自“retrieval”,检索,因为Trie可以只用一个前缀便可以在一部字典中找到想要的单词。
虽然发音与「Tree」一致,但为了将这种 字典树 与 普通二叉树 以示区别,程序员小吴一般读「Trie」尾部会重读一声,可以理解为读「TreeE」。

Trie 树,也叫“字典树”。顾名思义,它是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。

此外 Trie 树也称前缀树(因为某节点的后代存在共同的前缀,比如pan是panda的前缀)。

它的key都为字符串,能做到高效查询和插入,时间复杂度为O(k),k为字符串长度,缺点是如果大量字符串没有共同前缀时很耗内存。

它的核心思想就是通过最大限度地减少无谓的字符串比较,使得查询高效率,即「用空间换时间」,再利用共同前缀来提高查询效率。

Trie树的特点

假设有 5 个字符串,它们分别是:code,cook,five,file,fat。现在需要在里面多次查找某个字符串是否存在。如果每次查找,都是拿要查找的字符串跟这 5 个字符串依次进行字符串匹配,那效率就比较低,有没有更高效的方法呢?

如果将这 5 个字符串组织成下图的结构,从肉眼上扫描过去感官上是不是比查找起来会更加迅速。

Trie树样子

Trie树样子

通过上图,可以发现 Trie树 的三个特点:

根节点不包含字符,除根节点外每一个节点都只包含一个字符

从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串

每个节点的所有子节点包含的字符都不相同

通过动画理解 Trie 树构造的过程。在构造过程中的每一步,都相当于往 Trie 树中插入一个字符串。当所有字符串都插入完成之后,Trie 树就构造好了。

 Trie 树构造

Trie 树构造

Trie树的插入操作

Trie树的插入操作

Trie树的插入操作

Trie树的插入操作很简单,其实就是将单词的每个字母逐一插入 Trie树。插入前先看字母对应的节点是否存在,存在则共享该节点,不存在则创建对应的节点。比如要插入新单词cook,就有下面几步:

插入第一个字母 c,发现 root 节点下方存在子节点 c,则共享节点 c

插入第二个字母 o,发现 c 节点下方存在子节点 o,则共享节点 o

插入第三个字母 o,发现 o 节点下方不存在子节点 o,则创建子节点 o

插入第三个字母 k,发现 o 节点下方不存在子节点 k,则创建子节点 k

至此,单词 cook 中所有字母已被插入 Trie树 中,然后设置节点 k 中的标志位,标记路径 root->c->o->o->k这条路径上所有节点的字符可以组成一个单词cook

Trie树的查询操作

在 Trie 树中查找一个字符串的时候,比如查找字符串 code,可以将要查找的字符串分割成单个的字符 c,o,d,e,然后从 Trie 树的根节点开始匹配。如图所示,绿色的路径就是在 Trie 树中匹配的路径。

code的匹配路径

code的匹配路径

如果要查找的是字符串cod(鳕鱼)呢?还是可以用上面同样的方法,从根节点开始,沿着某条路径来匹配,如图所示,绿色的路径,是字符串cod匹配的路径。但是,路径的最后一个节点「d」并不是橙色的,并不是单词标志位,所以cod字符串不存在。也就是说,cod是某个字符串的前缀子串,但并不能完全匹配任何字符串。

cod的匹配路径

cod的匹配路径

程序员不要当一条咸鱼,要向 cook 靠拢:)

Trie树的删除操作

Trie树的删除操作与二叉树的删除操作有类似的地方,需要考虑删除的节点所处的位置,这里分三种情况进行分析:

删除整个单词(比如`hi`)

删除整个单词

删除整个单词

从根节点开始查找第一个字符h

找到h子节点后,继续查找h的下一个子节点i

i是单词hi的标志位,将该标志位去掉

i节点是hi的叶子节点,将其删除

删除后发现h节点为叶子节点,并且不是单词标志位,也将其删除

这样就完成了hi单词的删除操作

删除前缀单词(比如`cod`)

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzsjxw.html