Trie
什么是Trie?
Trie(读try)是一种prefix tree, 即可以通过前缀来查找。和二叉树不同，Trie并不存储值本身，而是根据字符位置来索引。
Trie结构如下图所示：
Trie实现
- Trie类声明
首先， 我们需要定义一个TrieNode来表示Trie中节点:
class TrieNode {
public:
// constructor
explicit TrieNode() {
node.resize(26);
isLeaf = false;
}
const TrieNode*& operator [](int idx) {
return node[idx];
}
void setLeaf() {
isLeaf = true;
}
bool isLeaf() const {
return isLeaf;
}
private:
// here only consider lowercase alphabetic
vector<TrieNode*> node;
// indicate whether the node is leaf
bool isLeaf;
};
然后我们以上面TrieNode类为节点声明Trie类:
class Trie {
public:
// constructor
explicit Trie();
// insert an element
void insert(const string &s);
// check if an element exists
bool exists(const string &s);
private:
TrieNode *root;
};
- Trie类构造函数: 创建root节点， 并设置其为leaf节点
Trie::Trie() {
root = new TrieNode();
root->setLeaf();
}
- Trie类
insert(const string &s)成员函数
void Trie::insert(const string &s) {
TrieNode* node = root;
for(auto ch : s) {
if( node[ch - 'a'] == nullptr )
node[ch-'a'] = new TrieNode();
node = node[ch-'a'];
}
node->setLeaf();
}
- Trie类
exists(const string &s)成员函数
bool Trie::exists(const string &s) {
TrieNode* node = root;
for(auto ch : s) {
if( node[ch - 'a'] == nullptr )
return false;
node = node[ch-'a'];
}
return node->isLeaf();
}
Suffix Tree
什么是Suffix Tree?
Suffix Tree实现
- Suffix Tree类声明
//TODO
- Suffix Tree类构造函数
- Suffix Tree类
insert()成员函数