1回答

liuyubobobo

2022-07-10

已采纳

首先，Node 节点使用 TreeMap 确实对空间的浪费没有那么大，但还是浪费了很多空间。

对于一个长度为 n 的字符串，当使用 Trie 的时候，首先，每个节点 Node 的指针本身就是 n 的空间；在每个 Node 中，都有一个 boolean，又是 n 个空间。在 next 中，存储对应下一个 char 的 Node 的指针，又是 n 的空间。(而实际上，这里还少分析了一些空间。因为 TreeMap 是一棵红黑树。红黑树中的每个节点还要存储诸如 left, right, parent, color 等等和 char 以及对应的 Node 以外的信息。)

当然，如果有两个字符串，长度都为 n，其中前 n - 1 个字符都相同，只有最后一个字符不同，那么使用 Trie 存储是节省空间的。因为前 n - 1 个字符的 Node 是共用的。但是，另一方面，如果两个字符串，长度都为 n，只要第一个字符不同，那么这两个字符串就没有一个共用的节点，就要用 2n 个 Node 存储，其中每个 Node 的空间分析都如上所述，空间大大增加了。在这里，我考虑的是最坏情况。

==========

最关键的是，使用 TreeMap 作为 next 的 Trie，效率是低的。因为红黑树的效率是“低的”。这里说红黑树的效率低，是直接和含有 26 个元素的一维数组比。所以有了这一小节的内容：https://class.imooc.com/lesson/1587#mid=40052

（甚至我遇到过，在 OJ 上，使用 TreeMap 的 Trie 会超时，使用静态数组做 next 的 Trie 就 AC 的情况。）

但如果使用静态数组做 next，空间的耗费进一步增加了。因为此时，对于每一个 Node，都至少要有 26 个空间开出来用于存储 next，哪怕 next 指向的是 null。

此时，在最坏的情况下，所有字符串的所有字符都是单独的一个 Node，但是每个 Node 都需要额外分配 26 个空间供 next 使用（虽然他们都指向 null）。这就是我说的，在最坏情况下，Trie 用的空间，是单独一个字符串的存储空间的 27 倍的情况。

（实际上，我也在 OJ 上遇到过，使用静态数组做 next 的 Trie 会 MLE，但是使用 TreeMap 的 Trie 可以 AC 的情况：））

继续加油！：） 

1