基本概念
键树,又称数字查找树(Digital Search Tree)。
它是一棵度大于等于2的树,树中的每个结点中不是包含一个或几个关键字,而是只含有组成关键字的符号。
例如,若关键字是数值,则结点中只包含一个数位;若关键字是单词,则结点中只包含一个字母字符。
这种树会给某种类型关键字的表的查找带来方便。
如下图所示为一棵键树:
从根到叶子结点路径中结点的字符组成的字符串表示一个关键字,叶子结点中的特殊符号$
表示字符串的结束。
在叶子结点中还含有指向该关键字记录的指针。
为了查找和插入方便,我们约定键树是有序树,即同一层中兄弟结点之间依所含符号自左至右有序,并约定$
小于任何字符。
键树中每个结点的最大度d和关键字的“基”有关,若关键字是单词,则d=27,若关键字是数值,则d=11。
键树的深度h则取决于关键字中字符或数位的个数。
通常,键树可有两种存储结构,分别称为双链树和Trie树。
适用场景
适用于检索多字符串组时的场景,KMP适合检索单字符串
-
串的快速检索
给出N个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出现的顺序写出所有不在熟词表中的生词。
在这道题中,我们可以用数组枚举,用哈希,用字典树,先把熟词建一棵树,然后读入文章进行比较,这种方法效率是比较高的。 -
“串”排序
给定N个互不相同的仅由一个单词构成的英文名,让你将他们按字典序从小到大输出
用字典树进行排序,采用数组的方式创建字典树,这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。 -
最长公共前缀
对所有串建立字典树,对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数,于是,问题就转化为当时公共祖先问题。
208. 实现 Trie (前缀树)(Java实现)
Trie(发音类似 “try”)或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。
请你实现 Trie 类:
Trie()
初始化前缀树对象。void insert(String word)
向前缀树中插入字符串 word 。boolean search(String word)
如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false 。boolean startsWith(String prefix)
如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false 。
示例:
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
字典树
若以树的多重链表表示键树,则树的每个结点中应含有d个指针域,此时的键树又称Trie树。
(Trie是从检索retrieve中取中间四个字符的,读音同try)。
\(\text{Trie}\),又称前缀树或字典树,是一棵有根树,其每个节点包含以下字段:
- 指向子节点的指针数组 \(\textit{children}\)。对于本题而言,数组长度为 26,即小写英文字母的数量。此时 \(\textit{children}[0]\) 对应小写字母 a,\(\textit{children}[1]\) 对应小写字母 b,…,\(\textit{children}[25]\) 对应小写字母 z。
- 布尔字段 \(\textit{isEnd}\),表示该节点是否为字符串(单词)的结尾。
class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
children = new Trie[26]; // 26个字母,26叉树
isEnd = false; // 是不是某个单词的结尾
}
}
假如我们的词有 apple, apply, bed, bear, beat, beach 那我们应该构建如下的前缀树:
插入字符串
描述:向 Trie 中插入一个单词 word
实现:这个操作和构建链表很像。首先从根结点的子结点开始与 word 第一个字符进行匹配,一直匹配到前缀链上没有对应的字符,这时开始不断开辟新的结点,直到插入完 word 的最后一个字符,同时还要将最后一个结点isEnd = true;,表示它是一个单词的末尾。
我们从字典树的根开始,插入字符串。对于当前字符对应的子节点,有两种情况:
- 子节点存在。沿着指针移动到子节点,继续处理下一个字符。
- 子节点不存在。创建一个新的子节点,记录在 \(\textit{children}\) 数组的对应位置上,然后沿着指针移动到子节点,继续搜索下一个字符。
重复以上步骤,直到处理字符串的最后一个字符,然后将当前节点标记为字符串的结尾。
public void insert(String word) {
Trie node = this;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
node.children[index] = new Trie();
}
node = node.children[index];
}
node.isEnd = true;
}
查找
我们从字典树的根开始,查找前缀。对于当前字符对应的子节点,有两种情况:
- 子节点存在。沿着指针移动到子节点,继续搜索下一个字符。
- 子节点不存在。说明字典树中不包含该前缀,返回空指针。
重复以上步骤,直到返回空指针或搜索完前缀的最后一个字符。
private Trie searchPrefix(String prefix) {
Trie node = this;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
return null;
}
node = node.children[index];
}
return node;
}
查找前缀
描述:判断 Trie 中是或有以 prefix 为前缀的单词
实现:和 search 操作类似,只是不需要判断最后一个字符结点的isEnd,因为既然能匹配到最后一个字符,那后面一定有单词是以它为前缀的。
查找前缀:若搜索到了前缀的末尾,就说明字典树中存在该前缀。
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
查找单词
描述:查找 Trie 中是否存在单词 word
实现:从根结点的子结点开始,一直向下匹配即可,如果出现结点值为空就返回 false,如果匹配到了最后一个字符,那我们只需判断 node->isEnd即可。
查找单词:此外,若前缀末尾对应节点的 \(\textit{isEnd}\) 为真,则说明字典树中存在该字符串。
public boolean search(String word) {
Trie node = searchPrefix(word);
return node != null && node.isEnd;
}
完整代码
class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
children = new Trie[26];
isEnd = false;
}
public void insert(String word) {
Trie node = this;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
node.children[index] = new Trie();
}
node = node.children[index];
}
node.isEnd = true;
}
public boolean search(String word) {
Trie node = searchPrefix(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
private Trie searchPrefix(String prefix) {
Trie node = this;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
return null;
}
node = node.children[index];
}
return node;
}
}
复杂度分析:
-
时间复杂度:初始化为 \(O(1)\),其余操作为 \(O(|S|)\),其中 \(|S|\) 是每次插入或查询的字符串的长度。
-
空间复杂度:\(O(|T|\cdot\Sigma)\),其中 \(|T|\) 为所有插入字符串的长度之和,\(\Sigma\) 为字符集的大小,本题 \(\Sigma=26\)。
键树(C语言)
双链树
以树的孩子兄弟链表来表示键树,则每个分支结点包括三个域:
-
symbol域:存储关键字的一个字符;
-
first域:存储指向第一棵子树根的指针;
-
next域:存储指向右兄弟的指针。
同时,叶子结点不含first域,它的infoptr域存储指向该关键字记录的指针。
此时的键树又称双链树。
在双链树中插入或删除一个关键字,相当于在树中某个结点上插入或删除一棵子树。
结点的结构中可以设置一个枚举变量表示结点的类型,叶子结点和分支结点。
叶子结点和分支结点都有symbol域和next域。不同的一个域可以用联合表示,叶子结点包含infoptr指向记录,而分支结点是first域指向其第一棵子树。
数据结构:(C语言)
typedef struct DLTNode {
char symbol;
struct DLTNode *next; // 指向兄弟节点的指针
NodeKind kind;
union {
Record *infoptr; // 叶子节点内的记录指针
Struct DLTNode *first; // 分支节点内的孩子链指针
}
}DLTNode, *DLTree; // 双链树的类型
双链树如下图:
双链树的查找可如下进行:
假设给定值为K.ch(0..num-1)
, 其中K.ch[0]
至 K.ch[num-2]
表示待查关键字中num-1个字符,K.ch[num-1]
为结束符$
。
从双链树的根指针出发,顺first指针找到第一棵子树的根结点,以K.ch[0]
和此结点的symbol域比较,若相等,则顺first域再比较下一字符,否则沿next域顺序查找。
若直至空仍比较不等,则查找不成功。
下面是算法表示的代码:
双链树查找
#define MAXKEYLEN 16
typedef struct
{
char ch[MAXKEYLEN]; //keyword
int num;
}KeysType;
typedef enum
{
LEAF,
BRANCH
}NodeKind;
typedef struct DLTNode
{
char symbol;
struct DLTNode *next;
NodeKind kind;
union
{
Record *infoptr;
struct DLTNode *first;
};
}DLTNode,*DLTree;
Record *SearchDLTree(DLTree T, KeysType K)
{
DLTNode p=T->first;
int i=0;
while(p && i<K.num)
{
while(p && p->symbol!= K.ch[i])
{
p=p->next;
}
if(p && i<K.num-1)
{
p=p->first;
}
++i;
}//search end
if(!p)
{
return NULL; //search fail
}
else
{
return p->infoptr; //find
}
}
Trie树
若以树的多重链表表示键树,则树的每个结点中应含有d个指针域,此时的键树又称Trie树。
(Trie是从检索retrieve中取中间四个字符的,读音同try)。
若从键树中某个结点到叶子结点的路径上每个结点都只有一个孩子,则可将该路径上所有结点压缩成一个“叶子结点”,且在该叶子结点中存储关键字及指向记录的指针等信息。
在Trie树中有两种结点:
-
分支结点:含有d个指针域和一个指示该结点中非空指针域的个数的整数域。在分支结点中不设数据域,每个分支结点所表示的字符均有其父结点中指向该结点的指针所在位置决定。
-
叶子结点:含有关键字域和指向记录的指针域。
数据结构:(C语言)
typedef struct TrieNode {
NodeKind kind;
union {
// 叶子节点(关键字和指向记录的指针)
struct {KeysType K; Record *infoptr;}lf; //Leaf Node
// 分支节点(27个指向下一层节点的指针)
struct {TrieNode *ptr[27]; int num;}bh; //Branch Node
};
}TrieNode, *TrieTree; // 键树类型
Trie树如下图:
在Trie树上进行查找的过程为:
从根结点出发,沿和给定值相应的指针逐层向下,直至叶子结点,若叶子结点中的关键字和给定值相等,则查找成功,若分支结点中和给定值相应的指针为空,或叶子结点中的关键字和给定值不相等,则查找不成功。
算法表示如下:
Trie树查找
typedef struct TrieNode
{
NodeKind kind;
union
{
struct {KeysType K; Record *infoptr;}lf; //Leaf Node
struct {TrieNode *ptr[27]; int num;}bh; //Branch Node
};
}TrieNode,*TrieTree;
Record *SearchTrie(TrieTree T, KeysType K)
{
TrieNode p;
for(p=T,i=0; p && p->kind == BRANCH && i<K.num; p=p->bh.ptr[ord(K.ch[i]),++i])
;
if(p && p->kind==LEAF && p->lf.K==K)
{
return p->lf.infoptr;
}
else
{
return NULL;
}
}
其中ord方法将字符转换成该字符在字母表中的序号,并假设$
的序号为零。
(这个for循环写得真DT。)
本文资料来源:严蔚敏《数据结构》,文中图片来源于百度文库的PPT,代码是算法表示的伪代码,还不能直接运行。
关于Trie树,这里有篇博文:【数据结构】键树(字典树、前缀树)
本文转载自:【数据结构】键树(字典树、前缀树)
Trie树(C++实现)
Trie树也称字典树,因为其效率很高,所以在在字符串查找、前缀匹配等中应用很广泛,其高效率是以空间为代价的。
Trie树的原理
利用串构建一个字典树,这个字典树保存了串的公共前缀信息,因此可以降低查询操作的复杂度。
下面以英文单词构建的字典树为例,这棵Trie树中每个结点包括26个孩子结点,因为总共有26个英文字母(假设单词都是小写字母组成)。
则可声明包含Trie树的结点信息的结构体:
#define MAX 26
typedef struct TrieNode //Trie结点声明
{
bool isStr; //标记该结点处是否构成单词
struct TrieNode *next[MAX]; //儿子分支
}Trie;
其中next是一个指针数组,存放着指向各个孩子结点的指针。
如给出字符串”abc”,”ab”,”bd”,”dda”,根据该字符串序列构建一棵Trie树。则构建的树如下:
Trie树的根结点不包含任何信息,第一个字符串为”abc”,第一个字母为’a’,因此根结点中数组next下标为'a'-97
的值不为NULL,其他同理,构建的Trie树如图所示,红色结点表示在该处可以构成一个单词。
很显然,如果要查找单词”abc”是否存在,查找长度则为\(O(len)\),len为要查找的字符串的长度。而若采用一般的逐个匹配查找,则查找长度为\(O(len*n)\),n为字符串的个数。显然基于Trie树的查找效率要高很多。
但是却是以空间为代价的,比如图中每个结点所占的空间都为\((26*4+1)Byte=105Byte\),那么这棵Trie树所占的空间则为\(105*8Byte=840Byte\),而普通的逐个查找所占空间只需\((3+2+2+3)Byte=10Byte\)。
Trie树的操作
在Trie树中主要有3个操作,插入、查找和删除。一般情况下Trie树中很少存在删除单独某个结点的情况,因此只考虑删除整棵树。
1.插入
假设存在字符串str,Trie树的根结点为root。i=0,p=root。
-
取
str[i]
,判断p->next[str[i]-97]
是否为空,若为空,则建立结点temp,并将p->next[str[i]-97]
指向temp,然后p指向temp;
若不为空,则p=p->next[str[i]-97]
; -
i++
,继续取str[i]
,循环1)中的操作,直到遇到结束符’\0’,此时将当前结点p中的isStr置为true。
2.查找
假设要查找的字符串为str,Trie树的根结点为root,i=0,p=root
-
取
str[i]
,判断判断p->next[str[i]-97]
是否为空,若为空,则返回false;若不为空,则p=p->next[str[i]-97]
,继续取字符。 -
重复1)中的操作直到遇到结束符’\0′,若当前结点p不为空并且isStr为true,则返回true,否则返回false。
-
删除
删除可以以递归的形式进行删除。
测试程序:
/*Trie树(字典树) 2011.10.10*/
#include <iostream>
#include<cstdlib>
#define MAX 26
using namespace std;
typedef struct TrieNode //Trie结点声明
{
bool isStr; //标记该结点处是否构成单词
struct TrieNode *next[MAX]; //儿子分支
}Trie;
void insert(Trie *root,const char *s) //将单词s插入到字典树中
{
if(root==NULL||*s=='\0')
return;
int i;
Trie *p=root;
while(*s!='\0')
{
if(p->next[*s-'a']==NULL) //如果不存在,则建立结点
{
Trie *temp=(Trie *)malloc(sizeof(Trie));
for(i=0;i<MAX;i++)
{
temp->next[i]=NULL;
}
temp->isStr=false;
p->next[*s-'a']=temp;
p=p->next[*s-'a'];
}
else
{
p=p->next[*s-'a'];
}
s++;
}
p->isStr=true; //单词结束的地方标记此处可以构成一个单词
}
int search(Trie *root,const char *s) //查找某个单词是否已经存在
{
Trie *p=root;
while(p!=NULL&&*s!='\0')
{
p=p->next[*s-'a'];
s++;
}
return (p!=NULL&&p->isStr==true); //在单词结束处的标记为true时,单词才存在
}
void del(Trie *root) //释放整个字典树占的堆区空间
{
int i;
for(i=0;i<MAX;i++)
{
if(root->next[i]!=NULL)
{
del(root->next[i]);
}
}
free(root);
}
int main(int argc, char *argv[])
{
int i;
int n,m; //n为建立Trie树输入的单词数,m为要查找的单词数
char s[100];
Trie *root= (Trie *)malloc(sizeof(Trie));
for(i=0;i<MAX;i++)
{
root->next[i]=NULL;
}
root->isStr=false;
scanf("%d",&n);
getchar();
for(i=0;i<n;i++) //先建立字典树
{
scanf("%s",s);
insert(root,s);
}
while(scanf("%d",&m)!=EOF)
{
for(i=0;i<m;i++) //查找
{
scanf("%s",s);
if(search(root,s)==1)
printf("YES\n");
else
printf("NO\n");
}
printf("\n");
}
del(root); //释放空间很重要
return 0;
}
训练题目:
http://acm.hdu.edu.cn/showproblem.php?pid=1671
http://acm.hdu.edu.cn/showproblem.php?pid=1075
http://acm.hdu.edu.cn/showproblem.php?pid=1251
一步一步实现前缀树(C++)
Trie [traɪ] 读音和 try 相同,它的另一些名字有:字典树,前缀树,单词查找树等。
介绍 Trie🌳
Trie 是一颗非典型的多叉树模型,多叉好理解,即每个结点的分支数量可能为多个。
为什么说非典型呢?因为它和一般的多叉树不一样,尤其在结点的数据结构设计上,比如一般的多叉树的结点是这样的:
C++
struct TreeNode {
VALUETYPE value; //结点值
TreeNode* children[NUM]; //指向孩子结点
};
而 Trie 的结点是这样的(假设只包含’a’~’z’中的字符):
C++
struct TrieNode {
bool isEnd; //该结点是否是一个串的结束
TrieNode* next[26]; //字母映射表
};
要想学会 Trie 就得先明白它的结点设计。我们可以看到TrieNode结点中并没有直接保存字符值的数据成员,那它是怎么保存字符的呢?
这时字母映射表next 的妙用就体现了,TrieNode* next[26]中保存了对当前结点而言下一个可能出现的所有字符的链接,因此我们可以通过一个父结点来预知它所有子结点的值:
C++
for (int i = 0; i < 26; i++) {
char ch = 'a' + i;
if (parentNode->next[i] == NULL) {
说明父结点的后一个字母不可为 ch
} else {
说明父结点的后一个字母可以是 ch
}
}
我们来看个例子吧。
想象以下,包含三个单词 “sea”,”sells”,”she” 的 Trie 会长啥样呢?
它的真实情况是这样的:
Trie 中一般都含有大量的空链接,因此在绘制一棵单词查找树时一般会忽略空链接,同时为了方便理解我们可以画成这样:
接下来我们一起来实现对 Trie 的一些常用操作方法。
定义类 Trie
C++
class Trie {
private:
bool isEnd;
Trie* next[26];
public:
//方法将在下文实现...
};
插入
描述:向 Trie 中插入一个单词 word
实现:这个操作和构建链表很像。首先从根结点的子结点开始与 word 第一个字符进行匹配,一直匹配到前缀链上没有对应的字符,这时开始不断开辟新的结点,直到插入完 word 的最后一个字符,同时还要将最后一个结点isEnd = true;,表示它是一个单词的末尾。
C++
void insert(string word) {
Trie* node = this;
for (char c : word) {
if (node->next[c-'a'] == NULL) {
node->next[c-'a'] = new Trie();
}
node = node->next[c-'a'];
}
node->isEnd = true;
}
查找
描述:查找 Trie 中是否存在单词 word
实现:从根结点的子结点开始,一直向下匹配即可,如果出现结点值为空就返回 false,如果匹配到了最后一个字符,那我们只需判断 node->isEnd即可。
C++
bool search(string word) {
Trie* node = this;
for (char c : word) {
node = node->next[c - 'a'];
if (node == NULL) {
return false;
}
}
return node->isEnd;
}
前缀匹配
描述:判断 Trie 中是或有以 prefix 为前缀的单词
实现:和 search 操作类似,只是不需要判断最后一个字符结点的isEnd,因为既然能匹配到最后一个字符,那后面一定有单词是以它为前缀的。
C++
bool startsWith(string prefix) {
Trie* node = this;
for (char c : prefix) {
node = node->next[c-'a'];
if (node == NULL) {
return false;
}
}
return true;
}
到这我们就已经实现了对 Trie 的一些基本操作,这样我们对 Trie 就有了进一步的理解。完整代码我贴在了文末。
总结
通过以上介绍和代码实现我们可以总结出 Trie 的几点性质:
-
Trie 的形状和单词的插入或删除顺序无关,也就是说对于任意给定的一组单词,Trie 的形状都是唯一的。
-
查找或插入一个长度为 L 的单词,访问 next 数组的次数最多为 L+1,和 Trie 中包含多少个单词无关。
-
Trie 的每个结点中都保留着一个字母表,这是很耗费空间的。如果 Trie 的高度为 n,字母表的大小为 m,最坏的情况是 Trie 中还不存在前缀相同的单词,那空间复杂度就为 \(O(m^n)\)。
最后,关于 Trie 的应用场景,希望你能记住 8 个字:一次建树,多次查询。(慢慢领悟叭~~)
全部代码
class Trie {
private:
bool isEnd;
Trie* next[26];
public:
Trie() {
isEnd = false;
memset(next, 0, sizeof(next));
}
void insert(string word) {
Trie* node = this;
for (char c : word) {
if (node->next[c-'a'] == NULL) {
node->next[c-'a'] = new Trie();
}
node = node->next[c-'a'];
}
node->isEnd = true;
}
bool search(string word) {
Trie* node = this;
for (char c : word) {
node = node->next[c - 'a'];
if (node == NULL) {
return false;
}
}
return node->isEnd;
}
bool startsWith(string prefix) {
Trie* node = this;
for (char c : prefix) {
node = node->next[c-'a'];
if (node == NULL) {
return false;
}
}
return true;
}
};
实例
面试题 17.13. 恢复空格
哦,不!你不小心把一个长篇文章中的空格、标点都删掉了,并且大写也弄成了小写。像句子”I reset the computer. It still didn’t boot!”已经变成了”iresetthecomputeritstilldidntboot”。在处理标点符号和大小写之前,你得先把它断成词语。当然了,你有一本厚厚的词典dictionary,不过,有些词没在词典里。假设文章用sentence表示,设计一个算法,把文章断开,要求未识别的字符最少,返回未识别的字符数。
注意:本题相对原题稍作改动,只需返回未识别的字符数
示例:
输入:
dictionary = ["looked","just","like","her","brother"]
sentence = "jesslookedjustliketimherbrother"
输出: 7
解释: 断句后为"jess looked just like tim her brother",共7个未识别字符。
答案
未完待续
今天的文章前缀树和字典树_数据结构树的定义[通俗易懂]分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:http://bianchenghao.cn/59334.html