3.8.Trie树

Trie树

Trie 树，又称字典树或前缀树，是一种用于高效存储和检索字符串数据的数据结构，以下是关于它的详细介绍：

定义与原理

• 定义：Trie 树是一种树形结构，每个节点可以包含多个子节点，用于存储字符串集合。它的每个节点代表一个字符串的前缀，从根节点到任意节点的路径上的字符连接起来，就形成了一个字符串。
• 原理：Trie 树利用字符串的公共前缀来减少存储空间和提高检索效率。在插入和查找字符串时，从根节点开始，沿着与字符串中字符对应的子节点向下遍历，直到到达字符串的末尾或者无法继续匹配为止。

基本操作

• 插入操作：从根节点开始，对于要插入的字符串中的每个字符，检查当前节点的子节点中是否存在该字符对应的节点。如果存在，则移动到该子节点；如果不存在，则创建一个新的子节点，并将其与当前节点连接起来，然后继续处理下一个字符，直到字符串的所有字符都被处理完毕。
• 查找操作：同样从根节点开始，按照要查找的字符串中的字符顺序，依次检查当前节点的子节点中是否存在匹配的字符。如果在遍历过程中找不到匹配的字符，或者到达了字符串的末尾但当前节点不是一个完整字符串的结尾标志，则表示查找失败；如果能够完整地遍历完字符串，并且最后到达的节点标记为一个完整字符串的结尾，则表示查找成功。
• 删除操作：先执行查找操作，找到要删除的字符串对应的节点。如果该节点没有子节点，直接删除该节点，并将其父节点中指向该节点的指针置为 null。如果该节点有子节点，需要根据具体情况进行处理，通常是将该节点标记为不再是一个完整字符串的结尾，以实现逻辑上的删除。

应用场景

• 字符串检索：在搜索引擎、字典查询等应用中，用于快速判断一个字符串是否存在于给定的字符串集合中，或者查找具有特定前缀的所有字符串。
• 词法分析：在编译器、文本处理等领域，用于对输入的文本进行词法分析，将文本分割成一个个单词或符号。
• 自动补全：在输入法、代码编辑器等工具中，根据用户输入的前缀，自动提示可能的完整单词或语句。
• 路由表存储：在计算机网络中，用于存储和查找路由表信息，根据目的 IP 地址的前缀快速确定路由路径。

优缺点

• 优点：插入和查找操作的时间复杂度通常为O(m)，其中 m 是字符串的长度，在处理大量字符串时效率较高；可以高效地支持前缀查询；节点可以共享公共前缀，节省存储空间。
• 缺点：对于没有公共前缀的字符串集合，Trie 树可能会退化为链表，导致空间浪费和性能下降；删除操作相对复杂，可能需要进行一些额外的处理来维护树的结构和完整性；Trie 树的节点通常需要存储多个指针，对于内存空间有限的环境可能不太友好。

下面是C++中实现Trie树的方法：

节点结构定义

在 C++ 中，通常使用结构体或类来定义 Trie 树的节点。每个节点需要包含一个存储字符的成员变量，以及一个用于存储子节点指针的数组或容器，还需要一个标记来表示该节点是否是一个字符串的结尾。以下是一个简单的节点结构体定义示例：

struct TrieNode {TrieNode* children[26];  // 假设只包含小写英文字母，用数组存储子节点指针bool isEndOfWord;TrieNode() {// 初始化子节点指针为nullptr，标记为不是单词结尾for (int i = 0; i < 26; i++) {children[i] = nullptr;}isEndOfWord = false;}
};

Trie 树的基本操作实现

• 插入操作：从根节点开始，根据要插入字符串的每个字符，在当前节点的子节点中查找是否存在对应的字符节点。如果不存在，则创建一个新的节点。最后，将字符串末尾的节点标记为单词结尾。示例代码如下：

void insert(TrieNode* root, const std::string& word) {TrieNode* node = root;for (char c : word) {int index = c - 'a';if (node->children[index] == nullptr) {node->children[index] = new TrieNode();}node = node->children[index];}node->isEndOfWord = true;
}

• 查找操作：从根节点开始，按照要查找字符串的字符顺序，在 Trie 树中依次查找对应的子节点。如果在查找过程中遇到不存在的子节点，或者到达字符串末尾时节点不是单词结尾标记，则表示查找失败。示例代码如下：

bool search(TrieNode* root, const std::string& word) {TrieNode* node = root;for (char c : word) {int index = c - 'a';if (node->children[index] == nullptr) {return false;}node = node->children[index];}return node->isEndOfWord;
}

• 前缀匹配操作：用于查找是否存在以给定前缀开头的字符串。与查找操作类似，从根节点开始，按照前缀的字符顺序在 Trie 树中查找子节点。只要能够完整地匹配前缀的所有字符，就表示存在以该前缀开头的字符串。示例代码如下：

bool startsWith(TrieNode* root, const std::string& prefix) {TrieNode* node = root;for (char c : prefix) {int index = c - 'a';if (node->children[index] == nullptr) {return false;}node = node->children[index];}return true;
}

完整示例

以下是一个使用上述 Trie 树操作的完整示例：

#include <iostream>
#include <string>// 前面定义的TrieNode结构体和insert、search、startsWith函数int main() {TrieNode* root = new TrieNode();// 插入一些单词insert(root, "apple");insert(root, "app");insert(root, "banana");// 查找单词std::cout << "查找apple: " << (search(root, "apple")? "找到" : "未找到") << std::endl;std::cout << "查找app: " << (search(root, "app")? "找到" : "未找到") << std::endl;std::cout << "查找banana: " << (search(root, "banana")? "找到" : "未找到") << std::endl;std::cout << "查找orange: " << (search(root, "orange")? "找到" : "未找到") << std::endl;// 前缀匹配std::cout << "以app开头的单词: " << (startsWith(root, "app")? "存在" : "不存在") << std::endl;std::cout << "以ban开头的单词: " << (startsWith(root, "ban")? "存在" : "不存在") << std::endl;std::cout << "以ora开头的单词: " << (startsWith(root, "ora")? "存在" : "不存在") << std::endl;return 0;
}

在 C++ 标准库中没有直接提供 Trie 树的数据结构，但可以使用unordered_map等容器来实现类似的功能，STL 中的std::string_view也可以与 Trie 树结合使用，提高字符串处理的效率。