前缀树（字典树、Trie）

前缀树英文名为Trie也常被称作字典树、查找树是一种专门用于存储、检索字符串集合的多叉树形数据结构。它的核心设计思想为共享公共前缀将多个拥有相同前缀的字符串共用树中相同的前缀节点以此压缩存储空间、降低字符串查询的时间复杂度。最典型的特征是按字符分层存储区别于普通二叉树它没有固定的子节点数量子节点由字符集决定英文单词通常为26个小写英文字母。典例输入法、搜索框自动补全/联想推荐输入“我的世界”几乎是立刻显示出来以它为前缀的内容二、性质根节点不存储任何字符一般用空格仅作为入口其他节点中每个只存储一个字符并且有一个结束标志freqs以确定一个完整的单词等于0说明从此开始往上直到根节点不是一个完整的单词大于0说明是有相同前缀的字符串共享前缀节点比如hello与he有共同前缀he那么存储h, e这两个字符的节点被它们共享root---h---e---l---l---o// 为了省空间所以横着了字符唯一同一个父节点下不会出现重复的子字符查询高效字符串查询时间复杂度为 O(m)m为要查询的字符串的长度和存入的单词总数无关无回溯冗余每条从根到结束节点的路径唯一对应一个字符串三、功能实现// 节点struct Node {char _c; // 字符int _freqs; // 单词添加次数_c为单词最后一个字母mapchar, Node* _childNodes; // 存储子节点map用的是红黑树可以自动将字母排好序a~zNode(char c, int freqs) : _c(c), _freqs(freqs) {}};1)添加要添加word从根节点开始遍历如果word[i]已经在树中了那就继续遍历下一个字符若下一个字符不在树中即it cur-_childNodes.end()则创建含这个字符的节点并加入到前一个字符节点指向的map中示例添加a, app再添加apple, apply, ban, bank, cat, can结果如图所示C实现代码void add(const string word){Node *cur _root;for (int i 0; i (int)word.size(); i){auto it cur-_childNodes.find(word[i]);if (it cur-_childNodes.end()) // 没有该字母创建字母为word[i]的节点{Node *newNode new Node(word[i], 0);cur-_childNodes.emplace(word[i], newNode);cur newNode;} else cur it-second;}cur-_freqs; // 添加次数加1}2)删除这个是最麻烦的步骤只是相对而言其实一点也不复杂✿◕‿◕✿分3种情况讨论我也说不清楚为什么只有这三种感觉越说越模糊所以读者可以自己分析吧要删除的单词是某个单词的前缀删除某个单词但是该单词的前缀是另外一个单词要删除某个单词但是它和另外一个或多个单词有公共前缀对于情况1因为如果直接删掉a那么apple和apply将一起消失并且处理不当没有delete掉p、p、l、e、y还会造成内存泄漏那怎么办呢还记得每个节点都有一个结束标志freqs吗我们在添加a的时候会将a节点的freqs以此表示添加的单词在此结束那么删除的话只要freqs 0就可以了。对于情况2和情况3首先你可能会疑惑为什么2和3在一起讨论呢因为它们的本质是一样的——不能删除公共前缀只不过情况2中的前缀是一个单词其末尾的freqs大于0而情况3中前缀的freqs为0。那么怎么处理这两种情况呢我们可以这么想要删除某一段即要删除的word-prefix部分我们需要知道两个信息1从哪里开始删2删到哪里结束。接下来我们来分析怎么获知这两个信息。看情况2要删除bank但是不能去掉ban直接利用freqs即可因为字母n作为单词的最后一个字母它的结束标志大于0n-freqs 0所以可以利用这个信息定义一个指针指向它Node *del n遍历到一个节点的freqs 0就让del 该节点这样的话我们就知道了开始的节点是n的map中单词bank对应的下一个字母k而结束节点则是在遍历过程中就一直移动使用cur表示for循环遍历结束cur就指向最后一个节点。看情况3要删除can但是ca是公共的并且a-freqs 0所以不能使用freqs了但是想想有分叉那么a-map.size()一定大于1所以遍历到一个节点的map.size() 0让del 该节点而结束节点和情况2一样。最后为了开始删除的时候不要再去遍历map找到从哪个字母开始删除可以定义一个delCh来记录这个字母delCh word[i]Node *cur _root; // 指向要删除单词的最后一个字母所在节点Node *del _root; // 指向要删除单词的首字母所在节点即从del开始删char delCh word[0];// 找出单词word的最后一个字母以及要开始删除的字母所在位置for (int i 0; i (int)word.size(); i){auto it cur-_childNodes.find(word[i]);if (it cur-_childNodes.end()){cout The word word does not exit in the Trie Tree! endl;return;}// 应对情况2和3if (cur-_freqs 0 || cur-_childNodes.size() 1){del cur;delCh word[i];}cur it-second;}然后是删除过程情况1已经说了情况2、3就用层次遍历的方式一个一个删即可if (cur-_childNodes.empty()){Node *start del-_childNodes[delCh];del-_childNodes.erase(delCh);queueNode* q;q.push(start);while (!q.empty()){Node *cur q.front();q.pop();for (const auto p : cur-_childNodes)q.push(p.second);delete cur;}}// 情况1else cur-_freqs 0;要函数整体的话直接加上void remove(const string word)和一对花括号就可以了3)查询个人觉得这个没什么好讲的和删除里的哪个for循环一样只不过不需要del和delCh部分了返回类型设为int返回单词的freqs代码int query(const string word){Node *cur _root;for (int i 0; i (int)word.size(); i){const auto it cur-_childNodes.find(word[i]);if (it cur-_childNodes.end()) return 0; // 单词不存在else cur it-second; // 当前遍历到的字母存在继续查询下一个字母}return cur-_freqs;}4)遍历这里的遍历主要是为了依据前缀查询的时候能够按字典序返回字符串即搜索框中显示的是和你输入的字符串最相似的所以使用先序遍历。得益于使用map来存储子节点每个子节点的字母已经是排好序了所以直接用一个for循环遍历每个节点再递归就OK了和二叉树的的先序遍历差不多。但要注意查看节点的freqs是不是大于0是的话要将这个单词记录还有一个是根节点不能把根节点的字符算进去。/* 先序遍历递归接口 */void preOrder(Node* node, string word, vectorstring words){if (node ! _root){word.push_back(node-_c);if (node-_freqs 0) words.emplace_back(word); // 遍历完一个单词}for (const auto p : node-_childNodes)preOrder(p.second, word, words); // 递归遍历子节点}/* 先序遍历 */void preOrder(){vectorstring words;string word;preOrder(_root, word, words);cout \nPreorder traversal result: endl;cout ----------------------------------- endl;for (const auto w : words)cout w endl;cout -----------------------------------\n\n;}5)依据前缀查询这个功能就是开头看到的输入“我的世界”显示出来以它为前缀的内容。它分为两个部分1查询有没有以prefix为前缀的单词2从prefix的最后一个字符开始进行先序遍历把所有以prefix为前缀的单词全部记录下来。vectorstring findPrefix(const string prefix){Node *cur _root;for (int i 0; i (int)prefix.size(); i){const auto it cur-_childNodes.find(prefix[i]);if (it cur-_childNodes.end()) return {};else cur it-second;}// for循环结束后cur就指向prefix的最后一个字母所在节点// 从该节点开始进行先序遍历vectorstring words;string start prefix.substr(0, prefix.size() - 1);preOrder(cur, start, words); // 不能用prefix因为最后一个字母会重复return words;}四、注意事项我只写了适用于英文字符的中文的没有感兴趣的话可以自己更改代码以实现。完整的测试代码在最后可以复制来看博主是大学生希望提高自己的水平内容难免有错误和不合理的地方如果亲爱的读者看到了希望能够告知谢谢❤️❤️此外如果你觉得我的内容不错的话能不能给我点个你的支持与鼓励是我一步一步向前的重要动力题目推荐实现Trie五、总结从前缀树的核心概念、节点结构到以a、app、apple等单词为例的分步插入演示我们不难发现这一专为字符串处理而生的树形结构其核心魅力在于通过共享公共前缀实现空间压缩同时让前缀查询、自动补全等操作的时间复杂度稳定在字符串长度级别成为输入法联想、敏感词过滤、路由匹配等场景的高效解决方案尽管它的实现逻辑在纯英文场景下直观易懂但其“共享公共结构、优化重复数据处理”的思想早已拓展至多字符集乃至更复杂的数据场景不仅是算法面试中的高频考点更是理解字符串高效处理的经典范式为我们解决重复字符串的存储与检索问题提供了兼具空间与时间优势的清晰思路。六、完整代码示例#include iostream#include map#include string#include vector#include queueusing namespace std;class TrieTree {private:/* 节点 */struct Node {char _c; // 字符int _freqs; // 单词添加次数_c为单词最后一个字母mapchar, Node* _childNodes; // 存储子节点map用的是红黑树可以自动将字母排好序a~zNode(char c, int freqs) : _c(c), _freqs(freqs) {}};Node *_root; // 根节点存储的字母为空格public:TrieTree(){_root new Node(\0, 0);}~TrieTree(){queueNode* q;q.push(_root);while (!q.empty()){Node *cur q.front();q.pop();for (const auto p : cur-_childNodes)q.push(p.second);delete cur;}}private:/* 先序遍历递归接口 */void preOrder(Node* node, string word, vectorstring words){if (node ! _root){word.push_back(node-_c);if (node-_freqs 0) words.emplace_back(word); // 遍历完一个单词}for (const auto p : node-_childNodes)preOrder(p.second, word, words); // 递归遍历子节点}public:/* 添加 */void add(const string word){Node *cur _root;for (int i 0; i (int)word.size(); i){auto it cur-_childNodes.find(word[i]);if (it cur-_childNodes.end()) // 没有该字母创建字母为word[i]的节点{Node *newNode new Node(word[i], 0);cur-_childNodes.emplace(word[i], newNode);cur newNode;} else cur it-second;}cur-_freqs; // 添加次数加1}/* 删除 */void remove(const string word){Node *cur _root; // 指向要删除单词的最后一个字母所在节点Node *del _root; // 指向要删除单词的首字母所在节点即从del开始删char delCh word[0];// 找出单词word的最后一个字母以及开始删除的字母所在位置for (int i 0; i (int)word.size(); i){auto it cur-_childNodes.find(word[i]);if (it cur-_childNodes.end()){cout The word word does not exit in the Trie Tree! endl;return;}// 应对情况2和3if (cur-_freqs 0 || cur-_childNodes.size() 1){del cur;delCh word[i];}cur it-second;}// 情况2、3if (cur-_childNodes.empty()){Node *start del-_childNodes[delCh];del-_childNodes.erase(delCh);queueNode* q;q.push(start);while (!q.empty()){Node *cur q.front();q.pop();for (const auto p : cur-_childNodes)q.push(p.second);delete cur;}}// 情况1else cur-_freqs 0;cout You have removed word . endl;}/* 查询 */int query(const string word){Node *cur _root;for (int i 0; i (int)word.size(); i){const auto it cur-_childNodes.find(word[i]);if (it cur-_childNodes.end()) return 0; // 单词不存在else cur it-second; // 当前遍历到的字母存在继续查询下一个字母}return cur-_freqs;}/* 前缀搜索 */vectorstring findPrefix(const string prefix){Node *cur _root;for (int i 0; i (int)prefix.size(); i){const auto it cur-_childNodes.find(prefix[i]);if (it cur-_childNodes.end()) return {};else cur it-second;}// for循环结束后cur就指向prefix的最后一个字母所在节点// 从该节点开始进行先序遍历vectorstring words;string start prefix.substr(0, prefix.size()-1);preOrder(cur, start, words); // 不能用prefix因为最后一个字母会重复return words;}/* 先序遍历 */void preOrder(){vectorstring words;string word;preOrder(_root, word, words);cout \nPreorder traversal result: endl;cout ----------------------------------- endl;for (const auto w : words)cout w endl;cout -----------------------------------\n\n;}};int main(){TrieTree trie;trie.add(TrieTree);trie.add(TrieTree);trie.add(Trie);trie.add(Hello);trie.add(He);trie.add(Helloo);trie.add(Avril);trie.add(Avril);trie.add(Av);trie.add(Avril);trie.add(Taylor);cout trie.query(TrieTree) ;cout trie.query(Trie) ;cout trie.query(He) ;cout trie.query(Hello) ;cout trie.query(Avril) ;cout trie.query(Taylor) ;cout trie.query(Av) endl;trie.preOrder();string remove Taylor;trie.remove(remove);trie.preOrder();string prefix Trie;vectorstring prefixes trie.findPrefix(prefix);cout These words own the prefix: prefix endl;cout ----------------------------------- endl;for (const auto word : prefixes)cout word endl;cout -----------------------------------\n\n;return 0;}