字典树

1. 字典树的定义

定义 字典树（Trie-Tree）是一种广泛用于查找字符串的数据结构。

先给你大量字符串作为字典，然后给其他字符串看这些字符串是否在开始给的字符串里，可能对于这种情况首先想到的便是 map，但 map 查找效率十分低下，碰到大量的数据时很容易超时或超内存。

它实际上就是一个树，类似于求前缀码，用第一层表示第一个字母，第二层表示第二个字母，以此类推，而每个字母不一定都有，这样便减小了搜索所需时间。

字典树是为了支持快速模式匹配的储存字符串的基于树的数据结构。字典树主要应用于信息检索。对于一个确定的字符串集合 $S$ ，所有定义使用了相同的字母表。字典树支持的主要查询操作是模式匹配和前缀匹配。

因此，字典树广泛用于这样的任务：给定一个字符串 $X$ ，查找以 $X$ 作为前缀是所有在 $S$ 中的字符串。

字母表 $\Sigma$ 的长度为 $n$ ，对于存储了 $s$ 个字符串的集合 $S$ 的标注字典树 $T$ 有以下特征：