当前位置： 首页 > article >正文

【算法与数据结构】字典树（Trie）详解

article 2025/2/22 18:39:54

目录

一，字典树的定义

二，字典树的代码实现

完整代码+详细注释：

测试用例+测试结果：

三，处理其他字符 

四，内存优化与扩展

1. 内存优化

2. 扩展功能

五，扩展功能支持通配符匹配

六，相关题目

1，实现前缀树

2，添加与搜索单词 - 数据结构设计

 

一，字典树的定义

字典树，也叫前缀树或Trie树，是一种树形结构，是一种用于快速检索字符串的数据结构，每个节点代表一个字符，从根节点到某一节点的路径组成一个字符串。主要思想是利用字符串的公共前缀来节省存储空间。

【示例】：

给你n个单词，进行q次查询，每次询问一个单词，让你判断每次查询的字符串是否存在？

我们能想到的是暴力求解，遍历n个字符串，判断是否存在。

对于该问题，查找字符串，就像我们平时查字典的操作。首先确定它的第一个字母，再确定它的第二个字母......，最后就可以找到想要查找的单词。或者这个字符不存在于字典中。

下图是用字典树来存储字符串"abc"，"abb"，"bca"。

 上图中，红色节点表示：有一个以此节点为终点的单词。

比如在查找字符串"abb"时，每个字符都可以在树中查到，并且最后一个字符b节点为红色，说明该字符串存在与该字典树中。查找字符串"bc"时，每个租房有都可以在树种查到，但最后一个字符c节点不为红色，说明该字符串不存在于该字典树中。

从上面的示例中可以看出，对于字典树的每次查询，时间复杂度都是log级别的，比暴力求解更优。

二，字典树的代码实现

字典树的结构，通常每个节点包含一个指向子节点的指针数组，这里我们实现一个处理小写字母的字典树，每个字符对应的下标为ch-'a'，所以数组的大小为26。另外，还需一个标记位来标记是否是单词的结尾。而当前字符保存在哪呢？其实当前节点的字符可以不用保存，因为我们知道下标，加上‘a'，就可以拿到该字符了。

我们主要需要实现三种操作：包含插入、搜索和前缀匹配功能，这里我们用两个函数来实现，然后我们用一个二维数组来实现字典树的建树。

完整代码+详细注释：

#include <iostream>
#include <vector>
using namespace std;

//定义节点
struct TrieNode
{
	vector<TrieNode*> children;//存储字节点的指针数组
	bool isEnd;  //标记位
	TrieNode()
		:children(26, nullptr)
		, isEnd(false)
	{}
};

class Trie
{
public:
	Trie()
	{
		root = new TrieNode();
	}
	~Trie()
	{
		clear(root);
	}
	//插入单词
	void insert(const string& word)
	{
		TrieNode* node = root;
		for (char ch : word)
		{
			//计算索引
			int index = ch - 'a';  

			//当前节点为空，当前节点没有存储ch该字母,new一段空间出来
			if (node->children[index] == nullptr)
				node->children[index] = new TrieNode();

			//当前节点不为空，也就是当前节点已经存储ch该字母了，在ch的下面节点继续插入下一个字母
			node = node->children[index]; 
		}
		node->isEnd = true;
	}
	//搜索单词
	bool search(const string& word)
	{
		TrieNode* node = root;
		for (auto ch : word)
		{
			//计算索引
			int index = ch - 'a';

			//当前索引下为空，该字母不存在，则该字符串不存在
			if (node->children[index] == nullptr)
				return false;

			//当前索引下不为空，该字母存在，继续匹配下一个字母
			node = node->children[index];
		}
		//检查最后一个字母是否是结尾
		return node->isEnd;  
	}
	//前缀匹配
	bool startsWith(const string& prefix)
	{
		TrieNode* node = root;
		for (auto& ch : prefix)
		{
			int index = ch - 'a';
			if (node->children[index] == nullptr)
				return false;
			node = node->children[index];
		}
		return true; //不检查结尾状态
	}
private:
	//递归释放（析构辅助函数）
	void clear(TrieNode* node)
	{
		if (node == nullptr) return;
		for (int i = 0; i < 26; i++)
		{
			if (node->children[i])
				clear(node->children[i]);
		}
		delete node;
	}
	TrieNode* root; //根节点
};

测试用例+测试结果：


