数据结构：Trie（前缀树/字典树）

文章目录

  • 一、介绍Trie
    • 1.1、Trie的结点结构
    • 1.2、Trie的整体结构
  • 二、Trie的操作
    • 2.1、Trie插入操作
    • 2.2、Trie查找操作
    • 2.3、Trie前缀匹配操作
    • 2.4、Trie删除操作
  • 三、实战
    • 3.1、实现Trie（前缀树）

一、介绍Trie

  Trie 又称字典树、前缀树和单词查找树，是一颗非典型的多叉树模型，即每个结点的分支数量可能为多个。Trie这个名字取自“retrieval”，检索，读音和 try 相同。
  百度百科：Trie

1.1、Trie的结点结构

Trie的结点结构是这样的:

strcut TrieNode{
	bool isEnd;//该结点是否是一个串的结束。
	TrieNode * next[26];//字母映射表，结点个数跟一个串中包含的字符种树有关
	TrieNode(){//默认为空
		isEnd=false;//默认不是一个串的结束
		for(auto & i:next) i=nullptr;
	}
};

  需要注意的是，一个节点即使标记为某个串的结束（isEnd=true），也可以是其他更长串的前缀。这意味着，该节点可以有子节点，它们代表着以当前串为前缀的其他串。这个特性使得Trie成为一种极其有效的数据结构，用于处理具有共同前缀的字符串集合。

1.2、Trie的整体结构

在这个结点结构下，包含三个单词 “sea”,“sells”,“she” 的 Trie 会长啥样呢？
在这里插入图片描述
为了方便理解我们可以画成这样（也是实际树结构）：
在这里插入图片描述
  根据整体结构，我们可以理解Trie实际上用边表示字符，每次选择一个子节点就可以选定一个字符，如果某结点对应位置为空，则说明Trie不包含 从根到该结点的边连接成的串加上该位置对应的字符 构成的 前缀。

二、Trie的操作

首先创建根结点，初始时根结点为空。

TrieNode * root=new TrieNode();

2.1、Trie插入操作

向字典树Trie中插入一个单词word，它保证使用了已有字典树的最长单词前缀：

  1. 初始化：从Trie的根节点开始。
  2. 遍历单词中的每个字符：对于单词 word 中的每个字符 c：
    • 检查当前节点是否存在字符 c 对应的子节点。
    • 如果存在，移动到该子节点，继续查找下一个字符。
    • 如果不存在，查找则创建该子节点，并移动到该子节点。
  3. 检查单词完全匹配：在成功遍历单词 word 中的所有字符后，将最后一个节点标记isEnd=true。
void insert(string word){
	TrieNode * node=root;
	for(char c:word){
		if(node->next[c-'a']==nullptr){
			node->next[c-'a']=new TrieNode();
		}
		node=node->next[c-'a'];
	}
	node->isEnd=true;//串的结束只跟插入时的串有关。
	return;
}

2.2、Trie查找操作

判断字典树Trie中是否包含单词word：

  1. 初始化：从Trie的根节点开始。
  2. 遍历单词中的每个字符：对于单词 word 中的每个字符 c：
    • 检查当前节点是否存在字符 c 对应的子节点。
    • 如果存在，移动到该子节点，继续查找下一个字符。
    • 如果不存在，查找失败，返回 false（表示Trie中不存在单词 word）。
  3. 检查单词完全匹配：在成功遍历单词 word 中的所有字符后，需要检查当前节点是否标记为某个单词的结尾。
    • 如果当前节点标记为单词的结尾，则查找成功，返回 true。
    • 如果当前节点未标记为单词的结尾，则意味着Trie中没有完全匹配的单词，返回 false。
bool search(string word){
	TrieNode * node=root;
	for(char c:word){
		if(node->next[c-'a']==nullptr)
			return false;
		node=node->next[c-'a'];
	}
	return node->isEnd;//if(node->isEnd) return true;
}

2.3、Trie前缀匹配操作

判断字典树Trie中是否有以prefix为前缀的单词，由于Trie是通过插入结点生成的，因此只要一颗Trie能遍历完所有prefix中的字符，那么它必然是含有以prefix为前缀的单词的。它的实现和search操作类似：

  1. 初始化：从Trie的根节点开始。
  2. 遍历单词中的每个字符：对于单词 prefix 中的每个字符 c：
    • 检查当前节点是否存在字符 c 对应的子节点。
    • 如果存在，移动到该子节点，继续查找下一个字符。
    • 如果不存在，查找失败，返回 false。
  3. 检查单词完全匹配：在成功遍历单词 prefix 中的所有字符后，即所有字符均匹配，因此存在这样的前缀，返回true。
