Tries

前缀树（Tries） 是将字符串中的各个字符按顺序存入到树形结构当中，这样可以高效的检索给定单词和前缀是否存在于集合当中的树形数据结构。具体的结构可以参考下图：

flowchart TD

s((" ")) -- t --> t((t))
s -- A --> a((A))
s -- i --> i((i))

t -- o --> to((to))
t -- e --> te((te))
i -- n --> in((in))

te -- a --> tea((tea))
te -- d --> ted((ted))
te -- n --> ten((ten))
in -- n --> inn((inn))
in -- t --> int((int))

在实际实现中 $Node$ 中不需要额外存储字符信息，字符在 $Children$ 的字段中作为 $key$ 存在。为了判断当前节点是否可以作为一个单词还是只是前缀，需要存储当前 $Node$ 是否是一个单词的标志位。为了快速的得到对应路径的单词，也可以在节点额外存储一个单词信息，像在 Leetcode 题目212 中做的那样。

复杂度

Algorithm	Average	Worst case
Space	$O(n)$	$O(n)$
Search	$O(n)$	$O(n)$
Insert	$O(n)$	$O(n)$
Delete	$O(n)$	$O(n)$

Code example

struct TrieNode {
    pub children: HashMap<Char, Box<TrieNode>>,
    pub is_word: Bool,
    pub word: Option<String>,
}