trie 相当于 C++ 中的 std::map<std::string, int> 吗？

Question

trie 的通常实现是否等同于

std::map<std::string, int>

在 C++ 中？

所谓等价，我的意思是：它们是否具有相同的空间复杂度，以及它们各自的操作是否具有相同的时间复杂度？

Answer 1

不，我不这么认为。

std::map

和

std::set

通常实现为红黑平衡二叉树

前缀树中的空间复杂度要好得多——您将一大堆字符串的公共前缀存储在一个统一的位置，而在二叉树中，整个字符串存储在节点中，因此前缀在每个有它的字符串。

查找、插入、删除的时间复杂度仍然是平均水平

O(log n)

。然而，常数因子通常很重要。前缀树通常会降低高度但增加宽度。具体应用对于选择哪一个很重要。

Answer 2

trie 更加结构化：它的重要性不是相对比较，而是按字典顺序排列。当一个人特别需要一个 trie 时，通常是因为它给出了

O(log n)

中给定前缀的有序元素，然后可以对其进行迭代；就像制表符补全一样。

简单数字树的大小是众所周知的大，这是由于

O(sum of letters in trie)

的空间复杂度，其中常数因子是字母表的大小。共享分支使其成为上限，但通常大多数空间都被 null 占据。然而，如果我们存储子字符串而不是字母（路径压缩的一个示例），我们会得到一个空格

O(n)

优化版本。 Patrica 树——即具有路径压缩的二叉树——如 Nilsson1993Implementing——没有空值，非常紧凑。事实上，常量 Patrica 树甚至不需要存储字符串，只需要存储它们之间的差异。在某些方面，它很像 gperf 的某些算法（的开始）。

最坏情况下的 trie 时间性能很容易限制在

O(max length of any string)

。更好的界限来自于 Tong2016Smoothed，他展示了字符串差异是 独立且同分布 的情况下的性能——这是一个合理的假设，除非存储 {a, aa, aaa, aaaa，…}—是，

Trie [大概使用路径压缩]和 Patricia 树的平滑高度都是

Θ(log n)

。

因此，对于足够大的问题，查找两者之间可能不会发现太大差异。在实践中，我发现使用

map

由于局部性而稍微快一点，并且它比 C++ 中的

trie

更符合意识形态。