我知道在 trie 中搜索给定前缀的时间为 O(M)，其中 M 是插入到 trie 中的任何单词的最大长度。
但是检索所有以特定前缀开头的元素的时间复杂度是多少？
我想到了一个可能的答案：
O(M+n) 其中 n 是以前缀开头的单词数。想法：搜索前缀在 O(M) 中。然后我有一个包含所有以给定前缀开头的单词的 subtrie，我只需要遍历它。问题（可能）：前缀树中的节点多于单词。但也许有某种形式的有效存储，这样我就不必看它们了？
问问题
433 次
1 回答
0
假设您有一个 trie，其中所有单词都以长度 L 的相同前缀开头。现在，报告以该前缀开头的所有单词需要您对 trie 进行完整搜索，这将花费时间 O(n)，其中 n 是trie 中的节点总数。
这里的挑战是，在 trie 中搜索以某个前缀开头的所有单词可能需要您搜索许多与前缀长度无关的节点。这取决于 trie 中有哪些节点。
如果您知道要经常进行这样的搜索，您可能需要考虑使用 Patricia trie（也称为基数 trie）。这是一种 trie，其中每条边都可以用多个字符标记，并且不允许有一个子节点和一个父节点的节点。如果你以这种方式存储 trie，那么你可以证明访问与特定 subtrie 中的单词对应的所有节点所需的时间是 O(z)，其中 z 是找到的单词数。这样做的原因是 Patricia trie 中的每个非叶节点都至少有两个子节点，因此包含 z 个叶节点的子树将有 z 个内部节点（检查这一点是一个很好的练习），所以你可以发现所有的叶子在扫描 O(z) 个节点之后。他们自己。如果您对此感到满意，这可以节省大量时间。
于 2016-11-01T01:49:51.487 回答