字典树介绍以及C++实现

字典树的概念

字典树（Trie），又称为前缀树或单词查找树，是一种树形数据结构，主要用于存储具有相同前缀的字符串集合。它特别适合用于词典中的单词查找、自动补全、拼写检查等应用。

字典树算法的核心思想就是每层存入单词的字符，顺着树节点依次往下排布，用bool judge变量来标记此字符处是否构成单词（某个单词的结尾字符），还可以用一个int counter变量来累计某个前缀出现的次数。

字典树的特点：

1. 根节点不包含字符，通常为空。
2. 每个节点表示一个字符串中的字符。
3. 从根节点到某一节点的路径表示一个字符串。
4. 每个节点的所有子节点包含的字符都不相同。

字典树的操作：

• 插入操作：将一个字符串逐字符插入字典树。对于每个字符，从根节点开始，检查是否存在对应的子节点。如果不存在，则创建一个新的节点。
• 查找操作：检查一个字符串是否在字典树中。类似于插入操作，逐字符检查是否存在对应的节点。
• 删除操作：从字典树中删除一个字符串。需要小心处理节点的删除，以确保不影响其他字符串的存储。

字典树的优点：

• 快速查找：查找的时间复杂度为O(m)，其中m为待查找字符串的长度。
• 节省空间：通过共享相同前缀的方式，节省了存储空间。

字典树的缺点：

• 空间消耗大：在最坏的情况下，字典树可能需要大量的节点和指针。
• 实现复杂性：相对于哈希表，字典树的实现相对复杂。

字典树在很多应用中表现出色，尤其是在需要处理大量字符串并进行快速查找的场景中。

C++代码实现字典树

在C++中实现字典树（Trie）通常包括以下几个步骤：

1. 定义 TrieNode 类：每个节点包含若干子节点和一些必要的信息，比如标记是否是某个单词的结尾。
2. 定义 Trie 类：主要提供插入、查找和删除等功能。

下面是一个简单的字典树（Trie）的C++实现：

1. 定义 TrieNode 类

#include <iostream>
#include <unordered_map>using namespace std;// TrieNode 节点结构
class TrieNode {
public:unordered_map<char, TrieNode*> children; // 子节点映射bool isEndOfWord;  // 是否是一个单词的结尾TrieNode() : isEndOfWord(false) {}
};

2. 定义 Trie 类

class Trie {
private:TrieNode* root;  // 根节点public:// 构造函数Trie() {root = new TrieNode();}// 插入一个单词到字典树void insert(const string& word) {currentNode = root;for (char c : word) {if (currentNode->children.find(c) == currentNode->children.end()) {currentNode->children[c] = new TrieNode();}currentNode = currentNode->children[c];}currentNode->isEndOfWord = true;  // 标记单词的结尾}// 查找一个单词是否存在于字典树中bool search(const string& word) {TrieNode* currentNode = root;for (char c : word) {if (currentNode->children.find(c) == currentNode->children.end()) {return false;  // 如果有任何字符找不到，返回 false}currentNode = currentNode->children[c];}return currentNode->isEndOfWord;  // 返回当前节点是否是单词的结尾}// 查找是否有任何单词以给定的前缀开始bool startsWith(const string& prefix) {TrieNode* currentNode = root;for (char c : prefix) {if (currentNode->children.find(c) == currentNode->children.end()) {return false;  // 如果前缀中的某个字符找不到，返回 false}currentNode = currentNode->children[c];}return true;  // 如果前缀存在，返回 true}
};

3. 使用字典树

int main() {Trie trie;// 插入单词trie.insert("apple");trie.insert("app");trie.insert("banana");// 查找单词cout << "search(\"apple\"): " << trie.search("apple") << endl;   // 输出 1 (true)cout << "search(\"app\"): " << trie.search("app") << endl;       // 输出 1 (true)cout << "search(\"banana\"): " << trie.search("banana") << endl; // 输出 1 (true)cout << "search(\"bat\"): " << trie.search("bat") << endl;       // 输出 0 (false)// 查找前缀cout << "startsWith(\"app\"): " << trie.startsWith("app") << endl;  // 输出 1 (true)cout << "startsWith(\"ban\"): " << trie.startsWith("ban") << endl;  // 输出 1 (true)cout << "startsWith(\"bana\"): " << trie.startsWith("bana") << endl;  // 输出 1 (true)cout << "startsWith(\"cat\"): " << trie.startsWith("cat") << endl;  // 输出 0 (false)return 0;
}

4. 代码解析

• TrieNode 类：

  • 使用 unordered_map 存储子节点映射，unordered_map 是 C++ 中一个哈希表实现，用来存储每个字符对应的子节点。
  • isEndOfWord 用来标记当前节点是否是某个单词的结尾。

• Trie 类：

  • insert：通过遍历单词的每个字符，将它们插入到字典树中。如果字符不存在，就创建新的节点。最后标记该节点为单词的结尾。
  • search：查找一个单词是否在字典树中。如果路径上的任何字符不存在，直接返回 false。最终检查最后一个节点是否是单词的结尾。
  • startsWith：查找是否有任何单词以给定前缀开始。只要能够找到前缀的所有字符，就返回 true。

5. 输出示例：

search("apple"): 1
search("app"): 1
search("banana"): 1
search("bat"): 0
startsWith("app"): 1
startsWith("ban"): 1
startsWith("bana"): 1
startsWith("cat"): 0

6. 优化

• 字典树的空间复杂度较高，特别是当字典中的单词较多时。为了节省空间，可以使用更紧凑的结构，如 压缩字典树（Radix Tree），或者使用 字符数组 替代 unordered_map，减少指针的开销。

总结

这个 C++ 实现展示了一个基本的字典树（Trie）数据结构，支持插入、查找和前缀查找等操作。它适用于需要高效查找大量字符串的场景，比如自动补全、词典查询等。