数据结构中的 Patricia Trie

Patricia Trie，也称为 基数树 或 压缩前缀树，是一种用于存储一组字符串的空间高效数据结构。它是 Trie 数据结构的扩展，旨在通过压缩只有单个子节点的节点来最小化 内存使用。这种压缩减少了树中的节点和边数，使其在内存是关注点或处理具有共同前缀的大型字符串集时特别有用。

Patricia Trie 的主要思想是通过合并节点来消除冗余节点，从而在保持高效字符串检索操作的同时减少总体内存占用。它通过为每个节点的边标签分配唯一标识并 压缩具有单个子节点的路径 来实现这一点。在 Patricia Trie 中，每个节点代表一个或多个字符串的前缀。从节点出发的每条边代表一个字符，从根到叶节点的每条路径形成一个 完整的字符串。

通过压缩公共前缀，Patricia Trie 与 标准 Trie 相比节省了空间，在标准 Trie 中，每个节点代表一个字符。这种 优化 能够更快地搜索和插入操作，同时最大限度地减少内存使用。

方法一：基本 Patricia Trie 实现

程序

输出

Search 'apple': Not Found
Search 'app': Not Found
Search 'apple': Not Found
Search 'app': Not Found

说明

• 类定义

TrieNode：此类表示 trie 中的一个节点。每个节点包含一个无序映射 children，用于存储指向其子节点的指针，指示 trie 中的下一个字符。它还有一个布尔 isEnd 标志，用于标记单词是否在此节点结束。

PatriciaTrie：此类表示 Patricia Trie 本身。其私有成员 root 是 trie 根节点的指针。

• 构造函数

PatriciaTrie 的构造函数初始化 trie 的根节点。

• 插入（insert 函数）

将单词插入 trie 时，insert 函数接收单词作为输入并遍历 trie。它使用 longestCommonPrefix 函数查找单词与 trie 中现有节点之间的最长 公共前缀。

如果前缀完全匹配单词，它会将前缀的最后一个节点标记为单词的结尾，方法是将其 isEnd 标志设置为 true。如果前缀小于单词，它会使用 splitNode 函数 来分割节点。如果前缀大于单词，它会将单词的剩余字符添加到 trie。

• 搜索（search 函数）

search 函数用于检查给定的单词是否存在于 trie 中。它使用单词与 现有节点 之间的最长公共前缀来遍历 trie。

如果前缀完全匹配单词，并且前缀的最后一个节点被标记为单词的结尾，则返回 true，表示单词存在于 trie 中；否则，返回 false。

• 辅助函数

longestCommonPrefix：此函数查找给定单词与 trie 中现有节点之间的最长公共前缀。它遍历单词的 字符，检查每个字符是否存在于 trie 中。它返回找到的最长公共前缀。

splitNode：此函数在插入期间使用，当前缀小于单词时。它将节点分割成两个节点，一个用于 公共前缀，一个用于单词的剩余字符。

• 主函数

在 main 函数中，创建了一个 PatriciaTrie 实例，并将单词“apple”和“app”插入到 trie 中。

然后它在 trie 中搜索单词“apple”和“app”，并打印出每个单词是否找到。

复杂度分析

时间复杂度

插入（insert 函数）

插入操作涉及查找要插入的单词与 trie 中现有节点之间的最长公共前缀。此操作的时间复杂度为 O(m)，其中 m 是最长公共前缀的长度。

如果前缀小于单词，分割节点需要创建新节点，这需要 恒定时间。

因此，插入的最终时间复杂度为 O(m)。

搜索（search 函数）

在 trie 中搜索单词也涉及查找单词与现有节点之间的 最长公共前缀。此操作的时间复杂度为 O(m)。如果 前缀完全匹配 单词，则搜索操作需要恒定时间来检查 isEnd 标志。

因此，搜索的总时间复杂度为 O(m)。

空间复杂度

Trie 结构

trie 结构本身的空间复杂度取决于存储单词所需的节点数。在 最坏情况下，当单词之间没有公共前缀时，每个单词的每个字符在 trie 中都会有一个节点。

