TRIE数据结构中Search操作的时间复杂度

Question

我正在尝试实现基于字典的 trie 数据结构。请在下面找到 python 代码。

class Trie:
  def __init__(self):
     self.word_end = '_end_'
     self.root = {}

  def add_word(self, word):
     self.add_words([word])

  def add_words(self, words):
     for word in words:
         current_dict = self.root
         for letter in word:
             current_dict = current_dict.setdefault(letter, {})
         current_dict[self.word_end] = self.word_end


  def check_word(self, word):
     current_dict = self.root
     for letter in word:
         if letter in current_dict:
             current_dict = current_dict[letter]
         else:
             return False
     else:
         if self.word_end in current_dict:
             return True
         else:
             return False



tree = Trie()
tree.add_words(['foo', 'bar', 'baz', 'barz'])
print tree
"""
{'b': {'a': {'r': {'_end_': '_end_', 'z': {'_end_': '_end_'}}, 
             'z': {'_end_': '_end_'}}}, 
 'f': {'o': {'o': {'_end_': '_end_'}}}}
 """

print check_word('baz')
# True
print check_word('barz')
# True
print check_worf('barzz')
# False

我看到搜索一个词的复杂度是 O(m)，其中 m 是被搜索词的长度。此外，添加一个单词的复杂度非常相似 - O(m)，其中 m 是要添加的单词的长度。

问题： 这些复杂性太好了。有人可以确认这些复杂性吗？是不是我实现的 Trie 有问题？

Answer 1

在TRIE中搜索的时间复杂度确实是O(k)，其中k是要搜索的字符串的长度。这是正确的和被证明的事实。但是，存储要求是不利之处。 Trie 的每个节点都由多个分支组成。每个分支代表一个可能的键字符。我们需要将每个键的最后一个节点标记为单词节点的结尾。一个 Trie 节点字段 isEndOfWord 用于区分该节点为词尾节点。

一般来说，插入和搜索的开销为O(length_of_string)，而Trie的内存需求为O(ALPHABET_SIZE * length_of_string* N)，其中N是键的数量在特里。有高效的 trie 节点表示（例如压缩 trie、三元搜索树等）以最小化 trie 的内存需求。

TRIE数据结构中Search操作的时间复杂度

Time complexity of Search operation in TRIE data structure

python

algorithm

trie

data-structures