网站开发目的和意义,3.建设营销型网站流程.,中山做营销型网站公司,微网站建设步骤介绍Trie树
Trie#xff08;发音类似 try#xff09;或者说 前缀树 是一种树形数据结构#xff0c;用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景#xff0c;例如自动补全和拼写检查。
前缀树也有一些其它的名称#xff1a;字典…介绍Trie树
Trie发音类似 try或者说 前缀树 是一种树形数据结构用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景例如自动补全和拼写检查。
前缀树也有一些其它的名称字典树前缀树单词查找树等。
Trie树是一颗非典型的多叉树模型。
一般的多叉树它们的结点通常主要包含了
1.该结点的值
2.它的下一个孩子的指针 假设我们要查找的字符的范围是 [a,z]也就是26的大小
那么每一个前缀树的结点主要就包含以下两个值
bool isEnd;
Trie* next[26];
第一个是一个bool值它用来表示这个字符串是否到了结尾。
第二个值就是一个前缀树结点的指针的数组它的大小刚好是26那么这个结点的下一个孩子的指针数组下标就可以表示一个字符而却并没有直接保存字符这就是Trie树的巧妙之处。
比如用如下的示意图可以表示字符串 aa aba 其它空指针就没有画出来了。并且它也可以表示字符串a ab只要在对应的结点将isEnd改为true表示它是一个字符串的末尾即可。 Trie树的简单实现
在力扣上有一道题 这道题的大致意思就是让我们实现一个简单的前缀树这个前缀树可以进行插入查找以及判断一个字符串是否是某个字符串的前缀。
代码
class Trie {bool isEnd;Trie* next[26];
public:Trie() {isEnd false;memset(next,0,sizeof(next));}void insert(string word) {Trie* cur this; // 用来迭代for(auto ch : word){if(cur-next[ch - a] nullptr) cur-next[ch - a] new Trie();cur cur-next[ch - a];}cur-isEnd true;}bool search(string word) {Trie* cur this;for(auto ch : word){if(cur-next[ch - a] nullptr) return false;cur cur-next[ch - a];}return cur-isEnd;}bool startsWith(string prefix) {Trie* cur this;for(auto ch : prefix){if(cur-next[ch - a] nullptr) return false;cur cur-next[ch - a];}return true;}
}; 这里的实现其实将结点和函数的实现放在一起了也可以将结点在类外面进行封装。 Trie树小总结
Trie 的形状和单词的插入或删除顺序无关也就是说对于任意给定的一组单词Trie 的形状都是唯一的。
查找或插入一个长度为 L 的单词访问 next 数组的次数最多为 L1和 Trie 中包含多少个单词无关。
Trie 的每个结点中都保留着一个字母表这是很耗费空间的。如果 Trie 的高度为 n字母表的大小为 m最坏的情况是 Trie 中还不存在前缀相同的单词那空间复杂度就为 O(m * n)。 关于Trie树的应用场景一次建树多次查询。
