Trie 树详解编程语言

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/20450.html