Python中的树形算法: Trie树

2023-04-11 00:00:00 python trie 算法

Trie树，也叫字典树、前缀树，是一种树形结构，常用于字符串的存储和查找。它的核心思想是利用字符串的公共前缀来减少存储空间和查询时间的消耗。

Trie树的节点具有以下性质：

  1. 每个节点包含多个指向子节点的指针（引用）。
  2. 每个节点表示的是一个字符串的某一前缀。
  3. 根节点表示空字符串，即整棵Trie树的根。
  4. 叶子节点表示某个字符串的结束。
  5. 每个非叶子节点的子节点所代表的字符都不相同。

下面是一个简单的Trie树的示例，用于存储三个字符串：“dog”、“duck”和“dove”。

     root
     / \
    d   *
   / \   
  o   u 
 / \   \
g   v   c

在Trie树中查找一个字符串的过程十分简单，只需要从根节点开始依次匹配字符即可。如果匹配到某个字符，就继续往下遍历，查找下一个字符。如果所有字符都匹配成功，说明该字符串存在于Trie树中。如果在遍历过程中发现不存在某个字符，则说明该字符串不存在于Trie树中。

下面是一个简单的Trie树的Python代码示例。我们可以使用字典（map）来实现存储子节点的指针，键值对表示字符和指向子节点的引用。

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True

    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_end

    def starts_with(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children:
                return False
            node = node.children[c]
        return True

使用上面的代码，我们可以很容易地插入一个字符串，查找一个字符串是否存在于Trie树中，以及查找是否存在某个前缀。

trie = Trie()
trie.insert("dog")
trie.insert("duck")
trie.insert("dove")
print(trie.search("dog"))    # True
print(trie.search("dot"))    # False
print(trie.starts_with("do"))    # True
print(trie.starts_with("cat"))    # False

相关文章