int main() {
	Trie trie;

	// 插入单词
	trie.insert("apple");
	trie.insert("app");
	trie.insert("banana");

	// 搜索测试
	cout << boolalpha;
	cout << "Search 'apple': " << trie.search("apple") << endl;    // true
	cout << "Search 'app': " << trie.search("app") << endl;        // true
	cout << "Search 'appl': " << trie.search("appl") << endl;      // false

	// 前缀匹配测试
	cout << "Prefix 'app': " << trie.startsWith("app") << endl;    // true
	cout << "Prefix 'ban': " << trie.startsWith("ban") << endl;    // true
	cout << "Prefix 'cat': " << trie.startsWith("cat") << endl;    // false

	return 0;
}

三，处理其他字符 

我们实现的Trie现在只适用于小写字母。

若要支持更多字符（如大写字母，数字，中文等），需要调整字符索引方式：

// 示例：扩展支持大写字母和数字（共62种字符）
int getIndex(char c) {
    if (c >= 'a' && c <= 'z') return c - 'a';          // 0-25
    else if (c >= 'A' && c <= 'Z') return 26 + c - 'A'; // 26-51
    else if (c >= '0' && c <= '9') return 52 + c - '0'; // 52-61
    else throw invalid_argument("Invalid character");
}

四，内存优化与扩展

1. 内存优化

  • 压缩字典树（Radix Tree）：合并只有一个子节点的路径，减少节点数量。

  • 动态分配子节点：使用unordered_map或vector替代固定数组，节省空间（适用于稀疏字符集）。

2. 扩展功能

  • 词频统计：在节点中添加count字段，统计单词出现次数。

  • 前缀自动补全：遍历前缀后的所有分支，收集完整单词。

  • 模糊搜索：支持通配符（如app*e）或编辑距离匹配。

总结：

字典树通过共享前缀高效存储字符串集合，适合前缀匹配和快速检索场景 。

五，扩展功能支持通配符匹配

对于通配符的情况，通常的处理方法是在搜索时遇到通配符时遍历所有可能的子节点。例如，处理"ap？e"时，在遍历到通配符的位置，需要检查所有子节点，继续匹配剩下的模式。这种方法可能需要递归或队列来管理多个可能的路径。

 如下图所示，当遍历到通配符？的位置时，需要遍历所有子节点l和p，然后继续匹配。直到匹配到e结束。

前面我们是通过vector来模拟字典树，这里用哈希表来实现。

那对于一个节点该存什么？一个标记位与前面实现的用途一样，一个哈希表来存字符和子节点的映射关系。通过该字符，可以找到它的所有字节点。

通配符？可以匹配任意单个字符，通配符*可以匹配任意长度字符（包括空）。

代码+注释：

bool wildcardSearch(TrieNode* node, const string& pattern, int pos)
{
	//访问到最后一个位置，直接返回
	if (pos == pattern.size())
		return node->isEnd;

	char c = pattern[pos];
	if (c == '？') //匹配任意单个字符
	{
		for (auto& pair : node->children)
		{
			//尝试匹配所有可能的节点
			if (wildcardSearch(pair.second, pattern, pos + 1));
			return true;
		}
		//走到这，说明*匹配成任何节点都找不到该字符串
		return false;
	}
	else if (c == '*') //匹配任意长度字符 包括空
	{
		return wildcardSearch(node, pattern, pos + 1) //跳过*
			|| wildcardSearch(node, pattern, pos);  //继续匹配当前字符
	}
	else //其他正常情况
	{
		if (node->children.count(c) == 0)
			return false;
		return wildcardSearch(node->children[c], pattern, pos+1);
	}
}

完整代码：

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

struct TrieNode
{
	bool isEnd=false;//结尾标志
	unordered_map<char, TrieNode*> children; //存储子节点
};

class FuzzyTrie
{
public:
	FuzzyTrie()
	{
		root = new TrieNode();
	}
	~FuzzyTrie()
	{
		clear(root);
	}
	void insert(const string& word)
	{
		//插入逻辑与Trie一样
		TrieNode* node = root;
		for (auto ch : word)
		{
			if (node->children[ch] == nullptr)
				node->children[ch] = new TrieNode();
			node = node->children[ch];
		}
		node->isEnd = true;
	}
	//通配符搜索接口
	bool wildcardMatch(const string& pattern)
	{
		return wildcardSearch(root, pattern, 0);
	}
private:
	//通配符匹配辅助函数
	bool wildcardSearch(TrieNode* node, const string& pattern, int pos)
	{
		//访问到最后一个位置，直接返回
		if (pos == pattern.size())
			return node->isEnd;

		char c = pattern[pos];
		if (c == '？') //匹配任意单个字符
		{
			for (auto& pair : node->children)
			{
				//尝试匹配所有可能的节点
				if (wildcardSearch(pair.second, pattern, pos + 1));
				return true;
			}
			//走到这，说明*匹配成任何节点都找不到该字符串
			return false;
		}
		else if (c == '*') //匹配任意长度字符 包括空
		{
			return wildcardSearch(node, pattern, pos + 1) //跳过*
				|| wildcardSearch(node, pattern, pos);  //继续匹配当前字符
		}
		else //其他正常情况
		{
			if (node->children.count(c) == 0)
				return false;
			return wildcardSearch(node->children[c], pattern, pos+1);
		}
	}
	void clear(TrieNode* node)
	{
		if (node == nullptr)
			return;
		for (auto& pair : node->children)
		{
			clear(pair.second);
		}
		delete node;
	}
	TrieNode* root;
};

 

