我对 Trie 实现如何节省空间并以最紧凑的形式存储数据感到困惑！
如果你看下面的树。当您在任何节点存储字符时，您还需要存储对该字符的引用，因此对于字符串的每个字符，您需要存储其引用。
好吧，当常见字符到达时，我们节省了一些空间，但在存储对该字符节点的引用时我们失去了更多空间。
那么维护这棵树本身不是有很多结构开销吗？相反，如果使用 TreeMap 来代替它，比如说实现一个字典，这可以节省更多的空间，因为字符串将被保存在一个片段中，因此在存储引用时不会浪费空间，不是吗？
为了在使用 trie 时节省空间，可以使用压缩特里树 http://en.wikipedia.org/wiki/Radix_tree（也称为帕特里夏特里树或基数树），其中一个节点可以表示多个字符：
在计算机科学中，基数树（也称为帕特里夏特里或基数特里）
是一种空间优化的 trie 数据结构，其中每个节点只有一个
孩子与其孩子合并。结果是每个内部节点
至少有两个孩子。与常规尝试不同，边缘可以是
用字符序列和单个字符标记。
这使得它们对于小集合更加有效（特别是如果
字符串很长）以及共享长前缀的字符串集。
基数树的示例：
请注意，trie 通常用作一种有效的数据结构，用于对一组字符串进行前缀匹配。 trie 还可以用作关联数组（如哈希表），其中键是字符串。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
