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树常用于搜索提示，词频统计