trie tree

算法 --Trie Tree

【字典树】(Trie Tree) 是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串）。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。 ——百度百科

【经典的字典树（只包含26个小写字母）】

1）构建树节点

class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.isEnd = False

two keys:

isEnd为True的节点就是上面图中红色的节点；
第二点很巧妙：利用了一个长度为26的数组，用下标表示字符（char - 'a'）,用该下标对应的值表示指向子节点的引用。

2）构建树，并写出树的一些方法

class Trie:
  def __init__(self):
      self.children = [None] * 26
      self.isEnd = False
  
  def searchPrefix(self, prefix: str) -> "Trie":
      node = self
      for ch in prefix:
          ch = ord(ch) - ord("a")
          if not node.children[ch]:
              return None
          node = node.children[ch]
      return node

  def insert(self, word: str) -> None:
      node = self
      for ch in word:
          ch = ord(ch) - ord("a")
          if not node.children[ch]:
              node.children[ch] = Trie()
          node = node.children[ch]
      node.isEnd = True

  def search(self, word: str) -> bool:
      node = self.searchPrefix(word)
      return node is not None and node.isEnd

  def startsWith(self, prefix: str) -> bool:
      return self.searchPrefix(prefix) is not None

分类：

后端

标签：

数据结构与算法

作者介绍

monica1005

微信公众号风控建模