面试刷题-前缀树(Trie)
Trie树，又称前缀树或字典树，是一种树形结构。典型应用是用于统计和排序大量的字符串，经常被搜索引擎系统用于文本词频统计或者自动联想搜索词等。
Trie有三个基本特征：
1）除根节点外，每一个节点都只包含一个字符；
2）从根节点到某一节点的路径上经过的字符连接起来，为该节点对应的字符串；
3）每个节点的所有子节点包含的字符都不相同。)
Trie树实现
Trie 树的结点结构
假设Trie树中存储的全部是英文字符串，英文最多有26个字母，所以TrieNode的next节点最多有26个。
class TrieNode {
public:
bool isEnd; //该结点是否是一个串的结束
std::shared_ptr<TrieNode> next[26]; //字母映射表
public:
TrieNode():isEnd(false) {
std::cout << "TrieNode Constructor" << std::endl;
for (int i = 0; i < 26; i++) {
next[i] = nullptr;
}
}
~TrieNode() {
std::cout << "TrieNode Destructor" << std::endl;
}
};
TrieNode中并没有直接保存字符值，而是通过数字与字母的映射来实现字符的存储。
Trie 树的插入(Insert)
向 Trie 中插入一个单词word。首先从根结点的子结点开始与 word 第一个字符进行匹配，一直匹配到前缀链上没有对应的字符，然后不断插入新的结点，直到插入完 word 的最后一个字符；同时将最后一个结点的isEnd设置为true，表示它是一个单词的末尾。
void insert(const std::string& word) {
auto node = _root;
for (const auto& c : word) {
if (node->next[c -'a'] == nullptr) {
node->next[c -'a'] = std::make_shared<TrieNode>();
}
node = node->next[c - 'a'];
}
node->isEnd = true;
}
Trie 树的搜索(Search)
查找 Trie 中是否存在单词word。从根结点的子结点开始，一直向下匹配，如果出现结点值为空就返回 false；如果匹配到了最后一个字符，则只需判断 node->isEnd即可。
bool search(const std::string& word) {
auto node = _root;
for (const char& c : word) {
node = node->next[c - 'a'];
if (node == nullptr) {
return false;
}
}
return node->isEnd;
}
Trie树的前缀匹配(prefix)
判断Trie中是否有以prefix 为前缀的单词。和search操作类似，只是不需要判断最后一个字符结点的isEnd，因为既然能匹配到最后一个字符，那一定有单词是以它为前缀的。
bool startsWith(const std::string& prefix) {
auto node = _root;
for (const char& c : prefix) {
node = node->next[c-'a'];
if (node == nullptr) {
return false;
}
}
return true;
}
完整Trie树代码
完整Trie树的C++代码如下：
#include <string>
#include <memory>
#include <iostream>
class TrieNode {
public:
bool isEnd; //该结点是否是一个串的结束
std::shared_ptr<TrieNode> next[26]; //字母映射表
public:
TrieNode():isEnd(false) {
std::cout << "TrieNode Constructor" << std::endl;
for (int i = 0; i < 26; i++) {
next[i] = nullptr;
}
}
~TrieNode() {
std::cout << "TrieNode Destructor" << std::endl;
}
};
class Trie {
public:
Trie() {
_root = std::make_shared<TrieNode>();
}
~Trie() { }
private:
std::shared_ptr<TrieNode> _root = nullptr;
public:
void insert(const std::string& word) {
auto node = _root;
for (const auto& c : word) {
if (node->next[c -'a'] == nullptr) {
node->next[c -'a'] = std::make_shared<TrieNode>();
}
node = node->next[c - 'a'];
}
node->isEnd = true;
}
bool search(const std::string& word) {
auto node = _root;
for (const char& c : word) {
node = node->next[c - 'a'];
if (node == nullptr) {
return false;
}
}
return node->isEnd;
}
bool startsWith(const std::string& prefix) {
auto node = _root;
for (const char& c : prefix) {
node = node->next[c-'a'];
if (node == nullptr) {
return false;
}
}
return true;
}
};
int main() {
auto obj = std::make_shared<Trie>();
obj->insert("apple");
bool ret = obj->search("apple");
std::cout << "search apple result:" << ret << std::endl;
ret = obj->search("app");
std::cout << "search app result:" << ret << std::endl;
ret = obj->startsWith("app");
std::cout << "startsWith app result:" << ret << std::endl;
obj->insert("apple");
ret = obj->search("app");
std::cout << "search app result:" << ret << std::endl;
return 0;
}
程序的输入如下：
TrieNode Constructor TrieNode Constructor TrieNode Constructor TrieNode Constructor TrieNode Constructor TrieNode Constructor search apple result:1 search app result:0 startsWith app result:1 search app result:0 TrieNode Destructor TrieNode Destructor TrieNode Destructor TrieNode Destructor TrieNode Destructor TrieNode Destructor
参考材料
https://zh.wikipedia.org/wiki/Trie
除非注明，否则均为[半杯茶的小酒杯]原创文章，转载必须以链接形式标明本文链接