algorithm - 前缀树的查找成本是多少，为什么？

Question

给定一个前缀树和一个键。在树中查找密钥的成本是多少？

我在一篇论文中读到它是 O(1)。据我所知，它是 O(LogM)，其中 M 是密钥的长度。我找不到答案，为什么它是 O(1)，但有人提到，关键可能是如果我们忽略扫描密钥，那么它将是 O(1)。如果我们忽略扫描密钥，有人可以以图形方式（通过制作树并遍历）向我解释它是 O(1) 吗？

Answer 1

在 Trie 中查找密钥的成本不是O(1).

总时间是您尝试匹配的单词长度或树的深度中的最小值O(l)。l请注意，许多人将其写为O(log n)其中 n 是树中的总元素。

你从树的根开始。您只需要遍历与当前单词匹配的 1 个节点。你继续这个遍历，直到你匹配了这个词，或者这个词不在树中。由于每个节点只搜索 1 个子节点，因此它是O(l).