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