六，相关题目

1，实现前缀树

题目链接：208. 实现 Trie (前缀树) - 力扣（LeetCode）

class Trie {
public:
    Trie() :children(26),isend(false){}
    
    void insert(string word) {
        Trie* node=this;
        for(char ch:word)
        {
            ch-='a';
            if(node->children[ch]==nullptr)
            node->children[ch]=new Trie();
            node=node->children[ch];
        }
        node->isend=true;
    }
    Trie* searchPrefix(string prefix)
    {
        Trie* node=this;
        for(char ch:prefix)
        {
            ch-='a';
            if(node->children[ch]==nullptr)
            return nullptr;
            node=node->children[ch];
        }
        return node;
    }
    
    bool search(string word) {
        Trie* node=this->searchPrefix(word);
        return node!=nullptr&&node->isend;
    }
    
    bool startsWith(string prefix) {
        return searchPrefix(prefix)!=nullptr;
    }
    private:
    vector<Trie*> children;
    bool isend;
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

2，添加与搜索单词 - 数据结构设计

题目链接：211. 添加与搜索单词 - 数据结构设计 - 力扣（LeetCode）

struct TrieNode
{
    vector<TrieNode*> children;
    bool isend;
    TrieNode():children(26,nullptr),isend(false){}
};
void insert(const string& s,TrieNode* root)
{
    TrieNode* node=root;
    for(char ch:s)
    {
        ch-='a';
        if(node->children[ch]==nullptr)
        node->children[ch]=new TrieNode();
        node=node->children[ch];
    }
    node->isend=true;
}
class WordDictionary {
public:
    WordDictionary() {
        trie=new TrieNode();
    }
    
    void addWord(string word) {
        insert(word,trie);
    }
    
    bool search(string word) {
        //遇到.匹配任意字符
        return dfs(word,0,trie);
    }
    bool dfs(string& word,int index,TrieNode* node)
    {
        if(index==word.size())
        return node->isend;

        char ch=word[index];
        if(ch>='a'&&ch<='z')
        {
            TrieNode* children=node->children[ch-'a'];
            if(children!=nullptr&&dfs(word,index+1,children))
            return true;
        }
        else if(ch=='.')
        {
            for(int i=0;i<26;i++)
            {
                TrieNode* child=node->children[i];
                if(child!=nullptr&&dfs(word,index+1,child))
                return true;
            }
        }

        return false;
    }
    private:
    TrieNode* trie;
};

 

 


http://www.kler.cn/a/556445.html

相关文章：

  • 火语言RPA--Excel插入空列
  • 虚幻5 UI/HUD界面如何设置、播放动画
  • 设计模式教程：解释器模式（Interpreter Pattern）
  • [GESP202312 六级] 工作沟通
  • Java 内存区域详解
  • Python与MCU通信：串口数据采集及CSV/Excel存储方法
  • CloudMounter for Mac v4.11 挂载云盘为本地磁盘 支持M、Intel芯片
  • 教育界的“元宇宙”：虚拟展厅如何重塑学习世界
  • Day8 25/2/21 FRI
  • 破局与重构：水务企业数字化转型路径探索
  • 解决elementUi el-select 响应式不生效的问题
  • 使用 pjsua2 开发呼叫机器人，批量拨打号码并播放固定音频
  • Windows 下免费开源的多格式文件差异对比工具
  • 什么是逻辑分析仪？
  • 【C# 数据结构】队列 FIFO
  • HTML 中的 Canvas 样式设置全解
  • 【deepseek】Ubuntu/centos系统中无法直接git clone下载模型的解决方法（手动下载）
  • js面试八股
  • ESP32 websocket-client
  • DuodooBMS源码解读之 purchase_change 模块