bool startsWith(string prefix){
	TrieNode * node=root;
	for(char c:prefix){
		if(node->next[c-'a']==nullptr)
			return false;
		node=node->next[c-'a'];
	}
	return true;
}

2.4、Trie删除操作

从Trie中删除一个串word时，我们应当从根结点把该路径上的结点依次删除，直至某结点的儿子不为空 或者 为根结点时，则不再删除。如果采用删除操作可以在树结点中记录儿子个数，这样可以快速判断是否还有儿子。可以通过在Trie结构中加入char ch，表示当前结点的字符应当是什么，可以快速找到儿子位置。这里采用整个文章的结构，所以不记录。

  1. 初始化节点数组：为了存储删除路径上的每个节点，函数首先创建了一个指针数组 path，大小为待删除字符串 str 的长度。
  2. 遍历Trie以找到字符串：函数遍历Trie以寻找与 str 匹配的字符串，同时在 path 数组中记录遍历过程中访问的每个节点。
  3. 检查并删除字符串：
    • 如果未找到完全匹配的字符串（即在Trie中不存在该字符串），函数返回 false。
      找到后，标记其isEnd=true。从字符串的末尾开始向上回溯，检查每个节点是否有其他子节点。
    • 如果有其他子节点或该节点为根，说明当前节点是其他字符串的前缀，函数结束，返回 true。
    • 如果没有其他子节点，并且isEnd==true，则函数结束，返回true。
    • 如果没有其他子节点，并且isEnd!=true，删除当前节点，并将其父节点中对应的指针设置为 nullptr。
bool delete(string word){
	vector<TrieNode *> path;
	TrieNode * node=root;
	path.push_back(node);
	for(auto &c:word){
		if(node->next[c-'a']==nullptr)
			return false;
		node=node->next[c-'a'];
		path.push_back(node);
	}
	if(path.back()->isEnd==false) return false;
	path.back()->isEnd=false;//可能非叶子结点，不能直接删除，先标记为不是串的结尾
	bool flag=true;
	while(flag&&path.size()>1){//回溯向上，判断是否删除结点
		if(path.back()->isEnd) break;//如果是串的结尾 那么也不能再删除了
		TrieNode * child=path.back();
		for(auto &i=child->next){//查看其是否有儿子，可以通过为每一个Trie结点维护一个儿子数量，来快速判断。
			if(i!=nullptr) {flag=false;break;}//不可删除
		}
		if(flag){//没儿子
			path.pop_back();
			TrieNode * fa=path.back();
			for(auto & i=fa->next)//找到儿子，并删除，可以通过在Trie结构中加入char ch，表示当前结点的字符应当是什么，可以快速找到儿子位置。
				if(i==child) {delete child;i=nullptr;break;}//删了之后break;不break会访问野指针。~
		}
	}
	return true;
}

这里需要注意指针 和 指针指向的内容 的区别：

  • i==child：指的是i和child的值相同，指针类型 相当于i和child指向的地址相同。
  • delete child：指的是回收child指向的内容。
  • i=nullptr：i是引用，实际上是修改i引用的fa->next[x]=nullptr。

三、实战

3.1、实现Trie（前缀树）

题目链接：LeetCode：208.实现Trie（前缀树）

class Trie {
public:
    Trie() {
        isEnd=false;
        for(auto &i:next) i=nullptr;
    }
    
    void insert(string word) {
        Trie * node=this;//this指针表示被插入的字典树的根结点。
        for(char c:word){
            if(node->next[c-'a']==nullptr)
                node->next[c-'a']=new Trie();
            node=node->next[c-'a'];
        }
        node->isEnd=true;
        return;
    }
    
    bool search(string word) {
        Trie * node=this;
        for(char c:word){
            if(node->next[c-'a']==nullptr)  return false;
            node=node->next[c-'a'];
        }
        return node->isEnd;
    }
    
    bool startsWith(string prefix) {
        Trie * node=this;
        for(char c:prefix){
            if(node->next[c-'a']==nullptr)  return false;
            node=node->next[c-'a'];
        }
        return true;
    }
private:
    bool isEnd;
    Trie * next[26];
};
/*使用样例：始终对root进行插入、查找、前缀匹配查找操作
Trie * root=new Trie;
root->insert(val);
root->insert(val2);
root->insert(val3);
if(root->search(val4)) cout<<true<<endl;
if(root->startsWith(val4)) cout<<true<<endl;
*/

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/488549.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

flask_restful渲染模版

