Tire树学习（个人笔记14）

### 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树了。