Python里面用什么trie树实现模块比较好

作者：tobe

链接：/question/21610353/answer/93639666

来源：知乎

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Trie树是一种树的数据结构，又被称为字典树，非常适用于Ajax自动补全等场景，因为它通过空间换时间能极大提高特别字符串的查询速度。

class TrieTree(object):

def __init__(self):

self.tree = {}

def add(self, word):

tree = self.tree

for char in word:

if char in tree:

tree = tree[char]

else:

tree[char] = {}

tree = tree[char]

tree['exist'] = True

def search(self, word):

tree = self.tree

for char in word:

if char in tree:

tree = tree[char]

else:

return False

if "exist" in tree and tree["exist"] == True:

return True

else:

return False

tree = TrieTree()

tree.add("abc")

tree.add("bcd")

print(tree.tree)

# Print {'a': {'b': {'c': {'exist': True}}}, 'b': {'c': {'d': {'exist': True}}}}

print(tree.search("ab"))

# Print False

print(tree.search("abc"))

# Print True

print(tree.search("abcd"))

# Print False