【数据结构】前缀树（字典树)汇总

2024-06-10 09:04
文章标签 数据结构 前缀 字典 汇总

本文主要是介绍【数据结构】前缀树（字典树)汇总，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

基础

{“a”,“abc”,“bac”,“bbc”,“ca” }的字典树如下图：
在这里插入图片描述
最主用的应用：一，字符串编码。二，位运算。

字符串编码

相比利用哈希映射编码，优点如下：
依次查询长度为n的字符串s的前缀时间复杂度是O(n)。查询完s[0…i]，再查询s[0…i+1]的时间复杂度是O(1)。而哈希映射的时间复杂度是：O(nn)。
利用哈希映射编码的代码如下：
注意m_iLeafIndex 为-1，表示此节点不是任何字符串的结束字符。

class CStrToIndex
{
public:CStrToIndex() {}CStrToIndex(const vector<string>& wordList) {for (const auto& str : wordList){Add(str);}}int Add(const string& str){if (m_mIndexs.count(str)) { return m_mIndexs[str]; }m_mIndexs[str] = m_strs.size();m_strs.push_back(str);return  m_strs.size()-1;}vector<string> m_strs;int GetIndex(const string& str){if (m_mIndexs.count(str)) { return m_mIndexs[str]; }return -1;}
protected:unordered_map<string, int> m_mIndexs;
};

利用字典树编码的代码如下：

template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrieNode
{
public:~CTrieNode(){for (auto& [tmp, ptr] : m_dataToChilds) {delete ptr;}}CTrieNode* AddChar(TData ele, int& iMaxID){
#ifdef _DEBUGif ((ele < cBegin) || (ele >= cBegin + iTypeNum)){return nullptr;}
#endifconst int index = ele - cBegin;auto ptr = m_dataToChilds[ele - cBegin];if (!ptr){m_dataToChilds[index] = new CTrieNode();
#ifdef _DEBUGm_dataToChilds[index]->m_iID = ++iMaxID;m_childForDebug[ele] = m_dataToChilds[index];
#endif}return m_dataToChilds[index];}CTrieNode* GetChild(TData ele){
#ifdef _DEBUGif ((ele < cBegin) || (ele >= cBegin + iTypeNum)){return nullptr;}
#endifreturn m_dataToChilds[ele - cBegin];}
protected:
#ifdef _DEBUGint m_iID = -1;std::unordered_map<TData, CTrieNode*> m_childForDebug;
#endif
public:int m_iLeafIndex = -1;
protected://CTrieNode* m_dataToChilds[iTypeNum] = { nullptr };//空间换时间 大约216字节//unordered_map<int, CTrieNode*>    m_dataToChilds;//时间换空间 大约56字节map<int, CTrieNode*>    m_dataToChilds;//时间换空间,空间略优于哈希映射，数量小于256时，时间也优。大约48字节
};
template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrie
{
public:int GetLeadCount(){return m_iLeafCount;}CTrieNode<TData, iTypeNum, cBegin>* AddA(CTrieNode<TData, iTypeNum, cBegin>* par,TData curValue){auto curNode =par->AddChar(curValue, m_iMaxID);FreshLeafIndex(curNode);return curNode;}template<class IT>int Add(IT begin, IT end){auto pNode = &m_root;for (; begin != end; ++begin){pNode = pNode->AddChar(*begin, m_iMaxID);}FreshLeafIndex(pNode);return pNode->m_iLeafIndex;}	template<class IT>CTrieNode<TData, iTypeNum, cBegin>* Search(IT begin, IT end){auto ptr = &m_root;for (; begin != end; ++begin){ptr = ptr->GetChild(*begin);if (nullptr == ptr){return nullptr;}}return ptr;}CTrieNode<TData, iTypeNum, cBegin> m_root;
protected:void FreshLeafIndex(CTrieNode<TData, iTypeNum, cBegin>* pNode){if (-1 == pNode->m_iLeafIndex){pNode->m_iLeafIndex = m_iLeafCount++;}}int m_iMaxID = 0;int m_iLeafCount = 0;
};

二进制位运算（01前缀树)

比如求nums和x的xor最大值。
将nums放到01放到前缀树中。通过拆位法依次从高到低处理各位，如果x 此为1，则优先选择前缀树的0分支；如果x为0，则优先选择前缀树的1分支。

