Trie节省空间，但如何？
我很困惑Trie实现如何以最紧凑的forms节省空间并存储数据！
如果你看下面的树。 在任何节点上存储字符时，还需要存储对该字符的引用，因此对于存储其引用所需的字符串的每个字符。 好的，当一个普通角色到达时我们节省了一些空间，但是在存储对该角色节点的引用时我们失去了更多空间。
那么维护这棵树本身不是很多结构开销吗？ 相反，如果使用TreeMap代替这个，让我们说实现一个字典，这可以节省更多的空间，因为字符串将被保存在一个片段中因此没有浪费存储引用的空间，不是吗？
您可能会推断它节省空间是在理想的机器上，每个字节都有效地分配。 然而，真正的机器分配对齐的内存块（Java上为8个字节，某些C ++上为16个字节），因此可能无法节省任何空间。
Java字符串和集合会增加相对较高的数量，因此百分比差异可能非常小。
除非你的结构非常大，否则你的超时值会降低内存成本，使用最简单，最标准和最容易维护的集合更为重要。 例如，您的时间很容易达到您尝试保存的内存值的1000倍或更多。
例如，假设您有10000个名称，使用trie可以节省16个字节。 （假设这可以在没有花费更多时间的情况下得到certificate）这相当于16 KB，在今天的价格是0.1美分。 如果您的公司每小时花费30美元，那么编写一行测试代码的成本可能是1美元。
如果你考虑一下，眨眼间就可以节省16 KB，这对于PC来说不太值得。 （移动设备是一个不同的故事，但同样的论点适用于恕我直言）
编辑：您激励我添加更新http://vanillajava.blogspot.com/2011/11/ever-decreasing-cost-of-main-memory.html
为了在使用trie时节省空间，可以使用压缩的trie （也称为patricia trie或radix tree），其中一个节点可以表示多个字符：
在计算机科学中，基数树（也称为patricia trie或radix trie）是一种空间优化的trie数据结构，其中每个只有一个子节点的节点与其子节点合并。 结果是每个内部节点至少有两个子节点。 与常规尝试不同，边缘可以用字符序列和单个字符标记。 这使得它们对于小集合（特别是如果字符串很长）以及共享长前缀的字符串集更有效。
基数树的示例：
请注意，trie通常用作在一组字符串上进行前缀匹配的高效数据结构。 trie也可以用作关联数组（如哈希表），其中键是字符串。
当您有很多单词要由树表示时，会保存空间。 因为许多单词在树中共享相同的路径; 你的话越多，你就会节省更多的空间。
但是如果你想节省空间，有一个更好的数据结构。 Trie不像有向非循环字图（DAWG）那样节省空间，因为它在整个结构中共享公共节点，而trie不共享节点。 wiki条目解释了这么多细节，所以看看它。
以下是Trie和DAWG之间的差异（图形）：
存储在Trie（左）和DAWG（右）中的字符串“tap”，“tap”，“top”和“tops”，EOW代表词尾。
左侧的树是Trie，右侧的树是DAWG。 比较它们，看看DAWG如何有效地节省空间。 Trie具有表示相同字母/子字的重复节点，而DAWG对于每个字母/子字只有一个节点。
它不是关于内存中的廉价空间，而是关于文件或通信链接中的宝贵空间。 使用构建该trie的算法，我们可以以三位，左右右方式发送“十”。 相比24位“十”将占用未压缩的，这是宝贵的磁盘空间或传输带宽的巨大节省。
Guava确实可以在每个级别存储密钥，但要意识到的是，密钥并不真正需要存储，因为节点的路径完全定义了该节点的密钥。 实际上需要存储在每个节点的所有内容都是一个布尔值，指示这是否是叶子节点。
像任何其他结构一样，尝试擅长存储某些类型的数据。 具体来说，尝试最好存储共享公共根的字符串。 例如，考虑存储完整路径目录列表。