data-structures - Trie vs 红黑树 : which is better in space and time？

Question

尝试和红黑树对于存储字符串非常有效。

哪个时间复杂度更好？空间复杂度如何？

Answer 1

这取决于许多因素，例如您存储的字符串以及 trie 的表示方式。

在红黑树中，您需要对每个操作(插入、删除、查找等)进行 O(log n) 字符串比较。如果您比较两个没有共同前缀的字符串，或者比较两个 on string 较小的字符串，则比较的成本很小。比较的最坏情况是一个字符串是另一个字符串的前缀，在这种情况下必须读取所有字符。因此，如果您想在字符串的红黑树中查找长度为 L 的字符串，在最坏的情况下，您将通过进行 O(log n) 比较来完成 O(L log n) 工作，每个比较看输入字符串中的所有字符。但是，在最好的情况下，这只需要 O(log n) 时间，如果比较总是立即失败，就会发生这种情况。

在空间使用方面，红/黑树每个节点需要两个指针，每个字符串需要一个节点。 (红/黑位通常可以打包到指针的低位中)。因此总空间为 2n +(所有字符串的总长度)。

在 trie 中，插入、删除和查找在最坏的情况下(如果必须考虑输入的所有字符)需要 O(L)，在最好的情况下需要 O(1)(如果你很早就脱离了 trie)。这比红黑树快 O(log n) 倍，这对于大型集合可能很重要。然而，trie 的局部性更差，因为涉及到更多的指针追踪，并且没有要扫描的连续字符数组。

在内存使用方面，字母表大小为 k 的 trie 通常需要总共 kn 个指针，其中 n 是节点数。如果字母表很大，这可能比红/黑树严重得多。但是，可以通过使用 Patricia 树表示压缩 trie、使用更有效的数据结构来存储子指针或从 trie 构建 DAWG 来减少空间开销。

希望这可以帮助!