Prefix Tree(Trie Tree) - 前缀树

前缀树是一种按照前缀快速查找的数据结构，典型的应用场景是在一个英文单词集合中快速查询某个单词。

为了方便，本问题只考虑字典中的 $a - z$ 这 $26$ 个小写字母。前缀树的树节点包含 $26$ 个孩子节点，跟节点不包含任何字符，从根节点开始向下查找就可以得到完整的单词。一个包含 $boy$ 、 $dog$ 、 $bible$ 、 $bill$ 的前缀树如图：

每次查找单词，从根节点开始向下匹配即可。在前缀树中查找一个长度为 $n$ 的单词的时间复杂度为 $O(n)$ 。