“字典树又称前缀树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。”------百度百科
前缀树大致长成这样：?
前缀树的特点：
? ? ? ?1.根节点不包含任何字符内容，除根节点之外的其他节点只能包含一个字符；
??2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
??3.每个节点的所有子节点包含的字符都不相同。
??4.除根节点外，每个节点都包含一个是否是单词或字符串结尾的标识。
根据前缀树的性质我们可以定义出他的大体结构：
我们首先来看使用数组的方式来定义：
struct TrieNode { TrieNode() :pass(0) , end(0) , _next(26)//26个节点对应26个不同字母 {} int pass;l int end;//记录字符串的结尾 vector<TrieNode*>_next; ~TrieNode() { for (auto it : _next) {//遍历释放节点 delete it; } } };
?前缀树的插入：
①insert。意思就是像前缀树中插入字符串。我们先来想一想插入的过程，由于前缀树的每个结点代表一个字母，那么其插入的过程肯定是一个一个字母进行插入的。那就对整个字符串进行遍历，如果当前字母所在的子结点为空，说明当前结点的下面还没有串入该字母，那就直接将该字母所在的子结点处开辟一个新的结点；如果当前字符所对应的子结点不为空，那就迭代到该子结点，继续遍历下一个字母……当字符串遍历结束后，那最后一个字母所在的结点自然而然就是末尾结点了，那就将其end++即可：
void Insert(string word) { if (!word.size()) {//空串直接返回 return; } TrieNode* Node = _root; Node->pass++; int index = 0;//记录对应映射位置 for (int i = 0; i < word.size(); i++) { index = word[i] - 'a'; if (!Node->_next[index]) {//如果没有子节点开辟一个 Node->_next[index] = new TrieNode; } Node = Node->_next[index];//迭代往后走 Node->pass++; } Node->end++; }
前缀树的查找：Search
?意思就是查找当前树中是否存在某一字符串。其实根据上面插入的过程，也不难想到查找的方式了，依然是根据字符串每个字符来迭代至相应结点，如果该字符串中某一字符所对应的结点为空，那就说明这个字符串不存在了。如果均不为空，那是不是说明这个字符串就在树中呢？不一定，比如说在前面的树的结构图中查找“og”，实际上这个字符串是没有的，但是它的每个结点又都存在，因此，我们还需要引入另一个判断条件，即是这个字符串的末尾字符对应的结点是否也是末尾结点，如果也是末尾结点，那么就说明字符串存在了，否则就不存在。该段代码如下：
//word这个单词之前加入过几次 int Search(string word) { if (!word.size()) { return 0; } TrieNode* Node = _root; int index = 0; for (int i = 0; i < word.size(); i++) {//遍历字符串 index = word[i] - 'a'; if (!Node->_next[index]) { return 0; } Node = Node->_next[index];//迭代 } return Node->end; }
?前缀树的前缀查找：PrefixNumber
PrefixNumber。简单的讲，就是判断树中是否有该前缀，比如说在前面的树的结构图中查找“og”，很明显“og”是一个前缀，因此就返回true了。这样说的话，PrefixNumber的实现还比search更简单，不用判断末尾字符对应结点是否为末尾结点了。对应代码如下：
int PrefixNumber(string pre) { if (!pre.size()) { return 0; } int index = 0; TrieNode* Node = _root; for (int i = 0; i < pre.size(); i++) {//遍历 index = pre[i] - 'a'; if (Node->_next[index] == nullptr) { return 0; } Node = Node->_next[index]; } return Node->pass; }
前缀树的删除：
首先我们找到第一个要删除字符串中pass值为1的位置并记录他的父亲节点和对应的下标并将所有pass值为1的节点放入set中遍历结束后在将其一个一个释放并将其父节点的指向置空。对应代码：?
?
void Delete(string word) { if (!word.size()) { return; } if (Search(word) != 0) { set<TrieNode*>DeleteSet; TrieNode* prev = nullptr; int delteIndex = -1; TrieNode* Node = _root; Node->pass--; int index = 0; for (int i = 0; i < word.size(); i++) { index = word[i] - 'a'; if (--Node->_next[index]->pass == 0) { prev = (prev == nullptr ? Node : prev);//记录第一个pass为1的节点 delteIndex = (delteIndex == -1 ? index : delteIndex);//记录其下标 DeleteSet.insert(Node->_next[index]);//放入set中 } Node = Node->_next[index]; } Node->end--; if (prev) prev->_next[delteIndex] = nullptr;//置空 for (auto& it : DeleteSet) {//遍历节点释放 delete it; } } }
代码汇总：
struct TrieNode { TrieNode() :pass(0) , end(0) , _next(26) {} int pass; int end; vector<TrieNode*>_next; ~TrieNode() { for (auto it : _next) { delete it; } } }; class Trie { public: Trie() :_root(new TrieNode) {} void Insert(string word) { if (!word.size()) { return; } TrieNode* Node = _root; Node->pass++; int index = 0; for (int i = 0; i < word.size(); i++) { index = word[i] - 'a'; if (!Node->_next[index]) { Node->_next[index] = new TrieNode; } Node = Node->_next[index]; Node->pass++; } Node->end++; } void Delete(string word) { if (!word.size()) { return; } if (Search(word) != 0) { set<TrieNode*>DeleteSet; TrieNode* prev = nullptr; int delteIndex = -1; TrieNode* Node = _root; Node->pass--; int index = 0; for (int i = 0; i < word.size(); i++) { index = word[i] - 'a'; if (--Node->_next[index]->pass == 0) { prev = (prev == nullptr ? Node : prev);//记录第一个pass为1的节点 delteIndex = (delteIndex == -1 ? index : delteIndex); DeleteSet.insert(Node->_next[index]); } Node = Node->_next[index]; } Node->end--; if (prev) prev->_next[delteIndex] = nullptr; for (auto& it : DeleteSet) { delete it; } } } //word这个单词之前加入过几次 int Search(string word) { if (!word.size()) { return 0; } TrieNode* Node = _root; int index = 0; for (int i = 0; i < word.size(); i++) { index = word[i] - 'a'; if (!Node->_next[index]) { return 0; } Node = Node->_next[index]; } return Node->end; } int PrefixNumber(string pre) { if (!pre.size()) { return 0; } int index = 0; TrieNode* Node = _root; for (int i = 0; i < pre.size(); i++) { index = pre[i] - 'a'; if (Node->_next[index] == nullptr) { return 0; } Node = Node->_next[index]; } return Node->pass; } ~Trie() { } private: TrieNode* _root; };
?但是如果字符种类特别多上面这种动态数组的方式实现的就不够用这时我们可以采用hash表来存储节点：其他思路都是一样的在这里就只给出代码：
struct TrieNode { int _pass; int _end; unordered_map<char, TrieNode*>_hash; TrieNode() :_pass(0) ,_end(0) {} ~TrieNode() { for (auto &x : _hash) { delete x.second; } } }; class Trie{ public: Trie() :_root(new TrieNode) {} void Insert(string word) { if (word.size() == 0)return; TrieNode* Node = _root; Node->_pass++; for (int i = 0; i < word.size(); i++) { if (Node->_hash[word[i]]==nullptr) { Node->_hash[word[i]] = new TrieNode; } Node = Node->_hash[word[i]]; Node->_pass++; } Node->_end++; } int Search(string word) { if (word.size() == 0) { return 0; } TrieNode* Node = _root; for (int i = 0; i < word.size(); i++) { if (Node->_hash[word[i]] == nullptr) { return 0; } Node=Node->_hash[word[i]]; } return Node->_end; } int PrefixNumber(string pre) { if (pre.size() == 0)return 0; TrieNode* Node = _root; for (int i = 0; i < pre.size(); i++) { if (Node->_hash[pre[i]] == nullptr) { return 0; } Node = Node->_hash[pre[i]]; } return Node->_pass; } void delte(string word) { if (word.size() == 0)return; if (Search(word) !=0) { TrieNode* Node = _root; set<TrieNode*>DeleteSet; TrieNode* prev = nullptr; int deleteIndex = -1; Node->_pass--; for (int i = 0; i < word.size(); i++) { if (--Node->_hash[word[i]]->_pass == 0) { prev = (prev == nullptr ? Node : prev); deleteIndex = (deleteIndex == -1 ? i : deleteIndex); DeleteSet.insert(Node->_hash[word[i]]); } Node = Node->_hash[word[i]]; } Node->_end--; if(prev) prev->_hash[word[deleteIndex]] = nullptr; for (auto& x : DeleteSet) { delete x; } } } private: TrieNode* _root; };
最后🙌🙌🙌🙌
结语：对于个人来讲，在算法上进行探索是一件有趣的时间，一个程序员，如果不喜欢编程，那么可能就失去了这份职业的乐趣。刷到我的文章的人，我希望你们可以驻足一小会，忙里偷闲的阅读一下我的文章，可能文章的内容对你来说很简单，(^▽^)不过文章中的每一个字都是我认真专注的见证！希望您看完之后，若是能帮到您，劳烦请您简单动动手指鼓励我，我必回报更大的付出~??
?