flask_restful渲染模版

渲染模版就是在 Flask_RESTful 的类视图中要返回 html 片段代码&#xff0c;或 者是整个html 文件代码。 如何需要浏览器渲染模板内容应该使用 api.representation 这个装饰器来定 义一个函数&#xff0c; 在这个函数中&#xff0c;应该对 html 代码进行一个封装&#xff…
阅读更多...
JAVA中jwt令牌生成和下发

JAVA中jwt令牌生成和下发

阅读更多...
vue2 key的作用和原理

vue2 key的作用和原理

我们在写v-for的时候都会绑定一个key值，这个key在vue中有什么作用呢，不写可以吗？ 目标 1 key有什么作用 2 如何不写key会产生什么影响 3 key使用原理 key的作用 可以看vue2官网上给的解释，“给vue一个提示，以便跟踪每个节点的身份”，这样听着很模棱两可，到底是什么作用…
阅读更多...
解决“Pycharm中Matplotlib图像不弹出独立的显示窗口”问题

解决“Pycharm中Matplotlib图像不弹出独立的显示窗口”问题

matplotlib的绘图的结果默认显示在SciView窗口中, 而不是弹出独立的窗口, 这样看起来就不是很舒服&#xff0c;不习惯。 通过修改设置&#xff0c;改成独立弹出的窗口。 File—>Settings—>Tools—>Python Scientific—>Show plots in toolwindow 将√去掉即可
阅读更多...
在for循环加判断条件当条件都满足时，同时显现的解决方法

在for循环加判断条件当条件都满足时，同时显现的解决方法

