通州网站网站建设推广放单平台

介绍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 数组的次数最多为 L+1，和 Trie 中包含多少个单词无关。

Trie 的每个结点中都保留着一个字母表，这是很耗费空间的。如果 Trie 的高度为 n，字母表的大小为 m，最坏的情况是 Trie 中还不存在前缀相同的单词，那空间复杂度就为 O(m * n)。

 关于Trie树的应用场景：一次建树，多次查询。