前缀树(字典树)

本文主要介绍前缀树的概念以及其引用, 并且提供C++的前缀树实现.

概念介绍

前缀树(Trie)也称为字典树, 其基本结构是N叉树, 常用来存储字符串, 也可存储其他的数据类型. 前缀树中根节点不存储前缀(字符串), 其余每一个节点存储一个前缀, 一个节点对应的字符串是通过该节点的所有前缀组成的字符串.

前缀树名称的由来是树中任意节点的所有后代有共同的前缀.

前缀树有着广泛的应用, 例如自动补全, 拼写检查, 词频统计, IP 路由 (最长前缀匹配),

复杂度分析

再分析一下时间复杂度, n为输入字符串的长度, m为已插入字符串的数量.

插入字符串: O(n)
查询某字符串或某前缀: O(n)

与其他数据结构的对比

也有其他的数据结构可以用来存储字符串, 例如哈希表, 平衡树.

哈希表
- 哈希表可以在O(1)内查询特定字符串, 但在表增大之后会出现大量的冲突，使其时间复杂度增加到O(m), m为已插入字符串的数量
- 前缀树在存储有相同前缀的单词时会节省存储空间
- 哈希表无法高效的找到有相同前缀的所有字符串
- 哈希表无法按字典序枚举所有字符串
平衡树
- 平衡树中查找字符串的时间复杂度为 O(mlogn)

前缀树实现 (C++)

这里实现的前缀树只处理26个小写英文字母组成的串, 可以方便的扩展到更大的范围.

下面代码中实现了三个方法, 分别是:

插入字符串
查询字符串的数量
查询有某前缀的所有字符串的数量

此外, 本文这里使用定长数组来存储子节点的指针, 每个节点只存储1个字符, 其运算效率高, 但在字符集较大时会存在很大的存储开销. 另一种思路是利用哈希表存储前缀和对应子节点的关系, 这样可以节省空间.

此外还可以补充实现其他一些方法:

删除字符串
查询具有某前缀的所有字符串
按照字典序枚举所有字符串

// 前缀树
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class TrieNode{

private:

    int count;
    int prefix;

    TrieNode* nextNode[26];

public:

    TrieNode(){
        this->count=0;  // 以当前节点为结尾的单词数量
        this->prefix=0; // 包含该前缀的单词数量
    }

    // 插入新单词
    void insert(string str){
        TrieNode* root = this;
        // 注意：this指针可能为nullptr
        if(root==nullptr || str.empty()){
            return;
        }
        for(int i=0; i<str.size(); i++){
            if(root->nextNode[str[i]-'a']==nullptr){
                root->nextNode[str[i]-'a'] = new TrieNode();
            }
            root = root->nextNode[str[i]-'a'];
            root->prefix++;
        }
        root->count++;
    }

    // 查询单词的数量
    int search(string str){
        TrieNode* root = this;
        if(root==nullptr || str.empty()){
            return 0;
        }
        for(int i=0; i<str.size(); i++){
            if(root->nextNode[str[i]-'a']==nullptr){
                return 0;
            }
            root = root->nextNode[str[i]-'a'];
        }
        return root->count;
    }

    // 查询以str为前缀的单词的数量
    int searchPrefix(string str){
        TrieNode* root = this;
        if(root==nullptr || str.empty()){
            return 0;
        }
        for(int i=0; i<str.size(); i++){
            if(root->nextNode[str[i]-'a']==nullptr){
                return 0;
            }
            root = root->nextNode[str[i]-'a'];
        }
        return root->prefix;
    }

};


int main(){
    TrieNode* trie = new TrieNode();
    vector<string> test = {
        "hello", "hello", "helloworld", "", "hello",
    };
    for(string t: test){
        trie->insert(t);
    }
    cout<<trie->search("hello")<<" "<<trie->searchPrefix("hello")<<'\n';
    return 0;
}