一、代码示例 function fu(s) {str ;ste ;console.log(s);let Things s;for (let i 0; i < Things.length; i) {if (Things[i].pid kk) {console.log(Things[i].pid);ste <div class"commodity_nei"><div class"zxc_pic"><div cl…
阅读更多...
数据库专题（oracle基础和进阶）

数据库专题（oracle基础和进阶）

前言 本专题主要记录自己最近学的数据库&#xff0c;有兴趣一起补习的可以一起看看&#xff0c;有补充和不足之处请多多指出。希望专题可以给自己还有读者带去一点点提高。 数据库基本概念 本模块有参考&#xff1a;数据库基本概念-CSDN博客 数据库管理系统是一个由互相关联的…
阅读更多...
Java两地经纬度通过高德api获取两地距离（公里）

Java两地经纬度通过高德api获取两地距离（公里）

代码如下&#xff1a; String startLongitude entity.getLONGITUDE(); // 起点&#xff08;当前位置&#xff09;经度String startLatitude entity.getLATITUDE(); // 起点纬度String endLongitude entity.getLO(); // 终点经度String endLatitude entity.getLA(); …
阅读更多...
Midjourney AI绘图工具介绍及使用

Midjourney AI绘图工具介绍及使用

介绍 Midjourney是一款目前被誉为最强的AI绘图工具。只要输入想到的文字&#xff0c;就能通过人工智能产出相对应的图片。 官网只是宣传和登录入口&#xff0c;提供个人主页、订阅管理等功能&#xff0c;Midjourney实际的绘画功能&#xff0c;是在另外一个叫discord的产品中实…
阅读更多...
计算机基础（中断、IO）

计算机基础（中断、IO）

操作系统 设备交互 CPU 与 IO 设备交互过程 CPU 通过设备控制器&#xff08;驱动&#xff1f;&#xff09;与计算机外设进行交互。可以将控制器想象成编程语言中的接口&#xff0c;然后不同地计算机外设的控制器去实现这个接口&#xff0c;CPU 只需要调用接口而无需关注具体地…
阅读更多...
记录三菱：Works2-计数器

记录三菱：Works2-计数器

参数设置&#xff1a;D200-D511掉电保持&#xff0c;这个范围可以更改 加减计数器 第一种&#xff1a; 第二种&#xff1a; 第三种&#xff1a; 例如&#xff1a;完成下面的功能 可以在触摸屏上仿真测试一下
阅读更多...
unity学习（70）——编译游戏发生错误2

unity学习（70）——编译游戏发生错误2

1.全屏问题其实无所谓&#xff0c;windows用tab可以切出来的。 2.现在主要问题是服务器try了以后虽然不崩溃了&#xff0c;但不再显示2个实例对象了&#xff0c;unity和exe此时都只能看到一个实例对象 2.1把之前报错位置的try-catch先注释掉 2.2 unity中此时登录666账号&…
阅读更多...
2015年认证杯SPSSPRO杯数学建模D题(第二阶段)城市公共自行车全过程文档及程序

2015年认证杯SPSSPRO杯数学建模D题(第二阶段)城市公共自行车全过程文档及程序

2015年认证杯SPSSPRO杯数学建模 D题 城市公共自行车 原题再现&#xff1a; 城市交通问题直接影响市民的生活和工作。在地形平坦的城市&#xff0c;公共自行车出行系统是一种很好的辅助手段。一般来说&#xff0c;公共自行车出行系统由数据中心、驻车站点、驻车桩、自行车&…
阅读更多...
【Linux】信号量与信号

【Linux】信号量与信号

目录 先导知识 信号量 信号 信号概念及产生信号的一般方式 进程递达、阻塞和捕捉 信号集操作函数 信号的捕捉 可重入函数 先导知识 信号量与信号没有任何关系&#xff0c;它们是两个完全不同的概念&#xff01; 操作系统的本质&#xff0c;就是一个死循环&#xff1b;…
阅读更多...
Django日志（四）

Django日志（四）

一、Filters介绍 过滤器用于从logger传递给handler的哪些日志要做额外控制 默认情况下，满足日志级别的任何消息都将处理。只要级别匹配，任何日志消息都会被处理。不过，也可以通过添加 filter 来给日志处理的过程增加额外条件。例如，可以添加一个 filter 只允许某个特定来源…
阅读更多...
【C++】模板与泛型编程

【C++】模板与泛型编程

文章目录 1. 泛型编程2. 函数模板2.1 函数模板概念2.2 函数模板格式2.3 函数模板的原理2.4 函数模板的实例化2.5 模板参数的匹配原则 3. 类模板3.1 类模板的定义格式3.2 类模板的实例化 4. 非类型模板参数5. 模板的特化5.1 概念5.2 函数模板特化5.3 全特化5.4 偏特化5.5 类模板…
阅读更多...
Android 系统应用 pk8签名文件转jks或keystore教程

Android 系统应用 pk8签名文件转jks或keystore教程

一、介绍 签名文件对于我们在做应用开发中&#xff0c;经常遇到&#xff0c;且签名文件不仅仅是保护应用安全&#xff0c;还会涉及到应用与底层之间的数据共享和API文件等问题。 在Android中&#xff0c;签名文件同样也存在这个问题。但是android中又区分系统应用和普通应用。系…
阅读更多...
汉明校验·简明教程

汉明校验·简明教程

汉明校验 一、简介 汉明码是由 Richard Hanming 于 1950 年提出的&#xff0c;它具有一位纠错能力。 新增的汉明码校验位数应满足如下关系&#xff1a; 2 k ⩾ n k 1 2^{k}\geqslant nk1 2k⩾nk1&#xff0c;其中k为校验位位数&#xff0c;n位数据位数。 二、汉明码生成 确…
阅读更多...
centos7 的redis的安装

centos7 的redis的安装

文章目录 查看本机redis⾸先安装 scl 源, 再安装 redis 基本配置启动redis停止redis 查看本机redis ⾸先安装 scl 源, 再安装 redis 安装scl源 yum install centos-release-scl-rh安装redis5 yum install rh-redis5-redis安装成功 基本配置 修改etc/redis/redis.conf 文件…
阅读更多...
代码随想录算法训练营第二十一天（二叉树VII）| 530. 二叉搜索树的最小绝对差、501. 二叉搜索树中的众数、236. 二叉树的最近公共祖先(JAVA)

代码随想录算法训练营第二十一天（二叉树VII）| 530. 二叉搜索树的最小绝对差、501. 二叉搜索树中的众数、236. 二叉树的最近公共祖先(JAVA)

文章目录 530. 二叉搜索树的最小绝对差解题思路源码 501. 二叉搜索树中的众数解题思路源码 236. 二叉树的最近公共祖先解题思路源码 530. 二叉搜索树的最小绝对差 给你一个二叉搜索树的根节点 root &#xff0c;返回 树中任意两不同节点值之间的最小差值 。 差值是一个正数&a…
阅读更多...
如何在 Ubuntu 安装桌面环境

如何在 Ubuntu 安装桌面环境

在 Ubuntu 上安装不同的桌面环境 如果你正在使用官方的 Ubuntu 发行版&#xff0c;它运行在 GNOME 上&#xff0c;那么你可以很容易地从默认的包管理器安装其他流行的桌面环境&#xff08;DE&#xff09;。让我们开始吧… 在 Ubuntu 上安装 KDE Plasma 如果你正在使用 GNOME…
阅读更多...
最新文章

Copyright @ 2022~2023