Trie 树又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串
是一种多叉树的结构，特性：
根节点不包含字符
除根节点之外的每个节点保存一个字符
一条路径上的所有节点保存一个字符串
优点：
对于字符串的搜索有比较高的效率，时间复杂度为O(m) ，m为string中字符个数
可以生成以字母顺序排序的键值对集合
缺点：
空间消耗比较大
搜索效率上可能会比Hash慢
python实现Trie 树
class TrieTree(object): def __init__(self): self.root = {} # 字典中添加word def insert(self, word): tree = self.root for char in word: if char in tree: tree = tree[char] else: tree[char] = {} tree = tree[char] tree['exist'] = True # 字典中删除word def delete(self, word): tree = self.root for c in word: if c not in tree: print('字典中没有不用删') return False tree = tree[c] # 如果找到了就把'/'删了 del tree["exist"] while tree == {}: if word == '': return tmp = word[-1] word = word[:-1] tree = self.root for c in word: tree = tree[c] del tree[tmp] # 查找一个单词是否完整的在字典树里 def search(self, word): tree = self.root 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 # 查找是否有一个单词是这个前缀开始的 def startsWith(self, prefix: str): node = self.root for char in prefix: if char not in node: return False node = node[char] return True tree = TrieTree() tree.insert("hello") tree.insert("world") print(tree.root) print(tree.search("he")) print(tree.search("hello")) print(tree.startsWith("he")) tree.delete("hello") print(tree.root) print(tree.search("hello"))
应用：
trie树常用于搜索提示，词频统计
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/20450.html