Acm Trie树

### ACM Trie树详解 #### 一、Trie树的基本概念 **Trie树**，又称为**字典树**或**前缀树**，是一种用于高效存储和检索字符串的树形数据结构。它通过利用字符串之间的公共前缀来减少查询时间，从而提高搜索效率。在诸如文本编辑器、搜索引擎、自动补全等功能中非常常见。 #### 二、Trie树的原理与结构 Trie树的基本思想是将关键字存放在路径上而不是节点上，这样可以减少存储空间的使用。每个节点代表一个字符，而从根节点到任意一个叶子节点的路径则构成了一个完整的字符串。 - **节点结构**：每个节点包含两个主要部分： - `isStr`：布尔标志位，用来标记该节点是否为一个完整字符串的结尾。 - `next[MAX]`：一个指针数组，每个指针指向一个子节点。在本例中，由于我们假设字符串由小写英文字母组成，因此数组大小为26。 ```c #define MAX 26 typedef struct TrieNode { bool isStr; // 标记该节点是否构成一个单词 struct TrieNode* next[MAX]; // 子节点分支 } Trie; ``` #### 三、Trie树的应用实例 假设我们需要构建一个Trie树，以存储字符串"abc"、"ab"、"bd"、"dda"。构建过程如下： 1. **创建根节点**：首先创建一个根节点，该节点没有任何信息。 2. **插入字符串**：对于每个字符串，从根节点出发，依次插入每个字符。 - 对于"abc"： - 首先检查根节点的`next['a' - 'a']`位置（即索引0），如果为空，则创建一个新的节点并将其链接到此位置。 - 然后移动到新创建的节点，并检查`next['b' - 'a']`（索引1）的位置，同样地，如果为空，则创建一个新节点并链接。 - 检查`next['c' - 'a']`（索引2）的位置，创建节点并链接。将最后一个节点的`isStr`设为`true`。 - 其他字符串的插入过程类似。 #### 四、Trie树的操作 Trie树支持多种操作，主要包括插入、查找和删除。 - **插入操作**：根据字符串逐个字符创建或链接节点，最后将最后一个节点的`isStr`设置为`true`。 - **查找操作**：从根节点开始，沿着字符路径向下遍历，如果到达字符串的末尾且该节点的`isStr`为`true`，则表示该字符串存在于Trie树中。 - **删除操作**：通常情况下，删除操作较为复杂，涉及到递归删除子树或节点。但在某些场景下，可能只需要简单地将某个节点的`isStr`设为`false`即可。 #### 五、代码实现示例 下面是一个简单的C++代码实现示例，用于插入和查找字符串。 ```cpp #include <iostream> #include <cstdlib> #define MAX 26 typedef struct TrieNode { bool isStr; // 标记该节点处是否构成单词 struct TrieNode* next[MAX]; // 儿子分支 } Trie; void insert(Trie* root, const char* s) { if (root == NULL || *s == '\0') return; int i; Trie* p = root; while (*s != '\0') { if (p->next[*s - 'a'] == NULL) { // 如果不存在，则建立节点 Trie* temp = (Trie*)malloc(sizeof(Trie)); for (i = 0; i < MAX; i++) temp->next[i] = NULL; temp->isStr = false; p->next[*s - 'a'] = temp; p = p->next[*s - 'a']; } else { p = p->next[*s - 'a']; } s++; } p->isStr = true; // 单词结束的地方标记此处可以构成一个单词 } int search(Trie* root, const char* s) { Trie* p = root; while (p != NULL && *s != '\0') { if (p->next[*s - 'a'] == NULL) return 0; // 字符串不存在 p = p->next[*s - 'a']; s++; } return p != NULL && p->isStr; // 检查是否到达字符串末尾且为一个单词 } ``` #### 六、Trie树的时间和空间复杂度分析 - **时间复杂度**：插入和查找操作的时间复杂度均为O(L)，其中L是字符串的平均长度。这是因为每个操作都沿着字符路径向下遍历，最多遍历L次。 - **空间复杂度**：在最坏的情况下，Trie树的空间复杂度为O(N * M)，其中N是字符串的数量，M是字符集的大小（本例中为26）。然而，在实际应用中，许多节点会共享相同的前缀，因此实际空间复杂度通常远低于理论最大值。 Trie树提供了一种有效的方法来存储和检索具有公共前缀的字符串集合。虽然它的空间消耗较大，但是在处理大量字符串时能够显著提高搜索效率。