字典树 Trie Tree

Trie 树（又叫 字典树 或 前缀树）是一种用于存储集合中字符串的数据结构，特别适合用于处理一些与字符串相关的问题，比如词典查找、字符串匹配和前缀匹配等。它的基本思想是将字符串的公共前缀共享出来，从而减少存储空间和加速查找过程。

Trie 树的结构

Trie 树的每个节点代表一个字符或一个状态，它是由多个节点组成的。每条从根节点到某个节点的路径表示一个前缀。Trie 树的关键特点是：

根节点：Trie 树的根节点不存储任何字符，根节点的子节点表示字符串的第一个字符。

每个节点：每个节点表示一个字符。节点的子节点代表该字符后面接着的字符。

路径表示字符串：从根节点到某个节点的路径，表示了一个字符串的前缀。路径上的字符拼接起来，便是一个字符串。

标记终结节点：每个完整字符串的结尾节点标记该字符串的结束。这通常通过一个标志 isEndOfWord 来表示，表示某个路径到达该节点时是一个有效的字符串。

Trie 树的基本操作

插入：将一个字符串插入到 Trie 树中。通过字符逐一插入，如果当前字符的节点不存在，则创建新的节点。如果已经存在，则直接沿着已有路径继续插入。

搜索：查找 Trie 树中是否存在一个完整的字符串。依次比较字符串的每个字符，沿着树的路径走，若字符存在则继续走下去，直到完整字符串被匹配或者某个字符没有找到。

删除：删除某个字符串。删除时需要根据路径逐步回退，确保删除的是完整字符串并且删除路径上没有影响到其他字符串的匹配。

Trie 树的特点

前缀共享：Trie 树通过将公共前缀部分共享，减少了存储空间。例如，字符串 apple 和 appetizer 共享 app 前缀，因此可以在 Trie 树中只存储一次公共前缀 app，从而节省了存储空间。

高效查找：对于一个字符串的查找，时间复杂度与字符串的长度有关，而与树中存储的总字符串数无关。因此，Trie 树在查找方面具有很高的效率，特别适用于前缀匹配。

空间消耗：由于每个节点存储一个字符，并且每个节点都可能有多个子节点，因此 Trie 树的空间消耗可能相对较大。但通过适当优化（如压缩存储、使用哈希表等），可以减少空间消耗。

Trie 树的应用场景

前缀匹配：Trie 树特别适合进行前缀匹配的操作。例如，在输入法中，当用户输入一个字母时，Trie 树能够快速找到所有以该字母为前缀的词汇。

自动补全：根据已输入的前缀，Trie 树可以快速给出可能的完整字符串。例如，当你在搜索框中输入一部分单词时，可以使用 Trie 树自动补全建议。

词典查找：Trie 树常用于实现高效的字典查找，因为它能将相同前缀的单词合并，从而加速搜索操作。

IP 地址查找：Trie 树也可以用于一些与 IP 地址相关的查找，比如 CIDR 匹配等。

Trie 树的优缺点

优点：

高效查找：在查找字符串时，时间复杂度为 O(L)，其中 L 是字符串的长度，不受字典中总单词数的影响。

前缀共享：可以有效利用公共前缀，节省空间。

支持高效的前缀匹配：能够快速获取所有以某个前缀开头的字符串。

缺点：

空间消耗大：每个节点可能有多个子节点，因此 Trie 树可能会占用较大的内存，尤其是当字符集很大时（比如汉字字符集）。

构建复杂度高：插入操作的时间复杂度与字符串长度有关，且对于大量数据，Trie 树的构建和维护也比较复杂。

Trie 树的变种

压缩 Trie（Patricia Trie）：压缩 Trie 是 Trie 树的一种优化版本，它通过合并单一子节点来减少空间消耗，适用于节点较多的情况。

字典树 + 哈希表：在某些场景中，Trie 树的每个节点使用哈希表来存储子节点，可以提高查找效率和减少内存占用。

总结

Trie 树是一种高效的字符串存储和检索结构，特别适用于需要频繁前缀匹配的应用。它通过共享公共前缀来节省存储空间，并且查找和插入操作的效率都比较高。在一些要求高性能、低延迟的场景下（如自动补全、字典查找等），Trie 树是非常理想的选择。不过，由于 Trie 树的空间消耗较大，在使用时需要进行适当的优化，尤其是在字符集较大时。

Keywords

字典树 前缀树