因此，trie 结构的空间复杂度为 O(n)，其中 n 是存储在 trie 中的所有单词的总字符数。

辅助空间

辅助空间复杂度包括 插入 和 搜索 操作期间存储变量、函数调用等所需的额外内存。

由于这些操作主要涉及 trie 的遍历和一些辅助计算，因此辅助空间复杂度为 O(1)。

方法二：使用数组或向量

程序

输出

Searching for apple: Found
Searching for app: Found
Searching for banana: Found
Searching for orange: Not found

说明

• TrieNode 结构

TrieNode 结构表示 trie 中的一个节点。它包含一个指向子节点（children）的指针向量和一个布尔标志 isEnd，指示该节点是否表示单词的结尾。构造函数使用 ALPHABET_SIZE 个空指针初始化 children 向量，并将 isEnd 设置为 false。

• PatriciaTrie 类

PatriciaTrie 类 表示 trie 本身。它包含用于插入和搜索操作的私有方法，以及一个根节点指针 root。insertUtil 函数 是一个递归辅助函数，用于将单词插入 trie。它根据单词的字符遍历树，在必要时创建 新节点，并将最后一个节点标记为单词的结尾。

searchUtil 函数 是一个递归辅助函数，用于在 trie 中搜索单词。它根据单词的字符遍历 trie，如果找到单词则返回 true，否则返回 false。

• 构造函数

PatriciaTrie 的构造函数初始化 trie 的根节点。

• 插入操作

insert 函数通过调用带有根节点和要插入的单词的 insertUtil 函数来插入单词。

• 搜索操作

search 函数通过调用带有根节点和要搜索的单词的 searchUtil 函数 来搜索 trie 中的单词。

主函数

在 main 函数中，创建了一个 PatriciaTrie 对象 trie。使用 insert 方法 将三个单词（“apple”、“app”和“banana”）插入到 trie 中。调用 search 方法来检查 trie 是否包含特定单词（“apple”、“app”、“banana”、“orange”）。将打印出搜索操作的结果。

复杂度分析

时间复杂度

插入

将单词插入 Patricia Trie 的时间复杂度为 O(L)，其中 L 是要插入的单词的长度。这是因为插入过程涉及根据单词的字符遍历 trie。

在插入期间，会调用 insertUtil 递归辅助函数，该函数遍历 trie 以查找新单词的适当位置。在 trie 的每个级别，函数都会访问相应的子节点，在必要时创建新节点以适应单词的字符。

由于 trie 表示为大小为 26 的数组（用于 小写英文字母），因此访问或创建子节点的每个操作都需要恒定时间。因此，插入的时间复杂度与要插入的单词的长度成正比。

搜索

在 Patricia Trie 中搜索单词也取决于其长度。在 search 函数中，会调用 searchUtil 递归辅助函数，该函数根据单词的字符遍历树。

在 trie 的每个级别，函数都会访问相应的子节点以检查下一个字符是否存在。如果单词存在于 trie 中，则搜索函数会到达单词的最后一个字符并返回 true。

否则，如果在遍历过程中缺少任何字符，则返回 false。

因此，搜索操作的时间复杂度也为 O(L)，其中 L 是要搜索的单词的长度。

空间复杂度

Patricia Trie 的空间复杂度主要取决于插入的单词数量和最长单词的长度。trie 中的每个节点代表单词中的一个字符，每个节点都包含指向子节点的指针向量。

对于长度为 L 的单词，trie 在对应于该单词的路径中最多可以有 L 个节点。在 最坏情况下，当所有单词都具有 不同的前缀 时，trie 可能包含 N 条路径，其中 N 是单词的数量。

trie 中的每个节点都需要一个固定大小的向量来保存子指针，通常是 26 个小写英文字母。这意味着每个节点为其 子指针 消耗恒定的空间。

因此，trie 的空间复杂度可以近似为 O(N⋅L)，其中 N 是单词的数量，L 是 最长单词 的长度。每个单词通过在其 trie 路径中添加节点来对空间复杂度做出贡献。如果单词共享 公共前缀，则可以通过仅存储这些前缀一次来节省空间，从而更有效地利用内存。

