前缀树（Trie）简介

前缀树，也称为字典树，是一种树形数据结构。它的核心思想是利用字符串的公共前缀来减少存储空间和提高查询效率。它由节点组成，每个节点包含多个指向子节点的指针（通常是一个固定大小的数组或者是一个哈希表），以及一个标记位用于表示从根节点到该节点是否构成一个完整的字符串。

工作原理

  • 插入操作
    从根节点开始，对于要插入的字符串中的每个字符，检查当前节点是否存在与该字符对应的子节点。
    如果不存在，则创建一个新的子节点；如果存在，则沿着对应的子节点继续处理下一个字符。
    当处理完字符串的最后一个字符后，将最后到达的节点的标记位置为表示一个完整字符串的结束。
  • 查询操作
    同样从根节点开始，按照待查询字符串的字符顺序依次在树中查找对应的子节点。
    如果在某一步找不到对应的子节点，则说明该字符串不存在于树中；如果能顺利找到最后一个字符对应的节点且该节点的标记位表示是一个完整字符串的结束，那么说明该字符串存在于树中。
  • 删除操作（相对复杂）
    首先要找到要删除的字符串对应的节点路径。
    如果该节点是其他字符串的中间节点，则不能直接删除，而是要清除该节点上表示字符串结束的标记位。
    如果该节点是叶子节点且没有其他字符串共享该节点的前缀部分，则可以从叶子节点开始依次向上删除节点直到遇到一个节点是其他字符串的中间节点或者是根节点。

主要特点和优势

  • 高效的字符串存储和检索：对于一组具有公共前缀的字符串，前缀树可以大大减少存储所需的空间，并且查询操作的时间复杂度与字符串的长度成正比，在大量字符串的场景下查询效率高。
  • 支持前缀搜索：可以很方便地查找具有某一特定前缀的所有字符串，这在自动补全、拼写检查等应用场景中非常有用。

应用场景

  • 自动补全功能：在搜索引擎、代码编辑器等软件中，当用户输入部分字符时，系统可以根据前缀树快速提供可能的完整字符串，如搜索框自动提示搜索词、代码编辑器自动补全变量名或函数名等。
  • 拼写检查：通过将字典中的单词构建成前缀树，可以快速检查一个输入的字符串是否是一个有效的单词或者找到最接近的正确拼写。
  • IP 路由：在网络中，IP 地址可以看作是由点分隔的数字字符串，利用前缀树可以高效地进行 IP 路由查找，根据 IP 地址的前缀匹配路由规则。
  • 单词统计和文本分析：统计文本中不同单词的出现次数等相关操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.value = 0

class MapSum:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()


    def insert(self, key: str, val: int) -> None:
        curNode = self.root
        for char in key:
            idx = ord(char) - ord("a")
            if not curNode.children[idx]:
                curNode.children[idx] = TrieNode()
            curNode = curNode.children[idx]
        curNode.value = val

    def _dfs(self, node):
        curNode, res = node, node.value
        for child in curNode.children:
            if child:
                res += self._dfs(child)
        return res


    def sum(self, prefix: str) -> int:
        curNode = self.root
        for char in prefix:
            idx = ord(char) - ord("a")
            if curNode.children[idx]:
                curNode = curNode.children[idx]
            else:
                return 0
        return self._dfs(curNode)