字典树（Trie）

字典树（Trie），又称为前缀树或单词查找树，是一种树形数据结构，主要用于存储字符串集合。它的特点是能够高效地进行字符串的插入、删除和查找操作，特别适合用于字典相关的应用场景。

基本结构

字典树的每个节点代表一个字符，根节点为空字符。每条从根到叶的路径代表一个字符串。字典树的每个节点可以有多个子节点，每个子节点代表一个可能的字符扩展。

操作

插入

插入一个字符串时，从根节点开始，逐字符检查是否存在对应的子节点。如果不存在，则创建一个新的子节点。重复此过程直到字符串的所有字符都被插入。

查找

查找一个字符串时，从根节点开始，逐字符检查是否存在对应的子节点。如果在某个字符上没有找到对应的子节点，则说明该字符串不在字典树中。

删除

删除一个字符串时，首先查找该字符串。如果找到，则从叶节点开始逐步删除节点，直到遇到一个有其他分支的节点为止。

优点

快速查找：字典树可以在O(m)时间复杂度内查找一个字符串，其中m是字符串的长度。
节省空间：通过共享公共前缀，字典树可以节省存储空间。

应用

自动补全：字典树可以用于实现输入法的自动补全功能。
拼写检查：可以快速查找和验证单词的拼写。
IP路由：在网络路由中，字典树用于存储和查找IP地址前缀。

示例

以下是一个简单的字典树实现示例：

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

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

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

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

    def delete(self, word):
        def _delete(node, word, depth):
            if depth == len(word):
                if not node.is_end_of_word:
                    return False
                node.is_end_of_word = False
                return len(node.children) == 0
            char = word[depth]
            if char not in node.children:
                return False
            should_delete_child = _delete(node.children[char], word, depth + 1)
            if should_delete_child:
                del node.children[char]
                return len(node.children) == 0
            return False

        _delete(self.root, word, 0)

字典树是一种强大的数据结构，广泛应用于各种需要快速字符串操作的场景中。