class C2BNumTrieNode
{
public:C2BNumTrieNode(){m_childs[0] = m_childs[1] = nullptr;}bool GetNot0Child(bool bFirstRight){auto ptr = m_childs[bFirstRight];if (ptr && (ptr->m_iNum > 0)){return bFirstRight;}return !bFirstRight;}int m_iNum = 0;C2BNumTrieNode* m_childs[2];
};template<class T = int, int iLeveCount = 31>
class C2BNumTrie
{
public:C2BNumTrie(){m_pRoot = new C2BNumTrieNode();}void  Add(T iNum){m_setHas.emplace(iNum);C2BNumTrieNode* p = m_pRoot;for (int i = iLeveCount - 1; i >= 0; i--){p->m_iNum++;bool bRight = iNum & ((T)1 << i);if (nullptr == p->m_childs[bRight]){p->m_childs[bRight] = new C2BNumTrieNode();}p = p->m_childs[bRight];}p->m_iNum++;}void Del(T iNum){auto it = m_setHas.find(iNum);if (m_setHas.end() == it){return;}m_setHas.erase(it);C2BNumTrieNode* p = m_pRoot;for (int i = iLeveCount - 1; i >= 0; i--){p->m_iNum--;bool bRight = iNum & ((T)1 << i);p = p->m_childs[bRight];}p->m_iNum--;}	void Swap(C2BNumTrie<T, iLeveCount>& o) {swap(m_pRoot, o.m_pRoot);swap(m_setHas, o.m_setHas);}C2BNumTrieNode* m_pRoot;std::unordered_multiset<T> m_setHas;
};template<class T = int, int iLeveCount = 31>
class CMaxXor2BTrie : public C2BNumTrie<T, iLeveCount>
{
public:T MaxXor(T iNum){C2BNumTrieNode* p = C2BNumTrie<T, iLeveCount>::m_pRoot;T iRet = 0;for (int i = iLeveCount - 1; i >= 0; i--){bool bRight = !(iNum & ((T)1 << i));bool bSel = p->GetNot0Child(bRight);p = p->m_childs[bSel];if (bSel == bRight){iRet |= ((T)1 << i);}}return iRet;}
};

题解

给字符串编码难道分
字典树】 【哈希表】 【字符串】3076. 数组中的最短非公共子字符串1635
【字典树（前缀树) 字符串】2416. 字符串的前缀分数和需要记录子孙数量1725
【字典树 最长公共前缀】1316. 不同的循环子字符串1836
【字典树（前缀树）】1032. 字符流1970
【map】【滑动窗口】【字典树】C++算法：2781最长合法子字符串的长度2203
【字典树】【字符串】【 前缀】3093. 最长公共后缀查询2118
【字典树】【KMP】【C++算法】3045统计前后缀下标对 II2327
【字典树 离线查询 深度优先】1938. 查询最大基因差2502
动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本2695
【动态规划】 【字典树】C++算法：472 连接词
【回溯 字典树（前缀树）】212. 单词搜索 II
【字典树 马拉车算法】336. 回文对
01前缀树
【字典树】2935找出强数对的最大异或值 II2348
【字典树（前缀树） 异或 离线查询】1707. 与数组中元素的最大异或值2358
【字典树（前缀树） 位运算】1803. 统计异或值在范围内的数对有多少2479
其它前缀树
【字典树（前缀树) 哈希映射 后序序列化】1948. 删除系统中的重复文件夹需要DFS2533

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

这篇关于【数据结构】前缀树（字典树)汇总的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1047734。

相关文章

C++工程编译链接错误汇总VisualStudio

C++工程编译链接错误汇总VisualStudio

目录 一些小的知识点 make工具 可以使用windows下的事件查看器崩溃的地方 dumpbin工具查看dll是32位还是64位的 _MSC_VER .cc 和.cpp 【VC++目录中的包含目录】 vs 【C/C++常规中的附加包含目录】——头文件所在目录如何怎么添加，添加了以后搜索头文件就会到这些个路径下搜索了 include<> 和 include"" WinMain 和
阅读更多...
一道经典Python程序样例带你飞速掌握Python的字典和列表