方法三：使用链表

程序

输出

Searching for apple: Found
Searching for app: Found
Searching for banana: Found
Searching for orange: Not found

说明

• TrieNode 结构

此结构表示 Patricia Trie 中的每个节点。它包含四个成员

data：节点中存储的字符。

isEnd：一个 布尔标志，指示该节点是否标记为单词的结尾。

firstChild：指向第一个子节点的指针。

nextSibling：指向 下一个同级节点 的指针。

• PatriciaTrie 类

此类封装了 trie 的功能。它包含一个指向根节点的指针。

• 构造函数

使用空根节点初始化 trie。

• insertUtil 函数

递归地将单词插入 trie。如果节点为空，则创建带有单词第一个字符的新节点。如果 当前字符 为空（'\0'），则将当前节点标记为单词的结尾。如果当前字符与当前节点的 data 匹配，则递归地将单词的其余部分插入 firstChild。

如果当前字符与当前节点的 data 不匹配，则递归地将单词插入 nextSibling。

• searchUtil 函数

递归地在 trie 中搜索单词。如果节点为空，则返回 false。如果 当前字符 为空（'\0'），则检查当前节点是否标记为单词的结尾。如果当前字符与当前节点的 data 匹配，则递归地搜索 firstChild 中单词的其余部分。

如果当前字符与当前节点的 data 不匹配，则递归地在 nextSibling 中搜索单词。

• insert 函数

调用 insertUtil 来将单词插入 trie。

• search 函数

调用 searchUtil 来在 trie 中搜索单词。

• 主函数

创建一个 PatriciaTrie 对象。将一些单词插入 trie：“apple”、“app”和“banana”。在 trie 中搜索各种单词，并打印它们是否被找到。

复杂度分析

时间复杂度

插入

在 insertUtil 函数中，单词的每个字符只处理一次。插入长度为 m 的单词的最坏时间复杂度为 O(m)。

由于没有嵌套的循环，因此将 n 个单词插入树的总时间复杂度为 O(nm)。

搜索

在 searchUtil 函数 中，单词的每个字符只处理一次。因此，搜索长度为 m 的单词的最坏时间复杂度为 O(m)。由于没有嵌套的循环，因此在 trie 中搜索 n 个单词的总时间复杂度为 O(nm)。这种 复杂性 的出现是因为对于每个单词，我们都从根遍历 trie 到相应的叶节点，这涉及到处理单词的每个字符。因此，搜索 n 个单词的总时间与所有单词的总字符数成正比，即 n 乘以最长单词的长度。

主函数

在 main 函数中，每个单词都 插入 到 trie 中，然后进行搜索。此部分的时间复杂度与所有单词的总字符数成正比，即 O(nm)。总的来说，所提供实现的插入和搜索操作的总时间复杂度为 O(nm)，其中 n 是插入的单词数，m 是单词的平均长度。

空间复杂度

TrieNode

每个 TrieNode 结构包含一个字符、一个 布尔标志 和两个指针。每个节点所需的空间是恒定的。由于每个节点仅取决于其数据和指针的大小，因此每个节点空间复杂度为 O(1)。

节点总数

trie 中的节点数取决于所有单词中的字符数。在最坏的情况下，当没有公共前缀时，每个字符都会创建一个新节点。

因此，trie 的空间复杂度 与 所有单词的总字符数成正比，即 O(nm)。

辅助空间

除了节点之外，在插入和搜索操作期间，还需要额外的空间用于堆栈中的函数调用和变量。此空间 与 trie 的深度成正比，而 trie 的深度受最长单词的长度限制。因此，辅助空间 复杂度为 O(m)，其中 m 是最长单词的长度。此空间用于维护递归调用和局部变量，从而使 Patricia Trie 的总体空间复杂度为 O(N⋅L + m)，其中 N 是单词的数量，L 是最长单词的长度。

由于 trie 节点，所提供实现的总体空间复杂度为 O(nm)，而操作期间的辅助空间为 O(m)。