我很困惑如何Trie实施节省空间&以最紧凑的形式存储数据！Trie节省空间，但是如何？
如果你看看下面的树。在任何节点上存储字符时，还需要存储对该字符串的每个字符的引用，以便存储其引用。 好吧，我们在普通字符到达时保存了一些空间，但是在存储对该字符节点的引用时我们失去了更多空间。
那么维护这棵树本身没有太多的结构性开销吗？相反，如果使用TreeMap来替代这个，可以说实现一个字典，这可以节省更多的空间，因为字符串将保存在一块，因此在存储引用时不会浪费空间，不是吗？当你很多的话要由树表示
你可能会推断出它节省的空间是在一个理想的机器上，每个字节都被有效分配。然而，真正的机器分配对齐的内存块（在Java上是8个字节，在某些C++上是16个字节），因此它可能不会节省任何空间。
Java字符串和集合增加了相对较高的数量，因此百分比差异可能非常小。
除非您的结构非常大，否则您的超时值会加重使用最简单，最标准，最容易维护收集的内存成本。例如你的时间可以很容易地胜过你试图保存的内存值的1000倍或更多。
例如假设你有10000个名字，你可以使用一个trie来保存16个字节。 （假设这可以在不花费更多时间的情况下证明），这相当于16 KB，在今天的价格是0.1美分。如果您的时间花费您的公司每小时30美元，则编写一行测试代码的成本可能为1美元。
如果您已经考虑更长时间以节省16 KB的时间，那么它不太可能在PC上值得。 （移动设备是一个不同的故事，但同样的论点适用恕我直言）
编辑：您启发了我补充更新http://vanillajava.blogspot.com/2011/11/ever-decreasing-cost-of-main-memory.html
特里将更快，节省空间。对于15K条目，它可以为您节省0.2美分的内存和CPU。如果你看到在路的另一边可能会有0.2美分，你会跨过去捡起来吗？如果需要大约一秒的时间，我只会这样做。鉴于TreeMap是一个内置的，经过良好测试的文档，并且被任何人支持你的代码所理解，它将为你节省更多的时间，而不仅仅是在内存中花费的时间（除非你使用许多设备将限制内存） –
如果您正在编写部署到数千或数百万用户的库，那么0.2美分就有多个，而当部署到按使用量收费的服务器时，0.2美分有另一个倍数。 “性能无关紧要”不是解决方案，而是意识形态。 – Ajax
如果您在总计2000美元的100万台机器中节省0.2美分。这值得花费几天甚至一周的时间。如果只有几十个小时甚至一天的时间，它只有100K台机器。如果只有10K台机器，你只需要几分钟的时间。如果只有一千台或更少的机器，你可能会浪费你的时间来担心它。规模确实很重要，大多数项目都没有部署到足够的机器上，担心少量资源是一个好主意。 –
空间被保存。因为许多单词在树中共享相同的路径;你有更多的话，你会节省更多的空间。
但是如果您想节省空间，那么会有更好的数据结构。 Trie并没有像directed acyclic word graph (DAWG)那样节省空间，因为它在整个结构中共享公共节点，而trie不共享节点。 wiki entry解释了这个细节，所以看看它。
这里是Trie树和DAWG之间的差（以图形方式）：
字符串 “抽头”， “轻敲”， “顶” 和 “强” 存储在字典树（左）和DAWG（右），EOW代表词末。
左边的树是Trie，右边的树是DAWG。比较它们并观察DAWG如何有效节省空间。 Trie具有代表相同字母/子字的重复节点，而DAWG每个字母/子字恰好有一个节点。
要使用字典树时节省空间，可以使用一个compressed trie（也称为帕特里夏字典树或基数树）中，其中一个节点可以代表多个字符：
在计算机科学中，基数树（还有patricia trie或radix trie） 是一个空间优化的trie数据结构，其中只有一个 子节点的每个节点都与其子节点合并。结果是每个内部节点 至少有两个孩子。与常规尝试不同的是，边缘可以是 ，标有字符序列以及单个字符。 这使得它们对于小集合（尤其是如果 字符串很长）以及共享长前缀的字符串集更有效。基数树的
实施例：
。注意，线索通常用作一个有效的数据结构，用于前缀匹配的一组串。一个trie还可以用作关联数组（如哈希表），其中的关键字是一个字符串。
我看了一下Patricia Trie的实现，但它是否是Guava和Apache Commons等流行库的一部分？我无法弄清楚它在Guava/apache commons集合中的实现 –
@Marcos在Guava中没有任何实现，尽管有一个长期运行的问题需要添加一个，所以最终可能会发生。 – ColinD
冷却。感谢您的澄清！ –
这不是关于内存中的廉价空间，而是关于文件或通信链接中的宝贵空间。使用构建该特里结构的算法，我们可以发送三位左右的“十”。与24比特相比，'十'会占用未压缩的空间，这是宝贵的磁盘空间或传输带宽的巨大节省。
这真的是一个很大的优势！ –
所以，仅仅为了在内存结构中不需要传输数据，而是为了获得大约10,000个名称的电话名称目录的搜索建议的高性能和空间有效的解决方案，是否会使用Trie在TreeMap上推荐？ –
番石榴确实可以存储在每个级别的关键，但实现的一点是，密钥并不需要存储，因为节点的路径完全定义了该节点的密钥。所有实际需要存储在每个节点的是一个布尔值，指示这是否是叶节点。
像任何其他结构一样，尝试擅长存储某些类型的数据。具体而言，尝试最好是存储共享公共根的字符串。例如，考虑存储全路径目录列表。
如果一个节点需要16个字节，但在16个以上的字符串（8个Java）中重用，它节省了空间。那么这只是一个问题，你是否节省了更多的空间而不是浪费。假设您的示例中的蓝色数字是重复计数，与简单的字符串数组相比，节省量确实会比浪费的空间大。但是在这种情况下，用重复计数存储完整的字符串会更好。 – han