一道经典Python程序样例带你飞速掌握Python的字典和列表

Python中的列表（list）和字典（dict）是两种常用的数据结构，它们在数据组织和存储方面有很大的不同。 列表（List） 列表是Python中的一种有序集合，可以随时添加和删除其中的元素。列表中的元素可以是任何数据类型，包括数字、字符串、其他列表等。列表使用方括号[]表示，元素之间用逗号,分隔。 定义和使用 # 定义一个列表 fruits = ['apple', 'banana
阅读更多...
【数据结构】线性表：顺序表

【数据结构】线性表：顺序表

文章目录 1. 线性表2. 顺序表2.1 概念及结构2.2 接口实现2.3 顺序表的问题及思考 1. 线性表 线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式
阅读更多...
数据结构9——排序

数据结构9——排序

一、冒泡排序 冒泡排序（Bubble Sort），顾名思义，就是指越小的元素会经由交换慢慢“浮”到数列的顶端。 算法原理 从左到右，依次比较相邻的元素大小，更大的元素交换到右边；从第一组相邻元素比较到最后一组相邻元素，这一步结束最后一个元素必然是参与比较的元素中最大的元素；按照大的居右原则，重新从左到后比较，前一轮中得到的最后一个元素不参4与比较，得出新一轮的最大元素；按照上述规则，每一轮结
阅读更多...
【汇总】vivado_zynq学习资料

【汇总】vivado_zynq学习资料

DMA：https://www.xilinx.com/support/answers/57550.html
阅读更多...
直接得到Json串，转换为字典

直接得到Json串，转换为字典

0.新创建一个json文件，把json串拷贝到里面 1.先通过MainBundle找到资源对应的路径 2.将文件转换为NSData 3.通过NSJSonSerization得到字典 NSString*fileName=[[NSBundle mainBundle] pathForResource:@"myJson" ofType:@"json"];           NS
阅读更多...
【计算机组成原理】部分题目汇总

【计算机组成原理】部分题目汇总

计算机组成原理 部分题目汇总 一. 简答题 RISC和CICS 简要说明，比较异同 RISC（精简指令集）注重简单快速的指令执行，使用少量通用寄存器，固定长度指令，优化硬件性能，依赖软件（如编译器）来提升效率。 CISC（复杂指令集）包含多样复杂的指令，能一条指令完成多步操作，采用变长指令，减少指令数但可能增加执行时间，倾向于硬件直接支持复杂功能减轻软件负担。 两者均追求高性能，但RISC
阅读更多...
算法与数据结构面试宝典——回溯算法详解（C#，C++）

算法与数据结构面试宝典——回溯算法详解（C#，C++）

文章目录 1. 回溯算法的定义及应用场景2. 回溯算法的基本思想3. 递推关系式与回溯算法的建立4. 状态转移方法5. 边界条件与结束条件6. 算法的具体实现过程7. 回溯算法在C#，C++中的实际应用案例C#示例C++示例 8. 总结回溯算法的主要特点与应用价值 回溯算法是一种通过尝试各种可能的组合来找到所有解的算法。这种算法通常用于解决组合问题，如排列、组合、棋盘游
阅读更多...
PTA基础题考点汇总

PTA基础题考点汇总

一：字符串（数组）的逆序，栈的方法 **字符串数组的逆序 : ** 标准容器库的知识：定义stack容器于字符串：stackv; string s； //这里用到了c++中stl（标准容器库的知识）stack；//用的时候要声明头文件；定义stack容器和string；stack<string>v; string s；了解几个函数，v.top( )；//让最后一个元素出栈；（v是定义的
阅读更多...
嵌入式学习——数据结构（哈希、排序）——day50

嵌入式学习——数据结构（哈希、排序）——day50

1. 查找二叉树、搜索二叉树、平衡二叉树 2. 哈希表——人的身份证——哈希函数 3. 哈希冲突、哈希矛盾 4. 哈希代码 4.1 创建哈希表 4.2  5. 算法设计 5.1 正确性 5.2 可读性（高内聚、低耦合） 5.3 健壮性 5.4 高效率（时间复杂度）时间复杂度越低，效率越高， 5.5 低储存（空间复杂度）空间复杂度越低，存储空间越少 6.排序算法 6.1 冒
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2