C++前缀树字典树的学习与模拟实现代码示例

前缀树介绍

在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。常用与拼写检查自动补全等; 是一种查找结构他的存储逻辑类似于哈希表，但是它相对于哈希表来说，限制更多，通用性较差，但是它的功能更加强大，可定制性也更强。 leetcode指路：实现Trie(前缀树)

如图可以查看trie树的基本结构：

与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。(这个是前缀树的精髓，也是难理解的地方，他不用存储某个节点的实际字符，他的对应下标映射出了需要存储的字符！)

一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。

一般情况下，不是所有的节点都有对应的值（他们只是前缀），只有叶子节点和部分内部节点所对应的键才有相关的值。

C++实现

核心思想

单链表:通过Node中封装的Node* next来找下一个连着的节点;

二叉树:通过Node中封装的Node* left 和 Node* right来找左右孩子节点;

前缀树？

因为维护了26个可能的Node*节点，所以跟上面一个道理，只是不能枚举出来了，用了一个Node*arr[26]来维护，恰巧把这个数组的下标设计成了某个字符的种类，就可以达到利用逻辑下标存储一个实际字符的作用了！

前缀树插入示意图

C++前缀树字典树的学习与模拟实现代码示例

上图中，每经过一个节点，将该节点的pass值加一，将末尾节点的end值加一。通过这种操作记录所有经过的数据记录

前缀树的插入是灵魂所在，搞懂了之后结构就明白了，不管是查找还是删除无非就是类似对链表的相关操作;

前缀树的大致框架

假设只存小写字符:

#include <iostream>
#include <vector>
#include <string>
using namespace std;
//26 个小写英文字母
#define NUM 26
class Trie{
private:
    Trie* arr[NUM];//多叉树(最大26个分支，因为26个小写字母嘛)
    int end;  //代表word完整单词的个数，0就是无此单词，只是一个前缀;insert一个单词的时候，这个单词的end首次出现就置为1;之后重复插入就end++;
    int pass; //代表以此前缀为公共前缀的节点个数,每次insert的时候会调整;
public:
    Trie() {
        memset(arr,0,sizeof(arr));//每个新节点的映射数组内容置nullptr
	    end = 0;
        ncount = 0; //初始化时以该映射信息字符为前缀的个数为1(这个字符本身算的1)
    }
    //插入单词
    void Insert(string &x)
    {
    }
    //查找 完全匹配字符串x 的数量
    int Find(string &x)
    {
    }
    //查找 前缀为字符串x 的数量
    int FindContain(string& x)
    {
    }
    //删除某个单词(前缀)
    bool Erase(string &x)
    {
    }
    ~Trie()
    {
        //因为new了26个连续的tire*空间，不要某个节点，不要把它对应给下层准备的26个空间也delete掉 防止内存泄漏
        for (int i = 0; i < NUMBER; i++)
		{
			if (nexts[i]){
                delete nexts[i];
            }
		}
    }
};

二叉树，父节点之下包含两个节点，分别为左右子节点，分别开辟空间，进行数据存储。

前缀树的结构也是类似的，它的每个节点包含两个部分: 值部分和指针部分。

它的存储方式为：在一棵树上，从根到子节点，分别存储所有目标数据的每一个下标位置上的数据

值部分主要又包含两个数据: 路过该节点的数量为pass，以该节点为结尾的数量为end。

指针部分主要包含它的所有子节点（比如26个小写字母），记为arr

下面的实现给出了四个接口:

Insert插入字符串，给前缀树添加一组数据

其中Insert方法需要注意插入新单词的过程中，路径所有前缀的个数pass+1

Find查找已存入的完整匹配的字符串个数
FindContain 查找已存入的前缀匹配的字符串个数
Erase 从前缀树中擦除一个完整字符串

Erase方法需要注意的是：

需Find先检查字符串是否存在；

pass == 1 时，代表其下没有任何可能存在的字符子串，所以直接将这个节点delete删除即可；

pass不为1且存在这个字符串，我们把end有效字符串个数-1就行

移除节点时，需要提前写好析构函数，将其节点开辟的26个Node*内存全部释放，以免出现内存泄漏;

前缀树插入字符串

另外，下面的功能代码不过多解释，代码注释自行理解，核心要点就是用数组下表映射的方式确定前往哪一条链表，之后的寻找和插入等操作都有点像链表的操作，搞个cur指针向后遍历等;

