我在大学里最喜欢的数据结构之一是 Trie .如果前缀是共享的，它是一个很好的数据结构，用于保存大量字符串。查找也很好，因为无论集合中有多少字符串，它们都是在字符串的 O(|length|) 处完成的。
相比之下，平衡树的设置项目数量为 O(log N)，加上您为比较支付的任何费用。哈希表将涉及哈希计算、比较等。
因此，there is no Trie implementation in the standard library of most languages 令我感到惊讶。 .
我能想出的唯一原因是内存访问成本可能使其过于昂贵。如果进行树查找，而不是调查 O(log N) 个位置，而不是执行 O(|length|) 个不同的位置，这会带来所有后果。如果字符串很长，这最终可能会太多。
所以我想知道:我刚才描述的问题有多少？当您需要存储大量字符串或字符串时，您会怎么做？
最佳答案
以前我不认为这是一个值得关注的领域，但现在你提到它，有时标准的 Trie 实现可能会很方便。另一方面，据我所知，Python 和 Perl 以及我现在使用的其他精通字符串的语言都使用 Tries。
最后我检查了一下，那是很久以前的事了，BSD 内核代码在代码中使用了 Tries (Patricia Tries) 来选择发送数据包的最佳接口(interface)。看起来像 Wikipedia has some info .
关于data-structures - 在现代架构上，Tries 仍然是一个好主意吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/624599/