【数据结构】字典树

字典树（Trie/前缀树）

字典树是一种用空间换时间的数据结构，主要用于统计、排序和保存大量字符串。

字典树通过存储字符串的公共前缀来节约空间，因此字典树又叫前缀树。

字典树是对于字典的一种存储方式，这个词典中的每个单词就是从根节点出发一直到某一个目标节点的路径，路径上的字母连接起来就是一个单词。

用字典树来存储这组字符串 {"a","abc","bac","bbc","ca" }，字典树的结构如下：

从这张图我们可以看出，这棵字典树的每条边上都有一个字母（可以类比查字典时查找的第k个字母来理解），并且这棵树的一些节点被指定成了标记节点，用于表示到此为止是一个完整的单词。

参考

字典树（Trie/前缀树）