Python 字典树（Trie）介绍

2023-04-11 00:00:00 python 介绍字典

字典树，也称为 Trie 树，是一种用于字符串匹配的数据结构。它存储一组键值对，并支持快速地查找一个字符串是否出现在这组键值中。

字典树的主要思想是利用字符串重叠的性质来压缩存储空间。它将每个字符串拆分成单个字符，并按照字符顺序依次存储在树的节点中。每个节点有多个子节点，每个子节点对应一个不同的字符。如果某个节点表示的字符串是某个键值的前缀，则该节点被标记为“终止节点”，并保存该键值。

字典树的基本操作包括插入、查找和删除。插入操作将一个新的键值对添加到字典树中。查找操作检查某个字符串是否出现在字典树中。删除操作将某个键值从字典树中删除。

Python 代码演示：

class TrieNode:
    # 字典树节点类
    def __init__(self):
        # 初始化字典树节点
        self.children = {}
        self.is_end = False

class Trie:
    # 字典树类
    def __init__(self):
        # 初始化字典树
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        # 插入一个字符串到字典树中
        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: str) -> bool:
        # 在字典树中查找一个字符串
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_end

    def startsWith(self, prefix: str) -> bool:
        # 在字典树中查找是否存在以 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.insert("pidancode.com")
trie.insert("皮蛋编程")
print(trie.search("pidancode.com"))    # True
print(trie.startsWith("pi"))           # True
print(trie.search("pianobencheng"))    # False

相关文章