Python中的树形数据结构: 前缀树

2023-04-11 00:00:00 python 前缀 数据结构

前缀树又称 Trie 树，是一种树形结构，用于处理字符串匹配问题。它的优点在于能够快速进行字符串的查找、插入和删除操作。

以下是 Python 中使用前缀树实现字符串查找的示例代码：

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = 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_word = 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_word

t = Trie()
t.insert("pidancode")
t.insert("皮蛋编程")
print(t.search("pidancode")) # True
print(t.search("pi")) # False

在上面的示例代码中，我们定义了两个类：TrieNode 和 Trie。TrieNode 用于表示前缀树节点，包含一个 children 字典和一个 is_word 布尔值。Trie 类则包含一个根节点和两个方法：insert 和 search。

在 insert 方法中，我们遍历要插入的字符串中的每个字符，判断其是否在当前节点的 children 中。如果不在，则在 children 中新建一个 TrieNode；如果已存在，则继续遍历下一个字符。最后，将最后一位的 is_word 置为 True。

在 search 方法中，我们同样遍历要搜索的字符串中的每个字符，判断其是否在节点的 children 中。如果存在，则将节点指向该字符所在的子节点；如果不存在，则说明该字符串不在前缀树中，返回 False。最后，判断最后一个节点的 is_word 是否为 True，如果是则返回 True，否则返回 False。

在前缀树中，所有具有共同前缀的字符串会被保存在同一个分支上，这使得字符串查找非常高效。在本例中，"pidancode" 和 "皮蛋编程" 都拥有相同的前缀 "pi"，因此它们在前缀树的结构中也共享同一个节点。

相关文章