Trie 在计算机科学中trie又称前缀树或字典樹是一种有序树用于保存关联数组其中的键通常是字符串与二叉查找树不同键不是直接保存在节点中而是由节点在树中的位置决定一个节点的所有子孙都有相同的前缀也就是这个节点对应的字符串而根节点对应空字符串一般情况下不是所有的节点都有对应的值只有叶子节点和部分内部节点所对应的键才有相关的值 Trie这个术语来自于retrievaltrie的发明者Edward Fredkin把它读作ˈtriː tree但是其他作者把它读作ˈtraɪ try 在图示中键标注在节点中值标注在节点之下每一个完整的英文单词对应一个特定的整数Trie可以看作是一个确定有限状态自动机尽管边上的符号一般是隐含在分支的顺序中的 键不需要被显式地保存在节点中图示中标注出完整的单词只是为了演示trie的原理 trie中的键通常是字符串但也可以是其它的结构trie的算法可以很容易地修改为处理其它结构的有序序列比如一串数字或者形状的排列比如bitwise trie中的键是一串位元可以用于表示整数或者内存地址