//插入单词
    void Insert(const string &x)
    {
        int size = x.size();
        Node* cur = root;
        cur->pass++;//不管insert啥，我们root空节点的pass相当于必须+1，最终这个root->pass可以代表一共insert了几次=-=
        for (int i = 0; i<size; i++) {
            char index = x[i] - 'a';
            //该字符在当前分支下的映射为空，没有那就new
            if (cur->arr[index] == nullptr) {
                cur->arr[index] = new Node;
            }
            cur->arr[index]->pass++; //不管 cur->arr[index] 是new的还是本来就有，insert要路过他了，他的pass+1,
            cur = cur->arr[index];//同时cur下指过去，进行下一个字符的insert
        }
        cur->end++;//insert最终将完整字符串个数end+1
    }

前缀树查找完整的字符串

  //查找 完全匹配字符串 x 的数量 -->end
    int Find(const string &x)
    {
        int size = x.size();
        Node* cur = root;
        for (int i = 0; i < size; i++) {
            char index = x[i] - 'a';
            //搜索到某个字符断了，没有这个完整的字符串x 返回0
            if (cur->arr[index] == nullptr) return 0;
            //没断，继续向下一个字符搜索;
            cur = cur->arr[index];
        }
        return cur -> end;//返回完整字符串x的有效个数end
    }

前缀树查找前缀匹配的字符串

//查找 前缀为字符串 x 的数量 -->pass
    int FindContain(const string& x)
    {
        //与Find一模一样的逻辑，只是最后的return 变了，这体现了Node*封装 int end  和int pass的好处了吧
        int size = x.size();
        Node* cur = root;
        for (int i = 0; i < size; i++) {
            char index = x[i] - 'a';
            if (cur->arr[index] == nullptr) return 0;
            cur = cur->arr[index];
        }
        return cur -> pass;
    }

前缀树删除完整字符串

 //删掉某个完整单词-以及这个单词后面可能存在的所有路径;（end>1 出现了很多次时，只需要end--一下）
    bool Delete(const string &x)
    {
        if (Find(x) == 0) return false;//压根没这个单词，删除失败;
        //有这个单词，我们需要找到他的prev前一个，delete掉他,prev的arr[x]=nullptr!
        Node* cur = root;
        Node* prev = root;
        int size = x.size();
        for (int i = 0; i < size; i++) {
            char index = x[i]-'a';
            //if (cur->arr[index] == nullptr) return false;这句不需要，都过了Find 肯定x每个字符都存在于字典树中
            cur->pass--;//别忘了路过的路径都得-1;
            prev = cur;
            cur = cur->arr[index];
        }
        if (cur->end==1) {//代表x所在字符串的个数只有1，直接递归delete删掉它 和 他后面的子串
            delete cur;//这个delete调析构，我们析构已经写好了，防止内存泄漏;
            prev->arr[x[size - 1]-'a'] = nullptr; // prev的arr[x最后一个字符-'a'] = nullptr!
        }
        else  cur->end--;//end>1 :end--代表这个节点的有效字符串个数-1，end==1 end-- == 0，这个节点的字符有效个数为0了，但是他因为pass>1,暂时保存 后面的不删;
        //end>1,那就end有效个数-1就行了;
        return true;
    }

总结

这个字典树的树结构可以根据需求来进行多样式的处理；比如我为了实现设计的功能，每个节点都保存了pass和end俩int方便功能记录和函数内的使用;
字典树本质上是牺牲空间，换查找同前缀的字符串提升时间效率的一种措施，但是我们这种每个节点都开26个数组的方式是非常浪费空间的，比如只有一个有效字符下标，其他25个nullptr都浪费了，而且在大量相同的前缀下就是单链表，浪费更严重。
这时候我们可以把Node*arr[26]数组换成map<char,Node*>这样搞(每层某一个char只会出现一次，所以char做key没问题)，需要配对啥就insert给红黑树中添加啥,大大节省空间;

所以说这个树没有啥固定玩法，可塑性太强了…这可能也是不刷题的我不常见的愿因？

