柒葉灬 的博客

柒葉灬 的博客

Tire树学习(个人笔记14)

posted on 2018-12-05 16:58:30 | under 专题总结 |

Tire树(字典树)的学习。

Tire树就是一种快速查询的算法。

条件:字符少

缺点:空间大


比如说,有一本书,我们希望查询里面是否含有某个单词。

暴力:查询 $O(n)$

hash:排序 $O(nlogn)$ ,查询 $O(logn)$

Tire树:建树 $O(n*K)$ ,查询 $O(K)$ (K是单词长度)

是不是很神奇


Tire树写法:

插入read单词,标记前缀为r的节点,标记前缀为re的节点......

查询read,先查询是否含有r开头的,然后查询re开头,然后......

可以看出空间十分庞大,因为每一个单词加进去都有可能增加 $K$ 个节点。

重点是每个节点的可能有26个儿子,所以再乘以26。


适用范围

在遇到需要支持查询字符串的题目时,可以考虑Tire树了。