Trie 树和其它数据结构的比较

trie

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

  • ① 对于 Trie 树中的每一个节点都确定了一个自动机的状态;
  • ② 给定一个属于该自动机字母表的字符,在图中可以看到根据不同的字符形成的分支;

[……]阅读全文

back to top