Trie 树，又叫做前缀树或者是字典树，是一种有序的树。从空字符串的根开始，往下遍历到某个节点，确定了对应的字符串，也就是说，任意一个节点的所有子孙都具备相同的前缀。每一棵 Trie 树都可以被看做是一个简单版的确定有限状态的自动机（DFA，deterministic finite automaton），也就是说，对于一个任意给定的属于该自动机的状态 (①) 和一个属于该自动机字母表的字符 (②)，都可以根据给定的转移函数 (③) 转到下一个状态去。其中：
- ① 对于 Trie 树中的每一个节点都确定了一个自动机的状态；
- ② 给定一个属于该自动机字母表的字符，在图中可以看到根据不同的字符形成的分支；
[……]阅读全文