swift算法手记-9

在盘算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保留关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保留在节点中，而是由节点在树中的地位决议。一个节点的所有子孙都有雷同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情形下，不是所有的节点都有对应的值，只有叶子节点和部份内部节点所对应的键才有相干的值。Trie这个术语来自于retrieval。依据词源学，trie的创造者Edward Fredkin把它读作英语发音：/ˈtriː/ "tree"。[1][2]但是，其他著作把它读作英语发音：/ˈtraɪ/ "try"。[1][2][3]在图示中，键标注在节点中，值标注在节点之下。每一个完全的英文单词对应一个特定的整数。Trie可以看做是一个肯定有限状况主动机，虽然边上的符号通常为隐含在分支的次序中的。键不须要被显式地保留在节点中。图示中标注出完全的单词，只是为了演示trie的原理。trie中的键通常是字符串，但也能够是其它的构造。trie的算法可以很容易地修正为处置其它构造的有序序列，比如一串数字或形状的排列。比如，bitwise trie中的键是一串位元，可以用于表现整数或内存地址。在盘算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保留关联数组，其中的键通常是字符串。