来源：小小算法
作者：小小算法
“
Trie [traɪ] 读音和 try 相同，它的另一些名字有：字典树，前缀树，单词查找树等。
开始之前我们先看看来 Trie 树的几个常见的应用场景：
-
Google、Baidu 等搜索引擎的搜索提示
-
代码自动补全
-
IP路由查询使用的最长前缀匹配算法
介绍 Trie
Trie 是一颗非典型的多叉树模型，多叉好理解，即每个结点的分支数量可能为多个。
为什么说非典型呢？因为它和一般的多叉树不一样，尤其在结点的数据结构设计上，比如一般的多叉树的结点是这样的：
struct TreeNode {
VALUETYPE value; //结点值
TreeNode* children[NUM]; //指向孩子结点
};
而 Trie 的结点是这样的(假设只包含’a’~’z’中的字符)：
struct TrieNode {
bool isEnd; //该结点是否是一个串的结束
TrieNode* next[26]; //字母映射表
};
要想学会 Trie 就得先明白它的结点设计。我们可以看到TrieNode结点中并没有直接保存字符值的数据成员，那它是怎么保存字符的呢？
这时字母映射表next 的妙用就体现了，TrieNode* next[26]中保存了对当前结点而言下一个可能出现的所有字符的链接，因此我们可以通过一个父结点来预知它所有子结点的值：
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
class Trie {
private:
bool isEnd;
Trie* next[26];
public:
//方法将在下文实现...
};
插入
描述：向 Trie 中插入一个单词 word
实现：这个操作和构建链表很像。首先从根结点的子结点开始与 word 第一个字符进行匹配，一直匹配到前缀链上没有对应的字符，这时开始不断开辟新的结点，直到插入完 word 的最后一个字符，同时还要将最后一个结点isEnd = true;，表示它是一个单词的末尾。
void insert(const 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即可。
bool search(const 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，因为既然能匹配到最后一个字符，那后面一定有单词是以它为前缀的。
bool prefixMatched(const string& prefix) {
Trie* node = this;
for (char c : prefix) {
node = node->next[c - 'a'];
if (node == NULL) {
return false;
}
}
return true;
}
删除
描述：从 Trie 中删除一个单词 word
删除操作稍微有点抽象，不如先看个栗子吧！
由单词”ab”, “abc”, “aec” 构成的 Trie，单独删除 “abc” 或者 “ab” 或者 “aec” 之后会是啥样呢？
实现：我们首先要一直递归匹配到 word 的最后一个字符，并将最后一个字符对应结点的isEnd置为false，然后逐步删除并返回上一个结点。注意只有在当前结点的子结点都为空或者当前结点不是其它单词的结束结点时，才能将它删除。
void deleteWord(const string& word) {
if (!search(word)) {
return;
}
Trie* node = this;
__deleteWord(node, word, 0);
}
void __deleteWord(Trie*& node, const string& word, int d) {
if (d == word.length()) {
node->isEnd = false;
} else {
__deleteWord(node->next[word[d]-'a'], word, d+1);
}
if (node->isEnd) {
return;
}
for (Trie* item : node->next) {
if (item != NULL) {
return;
}
}
delete node;
node = NULL;
}
到这我们就已经实现了对 Trie 的一些基本操作，这样我们对 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];
//返回与前缀prefix匹配的最后一个结点的地址
Trie* __prefix(const string& prefix) {
Trie* node = this;
for (char c : prefix) {
node = node->next[c - 'a'];
if (node == NULL) {
return NULL;
}
}
return node;
}
//获取以root为起始结点的所有单词
void __getWords(Trie* root, string& word, vector<string>& allWords) {
if (root == NULL) {
return;
}
if (root->isEnd) {
allWords.push_back(word);
}
for (int i = 0; i < 26; i++) {
word.push_back(static_cast<char>('a'+i));
__getWords(root->next[i], word, allWords);
word.pop_back();
}
}
//删除一个单词
void __deleteWord(Trie*& node, const string& word, int d) {
if (d == word.length()) {
node->isEnd = false;
} else {
__deleteWord(node->next[word[d]-'a'], word, d+1);
}
if (node->isEnd) {
return;
}
for (Trie* item : node->next) {
if (item != NULL) {
return;
}
}
delete node;
node = NULL;
}
public:
//构造函数
Trie() {
isEnd = false;
memset(next, 0, sizeof(next));
}
//插入函数
void insert(const 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(const string& word) {
Trie* node = __prefix(word);
if (node == NULL) {
return false;
}
return node->isEnd;
}
//前缀匹配函数
bool prefixMatched(const string& prefix) {
Trie* node = this;
for (char c : prefix) {
node = node->next[c - 'a'];
if (node == NULL) {
return false;
}
}
return true;
}
//获取以prefix为前缀的所有单词
vector<string> getAllWordsOfPrefix(const string& prefix) {
vector<string> words;
string word = prefix;
Trie* node = __prefix(prefix);
__getWords(node, word, words);
return words;
}
//获取Trie中所有单词
vector<string> getAllWords() {
string word = "";
return getAllWordsOfPrefix(word);
}
//删除一个单词
void deleteWord(const string& word) {
if (!search(word)) {
return;
}
Trie* node = this;
__deleteWord(node, word, 0);
}
};
推荐 leetcode 的一个 Trie 树练手题：208. 实现 Trie (前缀树)[1]。
喜欢记得点亮好看哟 : )。
链接
208. 实现 Trie (前缀树): https://leetcode-cn.com/problems/implement-trie-prefix-tree/
