前缀树（字典树、Trie）

极客资料网推荐前缀树（字典树、Trie）这篇文章给大家，欢迎收藏极客资料网享受知识的乐趣

一、概念

前缀树，英文名为Trie，也常被称作字典树、查找树，是一种专门用于存储、检索字符串集合的多叉树形数据结构。它的核心设计思想为共享公共前缀：将多个拥有相同前缀的字符串，共用树中相同的前缀节点，以此压缩存储空间、降低字符串查询的时间复杂度。最典型的特征是按字符分层存储，区别于普通二叉树，它没有固定的子节点数量，子节点由字符集决定（英文单词通常为26个小写英文字母）。

典例：输入法、搜索框自动补全/联想推荐（输入“我的世界”几乎是立刻显示出来以它为前缀的内容）

---

二、性质

1. 根节点不存储任何字符（一般用空格），仅作为入口
2. 其他节点中，每个只存储一个字符，并且有一个结束标志freqs，以确定一个完整的单词（等于0说明从此开始往上直到根节点不是一个完整的单词，大于0说明是）
3. 有相同前缀的字符串共享前缀节点，比如hello与he，有共同前缀he，那么存储h, e这两个字符的节点被它们共享：root--->h--->e--->l--->l--->o // 为了省空间所以横着了
4. 字符唯一：同一个父节点下，不会出现重复的子字符
5. 查询高效：字符串查询时间复杂度为 O(m)，m为要查询的字符串的长度，和存入的单词总数无关
6. 无回溯冗余：每条从根到结束节点的路径，唯一对应一个字符串

---

三、功能实现

// 节点
struct Node {
    char _c;    // 字符
    int _freqs; // 单词添加次数（_c为单词最后一个字母）
    map<char, Node*> _childNodes; // 存储子节点（map用的是红黑树，可以自动将字母排好序，a~z）
    Node(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. 要删除的单词是某个单词的前缀
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作为单词的最后一个字母，它的结束标志大于0：n->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和3
    if (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);

    queue<Node*> 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;
    }
}
// 情况1
else 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, vector<string>& 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()
{
    vector<string> 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为前缀的单词全部记录下来。

vector<string> 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的最后一个字母所在节点
    // 从该节点开始进行先序遍历
    vector<string> words;
    string start = prefix.substr(0, prefix.size() - 1);
    preOrder(cur, start, words); // 不能用prefix！因为最后一个字母会重复！

    return words;
}

---

四、注意事项

1. 我只写了适用于英文字符的，中文的没有，感兴趣的话可以自己更改代码以实现。
2. 完整的测试代码在最后，可以复制来看
3. 博主是大学生，希望提高自己的水平，内容难免有错误和不合理的地方，如果亲爱的读者看到了，希望能够告知，谢谢❤️❤️
4. 此外如果你觉得我的内容不错的话，能不能给我点个👍，你的支持与鼓励是我一步一步向前的重要动力🫶🫶

五、总结

从前缀树的核心概念、节点结构，到以a、app、apple等单词为例的分步插入演示，我们不难发现，这一专为字符串处理而生的树形结构，其核心魅力在于通过共享公共前缀实现空间压缩，同时让前缀查询、自动补全等操作的时间复杂度稳定在字符串长度级别，成为输入法联想、敏感词过滤、路由匹配等场景的高效解决方案；尽管它的实现逻辑在纯英文场景下直观易懂，但其“共享公共结构、优化重复数据处理”的思想，早已拓展至多字符集乃至更复杂的数据场景，不仅是算法面试中的高频考点，更是理解字符串高效处理的经典范式，为我们解决重复字符串的存储与检索问题提供了兼具空间与时间优势的清晰思路。

六、完整代码示例

#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <queue>
using namespace std;

class TrieTree {
private:
    /* 节点 */
    struct Node {
        char _c;    // 字符
        int _freqs; // 单词添加次数（_c为单词最后一个字母）
        map<char, Node*> _childNodes; // 存储子节点（map用的是红黑树，可以自动将字母排好序，a~z）
        Node(char c, int freqs) : _c(c), _freqs(freqs) {}
    };

    Node *_root; // 根节点，存储的字母为空格

public:
    TrieTree()
    {
        _root = new Node('\0', 0);
    }

    ~TrieTree()
    {
        queue<Node*> 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, vector<string>& 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和3
            if (cur->_freqs > 0 || cur->_childNodes.size() > 1)
            {
                del = cur;
                delCh = word[i];
            }

            cur = it->second;
        }

        // 情况2、3
        if (cur->_childNodes.empty())
        {
            Node *start = del->_childNodes[delCh];
            del->_childNodes.erase(delCh);

            queue<Node*> 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;
            }
        }
        // 情况1
        else 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;
    }

    /* 前缀搜索 */
    vector<string> 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的最后一个字母所在节点
        // 从该节点开始进行先序遍历
        vector<string> words;
        string start = prefix.substr(0, prefix.size()-1);
        preOrder(cur, start, words); // 不能用prefix！因为最后一个字母会重复！

        return words;
    }

    /* 先序遍历 */
    void preOrder()
    {
        vector<string> 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";
    vector<string> 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;
}

文章来源:https://www.cnblogs.com/myInception/p/19989476
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！