在字符检索中我们常用到一种数据结构——Trie树，它是一种树形结构，其应用相当广泛，如：
自动补全
拼写检查
打字预测
单词游戏
在看这篇文章之前，读者们可以先复习一下树形结构的知识，不然可能会有些吃力，但如果熟悉树，你将能十分轻松的阅读下去。
前缀(Trie)树的基本概念Trie树是一个有根的树，其结点具有以下字段：
最多有R个指向子结点的链接，其中每个链接对应字母表数据集中的一个字母
结尾标识符，标记单词结尾
基本操作实现本节实现了前缀树中比较常用的四个操作：
添加字符串(insert)
匹配单词(search）
匹配前缀(startswith)
删除字符串(delete)
class Trie: def __init__(self): self.lookup = {} # 插入单词 def insert(self, word): tree = self.lookup # 游标 for c in word: # 如果结点中不存在字符c，那么新开辟一个字符存储空间 if c not in tree: tree[c] = {'count':1} else: tree[c]['count'] += 1 # 游标下移 tree = tree[c] tree['#'] = '#' # 结束标识 print(tree) # 检查单词 def search(self, word): tree = self.lookup for c in word: if tree.get(c) is None or tree[c]['count'] == 0: return False tree = tree[c] # 如果前面所有字符都匹配成功，那么就剩下两种结果： # 1.word为前缀树字符串中的一个子串；2.word恰好与前缀树的一个字符串重合 return False if '#' not in tree else True # 检查前缀 def startsWith(self, prefix): tree = self.lookup for c in prefix: if tree.get(c) is None or tree[c]['count'] == 0: return False tree = tree[c] # 如果前面所有字符都匹配成功，那么就剩下一种结果：word恰好与前缀树的一个字符串重合 return True # 删除单词 def delete(self, word): if not self.search(word): raise ValueError('Trie树中不存在该单词！') tree = self.lookup for c in word: tree[c]['count'] -= 1 tree = tree[c] del tree['#'] if __name__ == '__main__': sample = Trie() sample.insert('IloveYiYi') sample.insert('IloveAKai') print(sample.lookup) print(sample.search('Ilove')) print(sample.search('IloveYiYi')) print(sample.startsWith('Ilove')) sample.delete('IloveYiYi') print(sample.lookup) print(sample.search('Ilove')) print(sample.search('IloveYiYi')) print(sample.startsWith('Ilove')) 参考资料力扣：实现前缀树