完整代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;
//26 个小写英文字母
#define NUM 26
//前缀树节点
class Node {
public:
    Node* arr[NUM];//多叉树(最大26个分支，因为26个小写字母嘛)
    int end;  //代表
    int pass; //代表以此前缀为公共前缀的节点个数,每次insert的时候会调整
    Node()
    {
        end = 0;
        pass = 0;
        memset(arr, 0, sizeof(arr));
    }
    ~Node()
    {
        //这里有点递归的意思，除了删除当前节点，更重要的是如果当前节点的子节点还有非空。递归delete掉！
        for (int i = 0; i < NUM; i++)
        {
            if (arr[i]!=nullptr) delete arr[i];
        }
    }
};
//前缀树主体
class Trie{
public:
    Node* root = nullptr;
public:
    Trie() {
        root = new Node;
    }
    //插入单词
    void Insert(const string &x)
    {
        int size = x.size();
        Node* cur = root;
        cur->pass++;//不管insert啥，我们root空节点的pass相当于必须+1，最终这个root->pass可以代表一共insert了几次=-=
        for (int i = 0; i<size; i++) {
            char index = x[i] - 'a';
            //该字符在当前分支下的映射为空，没有那就new
            if (cur->arr[index] == nullptr) {
                cur->arr[index] = new Node;
            }
            cur->arr[index]->pass++; //不管 cur->arr[index] 是new的还是本来就有，insert要路过他了，他的pass+1,
            cur = cur->arr[index];//同时cur下指过去，进行下一个字符的insert
        }
        cur->end++;//insert最终将完整字符串个数end+1
    }
    //查找 完全匹配字符串 x 的数量 -->end
    int Find(const string &x)
    {
        int size = x.size();
        Node* cur = root;
        for (int i = 0; i < size; i++) {
            char index = x[i] - 'a';
            //搜索到某个字符断了，没有这个完整的字符串x 返回0
            if (cur->arr[index] == nullptr) return 0;
            //没断，继续向下一个字符搜索;
            cur = cur->arr[index];
        }
        return cur -> end;//返回完整字符串x的有效个数end
    }
    //查找 前缀为字符串 x 的数量 -->pass
    int FindContain(const string& x)
    {
        //与Find一模一样的逻辑，只是最后的return 变了，这体现了Node*封装 int end  和int pass的好处了吧
        int size = x.size();
        Node* cur = root;
        for (int i = 0; i < size; i++) {
            char index = x[i] - 'a';
            if (cur->arr[index] == nullptr) return 0;
            cur = cur->arr[index];
        }
        return cur -> pass;
    }
    //删掉某个完整单词-以及这个单词后面可能存在的所有路径;（end>1 出现了很多次时，只需要end--一下）
    bool Delete(const string &x)
    {
        if (Find(x) == 0) return false;//压根没这个单词，删除失败;
        //有这个单词，我们需要找到他的prev前一个，delete掉他,prev的arr[x]=nullptr!
        Node* cur = root;
        Node* prev = root;
        int size = x.size();
        for (int i = 0; i < size; i++) {
            char index = x[i]-'a';
            //if (cur->arr[index] == nullptr) return false;这句不需要，都过了Find 肯定x每个字符都存在于字典树中
            cur->pass--;//别忘了路过的路径都得-1;
            prev = cur;
            cur = cur->arr[index];
        }
        if (cur->end==1) {//代表x所在字符串的个数只有1，直接递归delete删掉它 和 他后面的子串
            delete cur;//这个delete调析构，我们析构已经写好了，防止内存泄漏;
            prev->arr[x[size - 1]-'a'] = nullptr; // prev的arr[x最后一个字符-'a'] = nullptr!
        }
        else  cur->end--;//end>1 :end--代表这个节点的有效字符串个数-1，end==1 end-- == 0，这个节点的字符有效个数为0了，但是他因为pass>1,暂时保存 后面的不删;
        //end>1,那就end有效个数-1就行了;
        return true;
    }
};

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

C++前缀树字典树的学习与模拟实现代码示例

目录

前缀树介绍

C++实现

核心思想

前缀树的大致框架

前缀树插入字符串

前缀树查找完整的字符串

前缀树查找前缀匹配的字符串

前缀树删除完整字符串

总结

完整代码

评论(0)

提示：请文明发言取消回复

作者信息

本站推荐

抖音小红书视频号短视频带货与直播变现更新

小红书电商自媒体创富课实战打卡笔记训练营

AI入门到精通，五阶课程学通识，掌握多领域实操要点

复制粘贴赚钱项目，零门槛零成本评论区留言评论即可轻松日赚取100+

商品卡运营课程，从选品到流量提升，学会抖音店铺动销与千川精准投放

今日头条掘金2.0，用AI工具写爆款文章，日入200+

热门资源

苹果cms海螺影视模板/大橙子模板/仿B站模板/v7模板/带手机移动端+详细安装使用说明

【已测】修复版H5骰子微信竞猜游戏骰宝免公众号版修复登录ID相同完美全套源码对接免签支付

网页游戏卧龙吟一键服务端加远程工具带架设教程

邪风曲单机版 2D回合制网络游戏源码一键安装即玩服务端公益服+GM工具

完整可用版本去水印小程序源码带教程源码

仙侠H5【苍穹剑诀】一键即玩端+授权后台+外网教程

C++前缀树字典树的学习与模拟实现代码示例

目录

前缀树介绍

C++实现

核心思想

前缀树的大致框架

前缀树插入字符串

前缀树查找完整的字符串

前缀树查找前缀匹配的字符串

前缀树删除完整字符串

总结

完整代码

评论(0)

提示：请文明发言 取消回复

相关文章

作者信息

本站推荐

热门资源

提示：请文明发言取消回复